9/24/2024

Capital University of Science and Technology.

Islamabad

Discrete Structures
CS2053

Dr. Samina Rashid

Department of Mathematics
Capital University of Science and Technology

| DS - Logic and Proofs 1

SE2053 Discrete Structures

Course Instructor
Prof. Dr. Samina Rashid
Department of Mathematics,
2nd Floor E-Block, Phone: 111 87 87 87 ext. 291
E-mail: samina.batul@cust.edu.pk

Class Schedule
Monday : 04:20 – 05:10
Friday: 09:00 – 10:50

| DS - Logic and Proofs 2

1
 9/24/2024

SE2053 Discrete Structures

Textbook
 Discrete Mathematics and Its Applications
Kenneth H. Rosen (McGraw Hill – 7th Edition)
Reference Books
 Discrete Mathematics with Applications
Susanna S. Epp (Thomson Learning Inc 4th Edition)
 Discrete Mathematics for Computer Secience
(G. Haggard, J. Schlipf, S. Whitesides – 2006 Brooks/Cole)

| DS - Logic and Proofs 3

Course Introduction (Course Catalog)

 Discrete mathematics is mathematics that deals with discrete objects.
 Discrete objects are those which are separated from (not connected to/distinct
from) each other. Integers (aka whole numbers), rational numbers (ones that
can be expressed as the quotient of two integers), automobiles, houses, people
etc. are all discrete objects.
 On the other hand, real numbers which include irrational as well as rational
numbers are not discrete and known as continuous.
 In this course we will be concerned with objects such as integers, propositions,
sets, relations, and functions, which are all discrete.
 We are going to learn concepts associated with them, their properties, and
relationships among others.

| DS - Logic and Proofs 4

2
 9/24/2024

Course Objectives

 This course will lay the foundations for theoretical computer science.
 Basic mathematical concepts generally required for most computer
science courses will be covered in the course.
 The course aims at developing precise and formal reasoning skills in
students.
 Different ways of mathematical thinking will be explored i.e., Logical
thinking, Relational thinking, Recursive thinking, Quantitative thinking,
and Analytical thinking.

| DS - Logic and Proofs 5

Course Learning Outcomes

 CLO:1. Describe propositional /predicate logic in terms of predicates,

quantifiers, and logical connective. [C2-Understanding]
 CLO:2. Explain properties of sets, functions, sequences, and
summations. [C2-Understanding]
 CLO:3. Solve counting problems and enumerate objects while
performing combinatorial analysis. [C3-Application]
 CLO:4. Use multiple discrete structures such as graphs, trees to analyze
problems in real life. [C3-Application]

| DS - Logic and Proofs 6

3
 9/24/2024

Evaluation Method

Assignments (Quiz)
1. 20%
2. Quiz 20%
3. Midterm Exam 20%
4. Final Exams 40%
5. There will be NO makeup Quiz or Assignment Quiz

| DS - Logic and Proofs 7

MT5643 – Course Contents

 Logic and Proofs  Counting
 Propositional Logic and its Applications  The Basics of Counting
 Propositional Equivalences  The Pigeonhole Principle
 Quantifiers and Predicates  Permutation and Combination
 Proof Techniques  Algorithms
 Basic Structures  Recursive Algorithms
 Sets and Set Operations  Program Correctness.
 Functions  Complexity of Algorithms
 Sequence and Summations  Graphs
 Induction and Recursion  Introduction and Graph Models
 Mathematical Induction  Terminology and Some Special Graphs
 Connectivity of Graphs

| DS - Logic and Proofs 8

4
 9/24/2024

Why Discrete Structures

 It is the mathematics underlying almost all of computer science:
 Program Correctness and Verification
 Analysing algorithms for correctness and efficiency
 Finding efficient algorithms
 (for sorting, searching, etc.)
 Formalizing security requirements
 Designing cryptographic protocols for enhanced security
 Graph Theory (Computer Networks)

| DS - Logic and Proofs 9

1.1 – Propositional Logic

 The rules of logic specify the meaning of mathematical statements.
 Logic is the basis of all mathematical reasoning, and of all automated
reasoning.
 It has practical applications to the design of computing machines, to the
specification of systems, to artificial intelligence, to computer
programming, to programming languages, to other advanced CS courses
like Data structures, algorithms, automata theory, formal languages,
Database, networks, operating system, security and to many other fields
of study.
 Logic is the study of the principles and methods that distinguishes
between a valid and an invalid argument.
| DS - Logic and Proofs 10

5
 9/24/2024

Propositions (Statements)
 A proposition is a declarative sentence (that is, a sentence that declares a
fact) that is either true or false, but not both.
 Example: All the following declarative sentences are propositions
 Islamabad, is the capital of the United States of America.

 Berlin is the capital of Germany.

 1+1 = 2

 2 + 3 = 15.

 𝑥 + 8 = −3 (Not a statement / proposition; neither true nor false)

 𝑥 = 4; we have 𝑥 + 8 = 12

 What is your name? (Not a statement / proposition; not a declarative)

| DS - Logic and Proofs 11

Propositional Calculus / Logic

 We use letters (𝑝, 𝑞, 𝑟, 𝑠, … ) to denote propositional variables (or statement variables),
that is, variables that represent propositions, just as letters are used to denote
numerical variables.
 If a proposition is a true statement then its truth value of is True, denoted by Tor 1.
 If a proposition is a false statement then its truth value of is False, denoted by F or 0.

Proposition Truth Value

𝑝 = “Islamabad, is the capital of the USA” F
𝑞 = “Dollar is United States of America’s currency” T
𝑟 = “Berlin is the capital of Germany” T
𝑠 = “1+1=11” F
𝑡 = “5 is a factor of 19” F
| DS - Logic and Proofs 12

