CS2301 - Discrete Structures

Fall 2023

Lecture-6

Introduction
Propositional Logic
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.
Propositional Logic
• Proposition
• A proposition is a declarative statement that is either TRUE or FALSE, but not
both.

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

• Example 2
• What time is it?
• X + 1 = 2.
• Close the door.
• Read this carefully.
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”
Propositional Logic
• The area of logic that deals with propositions is called the
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”
Symbols for Logical Operators

Symbol Meaning
Negation
And, Conjunction
∨ Or, Disjunction
→ Implication
↔ Bi-Conditional
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”.
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
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 the negation of the following proposition: “My PC runs Linux”

Logical Operator - Conjunction
• Conjunction is a binary operator that 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, is
false otherwise.
Logical Operator - Conjunction
• Truth Table

p q p q
T T T
T F F
F T F
F F F
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.”

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.

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.
Logical Operator - Disjunction
• Truth Table

p q p q
T T T
T F T
F T T
F F F
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.”

Example

Let p = “it is hot”,

q = “it is sunny”

• It is hot and sunny p q

• It is not hot but sunny p q

• It is neither hot nor sunny p q

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 otherwise.
• Truth Table

p q p q
T T F
T F T
F T T
F F F
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 enroll in this
class.”
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.

Inclusive or

• Experience with C++ or Java is required.

Inclusive or
• When you buy a car from XYZ company, you get $2500
cashback or accessories worth $2500. Exclusive or
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% in the final, then you will get an A.
• If p then 2+2 = 4.
Logical Operator – Implication
• Truth Table

p q pq
T T T
T F F
F T T
F F T
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
Logical Operator – Implication
• "p is sufficient for q”

• "It is sufficient for you to travel by car in order to reach your

destination on time.“

• Definitely, if you travel by car, you'll reach your destination on time. No

doubt. but if you won't travel by car, does it mean you'll never reach
your destination on time. May be by flight or other means of transport,
you'll reach your destination much earlier.

• Therefore, when we say that when A is sufficient for B then, truth of A

guarantees the truth of B but we cannot guarantee the falsity of B
from the falsity of A.

• Similarly, when we say "p is sufficient for q", then we can only
guarantee that when p is true then, q is definitely (or has to be) true.
Logical Operator – Implication
• "q is necessary for p”

• “Good food is necessary to keep us alive“

• According to the statement, if we won't have good food then, we'll

soon die. But is it the only factor to keep us alive? No.

• Example: My friend died at the age of 16 and he has no shortage of

good food.(Even though he is having good food but still he died.)

• Therefore, when we say A is necessary for B then falsity of A

guarantees the falsity of B but we cannot guarantee the truth of B
from the truth of A.

• Similarly, when we say q is necessary for p, then we can only

guarantee that when q is false then, p is definitely (or has to be) false.
Implication - Example
p: you get 100% in the final
q: you will get an A
• p implies that q.
you get 100% in the final implies that you will get an A.
• If p, then q.
If you get 100% in the final, then that you will get an A.
• If p, q.
If you get 100% in the final, that you will get an A.
• p is sufficient for q.
Get 100% in the final is sufficient for getting an A.
• q if p.
you will get an A if you get 100% in the final.
• q unless ￢ p.
you will get an A unless you don’t get 100% in final.
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.
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.”
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.”
Logical Operator – Bi-conditional
• Truth Table

p q p ↔q
T T T
T F F
F T F
F F T
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 or vice versa”
• “p iff q”
• “If p then q, and conversely”
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.
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
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
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
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
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
Truth Tables
• Construct the truth table of following compound
propositions
• p →￢ p
• p p
• (q →￢p) ↔ (p ↔ q)