CSC102 - Discrete Structures

(Discrete Mathematics)
Fall 2019

Lecture -1

Introduction
Propositional Logic
 CSC102 Discrete Structures 2

Instructor : Ms. Iqra Obaid

Email : [email protected]
Office: H-18
 CSC102 Discrete Structures 3

Course Objectives

• Deep understanding of discrete structures used in

Computer Science
• Developing problem solving and analytical skills
• Developing algorithmic and computational skills
• Ability to understand mathematical arguments and their design
• Understanding of logic
• Proofing techniques
 CSC102 Discrete Structures 4

Course Outline
• Formal Logic
• Quantifiers and Predicates
• Proof Techniques
• Functions
• Sequence and Summations
• Induction and Recursion
• Basic Set Theory
• Relations
• Number Theory
• Graphs
• Trees
 CSC102 Discrete Structures 5

Text Books

• Discrete Mathematics and its Applications 7th Ed. by

Kenneth H. Rosen, McGraw Hill Publisher.

• DiscreteMathematics with Applications 4th Ed. by

Susanna S., Thomson Learning, Inc.
 CSC102 Discrete Structures 6

Course Website

• Visit the following link:

https://sites.google.com/a/cuilahore.edu.pk/dscourse
• Course Handbook
• Deadlines & Important Information
• Course Material
• Assignments
• Quiz Solutions
 CSC102 Discrete Structures 7

Course Assessment/Grading
Component Weightage
Sessional 1 10%
Sessional 2 15%
Terminal 50%
Quizzes 15%
Assignments 10%

• For all assignments, do follow the formatting guidelines given in

course handbook.
• Submit all assignments in hard copy.
• No credit for copied or late submissions.
• No relaxation for students found cheating in any quiz or exam.
• At least 80% attendance is mandatory.
• To get good grade you must attend all lectures and perform good in
all course assessments.
 CSC102 Discrete Structures 8

Rules

• Mobile phones – Silent or switch off

• Arrive on time in class
• If you do not understand a point, raise your hand and ask me to
explain or contact during office hours
• No disturbance!!!! No Misconduct!!!!
• REMEMBER: Your first priority must be your studies
 CSC102 Discrete Structures 9

Reasons to Study Discrete Structures

• Proof
Ability to understand and create mathematical
argument

• Gateway to more advanced CS courses

Data structures, algorithms, automata theory, formal
languages, Database, networks, operating system,
security etc.
 CSC102 Discrete Structures 10

Reasons to Study Discrete Structures

• It is the mathematics underlying almost all of
computer science:
• Program verification
• Analyzing algorithms for correctness and efficiency
• Finding efficient algorithms
• (for sorting, searching, etc.)
• Formalizing security requirements
• Designing cryptographic protocols for enhanced
security
• Graph Theory (Networks – both physical & social)
 CSC102 Discrete Structures 11

Logic

Logic is the study of the principles and methods that

distinguishes between a valid and an invalid argument.

Logic deals with general reasoning laws, which you can

trust.
 CSC102 Discrete Structures 12

Applications

• Applied in proving program correctness and

verification
• Databases (Relational Algebra and calculus)
• Artificial Intelligence
 CSC102 Discrete Structures 13

Propositional Logic
• Proposition
• A proposition is a declarative statement that is either TRUE or FALSE,
but not both.

• Example 1
• 2 + 5 = 4.
• Lahore is the capital of Pakistan.
• It is Monday today.
• Ali is student of this class.

• Example 2
• What time is it?
• X + 1 = 2.
• Close the door.
• Read this carefully.
 CSC102 Discrete Structures 14

Propositional Logic

• Letter are used to denote propositional variables, to

symbolically represent propositions.
• Letters used for this purpose are p, q, r, s,………
• A propositional can have one of two values: true (T) or false (F).

• Example
• p = “Islamabad is the capital of Pakistan”
• q = “17 is divisible by 3”
 CSC102 Discrete Structures 15

Propositional Logic
• The area of logic that deals with propositions is called the
Propositional Calculus or Propositional Logic.

• Compound Propositions are constructed by combining

one or more propositions using logical operators
(connectives).

• Examples
• “3 + 2 = 5” and “Lahore is a city in Pakistan”
• “The grass is green” or “ It is hot today”
 CSC102 Discrete Structures 16

Symbols for Logical Operators

Symbol Meaning
¬ Negation
∧ And, Conjunction
∨ Or, Disjunction
→ Implication
↔ Bi-Conditional
 CSC102 Discrete Structures 17

Logical Operators (Logical connectives)

• Negation

• This just turns a false proposition to true and the opposite for a true
proposition.
• Symbol: ¬
• Let p is a proposition. The statement
“It is not the case that p.”
is another proposition, called the negation of p.

• The negation of p is written ¬ p and read as “not p”.

 CSC102 Discrete Structures 18