6
 9/24/2024

Exercises 1.1 (Q2)

 Which of these are propositions? What are the truth values of those that
are propositions?
a) Do not pass go.
b) What time is it?
c) There are no black flies in Maine.
d) 4 + 𝑥 = 5.
e) The moon is made of green cheese.
f) 2𝑛 ≥ 100.

| DS - Logic and Proofs 13

Compound Propositions
 Many mathematical statements are constructed by combining one or
more propositions. New propositions, called compound propositions, are
formed from existing propositions using logical operators.
 Logical operators also known as Logical Connectives.
Connectives Meaning Symbol
Negation Not ¬ or ~
Conjunction AND ∧
Disjunction OR ∨
Conditional if … then … → or ⇒
Biconditional if and only if ↔ or ⇔
| DS - Logic and Proofs 14

7
 9/24/2024

Negation or

 Example (C.W)
 Display the truth table for the negation of a proposition 𝑝.

| DS - Logic and Proofs 15

Conjunction (AND )

 Example: Find the conjunction of the propositions p and q where

p = “Rebecca’s PC has more than 16 GB free hard disk space” and
q = “The processor in Rebecca’s PC runs faster than 1 GHz.”
 Ans. (CW)
 Construct the truth table of 𝑝 ∧ 𝑞. (CW)

| DS - Logic and Proofs 16

8
 9/24/2024

Disjunction (OR )

 Here the connective OR is always in inclusive sense.

 That is, 𝑝 ∨ 𝑞 means either 𝑝 or 𝑞, or both.
 Example: Find the disjunction of the propositions p and q where
p = “Rebecca’s PC has more than 16 GB free hard disk space” and
q = “The processor in Rebecca’s PC runs faster than 1 GHz.”
 Ans. (CW)
 Construct the truth table of 𝑝 ∨ 𝑞. (CW)

| DS - Logic and Proofs 17

Example 1
 (Q10) Let p = “The election is decide” and q = “The votes have been counted”.
Express each of the following compound propositions as an English sentence.
a) ~𝑝 b) 𝑝 ∨ 𝑞 c) 𝑝 ∧ 𝑞 d) ~𝑝 ∧ ~𝑞 e) ~𝑝 ∧ 𝑞.
Ans. (CW)
 (Q11) Let 𝑝 and 𝑞 be the propositions
𝑝 : It is below freezing.
𝑞 : It is snowing.
Write these propositions using 𝑝 and 𝑞 and logical connectives (including negations).
a) It is below freezing and snowing.
𝑝 ∧ 𝑞, 𝑝 ∧ ~𝑞, ~𝑝 ∧ ~𝑞, 𝑝 ∨ 𝑞, ~𝑝 ∨ ~𝑞
b) It is below freezing but not snowing.
c) It is not below freezing and it is not snowing.
d) It is either snowing or below freezing (or both).
e) It is either not below freezing or not snowing.

| DS - Logic and Proofs 18

9
 9/24/2024

Exclusive OR ( xor )
 Sometimes, we use or in an exclusive sense.
 When the exclusive or is used to connect the propositions 𝑝 and 𝑞, the
proposition “𝑝 or 𝑞 (but not both)” is obtained.
 This proposition is true when 𝑝 is true and 𝑞 is false, and when 𝑝 is false and 𝑞
is true. It is false when both 𝑝 and 𝑞 are false and when both are true.

 For example, the coin toss result is either head or tail, the grade is either pass of fail.
 Construct the truth table of 𝑝 ⊕ 𝑞. (CW)

| DS - Logic and Proofs 19

Conditional Statements (Implication)

 Note that the statement 𝑝 → 𝑞 is true when both 𝑝 and 𝑞 are true and when 𝑝 is false
(no matter what truth value 𝑞 has).
 For example, if your cumulative score is at least 86% then you will get an 𝐴 in this
course.
 Here 𝑝 = Cumulative score ≥ 86% and 𝑞 = Grade is 𝐴.
 Construct the truth table of 𝑝 → 𝑞.

| DS - Logic and Proofs 20

10
 9/24/2024

 The conditional statement 𝑝 → 𝑞 is expressed in many ways like:

“if p, then q”
“p implies q”
“if p, q”
“p only if q”
“p is sufficient for q”
“a sufficient condition for q is p”
“q if p”
“q whenever p”
“q when p”
“q is necessary for p”
“a necessary condition for p is q”
“q follows from p”
“q unless ~𝑝”

| DS - Logic and Proofs 21

Example 2
 Let 𝑝 be the statement “Maria learns discrete mathematics” and 𝒒 the
statement “Maria will find a good job.” Express the statement 𝑝 → 𝑞 as
a statement in English.
 Solution:
 “If Maria learns discrete mathematics, then she will find a good job.”
 Some other ways to express this conditional statement in English are:
 “Maria will find a good job when she learns discrete mathematics.”
 “For Maria to get a good job, it is sufficient for her to learn discrete
mathematics.” and
 “Maria will find a good job unless she does not learn discrete
mathematics.”
| DS - Logic and Proofs 22

11
 9/24/2024

Converse, Contrapositive, Inverse (Implication)

 There are three conditional statements related to the implication 𝑝 → 𝑞.
1. Converse: The proposition 𝑞 → 𝑝

2. Contrapositive: The proposition ~𝑞 → ~𝑝

3. Inverses: The proposition ~𝑝 → ~𝑞

Construct the truth tables of these propositions.

Notice that only the contrapositive is equivalent to the statement 𝑝 → 𝑞.
That is, both have the same truth values (truth table).

| DS - Logic and Proofs 23

12