Logical Operator - Negation

• Logical operators are defined by truth tables –tables
which give the output of the operator
 in the right-most
column.
• Here is the truth table for negation:

p ¬p
T F
P ¬P
F T
 CSC102 Discrete Structures 19

Logical Operator - Negation

• Example

Let p = “Today is Friday.”

The negation of p is

¬p = “It is not the case that today is Friday.”

¬p = “Today is not Friday.”
¬p = “It is not Friday today.”

• What is negation of following proposition: “My PC runs Linux”

 CSC102 Discrete Structures 20

Logical Operator - Conjunction

• Conjunction is a binary operator in that it operates on two
propositions when creating compound proposition. On
the other hand, negation is a unary operator.
• Conjunction corresponds to English “and.”
• Symbol: ∧
• Let p and q be propositions. The conjunction of p and q,
denoted by p ∧ q, is the proposition “p and q”. The
conjunction p ∧ q is true when both p and q are true. If
one of these is false, than the compound statement is
false as well.
 CSC102 Discrete Structures 21

Logical Operator - Conjunction

• Truth Table

p q p∧q
T T T
T F F
F T F
F F F
 CSC102 Discrete Structures 22

Logical Operator - Conjunction

• Example

Let p = “Today is Friday.”

and q = “It is raining today.”

p ∧ q = “Today is Friday and it is raining today.”

 CSC102 Discrete Structures 23

Logical Operator - Conjunction

• Hamza’s PC has more than 16 GB free hard disk space,
and the processor in Hamza’s PC runs faster than 1 GHz.

• It is cold but sunny.

 CSC102 Discrete Structures 24

Logical Operator - Disjunction

• Disjunction is also a binary operator.

• Disjunction corresponds to English “or.”
• Symbol: ∨

• Let p and q be propositions. The disjunction of p and q,

denoted by p ∨ q, is the proposition “p or q”. The
conjunction p ∨ q is false when both p and q are false and
is true otherwise.
 CSC102 Discrete Structures 25

Logical Operator - Disjunction

• Truth Table

p q p∨q
T T T
T F T
F T T
F F F
 CSC102 Discrete Structures 26

Logical Operator - Disjunction

• Example

Let p = “Today is Friday.”

and q = “It is raining today.”

p ∨ q = “Today is Friday or it is raining today.”

 CSC102 Discrete Structures 27

Example

Let p = “it is sunny”,

q = “it is raining”

• It is sunny and raining. p∧q

• It is not sunny but raining. ¬p ∧ q

• It is neither sunny nor raining. ¬p ∧ ¬q

 CSC102 Discrete Structures 28

Logical Operator – Exclusive Or

• Symbol: ⊕
• Let p and q be propositions. The exclusive or of p and q,
denoted by p ⊕ q , is the proposition that is true when
exactly one of p and q is true and is false, and false
otherwise.
• Truth Table

p q p⊕q
T T F
T F T
F T T
F F F
 CSC102 Discrete Structures 29

Logical Operator – Exclusive Or

• Example
Let p = “Students who have taken calculus can take
this class.”
and q = “Students who have taken computer science
can take this class.”

p ∨ q = “Students who have taken calculus or

computer science can take this class.”
p ⊕ q = “Students who have taken calculus or
computer science, but not both, can take this
class.”
 CSC102 Discrete Structures 30

Exclusive or Versus Inclusive or (Disjunction)

• Coffee or tea comes with dinner. Exclusive or

• A password must have at least three digits or be at least

five characters long. Inclusive or

• Lunch includes soup or salad. Exclusive or

• Experience with C++ or Java is required. Inclusive or

 CSC102 Discrete Structures 31

Logical Operator – Implication

• p  q corresponds to English “if p then q,” or “p implies
q.”
• Symbol: 
• The implication p  q is the proposition that is false when
p is true and q is false, and true otherwise.
p→q

• Examples
• If it is raining then it is cloudy.
Hypothesis Conclusion
• If you get 100% on the final, then you will get an A.
• If p then 2+2 = 4.
 CSC102 Discrete Structures 32

Logical Operator – Implication

• Truth Table

p q pq
T T T
T F F
F T T
F F T
 CSC102 Discrete Structures 33

Logical Operator – Implication

• Alternate ways of stating an implication

• p implies q
• If p, q
• p only if q
• p is sufficient for q
• q if p
• q whenever p
• q is necessary for p
 CSC102 Discrete Structures 34

Implication - Example
p: you get 100% on the final
q: you will get an A
• p implies q.
you get 100% on the final implies you will get an A.
• If p, then q.
If you get 100% on the final, then you will get an A.
• If p, q.
If you get 100% on the final, you will get an A.
• p is sufficient for q.
Get 100% on the final is sufficient for getting an A.
• q if p.
you will get an A if you get 100% on the final.
• q unless ￢ p.
you will get an A unless you don’t get 100% on final.
 CSC102 Discrete Structures 35

Logical Operator – Implication

• Converse
The proposition q → p is converse of p → q.

• Contrapositive
The contrapositive of p → q is the proposition ￢q →￢p.

• Inverse
The proposition ￢p →￢q is called the inverse of p → q.
 CSC102 Discrete Structures 36

Logical Operator – Implication

• Example

“The home team wins whenever it is raining?”

Because “q whenever p”, so p → q, the original statement
can be rewritten as “If it is raining, then the home team wins.”

• Contrapositive
“If the home team does not win, then it is not raining.”
• Converse
“If the home team wins, then it is raining.”
• Inverse
“If it is not raining, then the home team does not win.”
 CSC102 Discrete Structures 37

Logical Operator – Bi-conditional

• p ↔ q corresponds to English “p if and only if q.”
• Symbol: ↔
• The bi-conditional statement p ↔ q is true when p and q
have the same truth values, and is false otherwise.
• Bi-conditional statements are also called bi-implications.
• Alternatively, it means “(if p then q) and (if q then p)”

• Example
• “You can take the flight if and only if you buy a ticket.”
 CSC102 Discrete Structures 38

Logical Operator – Bi-conditional

• Truth Table

p q p↔q
T T T
T F F
F T F
F F T
 CSC102 Discrete Structures 39

Logical Operator – Bi-conditional

p: You can take flight
q: You buy a ticket
𝑝↔𝑞
You can take flight if and only if you buy a ticket
What is the truth value when:
• you buy a ticket and you can take the flight ??
𝑇↔𝑇≡𝑇
• you don’t buy a ticket and you can’t take the flight ??
𝐹↔𝐹≡𝑇
• you buy a ticket but you can’t take the flight ??
𝑇↔𝐹≡𝐹
• you can’t buy a ticket but can take the flight ??
𝐹↔𝑇≡𝐹
 CSC102 Discrete Structures 40

Logical Operator – Bi-conditional

• Other English equivalents:

• “p if and only if q”
• “p is equivalent to q”
• “p is necessary and sufficient for q”
• “p iff q”
• “If p then q, and conversely”
 CSC102 Discrete Structures 41

Bi-conditional -Example
p: “You can take the flight”
q: “You buy a ticket”
p ↔ q:

You can take the flight if and only if you buy a ticket

You can take the flight iff you buy a ticket

The fact that you can take the flight is necessary and
sufficient for buying a ticket
 CSC102 Discrete Structures 42

Logical Operators Summary

Not Not And Or Xor Implication Bi-conditional

p q p q p∧q pq pq pq p↔q
T T F F T T F T T
T F F T F T T F F
F T T F F T T T F
F F T T F F F T T
 CSC102 Discrete Structures 43

Truth Table of Compound Propositions

• Construction of a truth table:
• Rows
• Need a row for every possible combination of values for the every
propositions.
• Columns
• Need a column for the compound proposition (usually at far right)
• Need a column for the truth value of each expression that occurs in
the compound proposition as it is built up.
• This includes the atomic propositions
 CSC102 Discrete Structures 44

Truth Table of Compound Propositions

• (p ∨￢q) → (p ∧ q)
 CSC102 Discrete Structures 45

Truth Table of Compound Propositions

• (p ∨￢q) → (p ∧ q)

p q ￢q p ∨￢q p∧q (p ∨￢q) → (p ∧ q)

T T F T T T
T F T T F F
F T F F F T
F F T T F F
 CSC102 Discrete Structures 46

Truth Table of Compound Propositions

• p → (￢q ∧ r )
 CSC102 Discrete Structures 47

Truth Table of Compound Propositions

• p → (￢q ∧ r )

p q r ￢q ￢q ∧ r p → (￢q ∧ r )

T T T F F F
T T F F F F
T F T T T T
T F F T F F
F T T F F T
F T F F F T
F F T T T T
F F F T F T
 CSC102 Discrete Structures 48

Precedence of Logical Operators

• Just as in algebra, operators have precedence

4+3*2 = 4+(3*2), not (4+3)*2

Operator Precedence
• Example
¬ 1
This means that
 2
p  q  ¬r → s ↔ t  3
yields: (p  (q  (¬r)) → s) ↔ (t) → 4

↔ 5
 CSC102 Discrete Structures 49

Truth Tables
• Construct the truth table of following compound
propositions
• p →￢p
• p⊕p
• (q →￢p) ↔ (p ↔ q)
 CSC102 Discrete Structures 50

Chapter Reading
• Chapter 1, Topic # 1.1, Kenneth H. Rosen, Discrete
Mathematics and Its Applications
 CSC102 Discrete Structures 51

Chapter Exercise ( For Practice)

• Question # 1, 2, 3, 4, 8, 9, 13, 24, 27, 28, 31, 32