Discrete Mathematics

Sumangal Bhattacharya
Department of Mathematics
Shiv Nadar University Chennai
sumangal.82@gmail.com
+91 7384846857

August 26, 2024

Contents

1 Unit-I: Logic and Proofs

2/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Syllabus: Mid Term Exam

1 UNIT-I: LOGIC AND PROOFS

Propositional Logic - Propositional equivalences - Principal
Normal forms - Rules of inference - Proof Techniques - Proof
methods and strategy.

2 UNIT-III: LATTICES AND BOOLEAN ALGEBRA

Partial ordering - Posets - Lattices as Posets - Properties of
lattices - Lattices as algebraic systems - Sub lattices - Some
special lattices - Boolean algebra - Stone’s representation
Theorem.

3/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Syllabus: End Semester Exam

1 UNIT-II: COMBINATORICS
Mathematical induction - The Pigeonhole principle - Principal
of Inclusion and Exclusion - Recurrence relations - Solution of
linear recurrence relations - Generating functions.

2 UNIT-IV: GRAPHS
Graph terminology - special types of graphs - Subgraphs -
Operations on graphs - Connectivity - Cut points - Bridges -
Blocks - Eulerian and Hamilton graphs.

3 UNIT-V: GRAPH ALGORITHMS

Matrix representation of graphs - graph isomorphism - Trees -
Spanning trees - Dijkstra’s algorithm for shortest path -
Kruskal’s and Prims’s algorithm for minimum spanning tree.

4/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Motivation and Application

• Discrete Mathematics forms the backbone of Artificial

Intelligence (AI), empowering machines to process
information, make decisions, and learn from data.
• Discrete Mathematics provides the theoretical
foundation for designing algorithms that power the AI
process.
• Combinatorics, a branch of Mathematics, is crucial for
AI-driven optimization problems.
• Graph theory, a significant component of discrete
Mathematics, enables the AI system to represent and
analyze complex relationships between various data
points.

5/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Unit-I

Logic and Proofs

6/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Propositional Logic

Definition
A number of words making complete grammatical structure
having sense and meaning are called a sentence.

7/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Propositional Logic

Definition
A number of words making complete grammatical structure
having sense and meaning are called a sentence.

Declarative Interrogative
Sentence
Non-Declarative Imperative

Exclamatory

7/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue.

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue. Declarative

2 2+8=10.

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue. Declarative

2 2+8=10. Declarative

3 Close the Door.

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue. Declarative

2 2+8=10. Declarative

3 Close the Door. Imperative

4 Is the sky blue?

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue. Declarative

2 2+8=10. Declarative

3 Close the Door. Imperative

4 Is the sky blue? Interrogative

5 Chennai is in England.

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue. Declarative

2 2+8=10. Declarative

3 Close the Door. Imperative

4 Is the sky blue? Interrogative

5 Chennai is in England. Declarative

6 What a beautiful day!

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

1 The Sky is blue. Declarative

2 2+8=10. Declarative

3 Close the Door. Imperative

4 Is the sky blue? Interrogative

5 Chennai is in England. Declarative

6 What a beautiful day! Exclamatory

8/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Proposition

Definition
A proposition is a declarative sentence that is either True (T)
or False (F), but not both.

Examples:
1 2 is a prime number. (T)
2 8 + 2 = 10. (T)
3 2+2=8. (F)
4 Jersey number 7 belongs to Dhoni. (T)
5 𝑥 + 2 = 2𝑥 when 𝑥 = −2. (F)
6 What time is it?
7 Read Discrete Mathematics regularly.
8 𝑥 + 2 = 8.

9/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Some Useful Terms

Definition
Propositions that can not be expressed in terms of simpler
propositions are called simple/primary statement or atomic
propositions. e.g., p: Venugopal is a Maths teacher.

Definition
A compound statement is a statement that is formed by
combining one or more simple statements using
connectives or logical operators. e.g., p: It is raining, and I
have an umbrella.

Definition
A truth table is a Mathematical table used in logic,
computer science, and related fields to determine the truth
values (T or F) of logical expressions based on their inputs.

10/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Basic Logical Operators

• NOT (¬)

• AND (∧)

• OR (∨)
É
• XOR/Exclusive OR ( )

• IF...THEN (→)

• IF AND ONLY IF (↔)

11/149 Sumangal Bhattacharya Shiv Nadar University Chennai

NOT

• Description: The negation ¬𝑝 is true if

𝑝 is false, and false if 𝑝 is true.
• Notation: ¬𝑝.
• Truth Table:
𝑝 ¬𝑝
𝑇 𝐹
𝐹 𝑇

12/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: NOT

• 𝑝 : 2 + 8 > 0 (T)
¬𝑝 : 2 + 8 ≤ 0 (F)

• 𝑝 : It is raining (F)
¬𝑝 : It is not raining (T)

13/149 Sumangal Bhattacharya Shiv Nadar University Chennai

AND

• Description: The conjunction 𝑝 ∧ 𝑞 is

true if and only if both 𝑝 and 𝑞 are true.
• Notation: 𝑝 ∧ 𝑞
• Truth Table:
𝑝 𝑞 𝑝∧𝑞
𝑇 𝑇 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝐹
𝐹 𝐹 𝐹

14/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: AND

• 𝑝 : 2 < 8. (T)
𝑞 : 2 + 8 = 12. (F)
𝑝 ∧ 𝑞 : 2 < 8 ≤ 0 and 2 + 8 = 12. (F)

• 𝑝 : It is raining. (T)
𝑞 : I am getting cold. (T)
𝑝 ∧ 𝑞 : It is raining and I am getting cold.
(T)

15/149 Sumangal Bhattacharya Shiv Nadar University Chennai

OR

• Description: The disjunction 𝑝 ∨ 𝑞 is

true if at least one of 𝑝 or 𝑞 is true.
• Notation: 𝑝 ∨ 𝑞
• Truth Table:
𝑝 𝑞 𝑝∨𝑞
𝑇 𝑇 𝑇
𝑇 𝐹 𝑇
𝐹 𝑇 𝑇
𝐹 𝐹 𝐹

16/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: OR

• 𝑝 : 3 + 5 = 8. (T)
𝑞 : 8 < 2. (F)
𝑝 ∨ 𝑞 : 3 + 5 = 8 or 8 < 2. (T)

• 𝑝 : 8 is a negative integer. (F)

√
𝑞 : 2 is a rational number. (F)
√
𝑝 ∨ 𝑞 : 8 is a negative integer or 2 is a
rational number. (F)

17/149 Sumangal Bhattacharya Shiv Nadar University Chennai

XOR

• Description: The exclusive OR (XOR)

operator is true if and only if exactly
one of 𝑝 or 𝑞 is true, but not both.
• Notation: 𝑝 ⊕ 𝑞 := ( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ 𝑞)
• Truth Table:
𝑝 𝑞 𝑝⊕𝑞
𝑇 𝑇 𝐹
𝑇 𝐹 𝑇
𝐹 𝑇 𝑇
𝐹 𝐹 𝐹

18/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: XOR

• Fact: I will use all my savings to travel

to Europe or to buy an electric car.
𝑝 : I will use all my savings to travel to
Europe.
𝑞 : I will use all my savings to buy an
electric cart.

𝑝 ⊕ 𝑞 : Either I will use all my savings to

travel to Europe or buy an electric car,
but not both. (T)

19/149 Sumangal Bhattacharya Shiv Nadar University Chennai

IF...THEN

• Description: The implication 𝑝 → 𝑞 is

false only if 𝑝 is true and 𝑞 is false;
otherwise, it is true.
• Notation: 𝑝 → 𝑞
• Truth Table:
𝑝 𝑞 𝑝→𝑞
𝑇 𝑇 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝑇
𝐹 𝐹 𝑇

20/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: IF...THEN

• 𝑝 : I study hard.
𝑞 : I will pass the exam.

𝑝 → 𝑞 : If I study hard, then I will pass

the exam.

• Note: 𝑝 → 𝑞 : 𝑞 is necessary for 𝑝 and 𝑝

is sufficient for 𝑞.

21/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Equivalent Statements

𝑝 → 𝑞 can be expressed as:

if 𝑝, then 𝑞 𝑝 implies 𝑞
if 𝑝, 𝑞 𝑝 only if 𝑞
a sufficient conditions
𝑝 is sufficient for 𝑞 for 𝑞 is 𝑝
𝑞 if 𝑝 𝑞 whenever 𝑝
𝑞 when 𝑝 𝑞 necessary for 𝑝
a necessary condition 𝑞 follows from 𝑝
for 𝑝 is 𝑞
𝑞, unless ¬𝑝 𝑞 provided that 𝑞

22/149 Sumangal Bhattacharya Shiv Nadar University Chennai

IF AND ONLY IF

• Description: The biconditional 𝑝 ↔ 𝑞 is

true if and only if 𝑝 and 𝑞 have the
same truth value.
• Notation: 𝑝 ↔ 𝑞
• Truth Table:
𝑝 𝑞 𝑝↔𝑞
𝑇 𝑇 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝐹
𝐹 𝐹 𝑇

23/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: IF AND ONLY IF

• 𝑝 : You can enter the club. (T)

𝑞 : You have a membership card. (T)

𝑝 ↔ 𝑞 : You can enter the club if and

only if you have a membership card. (T)

• Note: 𝑝 → 𝑞 : 𝑞 is necessary for 𝑝 and 𝑝

is sufficient for 𝑞.
𝑝 ← 𝑞 : 𝑝 is necessary for 𝑞 and 𝑞 is
sufficient for 𝑝.

24/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 1 (connectives)

• Number of rows needed in a truth table with 𝑛 propositions

= 2𝑛 .

𝑝 𝑞 ¬𝑝 𝑝 ∧ 𝑞 𝑝 ∨ 𝑞 𝑝 ⊕ 𝑞 𝑝 → 𝑞 𝑝 ↔ 𝑞
𝑇 𝑇
𝑇 𝐹
𝐹 𝑇
𝐹 𝐹

25/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 1 (Solution)

𝑝 𝑞 ¬𝑝 𝑝 ∧ 𝑞 𝑝 ∨ 𝑞 𝑝 ⊕ 𝑞 𝑝 → 𝑞 𝑝 ↔ 𝑞
𝑇 𝑇 𝐹 𝑇 𝑇 𝐹 𝑇 𝑇
𝑇 𝐹 𝐹 𝐹 𝑇 𝑇 𝐹 𝐹
𝐹 𝑇 𝑇 𝐹 𝑇 𝑇 𝑇 𝐹
𝐹 𝐹 𝑇 𝐹 𝐹 𝐹 𝑇 𝑇

26/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 2

Construct the truth table for ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ 𝑟).

𝑝 𝑞 𝑟 𝑝 ∧ 𝑞 𝑝 ∧ 𝑟 ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ 𝑟)
𝑇 𝑇 𝑇
𝑇 𝑇 𝐹
𝑇 𝐹 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝑇
𝐹 𝑇 𝐹
𝐹 𝐹 𝑇
𝐹 𝐹 𝐹

27/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 2 (Solution)

𝑝 𝑞 𝑟 𝑝 ∧ 𝑞 𝑝 ∧ 𝑟 ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ 𝑟)
𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
𝑇 𝑇 𝐹 𝑇 𝐹 𝑇
𝑇 𝐹 𝑇 𝐹 𝑇 𝑇
𝑇 𝐹 𝐹 𝐹 𝐹 𝐹
𝐹 𝑇 𝑇 𝐹 𝐹 𝐹
𝐹 𝑇 𝐹 𝐹 𝐹 𝐹
𝐹 𝐹 𝑇 𝐹 𝐹 𝐹
𝐹 𝐹 𝐹 𝐹 𝐹 𝐹

28/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 3

Construct the truth table for ¬( 𝑝 ∨ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞).

𝑝 𝑞 ¬𝑝 ¬𝑞 𝑝∨𝑞 ¬( 𝑝 ∨ 𝑞) ¬𝑝 ∧ ¬𝑞 ¬( 𝑝 ∨ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)

𝑇 𝑇
𝑇 𝐹
𝐹 𝑇
𝐹 𝐹

29/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 3 (Solution)

𝑝 𝑞 ¬𝑝 ¬𝑞 𝑝∨𝑞 ¬( 𝑝 ∨ 𝑞) ¬𝑝 ∧ ¬𝑞 ¬( 𝑝 ∨ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)

𝑇 𝑇 𝐹 𝐹 𝑇 𝐹 𝐹 𝐹
𝑇 𝐹 𝐹 𝑇 𝑇 𝐹 𝐹 𝐹
𝐹 𝑇 𝑇 𝐹 𝑇 𝐹 𝐹 𝐹
𝐹 𝐹 𝑇 𝑇 𝐹 𝑇 𝑇 𝑇

30/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 4

Construct the truth table for ( 𝑝 ∨ 𝑞) ↔ 𝑟.

𝑝 𝑞 𝑟 𝑝∧𝑞 𝑝∨𝑞 𝑝⊕𝑞 𝑝↔𝑞 ( 𝑝 ∧ 𝑞) → 𝑟 ( 𝑝 ∨ 𝑞) ↔ 𝑟

𝑇 𝑇 𝑇
𝑇 𝑇 𝐹
𝑇 𝐹 𝑇
𝑇 𝐹 𝐹
𝐹 𝑇 𝑇
𝐹 𝑇 𝐹
𝐹 𝐹 𝑇
𝐹 𝐹 𝐹

31/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Truth Table: Example 4 (Solution)

𝑝 𝑞 𝑟 𝑝∧𝑞 𝑝∨𝑞 𝑝⊕𝑞 𝑝↔𝑞 ( 𝑝 ∧ 𝑞) → 𝑟 ( 𝑝 ∨ 𝑞) ↔ 𝑟

𝑇 𝑇 𝑇 𝑇 𝑇 𝐹 𝑇 𝑇 𝑇
𝑇 𝑇 𝐹 𝑇 𝑇 𝐹 𝑇 𝐹 𝐹
𝑇 𝐹 𝑇 𝐹 𝑇 𝑇 𝐹 𝑇 𝑇
𝑇 𝐹 𝐹 𝐹 𝑇 𝑇 𝐹 𝑇 𝐹
𝐹 𝑇 𝑇 𝐹 𝑇 𝑇 𝐹 𝑇 𝑇
𝐹 𝑇 𝐹 𝐹 𝑇 𝑇 𝐹 𝑇 𝐹
𝐹 𝐹 𝑇 𝐹 𝐹 𝐹 𝑇 𝑇 𝐹
𝐹 𝐹 𝐹 𝐹 𝐹 𝐹 𝑇 𝑇 𝑇

32/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Home Work

Construct the truth table for the following

compound propositions:
1 ( 𝑝 ∨ 𝑞) → ( 𝑝 ∧ 𝑞).
2 ( 𝑝 → 𝑞) → (𝑞 → 𝑝).
3 (¬𝑝 ↔ ¬𝑞) ↔ (𝑞 ↔ 𝑟).
4 ¬( 𝑝 ∨ (𝑞 ∧ 𝑟)) ↔ (( 𝑝 ∨ 𝑞) ∧ ( 𝑝 → 𝑟)).
5 ( 𝑝 → (𝑞 → 𝑟)) ∧ (¬𝑟 ∨ 𝑝) ∧ 𝑞.
6 [ 𝑝 → (𝑞 → 𝑟)] → [( 𝑝 → 𝑞) → ( 𝑝 → 𝑟)]

33/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Converse, Contrapositive and Inverse

• Let us consider the implication, 𝑝 → 𝑞.

• Converse: 𝑞 → 𝑝.
Note: The converse is not necessarily always
true.
• Contrapositive: ¬𝑞 → ¬𝑝.
Note: The contrapositive is always true if the
original implication is true.
• Inverse: ¬𝑝 → ¬𝑞.
Note: The inverse is not necessarily always true.

34/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Example

• Question: Write the converse, contrapositive and inverse

of the statement "The home team wins whenever it is
raining".

35/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Example

• Question: Write the converse, contrapositive and inverse

of the statement "The home team wins whenever it is
raining".
• Solution: Let us consider the following propositions;
𝑝 : it is raining.
𝑞 : the home team wins.

35/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Example

• Question: Write the converse, contrapositive and inverse

of the statement "The home team wins whenever it is
raining".
• Solution: Let us consider the following propositions;
𝑝 : it is raining.
𝑞 : the home team wins.
• Converse: 𝑞 → 𝑝,, i.e., if the home team wins, then it is
raining.

35/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Example

• Question: Write the converse, contrapositive and inverse

of the statement "The home team wins whenever it is
raining".
• Solution: Let us consider the following propositions;
𝑝 : it is raining.
𝑞 : the home team wins.
• Converse: 𝑞 → 𝑝,, i.e., if the home team wins, then it is
raining.
• Contrapositive: ¬𝑞 → ¬𝑝,, i.e., if the home team does not
win, then it is not raining.

35/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Example

• Question: Write the converse, contrapositive and inverse

of the statement "The home team wins whenever it is
raining".
• Solution: Let us consider the following propositions;
𝑝 : it is raining.
𝑞 : the home team wins.
• Converse: 𝑞 → 𝑝,, i.e., if the home team wins, then it is
raining.
• Contrapositive: ¬𝑞 → ¬𝑝,, i.e., if the home team does not
win, then it is not raining.
• Inverse: ¬𝑝 → ¬𝑞,, i.e., if it is not raining, then the home
team does not win.

35/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 1
Question 1: Symbolize the sentences using logical
connectives
1 If the moon is out and it is not snowing, then Ram goes
out for a walk.
2 If the moon is out, then if it is not snowing, Ram goes
out for a walk.
3 It is not the case that Ram goes out for a walk if and only
if it is not snowing or the moon is out.

36/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 1
Question 1: Symbolize the sentences using logical
connectives
1 If the moon is out and it is not snowing, then Ram goes
out for a walk.
2 If the moon is out, then if it is not snowing, Ram goes
out for a walk.
3 It is not the case that Ram goes out for a walk if and only
if it is not snowing or the moon is out.

Solution: Consider the propositions;

p: the moon is out; q: It is snowing; r: Ram goes out for a
walk.

36/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 1
Question 1: Symbolize the sentences using logical
connectives
1 If the moon is out and it is not snowing, then Ram goes
out for a walk.
2 If the moon is out, then if it is not snowing, Ram goes
out for a walk.
3 It is not the case that Ram goes out for a walk if and only
if it is not snowing or the moon is out.

Solution: Consider the propositions;

p: the moon is out; q: It is snowing; r: Ram goes out for a
walk.
1 ( 𝑝 ∧ ¬𝑞) → 𝑟.
2 𝑝 → (¬𝑞 → 𝑟)
3 ¬(𝑟 ↔ (¬𝑞 ∨ 𝑝)).

36/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy.

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy. Ans: ¬𝑝 ∧ 𝑞.

2 Kutti is rich or unhappy.

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy. Ans: ¬𝑝 ∧ 𝑞.

2 Kutti is rich or unhappy. Ans: 𝑝 ∨ ¬𝑞.

3 Kutti is neither rich nor happy.

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy. Ans: ¬𝑝 ∧ 𝑞.

2 Kutti is rich or unhappy. Ans: 𝑝 ∨ ¬𝑞.

3 Kutti is neither rich nor happy. Ans: ¬𝑝 ∧ ¬𝑞.

4 It is necessary for kutti to be poor in order to be happy.

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy. Ans: ¬𝑝 ∧ 𝑞.

2 Kutti is rich or unhappy. Ans: 𝑝 ∨ ¬𝑞.

3 Kutti is neither rich nor happy. Ans: ¬𝑝 ∧ ¬𝑞.

4 It is necessary for kutti to be poor in order to be happy.

Ans: 𝑞 → ¬𝑝.

5 It is necessary and sufficient for kutti to be poor is to be

unhappy.

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy. Ans: ¬𝑝 ∧ 𝑞.

2 Kutti is rich or unhappy. Ans: 𝑝 ∨ ¬𝑞.

3 Kutti is neither rich nor happy. Ans: ¬𝑝 ∧ ¬𝑞.

4 It is necessary for kutti to be poor in order to be happy.

Ans: 𝑞 → ¬𝑝.

5 It is necessary and sufficient for kutti to be poor is to be

unhappy. Ans: ¬𝑞 ↔ ¬𝑝.

6 Kutti is rich, or he is poor and unhappy.

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Question 2: Symbolize the sentences using logical

connectives.
Let, p: Kutti is rich; q: Kutti is happy;
1 Kutti is poor but happy. Ans: ¬𝑝 ∧ 𝑞.

2 Kutti is rich or unhappy. Ans: 𝑝 ∨ ¬𝑞.

3 Kutti is neither rich nor happy. Ans: ¬𝑝 ∧ ¬𝑞.

4 It is necessary for kutti to be poor in order to be happy.

Ans: 𝑞 → ¬𝑝.

5 It is necessary and sufficient for kutti to be poor is to be

unhappy. Ans: ¬𝑞 ↔ ¬𝑝.

6 Kutti is rich, or he is poor and unhappy. Ans: 𝑝 ∨ (¬𝑝 ∧ ¬𝑞).

37/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.
Ans: p: Passing the exam; s: Studying

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.
Ans: p: Passing the exam; s: Studying
Symbolic: 𝑝 → 𝑠.

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.
Ans: p: Passing the exam; s: Studying
Symbolic: 𝑝 → 𝑠.
Explanation: " If you pass the exam, then you must have
studied."
2 Statement: It is necessary to have a password to access
the system.

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.
Ans: p: Passing the exam; s: Studying
Symbolic: 𝑝 → 𝑠.
Explanation: " If you pass the exam, then you must have
studied."
2 Statement: It is necessary to have a password to access
the system.
Ans: a: accessing the system; p: having a password;

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.
Ans: p: Passing the exam; s: Studying
Symbolic: 𝑝 → 𝑠.
Explanation: " If you pass the exam, then you must have
studied."
2 Statement: It is necessary to have a password to access
the system.
Ans: a: accessing the system; p: having a password;
Symbolic: 𝑎 → 𝑝.

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Question 3: Symbolize the sentences using logical
connectives.
1 Statement: It is necessary to study in order to pass the
exam.
Ans: p: Passing the exam; s: Studying
Symbolic: 𝑝 → 𝑠.
Explanation: " If you pass the exam, then you must have
studied."
2 Statement: It is necessary to have a password to access
the system.
Ans: a: accessing the system; p: having a password;
Symbolic: 𝑎 → 𝑝.
Explanation: "If you can access the system, then you
must have a password."

38/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

Ans: r: the car runs; f: having fuel

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

Ans: r: the car runs; f: having fuel
Symbolic: 𝑟 → 𝑓 .

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

Ans: r: the car runs; f: having fuel
Symbolic: 𝑟 → 𝑓 .
Explanation: "If the car runs, then it must have fuel."

2 Statement: It is necessary for a number to be even to be

divisible by 4.

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

Ans: r: the car runs; f: having fuel
Symbolic: 𝑟 → 𝑓 .
Explanation: "If the car runs, then it must have fuel."

2 Statement: It is necessary for a number to be even to be

divisible by 4.
Ans: d: number is divisible by 4; e: number is even

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

Ans: r: the car runs; f: having fuel
Symbolic: 𝑟 → 𝑓 .
Explanation: "If the car runs, then it must have fuel."

2 Statement: It is necessary for a number to be even to be

divisible by 4.
Ans: d: number is divisible by 4; e: number is even
Symbolic: 𝑑 → 𝑒.

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 4

Question 4: Symbolize the sentences using logical

connectives.

1 Statement: It is necessary to have fuel for the car to run.

Ans: r: the car runs; f: having fuel
Symbolic: 𝑟 → 𝑓 .
Explanation: "If the car runs, then it must have fuel."

2 Statement: It is necessary for a number to be even to be

divisible by 4.
Ans: d: number is divisible by 4; e: number is even
Symbolic: 𝑑 → 𝑒.
Explanation: "If a number is divisible by 4 then it must
be even."

39/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 5

Question 5: Symbolize the sentences using logical

connectives.
1 Statement: If either Tom takes 𝐶 + + or Jerry takes Pascal,
then Mr. Bean will take Lotus.

40/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 5

Question 5: Symbolize the sentences using logical

connectives.
1 Statement: If either Tom takes 𝐶 + + or Jerry takes Pascal,
then Mr. Bean will take Lotus.
Ans: t: Tom takes 𝐶 + +; j: Jerry takes Pascal;
b: Mr. Bean will take Lotus

40/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 5

Question 5: Symbolize the sentences using logical

connectives.
1 Statement: If either Tom takes 𝐶 + + or Jerry takes Pascal,
then Mr. Bean will take Lotus.
Ans: t: Tom takes 𝐶 + +; j: Jerry takes Pascal;
b: Mr. Bean will take Lotus
Symbolic: (𝑡 ∨ 𝑗) → 𝑏 or (𝑡 ⊕ 𝑗) → 𝑏.
2 Statement: Annu can access the internet from campus
only if she is a Computer Science (CS) major or she
completed 1st year.

40/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 5

Question 5: Symbolize the sentences using logical

connectives.
1 Statement: If either Tom takes 𝐶 + + or Jerry takes Pascal,
then Mr. Bean will take Lotus.
Ans: t: Tom takes 𝐶 + +; j: Jerry takes Pascal;
b: Mr. Bean will take Lotus
Symbolic: (𝑡 ∨ 𝑗) → 𝑏 or (𝑡 ⊕ 𝑗) → 𝑏.
2 Statement: Annu can access the internet from campus
only if she is a Computer Science (CS) major or she
completed 1st year.
Ans: p: annu can access the internet from campus; q:
She is a CS major; r: She is a 1st year student

40/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 5

Question 5: Symbolize the sentences using logical

connectives.
1 Statement: If either Tom takes 𝐶 + + or Jerry takes Pascal,
then Mr. Bean will take Lotus.
Ans: t: Tom takes 𝐶 + +; j: Jerry takes Pascal;
b: Mr. Bean will take Lotus
Symbolic: (𝑡 ∨ 𝑗) → 𝑏 or (𝑡 ⊕ 𝑗) → 𝑏.
2 Statement: Annu can access the internet from campus
only if she is a Computer Science (CS) major or she
completed 1st year.
Ans: p: annu can access the internet from campus; q:
She is a CS major; r: She is a 1st year student
Symbolic: 𝑝 → (𝑞 ∨ ¬𝑟).

40/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6

Question 6: Express logical connectives as an English

sentences.
p: swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: ¬𝑞

41/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6

Question 6: Express logical connectives as an English

sentences.
p: swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: ¬𝑞
Statement: Sharks have not been spotted near the
Marina Beach.
2 Symbolic: 𝑝 ∧ 𝑞

41/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6

Question 6: Express logical connectives as an English

sentences.
p: swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: ¬𝑞
Statement: Sharks have not been spotted near the
Marina Beach.
2 Symbolic: 𝑝 ∧ 𝑞
Statement: Swimming at the Marina Beach is allowed
and sharks have been spotted near the beach.
3 Symbolic: ¬𝑝 ∨ 𝑞

41/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6

Question 6: Express logical connectives as an English

sentences.
p: swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: ¬𝑞
Statement: Sharks have not been spotted near the
Marina Beach.
2 Symbolic: 𝑝 ∧ 𝑞
Statement: Swimming at the Marina Beach is allowed
and sharks have been spotted near the beach.
3 Symbolic: ¬𝑝 ∨ 𝑞
Statement: Swimming at the Marina Beach is not
allowed or sharks have been spotted near the beach.

41/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6 (cont...)
p: Swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: 𝑝 → ¬𝑞

42/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6 (cont...)
p: Swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: 𝑝 → ¬𝑞
Statement: If swimming at the Marina Beach is allowed,
then sharks have not been spotted near the beach.
2 Symbolic: ¬𝑞 → 𝑝

42/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6 (cont...)
p: Swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: 𝑝 → ¬𝑞
Statement: If swimming at the Marina Beach is allowed,
then sharks have not been spotted near the beach.
2 Symbolic: ¬𝑞 → 𝑝
Statement: If sharks have not been spotted near the
beach, then swimming at the Marina beach is allowed.
3 Symbolic: 𝑝 ↔ ¬𝑞

42/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6 (cont...)
p: Swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: 𝑝 → ¬𝑞
Statement: If swimming at the Marina Beach is allowed,
then sharks have not been spotted near the beach.
2 Symbolic: ¬𝑞 → 𝑝
Statement: If sharks have not been spotted near the
beach, then swimming at the Marina beach is allowed.
3 Symbolic: 𝑝 ↔ ¬𝑞
Statement: Swimming at the Marina Beach is allowed iff
sharks have not been spotted near the beach.
4 Symbolic: ¬𝑝 ∧ ( 𝑝 ∨ ¬𝑞)

42/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 6 (cont...)
p: Swimming at the Marina beach is allowed;
q: Sharks have been spotted near the Marina beach.
1 Symbolic: 𝑝 → ¬𝑞
Statement: If swimming at the Marina Beach is allowed,
then sharks have not been spotted near the beach.
2 Symbolic: ¬𝑞 → 𝑝
Statement: If sharks have not been spotted near the
beach, then swimming at the Marina beach is allowed.
3 Symbolic: 𝑝 ↔ ¬𝑞
Statement: Swimming at the Marina Beach is allowed iff
sharks have not been spotted near the beach.
4 Symbolic: ¬𝑝 ∧ ( 𝑝 ∨ ¬𝑞)
Statement: Swimming at the Marina Beach is not
allowed, and either Swimming at the Marina Beach is
allowed, or sharks have not been spotted near the beach.

42/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Propositional Equivalence

Definition
• A compound proposition that is always true, no matter
what the truth values of the propositional variables that
occur in it, is called a Tautology.
Note: If 𝑝 → 𝑞 is tautology, this is denoted by 𝑝 =⇒ 𝑞.
• A compund proposition that is always false is called a
contradiction.
• A compound proposition that is neither a tautology nor a
contradiction is called contingency.

p ¬𝑝 𝑝 ∨ ¬𝑝 𝑝 ∧ ¬𝑝
Example: T F T F
F T T F

43/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Logically Equivalence

Definition
The compound propositions 𝑝 and 𝑞 are called
logically equivalent if 𝑝 ↔ 𝑞 is a tautology.
Notation: 𝑝 ≡ 𝑞.
Note: ’≡’ is not a logical connection nor a
compound proposition.

Example:
1 𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝.

2 ¬( 𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞.

44/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Duality Law

Definition
The dual of a compound proposition that contains
only the logical operators ∨, ∧, and ¬ is the
proposition obtained by replacing each ∨ by ∧,
each ∧ by ∨, each 𝑇 by 𝐹 and each 𝐹 by 𝑇 .

Notation: Dual of a proposition 𝑝 is 𝑝 ∗ .

Theorem
If 𝑝 ≡ 𝑞, where 𝑝 and 𝑞 are compound propositions,
then 𝑝 ∗ ≡ 𝑞 ∗ .
Note: useful for simplification and verification.

45/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Logical Equivalences

Laws Logical Equivalences

Identity Laws 𝑝∧T≡ 𝑝
𝑝 ∨ F ≡ 𝑝 (Dual)
Domination Laws 𝑝∨T≡T
𝑝∧F≡F
Idempotent Laws 𝑝∨𝑝≡ 𝑝
𝑝∧𝑝≡ 𝑝
Double Negation Law ¬(¬𝑝) ≡ 𝑝
Commutative Laws 𝑝∨𝑞 ≡𝑞∨𝑝
𝑝∧𝑞 ≡𝑞∧𝑝
Associative Laws ( 𝑝 ∨ 𝑞) ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟)
( 𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)
Distributive Laws 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ 𝑟)
𝑝 ∨ (𝑞 ∧ 𝑟) ≡ ( 𝑝 ∨ 𝑞) ∧ ( 𝑝 ∨ 𝑟)

46/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Logical Equivalences (Cont...)

Laws Logical Equivalences

Contrapositive Law 𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝
De Morgan’s Laws ¬( 𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞
¬( 𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
Absorption Laws 𝑝 ∨ ( 𝑝 ∧ 𝑞) ≡ 𝑝
𝑝 ∧ ( 𝑝 ∨ 𝑞) ≡ 𝑝
Negation Laws 𝑝 ∨ ¬𝑝 ≡ T
𝑝 ∧ ¬𝑝 ≡ F
Conditional and Bicondi-
𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞
tional Equivalences
𝑝 ↔ 𝑞 ≡ ( 𝑝 → 𝑞) ∧ (𝑞 → 𝑝) ≡
( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)
Implication Laws 𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞
𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝
Exportation Laws ( 𝑝 → (𝑞 → 𝑟)) ≡ (( 𝑝 ∧ 𝑞) → 𝑟)

47/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Methods to Verify Tautology,...

Methods to verify tautology, contradiction

and contingency:

1 Method-1: Using Truth Tables.

2 Method-2: Using Equivalence Rules.

48/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1: Tautology
Problem 1: Prove that ( 𝑝 ∧ ( 𝑝 → 𝑞)) → 𝑞 is a
Tautology.

49/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1: Tautology
Problem 1: Prove that ( 𝑝 ∧ ( 𝑝 → 𝑞)) → 𝑞 is a
Tautology.
Solution:
𝑝 𝑞 𝑝 → 𝑞 𝑝 ∧ ( 𝑝 → 𝑞) ( 𝑝 ∧ ( 𝑝 → 𝑞)) → 𝑞
𝑇 𝑇 𝑇 𝑇 𝑇
𝑇 𝐹 𝐹 𝐹 𝑇
𝐹 𝑇 𝑇 𝐹 𝑇
𝐹 𝐹 𝑇 𝐹 𝑇
Conclusion: The resultant column entries are all
TRUE (T), the given statement formula is a
Tautology.

49/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1: Contradiction

Problem 2: Prove that (¬𝑝 ∧ 𝑝) ∧ 𝑞 is a contradiction.

50/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1: Contradiction

Problem 2: Prove that (¬𝑝 ∧ 𝑝) ∧ 𝑞 is a contradiction.

Solution:

𝑝 𝑞 ¬𝑝 ¬𝑝 ∧ 𝑝 (¬𝑝 ∧ 𝑝) ∧ 𝑞
𝑇 𝑇 𝐹 𝐹 𝐹
𝑇 𝐹 𝐹 𝐹 𝐹
𝐹 𝑇 𝑇 𝐹 𝐹
𝐹 𝐹 𝑇 𝐹 𝐹
Conclusion: The resultant column entries are all
FALSE (F). Therefore, the given statement formula
is a Contradiction.

50/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1: Contingency
Problem 3: Prove that ( 𝑝 ∨ 𝑞) → ( 𝑝 → 𝑞) is a
contingency.

51/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1: Contingency
Problem 3: Prove that ( 𝑝 ∨ 𝑞) → ( 𝑝 → 𝑞) is a
contingency.
Solution:
𝑝 𝑞 𝑝 ∨ 𝑝 𝑝 → 𝑞 ( 𝑝 ∨ 𝑞) → ( 𝑝 → 𝑞)
𝑇 𝑇 𝑇 𝑇 𝑇
𝑇 𝐹 𝑇 𝐹 𝐹
𝐹 𝑇 𝑇 𝑇 𝑇
𝐹 𝐹 𝐹 𝑇 𝑇
Conclusion: The resultant column entries have
both 𝑇 and 𝐹, the given statement formula is a
Contingency.

51/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1

Problem 4: Prove the following

implications by using truth tables:

a ( 𝑝 → (𝑞 → 𝑟)) =⇒ (( 𝑝 → 𝑞) → ( 𝑝 → 𝑟)).

b (( 𝑝 → (𝑞 → 𝑠)) ∧ (¬𝑟 ∨ 𝑝) ∧ 𝑞) =⇒ (𝑟 → 𝑠).

Note: 𝑝 =⇒ 𝑞 means 𝑝 → 𝑞 is a tautology.

52/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(a)

Solution:

𝑝 𝑞 𝑟 𝑝→𝑞 𝑞→𝑟 𝑝→𝑟 𝑝↔𝑏 𝑎→𝑐 𝑑→𝑒

(𝑎) (𝑏) (𝑐) (𝑑) (𝑒)
𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
𝑇 𝑇 𝐹 𝑇 𝐹 𝐹 𝐹 𝐹 𝑇
𝑇 𝐹 𝑇 𝐹 𝑇 𝑇 𝑇 𝑇 𝑇
𝑇 𝐹 𝐹 𝐹 𝑇 𝐹 𝑇 𝑇 𝑇
𝐹 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
𝐹 𝑇 𝐹 𝑇 𝐹 𝑇 𝑇 𝑇 𝑇
𝐹 𝐹 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
𝐹 𝐹 𝐹 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇

53/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-2

Problem 5: Prove the following

implications are tautology without using
truth tables:

a [( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ 𝑟)] → (𝑞 ∨ 𝑟).

b [( 𝑝 ∨ 𝑞) ∧ ¬(¬𝑝 ∧ (¬𝑞 ∨ ¬𝑟))] ∨ [(¬𝑝 ∧ ¬𝑞) ∨

(¬𝑝 ∧ ¬𝑟)].

c [( 𝑝 ∨ 𝑞) ∧ ( 𝑝 → 𝑟) ∧ (𝑞 → 𝑟)] → 𝑟.

54/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 5(a)
Solution:
[( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ 𝑟)] → (𝑞 ∨ 𝑟)
≡ ¬[( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ 𝑟)] ∨ (𝑞 ∨ 𝑟) [𝐶𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝐸𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑐𝑒𝑠]
≡ [[¬( 𝑝 ∨ 𝑞)] ∨ [¬(¬𝑝 ∨ 𝑟)]] ∨ (𝑞 ∨ 𝑟) [𝐷𝑒 − 𝑀𝑜𝑟𝑔𝑎𝑛′ 𝑠 𝐿𝑎𝑤]
≡ [(¬𝑝 ∧ ¬𝑞) ∨ ( 𝑝 ∧ ¬𝑟)] ∨ (𝑞 ∨ 𝑟) [𝐷𝑒 − 𝑀𝑜𝑟𝑔𝑎𝑛′ 𝑠 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [( 𝑝 ∧ ¬𝑟) ∨ (𝑞 ∨ 𝑟)] [ 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑒 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [(𝑞 ∨ 𝑟) ∨ ( 𝑝 ∧ ¬𝑟)] [𝐶𝑜𝑚𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑒 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [[(𝑞 ∨ 𝑟) ∨ 𝑝] ∧ [(𝑞 ∨ 𝑟) ∨ ¬𝑟]] [𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [[𝑞 ∨ (𝑟 ∨ 𝑝)] ∧ [𝑞 ∨ (𝑟 ∨ ¬𝑟)]] [ 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑒 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [[𝑞 ∨ ( 𝑝 ∨ 𝑟)] ∧ [𝑞 ∨ T]] [𝐶𝑜𝑚𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑒, 𝑁𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [[(𝑞 ∨ 𝑝) ∨ 𝑟] ∧ T] [ 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑒 𝐿𝑎𝑤, 𝐷𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 𝐿𝑎𝑤]
≡ (¬𝑝 ∧ ¬𝑞) ∨ [( 𝑝 ∨ 𝑞) ∨ 𝑟] [𝐶𝑜𝑚𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑒 𝐿𝑎𝑤, 𝐼𝑑𝑒𝑛𝑡𝑖𝑡𝑦 𝐿𝑎𝑤]
≡ [¬( 𝑝 ∨ 𝑞) ∨ ( 𝑝 ∨ 𝑞)] ∨ 𝑟 [ 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑒 𝐿𝑎𝑤, 𝐷𝑒 − 𝑀𝑜𝑟𝑔𝑎𝑛′ 𝑠 𝐿𝑎𝑤]
≡ T ∨ 𝑟 [𝑁𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝐿𝑎𝑤]
≡ T [𝐷𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 𝐿𝑎𝑤]

55/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 5(b)

Solution:
[( 𝑝 ∨ 𝑞) ∧ ¬(¬𝑝 ∧ (¬𝑞 ∨ ¬𝑟))] ∨ [(¬𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ ¬𝑟)].
≡ [( 𝑝 ∨ 𝑞) ∧ ( 𝑝 ∨ ¬(¬𝑞 ∨ ¬𝑟))] ∨ [¬𝑝 ∧ (¬𝑞 ∨ ¬𝑟)]. [D-M’s, Dist. Law]
≡ [( 𝑝 ∨ 𝑞) ∧ ( 𝑝 ∨ (𝑞 ∧ 𝑟))] ∨ [¬𝑝 ∧ (¬𝑞 ∨ ¬𝑟)]. [De-Morgan’s]
≡ [ 𝑝 ∨ (𝑞 ∧ (𝑞 ∧ 𝑟))] ∨ [¬𝑝 ∧ ¬(𝑞 ∧ 𝑟)]. [D-Morgan’s, Dist. Laws]
≡ [ 𝑝 ∨ ((𝑞 ∧ 𝑞) ∧ 𝑟))] ∨ ¬[ 𝑝 ∨ (𝑞 ∧ 𝑟)]. [D-Morgan’s, Associative Laws
≡ [ 𝑝 ∨ (𝑞 ∧ 𝑟)] ∨ ¬[ 𝑝 ∨ (𝑞 ∧ 𝑟)]. [Idempotent Laws]
≡ T. [Negation Laws]

56/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 5(c)
Solution:
[( 𝑝 ∨ 𝑞) ∧ (( 𝑝 → 𝑟) ∧ (𝑞 → 𝑟))] → 𝑟.
≡ [( 𝑝 ∨ 𝑞) ∧ ((¬𝑝 ∨ 𝑟) ∧ (¬𝑞 ∨ 𝑟)] → 𝑟. [Conditional Equivalence]
≡ [( 𝑝 ∨ 𝑞) ∧ ((¬𝑝 ∧ ¬𝑞) ∨ 𝑟)] → 𝑟. [Distributive Law]
≡ [( 𝑝 ∨ 𝑞) ∧ (¬( 𝑝 ∨ 𝑞) ∨ 𝑟)] → 𝑟. [De-Morgan’s Law]
≡ [(( 𝑝 ∨ 𝑞) ∧ ¬( 𝑝 ∨ 𝑞)) ∨ (( 𝑝 ∨ 𝑞) ∧ 𝑟)] → 𝑟. [Distributive Law]
≡ [F ∨ (( 𝑝 ∨ 𝑞) ∧ 𝑟)] → 𝑟. [Negation Law]
≡ [( 𝑝 ∨ 𝑞) ∧ 𝑟] → 𝑟. [Identity Law]
≡ ¬[( 𝑝 ∨ 𝑞) ∧ 𝑟] ∨ 𝑟. [Implication Law]
≡ [¬( 𝑝 ∨ 𝑞) ∨ ¬𝑟] ∨ 𝑟. [De-Morgan’s Law]
≡ ¬( 𝑝 ∨ 𝑞) ∨ [¬𝑟 ∨ 𝑟]. [Associative Law]
≡ ¬( 𝑝 ∨ 𝑞) ∨ T. [Negation Law]
≡ T. [Domination Laws]

57/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Home Work

Problem: Prove/Disprove the following

implications with and without using truth
tables:

a [(( 𝑝 ∨ ¬𝑞) → 𝑞) → (( 𝑝 ∨ ¬𝑝) → 𝑟)] =⇒

(𝑞 → 𝑟).

b [( 𝑝 ∨ 𝑞) ∧ ¬𝑝] =⇒ 𝑞.

c [¬𝑝 ∧ ( 𝑝 → 𝑞)] =⇒ ¬𝑞.

58/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Methods to Prove Equivalence

Methods to prove logical equivalence:

1 Method-1: Using Truth Tables.

2 Method-2: Using Tautology Definition.

3 Method-3: Using LHS=RHS.

4 Method-4: Using Duality Law.

59/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-1

Problem 1: Using truth table, prove the

following equivalences:

a ( 𝑝 → 𝑞) ≡ (¬𝑝 ∨ 𝑞)

b 𝑝 ↔ 𝑞 ≡ ( 𝑝 → 𝑞) ∧ (𝑞 → 𝑝) ≡
( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)

c ( 𝑝 → 𝑞) ∧ ( 𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∧ 𝑟)

60/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1(a)

Problem: Prove: ( 𝑝 → 𝑞) ≡ (¬𝑝 ∨ 𝑞).

61/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1(a)

Problem: Prove: ( 𝑝 → 𝑞) ≡ (¬𝑝 ∨ 𝑞).

Solution:

𝑝 𝑞 ¬𝑝 𝑝 → 𝑞 (¬𝑝 ∨ 𝑞)
𝑇 𝑇 𝐹 𝑇 𝑇
𝑇 𝐹 𝐹 𝐹 𝐹
𝐹 𝑇 𝑇 𝑇 𝑇
𝐹 𝐹 𝑇 𝑇 𝑇
Conclusion: Here, truth values of 𝑝 → 𝑞 and ¬𝑝 ∨ 𝑞
are same.
Hence, 𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞.

61/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1(b)

Problem: Prove:
𝑝 ↔ 𝑞 ≡ ( 𝑝 → 𝑞) ∧ (𝑞 → 𝑝) ≡ ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞).

62/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1(b)

Problem: Prove:
𝑝 ↔ 𝑞 ≡ ( 𝑝 → 𝑞) ∧ (𝑞 → 𝑝) ≡ ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞).

Solution:
𝑝 𝑞 𝑝↔𝑞 𝑝→𝑞 𝑞→𝑝 𝑎∧𝑏 ¬𝑝 ¬𝑞 𝑝∧𝑞 ¬ 𝑝 ∧ ¬𝑞 𝑐∨𝑑
(𝑎) (𝑏) (𝑐) (𝑑)
𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝐹 𝐹 𝑇 𝐹 𝑇
𝑇 𝐹 𝐹 𝐹 𝑇 𝐹 𝐹 𝑇 𝐹 𝐹 𝐹
𝐹 𝑇 𝐹 𝑇 𝐹 𝐹 𝑇 𝐹 𝐹 𝐹 𝐹
𝐹 𝐹 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝐹 𝑇 𝑇

Conclusion: Here, truth values of 𝑝 ↔ 𝑞,

( 𝑝 → 𝑞) ∧ (𝑞 → 𝑝), and ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞) are same.
Hence, 𝑝 ↔ 𝑞 ≡ ( 𝑝 → 𝑞) ∧ (𝑞 → 𝑝) ≡ ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞).

62/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1(c)

Problem: Prove: ( 𝑝 → 𝑞) ∧ ( 𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∧ 𝑟).

63/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1(c)

Problem: Prove: ( 𝑝 → 𝑞) ∧ ( 𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∧ 𝑟).

Solution:
𝑝 𝑞 𝑟 𝑝→𝑞 𝑝→𝑟 𝑎∧𝑏 𝑞∧𝑟 𝑝→𝑐
(𝑎) (𝑏) (𝑐)
𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
𝑇 𝑇 𝐹 𝑇 𝐹 𝐹 𝐹 𝐹
𝑇 𝐹 𝑇 𝐹 𝑇 𝐹 𝐹 𝐹
𝑇 𝐹 𝐹 𝐹 𝐹 𝐹 𝐹 𝐹
𝐹 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
𝐹 𝑇 𝐹 𝑇 𝑇 𝑇 𝐹 𝑇
𝐹 𝐹 𝑇 𝑇 𝑇 𝑇 𝐹 𝑇
𝐹 𝐹 𝐹 𝑇 𝑇 𝑇 𝐹 𝑇

Conclusion: Here, truth values of ( 𝑝 → 𝑞) ∧ ( 𝑝 → 𝑟)

and 𝑝 → (𝑞 ∧ 𝑟) are same.
Hence, ( 𝑝 → 𝑞) ∧ ( 𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∧ 𝑟).

63/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-2

Problem 2: Prove the following

equivalences using the definition:

a ( 𝑝 → 𝑞) ≡ (¬𝑞 → ¬𝑝).

b ( 𝑝 → (𝑞 → 𝑝)) ≡ (¬𝑝 → ( 𝑝 → ¬𝑞)).

64/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 2(a)
Problem: Prove: ( 𝑝 → 𝑞) ≡ (¬𝑞 → ¬𝑝).

65/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 2(a)
Problem: Prove: ( 𝑝 → 𝑞) ≡ (¬𝑞 → ¬𝑝).
Solution: To prove ( 𝑝 → 𝑞) ≡ (¬𝑞 → ¬𝑝), it is enough to
show that ( 𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝) is a tautology.
( 𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝).
≡ [( 𝑝 → 𝑞) → (¬𝑞 → ¬𝑝)] ∧ [(¬𝑞 → ¬𝑝) → ( 𝑝 → 𝑞)]. [Bi-condi. Law]
≡ [(¬𝑝 ∨ 𝑞) → (¬(¬𝑞) ∨ ¬𝑝)] ∧ [(¬(¬𝑞) ∨ ¬𝑝) → (¬𝑝 ∨ 𝑞)]. [Impli. Law
≡ [¬(¬𝑝 ∨ 𝑞) ∨ (𝑞 ∨ ¬𝑝)] ∧ [¬(𝑞 ∨ ¬𝑝) ∨ (¬𝑝 ∨ 𝑞)]. [Implication Law]
≡ [( 𝑝 ∧ ¬𝑞) ∨ (𝑞 ∨ ¬𝑝)] ∧ [(¬𝑞 ∧ 𝑝) ∨ (¬𝑝 ∨ 𝑞)]. [De-Morgan’s Law]
≡ [( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∨ 𝑞)] ∧ [( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∨ 𝑞)]. [Commutative Law]
≡ ( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∨ 𝑞). [Idempotent Law]
≡ ( 𝑝 ∧ ¬𝑞) ∨ ¬( 𝑝 ∧ ¬𝑞). [De-Morgan’s Law]
≡ T. [Negation Law]

Hence, ( 𝑝 → 𝑞) ≡ (¬𝑞 → ¬𝑝).

65/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-3

Problem 3: Prove the following

equivalences by demonstrating LHS =
RHS :

a [ 𝑝 → (𝑞 ∨ 𝑟)] ≡ [¬𝑟 ↔ ( 𝑝 → 𝑞)] ≡

[( 𝑝 ∧ ¬𝑞) → 𝑟].

b [(¬𝑝 ∧ (¬𝑞 ∧ 𝑟)) ∨ ((𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑟))] ≡ 𝑟.

c [ 𝑝 → (𝑞 → 𝑝)] ≡ [¬𝑝 → ( 𝑝 → 𝑞)].

66/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3(a)
Problem: Prove:
[ 𝑝 → (𝑞 ∨ 𝑟)] ≡ [¬𝑟 ↔ ( 𝑝 → 𝑞)] ≡ [( 𝑝 ∧ ¬𝑞) → 𝑟].

67/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3(a)
Problem: Prove:
[ 𝑝 → (𝑞 ∨ 𝑟)] ≡ [¬𝑟 ↔ ( 𝑝 → 𝑞)] ≡ [( 𝑝 ∧ ¬𝑞) → 𝑟].
Solution:
LHS = 𝑝 → (𝑞 ∨ 𝑟).
≡ ¬𝑝 ∨ (𝑞 ∨ 𝑟). [Implication Law]
≡ (¬𝑝 ∨ 𝑞) ∨ 𝑟. [Associative Law]
≡ ¬( 𝑝 ∧ ¬𝑞) ∨ 𝑟. [De-Morgan’s Law]
≡ ( 𝑝 ∧ ¬𝑞) → 𝑟 = RHS. [Implication Law]
LHS = 𝑝 → (𝑞 ∨ 𝑟).
≡ ¬𝑝 ∨ (𝑞 ∨ 𝑟). [Implication Law]
≡ (𝑟 ∨ 𝑞) ∨ ¬𝑝. [Commutative Law]
≡ 𝑟 ∨ (𝑞 ∨ ¬𝑝). [Associative Law]
≡ ¬(¬𝑟) ∨ (¬𝑝 ∨ 𝑞). [Double Negation and Commutative Law
≡ ¬𝑟 → ( 𝑝 → 𝑞) = Middle part. [Implication Law]

67/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3(b)

Problem: Prove:
[(¬𝑝 ∧ (¬𝑞 ∨ 𝑟)) ∨ ((𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑟))] ≡ 𝑟.

68/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3(b)

Problem: Prove:
[(¬𝑝 ∧ (¬𝑞 ∨ 𝑟)) ∨ ((𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑟))] ≡ 𝑟.
Solution:
LHS = [¬𝑝 ∧ (¬𝑞 ∧ 𝑟)] ∨ [(𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑟)].
≡ [(¬𝑝 ∧ ¬𝑞) ∧ 𝑟)] ∨ [(𝑟 ∧ 𝑞) ∨ (𝑟 ∧ 𝑝)]. [Asso. and Commu. Law
≡ [¬( 𝑝 ∨ 𝑞) ∧ 𝑟] ∨ [𝑟 ∧ (𝑞 ∨ 𝑝)]. [Neg. and Dist. Law]
≡ [𝑟 ∧ ¬( 𝑝 ∨ 𝑞)] ∨ [𝑟 ∧ (𝑞 ∨ 𝑝)]. [Commutative Law]
≡ 𝑟 ∧ [¬( 𝑝 ∨ 𝑞) ∨ (𝑞 ∨ 𝑝)]. [Distributive Law]
≡ 𝑟 ∧ T. [Negation Law]
≡ 𝑟. [Identity Law]
= RHS (𝑃𝑟𝑜𝑣𝑒𝑑)

68/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3(c)
Problem: Prove: [ 𝑝 → (𝑞 → 𝑝)] ≡ [¬𝑝 → ( 𝑝 → 𝑞)].

69/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3(c)
Problem: Prove: [ 𝑝 → (𝑞 → 𝑝)] ≡ [¬𝑝 → ( 𝑝 → 𝑞)].
Solution:
LHS = 𝑝 → (𝑞 → 𝑝).
≡ ¬𝑝 ∨ (¬𝑞 ∨ 𝑝). [Implication Law]
≡ ¬𝑝 ∨ ( 𝑝 ∨ ¬𝑞). [commutative Law]
≡ (¬𝑝 ∨ 𝑝) ∨ ¬𝑞. [Associative Law]
≡ T ∨ ¬𝑞. [Negation Law]
≡ T. [Domination Law]
RHS = ¬𝑝 → ( 𝑝 → 𝑞).
≡ ¬(¬𝑝) ∨ (¬𝑝 ∨ 𝑞). [Implication Law]
≡ ( 𝑝 ∨ ¬𝑝) ∨ 𝑞. [Double Negation and Associative Law]
≡ T ∨ 𝑞. [Negation Law]
≡ T. [Domination Law]
Hence, LHS=RHS, i.e. [ 𝑝 → (𝑞 → 𝑝)] ≡ [¬𝑝 → ( 𝑝 → 𝑞)].

69/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method-4

Problem 4: Prove the following

equivalences by proving the equivalences
of the duals:

a [¬((¬𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)) ∨ ( 𝑝 ∧ 𝑞)] ≡ 𝑝.

b [( 𝑝 ∨ 𝑞) → 𝑟] ≡ [( 𝑝 → 𝑟) ∧ (𝑞 → 𝑟)].

c [( 𝑝 ∧ ( 𝑝 ↔ 𝑞)) → 𝑞] ≡ T.

70/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(a)
Problem: Prove: [¬((¬𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)) ∨ ( 𝑝 ∧ 𝑞)] ≡ 𝑝.

71/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(a)
Problem: Prove: [¬((¬𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)) ∨ ( 𝑝 ∧ 𝑞)] ≡ 𝑝.
Solution: The dual of the given equivalence is
[¬((¬𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞)) ∧ ( 𝑝 ∨ 𝑞)] ≡ 𝑝.

Now, we proceed to prove the dual equivalence.

LHS = ¬((¬𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞)) ∧ ( 𝑝 ∨ 𝑞).

≡ ¬(¬𝑝 ∨ (𝑞 ∧ ¬𝑞)) ∧ ( 𝑝 ∨ 𝑞). [Distributive Law]
≡ ¬(¬𝑝 ∨ F) ∧ ( 𝑝 ∨ 𝑞). [Negation Law]
≡ ¬(¬𝑝) ∧ ( 𝑝 ∨ 𝑞). [Identity Law]
≡ 𝑝 ∧ ( 𝑝 ∨ 𝑞). [Double Negation Law]
≡ 𝑝 = RHS. [Absorption Law]

Hence, the principle of duality establishes the truth of the

given equivalence relation.

71/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(b)
Problem: Prove: [( 𝑝 ∨ 𝑞) → 𝑟] ≡ [( 𝑝 → 𝑟) ∧ (𝑞 → 𝑟)].

72/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(b)
Problem: Prove: [( 𝑝 ∨ 𝑞) → 𝑟] ≡ [( 𝑝 → 𝑟) ∧ (𝑞 → 𝑟)].
Solution: The given equivalence can be written as
[¬( 𝑝 ∨ 𝑞) ∨ 𝑟] ≡ [(¬𝑝 ∨ 𝑟) ∧ (¬𝑞 ∨ 𝑟)].

The dual of the that equivalence is

[¬( 𝑝 ∧ 𝑞) ∧ 𝑟] ≡ [(¬𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟)].

Now, we proceed to prove the dual equivalence.

LHS = ¬( 𝑝 ∧ 𝑞) ∧ 𝑟.
≡ (¬𝑝 ∨ ¬𝑞) ∧ 𝑟. [De-Morgan’s Law]
≡ (¬𝑝 ∧ 𝑟) ∨ (¬𝑞 ∧ 𝑟) = RHS. [Distributive Law]

Hence, the principle of duality establishes the truth of the

given equivalence relation.

72/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(c)
Problem: Prove: [ ( 𝑝 ∧ ( 𝑝 ↔ 𝑞) ) → 𝑞] ≡ T.

73/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4(c)
Problem: Prove: [ ( 𝑝 ∧ ( 𝑝 ↔ 𝑞) ) → 𝑞] ≡ T.
Solution: The given equivalence can be written as
[¬( 𝑝 ∧ ( (¬ 𝑝 ∨ 𝑞) ∧ (¬𝑞 ∨ 𝑝) ) ) ∨ 𝑞 ] ≡ T.
The dual of the that equivalence is
[¬( 𝑝 ∨ ( (¬ 𝑝 ∧ 𝑞) ∨ (¬𝑞 ∧ 𝑝) ) ) ∧ 𝑞 ] ≡ F.
Now, LHS = ¬( 𝑝 ∨ ( (¬ 𝑝 ∧ 𝑞) ∨ (¬𝑞 ∧ 𝑝) ) ) ∧ 𝑞.
≡ ¬[ ( 𝑝 ∨ (¬ 𝑝 ∧ 𝑞) ) ∨ (¬𝑞 ∧ 𝑝) ] ∧ 𝑞. [Associative Law]
≡ ¬[ ( ( 𝑝 ∨ ¬ 𝑝) ∧ ( 𝑝 ∨ 𝑞) ) ∨ (¬𝑞 ∧ 𝑝) ] ∧ 𝑞. [Distributive Law]
≡ ¬[ (T ∧ ( 𝑝 ∨ 𝑞) ) ∨ (¬𝑞 ∧ 𝑝) ] ∧ 𝑞. [Negation Law]
≡ ¬[ ( 𝑝 ∨ 𝑞) ∨ (¬𝑞 ∧ 𝑝) ] ∧ 𝑞. [Identity Law]
≡ ¬[ ( ( 𝑝 ∨ 𝑞) ∨ ¬𝑞) ∧ ( ( 𝑝 ∨ 𝑞) ∨ 𝑝) ] ∧ 𝑞. [Distributive Law]
≡ ¬[ ( 𝑝 ∨ T) ∧ ( 𝑝 ∨ 𝑞) ] ∧ 𝑞. [Asso., Negation, Absor. Laws]
≡ ¬[T ∧ ( 𝑝 ∨ 𝑞) ] ∧ 𝑞. [Domination Law]
≡ ¬( 𝑝 ∨ 𝑞) ∧ 𝑞. [Identity Law]
≡ (¬ 𝑝 ∧ ¬𝑞) ∧ 𝑞. [De-Morgan’s Law]
≡ ¬ 𝑝 ∧ (¬𝑞 ∧ 𝑞). [Associative Law]
≡ ¬ 𝑝 ∧ F. [Negation Law]
≡ F. [Dominant Law]
Hence, the principle of duality establishes the truth of the given
equivalence relation.

73/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Normal Forms

Definition
A given logical statement or formula written in terms of
conjunctions (∧), disjunctions (∨), and negations (¬) is called
a normal form or canonical form.

CNF: Conjunctive Normal Form.

Normal Form
DNF: Disjunctive Normal Form

74/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Elementary Definition

Definition
A disjunction (sum) of primary statements and their
negation is called an elementary sum.
e.g., 𝑝, ¬𝑝, 𝑝 ∨ 𝑞, ¬𝑝 ∨ 𝑞, 𝑝 ∨ ¬𝑞, ¬𝑝 ∨ ¬𝑞.

Definition
A conjunction (product) of primary statements and their
negation is called an elementary product.
e.g., 𝑝, ¬𝑝, 𝑝 ∧ 𝑞, ¬𝑝 ∧ 𝑞, 𝑝 ∧ ¬𝑞, ¬𝑝 ∧ ¬𝑞.

75/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Disjunctive Normal Forms (DNF)

Definition
A compound proposition that consists of a sum (∨) of
elementary products and which is equivalent to a given
proposition is called a disjunctive normal form (DNF) of the
given proposition.

DNF = (𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑎𝑟 𝑦 𝑃𝑟𝑜𝑑𝑢𝑐𝑡)∨ · · · ∨(𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑎𝑟 𝑦 𝑃𝑟𝑜𝑑𝑢𝑐𝑡)

Definition
A compound proposition that consists of a product (∧) of
elementary sums and which is equivalent to a given
proposition is called a conjunctive normal form (CNF) of the
given proposition.

CNF = (𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑎𝑟 𝑦 𝑆𝑢𝑚)∧ · · · ∧(𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑎𝑟 𝑦 𝑆𝑢𝑚)

76/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Procedure to Obtain the DNF and CNF

1 Step-1: Replace the logical operators → and ↔ with their

equivalent expressions using ∨, ∧, and ¬.

77/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Procedure to Obtain the DNF and CNF

1 Step-1: Replace the logical operators → and ↔ with their

equivalent expressions using ∨, ∧, and ¬.

2 Step-2: If a negation is present before a given

proposition, apply De Morgan’s laws to place the
negation directly before the individual variables.

77/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Procedure to Obtain the DNF and CNF

1 Step-1: Replace the logical operators → and ↔ with their

equivalent expressions using ∨, ∧, and ¬.

2 Step-2: If a negation is present before a given

proposition, apply De Morgan’s laws to place the
negation directly before the individual variables.

3 Step-3: If necessary, apply the distributive law and the

idempotent law.

77/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Procedure to Obtain the DNF and CNF

1 Step-1: Replace the logical operators → and ↔ with their

equivalent expressions using ∨, ∧, and ¬.

2 Step-2: If a negation is present before a given

proposition, apply De Morgan’s laws to place the
negation directly before the individual variables.

3 Step-3: If necessary, apply the distributive law and the

idempotent law.

4 Step-4: For Disjunctive Normal Form (DNF), omit any

elementary product that is equivalent to the truth value
F.
Similarly, for Conjunctive Normal Form (CNF), omit any
elementary sum that is equivalent to the truth value T.

77/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: DNF

Problem: Find the DNF of 𝑞 → (𝑞 → 𝑝).

78/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: DNF

Problem: Find the DNF of 𝑞 → (𝑞 → 𝑝).

Solution: The given proposition can be written as,

𝑞 → (𝑞 → 𝑝) ≡ ¬𝑞 ∨ (𝑞 → 𝑝) [Implication Law]
≡ ¬𝑞 ∨ (¬𝑞 ∨ 𝑝). [Implication Law]
≡ (¬𝑞 ∨ ¬𝑞) ∨ 𝑝. [Associative Law]
≡ ¬𝑞 ∨ 𝑝. [Idempotent Law]

Hence, the DNF form is ¬𝑞 ∨ 𝑝.

78/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: CNF

Problem: Find the CNF of ¬( 𝑝 ∨ 𝑞) ↔ ( 𝑝 ∧ 𝑞).

79/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples: CNF

Problem: Find the CNF of ¬( 𝑝 ∨ 𝑞) ↔ ( 𝑝 ∧ 𝑞).

Solution: The given proposition can be written as,

¬( 𝑝 ∨ 𝑞) ↔ ( 𝑝 ∧ 𝑞) ≡ [¬( 𝑝 ∨ 𝑞) ∧ ( 𝑝 ∧ 𝑞)] ∨ [¬(¬( 𝑝 ∨ 𝑞)) ∧ ¬( 𝑝 ∧ 𝑞)]

≡ [(¬𝑝 ∧ ¬𝑞) ∧ ( 𝑝 ∧ 𝑞)] ∨ [( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞)].
≡ [(¬𝑝 ∧ 𝑝) ∧ (𝑞 ∧ ¬𝑞)] ∨ [( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞)].
≡ [F ∧ F] ∨ [( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞)].
≡ [F] ∨ [( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞)].
≡ ( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞).

Hence, the CNF form is ( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ ¬𝑞).

79/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems

• Find the DNF of the following statements:

1 ( 𝑝 ∧ ¬(𝑞 ∧ 𝑟)) ∨ ( 𝑝 → 𝑞).

2 ¬(¬( 𝑝 ↔ 𝑞) ∧ 𝑟).

3 𝑝 ∨ (¬𝑝 → (𝑞 ∨ (𝑞 → ¬𝑟))).

• Find the CNF of the following statements:

1 ( 𝑝 ∧ ¬(𝑞 ∧ 𝑟)) ∨ ( 𝑝 → 𝑞).

2 (𝑞 ∨ ( 𝑝 ∧ 𝑞)) ∧ ¬(( 𝑝 ∨ 𝑟) ∧ 𝑞).

3 ( 𝑝 ∧ ¬(𝑞 ∨ 𝑟)) ∨ ((( 𝑝 ∧ 𝑞) ∨ ¬𝑟) ∨ 𝑝).

80/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Minterms and Maxterms

Definition
A minterm is a product (or conjunction) of all the variables in
the function, where each variable appears in either its true
form or its negated form.

• For 𝑛 variables, there are 2𝑛 minterms.

• For 𝑝 and 𝑞, minterms are; 𝑝 ∧ 𝑞, 𝑝 ∧ ¬𝑞, ¬𝑝 ∧ 𝑞, ¬𝑝 ∧ ¬𝑞.

81/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Minterms and Maxterms

Definition
A minterm is a product (or conjunction) of all the variables in
the function, where each variable appears in either its true
form or its negated form.

• For 𝑛 variables, there are 2𝑛 minterms.

• For 𝑝 and 𝑞, minterms are; 𝑝 ∧ 𝑞, 𝑝 ∧ ¬𝑞, ¬𝑝 ∧ 𝑞, ¬𝑝 ∧ ¬𝑞.

Definition
A maxterm is a sum (or disjunction) of all the variables in the
function, where each variable appears in either its true form
or its negated form. The maxterms are dual of minterms

• For 𝑛 variables, there are 2𝑛 maxterms.

• For 𝑝, 𝑞 and 𝑟, maxterms are; 𝑝 ∨ 𝑞 ∨ 𝑟, ¬𝑝 ∨ 𝑞 ∨ 𝑟, 𝑝 ∨ ¬𝑞 ∨
𝑟, 𝑝 ∨ 𝑞 ∨ ¬𝑟, ¬𝑝 ∨ ¬𝑞 ∨ 𝑟, ¬𝑝 ∨ 𝑞 ∨ ¬𝑟, 𝑝 ∨ ¬𝑞 ∨ ¬𝑟, ¬𝑝 ∨ ¬𝑞 ∨ ¬𝑟.

81/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Principal Disjunctive Normal Form

Definition
Principal disjunctive normal form (PDNF) is a standardized
format of a logical formula or compound proposition where
the formula is expressed as a disjunction (∨) of all possible
minterms.
i.e., A disjunction (∨) of all minterms where the function
evaluates to true. (Used to find PDNF using truth table)

82/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Principal Disjunctive Normal Form

Definition
Principal disjunctive normal form (PDNF) is a standardized
format of a logical formula or compound proposition where
the formula is expressed as a disjunction (∨) of all possible
minterms.
i.e., A disjunction (∨) of all minterms where the function
evaluates to true. (Used to find PDNF using truth table)

Definition
Principal Conjunctive Normal Form (PCNF) is a
standardized format of a logical formula where the formula
is expressed as a conjunction (∧) of all possible maxterms.
i.e., A conjunction (∧) of all maxterms where the function
evaluates to false. (Used to find PCNF using truth table)

82/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Principal Disjunctive Normal Form

Definition
Principal disjunctive normal form (PDNF) is a standardized
format of a logical formula or compound proposition where
the formula is expressed as a disjunction (∨) of all possible
minterms.
i.e., A disjunction (∨) of all minterms where the function
evaluates to true. (Used to find PDNF using truth table)

Definition
Principal Conjunctive Normal Form (PCNF) is a
standardized format of a logical formula where the formula
is expressed as a conjunction (∧) of all possible maxterms.
i.e., A conjunction (∧) of all maxterms where the function
evaluates to false. (Used to find PCNF using truth table)
• DNF, CNF are not unique, but PDNF, PCNF are unique.

82/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Examples

Example 1: Find PDNF of :

1 𝑝 ↔ 𝑞.
2 𝑝 ∨ ¬𝑞.
3 (¬𝑝 → 𝑞) ∧ (𝑞 ↔ 𝑝)

83/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution
Solution 1:
1 𝑝 ↔ 𝑞 ≡ ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞).
2

𝑝 ∨ ¬𝑞 ≡ [ 𝑝 ∧ (𝑞 ∨ ¬𝑞)] ∨ [¬𝑞 ∧ ( 𝑝 ∨ ¬𝑝)] [Ident., Neg. Law]

≡ [( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ ¬𝑞)] ∨ [(¬𝑞 ∧ 𝑝) ∨ (¬𝑞 ∧ ¬𝑝)]. [Dist. Law]
≡ ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ ¬𝑞) ∨ (¬𝑞 ∧ ¬𝑝). [Idempotent Law]
3

(¬𝑝 → 𝑞) ∧ (𝑞 ↔ 𝑝) ≡ ( 𝑝 ∨ 𝑞) ∧ [(𝑞 ∧ 𝑝) ∨ (¬𝑞 ∧ ¬𝑝)] [Imp., bico. L

≡ ( 𝑝 ∨ 𝑞) ∧ [(𝑞 ∧ 𝑝) ∨ ¬( 𝑝 ∧ 𝑞)]. [D-M., comm
≡ [( 𝑝 ∨ 𝑞) ∧ (𝑞 ∧ 𝑝)] ∨ [( 𝑝 ∨ 𝑞) ∧ ¬( 𝑝 ∧ 𝑞)]. [Di
≡ [( 𝑝 ∨ 𝑞) ∧ (𝑞 ∧ 𝑝)] ∨ F. [Neg. Law]
≡ [ 𝑝 ∧ (𝑞 ∧ 𝑝)] ∨ [𝑞 ∧ (𝑞 ∧ 𝑝)]. Dist. Law]
≡ [ 𝑝 ∧ 𝑞] ∨ [ 𝑝 ∧ 𝑞]. Idem., Asso. Law]
≡ 𝑝 ∧ 𝑞. Idem. Law]

84/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Methods

Methods to Obtain PDNF and PCNF:

1 Method-1: Using Truth Tables.
PDNF:
1 Given Statement should not be a contradiction.

2 Sum (∨) of the minterms corresponding to truth value T.

PCNF:
1 Given Statement should not be a tautology.

2 Sum (∨) of the minterms corresponding to truth value F.

Which is PDNF of ¬𝐴.
3 Negation of obtained PDNF is the required PCNF.
4 Another way is the conjunction (∧) of maxterms (of
negation of variables) corresponding to truth value F.

2 Method-2: Using Equivalence Laws.

85/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method 1: Truth Table

Problem: Find the PDNF and PCNF of the

following statements using the truth table :
1 (¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞).
2 𝑝 ∨ (¬𝑝 → (𝑞 ∨ (¬𝑞 → 𝑟))).
3 ( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟)).
4 ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ 𝑞 ∧ 𝑟)

86/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1: Using Truth Table

Problem: Find PDNF: (¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞).

87/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1: Using Truth Table

Problem: Find PDNF: (¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞).

Solution:
𝑝 𝑞 ¬𝑝 ¬𝑞 ¬𝑝 ∨ ¬𝑞 𝑝 ↔ ¬𝑞 [¬𝑝 ∨ ¬𝑞] → [ 𝑝 ↔ ¬𝑞]
𝑇 𝑇 𝐹 𝐹 𝐹 𝐹 𝑇
𝑇 𝐹 𝐹 𝑇 𝑇 𝑇 𝑇
𝐹 𝑇 𝑇 𝐹 𝑇 𝑇 𝑇
𝐹 𝐹 𝑇 𝑇 𝑇 𝐹 𝐹

The minterms corresponding to the three T values of the

final column are ( 𝑝 ∧ 𝑞), ( 𝑝 ∧ ¬𝑞), and (¬𝑝 ∧ 𝑞).
Hence, the PDNF of
[(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ 𝑞).

87/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1: Using Truth Table

Problem: Find PCNF: (¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞).

Solution:
Now, PDNF of ¬[(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ (¬𝑝 ∧ ¬𝑞).
[disjunction of the minterms corresponding to F]
[Missing minterms in PDNF of given statement.]
Hence, the PCNF of
[(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ ¬(¬𝑝 ∧ ¬𝑞) ≡ ( 𝑝 ∨ 𝑞).

88/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1: Using Truth Table

Problem: Find PCNF: (¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞).

Solution:
Now, PDNF of ¬[(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ (¬𝑝 ∧ ¬𝑞).
[disjunction of the minterms corresponding to F]
[Missing minterms in PDNF of given statement.]
Hence, the PCNF of
[(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ ¬(¬𝑝 ∧ ¬𝑞) ≡ ( 𝑝 ∨ 𝑞).
Another Way:
PCNF is the conjunction of maxterms corresponding to the
F values [but for example, the maxterm corresponding to
T, T, F value of 𝑝, 𝑞, 𝑟 is (¬𝑝 ∨ ¬𝑞, 𝑟).]
Hence, the PCNF of [(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ ( 𝑝 ∨ 𝑞).

88/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3: Using Truth Table
Problem: Find PDNF: ( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟)).

89/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3: Using Truth Table
Problem: Find PDNF: ( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟)).
Solution:
𝑝 𝑞 𝑟 ¬𝑝 ¬𝑞 ¬𝑟 𝑞 ∧ 𝑟 𝑝 → 𝑎 ¬𝑞 ∧ ¬𝑟 ¬𝑝 → 𝑐 𝑏∧𝑑
(𝑎) (𝑏) (𝑐) (𝑑)
𝑇 𝑇 𝑇 𝐹 𝐹 𝐹 𝑇 𝑇 𝐹 𝑇 𝑇
𝑇 𝑇 𝐹 𝐹 𝐹 𝑇 𝐹 𝐹 𝐹 𝑇 𝐹
𝑇 𝐹 𝑇 𝐹 𝑇 𝐹 𝐹 𝐹 𝐹 𝑇 𝐹
𝑇 𝐹 𝐹 𝐹 𝑇 𝑇 𝐹 𝐹 𝑇 𝑇 𝐹
𝐹 𝑇 𝑇 𝑇 𝐹 𝐹 𝑇 𝑇 𝐹 𝐹 𝐹
𝐹 𝑇 𝐹 𝑇 𝐹 𝑇 𝐹 𝑇 𝐹 𝐹 𝐹
𝐹 𝐹 𝑇 𝑇 𝑇 𝐹 𝐹 𝑇 𝐹 𝐹 𝐹
𝐹 𝐹 𝐹 𝑇 𝑇 𝑇 𝐹 𝑇 𝑇 𝑇 𝑇
The minterms corresponding to the two T values of the final
column are ( 𝑝 ∧ 𝑞 ∧ 𝑟), and (¬𝑝 ∧ ¬𝑞 ∧ 𝑟).
Hence, the PDNF of
[( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟))] ≡ ( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟).

89/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3: Using Truth Table

Problem: Find PCNF:

( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟)).
Solution: Now, PDNF of
¬[( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟))] ≡ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨
( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟).
[disjunction of the minterms corresponding to Fs]
[Missing minterms in PDNF of given statement.]
Hence, the PCNF of [( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟))] ≡
¬[( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ 𝑟)∨
(¬𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟)]
≡ (¬𝑝 ∨ ¬𝑞 ∨ 𝑟) ∧ (¬𝑝 ∨ 𝑞 ∨ ¬𝑟) ∧ (¬𝑝 ∨ 𝑞 ∨ 𝑟) ∧ ( 𝑝 ∨ ¬𝑞 ∨ ¬𝑟)∧
( 𝑝 ∨ ¬𝑞 ∨ 𝑟) ∧ ( 𝑝 ∨ 𝑞 ∨ ¬𝑟).

90/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3: Using Truth Table

Problem: Find PCNF:

( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟)).
Solution:
Another Way:
PCNF is the conjunction of maxterms corresponding to the
F values [but for example, the maxterm corresponding to
T, T, F value of 𝑝, 𝑞, 𝑟 is (¬𝑝 ∨ ¬𝑞, 𝑟).]
Hence, the PCNF of [(¬𝑝 ∨ ¬𝑞) → ( 𝑝 ↔ ¬𝑞)] ≡ ( 𝑝 ∨ 𝑞).

91/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Method 2: Equivalence Laws

Problem: Find the PDNF and PCNF of the

following statements without using the truth
table :

1 (¬𝑝 → 𝑞) ∧ ( 𝑝 ↔ 𝑞).

2 ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ 𝑞) ∨ (𝑞 ∧ 𝑟).

3 ( 𝑝 ∨ ¬(𝑞 ∨ 𝑟)) ∨ ((( 𝑝 ∧ 𝑞) ∧ ¬𝑟) ∧ 𝑝)

92/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 1: Equivalence Laws
Problem: Find PDNF and PCNF: (¬𝑝 → 𝑞) ∧ ( 𝑝 ↔ 𝑞).
Solution:
(¬𝑝 → 𝑞) ∧ ( 𝑝 ↔ 𝑞)
≡ ( 𝑝 ∨ 𝑞) ∧ [( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)] [Imp. & Bi-con. Law]
≡ ( 𝑝 ∨ 𝑞) ∧ [( 𝑝 ∧ 𝑞) ∨ ¬( 𝑝 ∨ 𝑞)] [De-Morgan’s Law]
≡ [( 𝑝 ∨ 𝑞) ∧ ( 𝑝 ∧ 𝑞)] ∨ [( 𝑝 ∨ 𝑞) ∧ ¬( 𝑝 ∨ 𝑞)] [Dist. Law]
≡ [( 𝑝 ∨ 𝑞) ∧ ( 𝑝 ∧ 𝑞)] ∨ F [Negation Law]
≡ [( 𝑝 ∧ ( 𝑝 ∧ 𝑞)] ∨ [𝑞 ∧ ( 𝑝 ∧ 𝑞)] ∨ F [Distributive Law]
≡ ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ 𝑞) [Commu., Asso. Idem. Law]
≡ ( 𝑝 ∧ 𝑞) [ Idempotent Law]

Hence the PDNF of the given statement (𝑆) is: ( 𝑝 ∧ 𝑞).

Now, PDNF of ¬𝑆 is: ( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞). [Missing
minterms.]
Therefore, the PCNF of 𝑆 is: ¬[( 𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞)].
i.e., (¬𝑝 ∨ 𝑞) ∧ ( 𝑝 ∨ ¬𝑞) ∧ ( 𝑝 ∨ 𝑞).

93/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 2: Equivalence Laws
Problem: Find PDNF and PCNF: ( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ 𝑞) ∨ (𝑞 ∧ 𝑟).
Solution:

( 𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ 𝑞) ∨ (𝑞 ∧ 𝑟)
≡ [( 𝑝 ∧ 𝑞) ∧ (𝑟 ∨ ¬𝑟)] ∨ [(¬𝑝 ∧ 𝑞) ∧ (𝑟 ∨ ¬𝑟)] ∨ [(𝑞 ∧ 𝑟) ∧ ( 𝑝 ∨ ¬𝑝)] [Iden.
≡ [( 𝑝 ∧ 𝑞) ∧ 𝑟] ∨ [( 𝑝 ∧ 𝑞) ∧ ¬𝑟] ∨ [(¬𝑝 ∧ 𝑞) ∧ 𝑟] ∨ [(¬𝑝 ∧ 𝑞) ∧ ¬𝑟]
∨[(𝑞 ∧ 𝑟) ∧ 𝑝] ∨ [(𝑞 ∧ 𝑟) ∧ ¬𝑝] [Distributive Law]
≡ ( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ ¬𝑟) [Idem. Law]

Hence the PDNF of the given statement (𝑆) is:

( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ ¬𝑟).
Now, PDNF of ¬𝑆 is:
(¬𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟).
[Missing minterms.]
Therefore, the PCNF of 𝑆 is:
¬[(¬𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟)]. i.e.,
( 𝑝 ∨ 𝑞 ∨ 𝑟) ∧ (¬𝑝 ∨ 𝑞 ∨ ¬𝑟) ∧ ( 𝑝 ∨ 𝑞 ∨ ¬𝑟) ∧ (¬𝑝 ∨ 𝑞 ∨ 𝑟).

94/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3: Equivalence Laws
Problem: Find PDNF and PCNF:
( 𝑝 ∨ ¬(𝑞 ∨ 𝑟)) ∨ ((( 𝑝 ∧ 𝑞) ∧ ¬𝑟) ∧ 𝑝).
Solution:
( 𝑝 ∨ ¬(𝑞 ∨ 𝑟)) ∨ ((( 𝑝 ∧ 𝑞) ∧ ¬𝑟) ∧ 𝑝)
≡ ( 𝑝 ∨ (¬𝑞 ∧ ¬𝑟)) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟 ∧ 𝑝) [Associative, De-Morgan’s. Law]
≡ [ 𝑝 ∧ (𝑞 ∨ ¬𝑞)] ∨ (¬𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) [Idem., Iden. Law]
≡ ( 𝑝 ∧ 𝑞) ∨ ( 𝑝 ∧ ¬𝑞) ∨ (¬𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) [Dist. Law]
≡ [( 𝑝 ∧ 𝑞) ∧ (𝑟 ∨ ¬𝑟)] ∨ [( 𝑝 ∧ ¬𝑞) ∧ (𝑟 ∨ ¬𝑟)]∨
[(¬𝑞 ∧ ¬𝑟) ∧ ( 𝑝 ∨ ¬𝑝)] ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) [Identity, Negation Law]
≡ ( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟)∨
( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) [Dist. Law]
≡ ( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟)∨
(¬𝑝 ∧ ¬𝑞 ∧ ¬𝑟) [Asso., commu. and Idempotent Laws]

95/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 3: Equivalence Laws

Problem: Find PDNF and PCNF:

( 𝑝 ∨ ¬(𝑞 ∨ 𝑟)) ∨ ((( 𝑝 ∧ 𝑞) ∧ ¬𝑟) ∧ 𝑝).
Solution:

( 𝑝 ∨ ¬(𝑞 ∨ 𝑟)) ∨ ((( 𝑝 ∧ 𝑞) ∧ ¬𝑟) ∧ 𝑝)

≡ ( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟)∨
(¬𝑝 ∧ ¬𝑞 ∧ ¬𝑟)

Hence the PDNF of the given statement (𝑆) is:

( 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ 𝑞 ∧ ¬𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ ( 𝑝 ∧ ¬𝑞 ∧ ¬𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ ¬𝑟).
Now, PDNF of ¬𝑆 is: (¬𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ ¬𝑟).
[Missing minterms.]
Therefore, the PCNF of 𝑆 is:
¬[(¬𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ ¬𝑞 ∧ 𝑟) ∨ (¬𝑝 ∧ 𝑞 ∧ ¬𝑟)]. i.e.,
( 𝑝 ∨ ¬𝑞 ∨ ¬𝑟) ∧ ( 𝑝 ∨ 𝑞 ∨ ¬𝑟) ∧ ( 𝑝 ∨ ¬𝑞 ∨ 𝑟).

96/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Home/Hostel Work

Problem: Find the PDNF and PCNF of the

following statements with and without using the
truth table :

1 𝑝 ∧ ¬(𝑞 ∧ 𝑟) ∨ ( 𝑝 → 𝑞).

2 (𝑞 ∨ ( 𝑝 ∧ 𝑟)) ∧ ¬(( 𝑝 ∨ 𝑟) ∧ 𝑞).

3 ( 𝑝 → (𝑞 ∧ 𝑟)) ∧ (¬𝑝 → (¬𝑞 ∧ ¬𝑟))

97/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Some Terminology

Definition
• An argument is a sequence of propositions (called
premises) followed by a proposition (called conclusion)
• Premises are statements that provide the basis or
reasons.
• An argument is valid, if all its premises are true, then the
conclusion is true.
• A fallacy is an error in reasoning that renders an
argument invalid.
• Inference is the process of deriving logical conclusions
from premises known or assumed to be true.
• A set of premises 𝑝 1 , 𝑝 2 , . . . , 𝑝 𝑛 is said to be inconsistent, if
( 𝑝 1 ∧ 𝑝 2 ∧ . . . ∧ 𝑝 𝑛 ) =⇒ F. Otherwise it is consistent.

98/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Rules of Inference

An argument form with premises 𝑝 1 , 𝑝 2 , . . . , 𝑝 𝑛 and

conclusion 𝑞 is valid if and only if
( 𝑝 1 ∧ 𝑝 2 ∧ . . . ∧ 𝑝 𝑛 ) → 𝑞 is a tautology.

Note:
1 We can always use a truth table to show an
argument is valid, but if n is large, the number
of rows 2𝑛 will be too large.
2 Instead, we can first establish the validity of
some relatively simple argument forms, called
rules of inference.

99/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Rules of Inference

Rule of Inference Tautology Symbol

𝑝 → 𝑞, 𝑝
𝑀𝑜𝑑𝑢𝑠 𝑃𝑜𝑛𝑒𝑛𝑠 ( 𝑝 → 𝑞) ∧ 𝑝 → 𝑞
∴ 𝑞
𝑝 → 𝑞, ¬𝑞
𝑀𝑜𝑑𝑢𝑠 𝑇 𝑜𝑙𝑙𝑒𝑛𝑠 ( 𝑝 → 𝑞) ∧ ¬𝑞 → ¬𝑝
∴ ¬𝑝
( 𝑝 → 𝑞) ∧ (𝑞 → 𝑟) → 𝑝 → 𝑞, 𝑞 → 𝑟
𝐻𝑦 𝑝𝑜𝑡ℎ𝑒𝑡𝑖𝑐𝑎𝑙 𝑆𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚
( 𝑝 → 𝑟) ∴ 𝑝→𝑟
𝐷𝑖𝑠 𝑗𝑢𝑛𝑐𝑡𝑖𝑣𝑒 𝑆𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚 ( 𝑝 ∨ 𝑞) ∧ ¬𝑝 → 𝑞 𝑝 ∨ 𝑞, ¬𝑝
∴ 𝑞
𝑝
𝐴𝑑𝑑𝑖𝑡𝑖𝑜𝑛 𝑝 → ( 𝑝 ∨ 𝑞)
∴ 𝑝∨𝑞
𝑆𝑖𝑚 𝑝𝑙𝑖 𝑓 𝑖𝑐𝑎𝑡𝑖𝑜𝑛 ( 𝑝 ∧ 𝑞) → 𝑝 𝑝∧𝑞
∴ 𝑝
𝑝, 𝑞
𝐶𝑜𝑛 𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑝 ∧ 𝑞 → ( 𝑝 ∧ 𝑞)
∴ 𝑝∧𝑞
𝑅𝑒𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 ( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨𝑟) → (𝑞 ∨𝑟) 𝑝 ∨ 𝑞, ¬𝑝 ∨ 𝑟
∴ 𝑞∨𝑟

100/149 Sumangal Bhattacharya Shiv Nadar University Chennai

R.I. for Quantified Statements

Rule of Inference Tautology Symbol

𝑈𝑛𝑖𝑣𝑒𝑟 𝑠𝑎𝑙 𝐼𝑛𝑠𝑡𝑎𝑛𝑡𝑖𝑎𝑡𝑖𝑜𝑛 ∀𝑥 𝑃(𝑥) → 𝑃(𝑐) ∀𝑥 𝑃(𝑥)

∴ 𝑃(𝑐)

𝐸𝑥𝑖𝑠𝑡𝑒𝑛𝑡𝑖𝑎𝑙 𝐼𝑛𝑠𝑡𝑎𝑛𝑡𝑖𝑎𝑡𝑖𝑜𝑛 ∃𝑥 𝑃(𝑥) → 𝑃(𝑐) ∃𝑥 𝑃(𝑥)

∴ 𝑃(𝑐)

𝑈𝑛𝑖𝑣𝑒𝑟 𝑠𝑎𝑙 𝐺𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛 𝑃(𝑐) → ∀𝑥 𝑃(𝑥) 𝑃(𝑐)

∴ ∀𝑥 𝑃(𝑥)

𝐸𝑥𝑖𝑠𝑡𝑒𝑛𝑡𝑖𝑎𝑙 𝐺𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛 𝑃(𝑐) → ∃𝑥 𝑃(𝑥) 𝑃(𝑐)

∴ ∃𝑥 𝑃(𝑥)

101/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Modus Ponens

102/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Modus Ponens

103/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Modus Tollens

104/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Modus Tollens

105/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Hypothetical Syllogism

106/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Hypothetical Syllogism

107/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Disjunctive Syllogism

108/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Disjunctive Syllogism

109/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Addition

110/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Addition

111/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Simplification

112/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Simplification

113/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Conjunction

114/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Conjunction

115/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Resolution

116/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Resolution

117/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Rules of Inference

Rule of Inference Tautology Symbol

𝑝 → 𝑞, 𝑝
𝑀𝑜𝑑𝑢𝑠 𝑃𝑜𝑛𝑒𝑛𝑠 ( 𝑝 → 𝑞) ∧ 𝑝 → 𝑞
∴ 𝑞
𝑝 → 𝑞, ¬𝑞
𝑀𝑜𝑑𝑢𝑠 𝑇 𝑜𝑙𝑙𝑒𝑛𝑠 ( 𝑝 → 𝑞) ∧ ¬𝑞 → ¬𝑝
∴ ¬𝑝
( 𝑝 → 𝑞) ∧ (𝑞 → 𝑟) → 𝑝 → 𝑞, 𝑞 → 𝑟
𝐻𝑦 𝑝𝑜𝑡ℎ𝑒𝑡𝑖𝑐𝑎𝑙 𝑆𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚
( 𝑝 → 𝑟) ∴ 𝑝→𝑟
𝐷𝑖𝑠 𝑗𝑢𝑛𝑐𝑡𝑖𝑣𝑒 𝑆𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚 ( 𝑝 ∨ 𝑞) ∧ ¬𝑝 → 𝑞 𝑝 ∨ 𝑞, ¬𝑝
∴ 𝑞
𝑝
𝐴𝑑𝑑𝑖𝑡𝑖𝑜𝑛 𝑝 → ( 𝑝 ∨ 𝑞)
∴ 𝑝∨𝑞
𝑆𝑖𝑚 𝑝𝑙𝑖 𝑓 𝑖𝑐𝑎𝑡𝑖𝑜𝑛 ( 𝑝 ∧ 𝑞) → 𝑝 𝑝∧𝑞
∴ 𝑝
𝑝, 𝑞
𝐶𝑜𝑛 𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑝 ∧ 𝑞 → ( 𝑝 ∧ 𝑞)
∴ 𝑝∧𝑞
𝑅𝑒𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 ( 𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨𝑟) → (𝑞 ∨𝑟) 𝑝 ∨ 𝑞, ¬𝑝 ∨ 𝑟
∴ 𝑞∨𝑟

118/149 Sumangal Bhattacharya Shiv Nadar University Chennai

R.I. for Quantified Statements

Rule of Inference Tautology Symbol

𝑈𝑛𝑖𝑣𝑒𝑟 𝑠𝑎𝑙 𝐼𝑛𝑠𝑡𝑎𝑛𝑡𝑖𝑎𝑡𝑖𝑜𝑛 ∀𝑥 𝑃(𝑥) → 𝑃(𝑐) ∀𝑥 𝑃(𝑥)

∴ 𝑃(𝑐)

𝐸𝑥𝑖𝑠𝑡𝑒𝑛𝑡𝑖𝑎𝑙 𝐼𝑛𝑠𝑡𝑎𝑛𝑡𝑖𝑎𝑡𝑖𝑜𝑛 ∃𝑥 𝑃(𝑥) → 𝑃(𝑐) ∃𝑥 𝑃(𝑥)

∴ 𝑃(𝑐)

𝑈𝑛𝑖𝑣𝑒𝑟 𝑠𝑎𝑙 𝐺𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛 𝑃(𝑐) → ∀𝑥 𝑃(𝑥) 𝑃(𝑐)

∴ ∀𝑥 𝑃(𝑥)

𝐸𝑥𝑖𝑠𝑡𝑒𝑛𝑡𝑖𝑎𝑙 𝐺𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛 𝑃(𝑐) → ∃𝑥 𝑃(𝑥) 𝑃(𝑐)

∴ ∃𝑥 𝑃(𝑥)

119/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 1

Problem: From the single proposition 𝑝 ∧ ( 𝑝 → 𝑞),

show that 𝑞 is the conclusion.

120/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 1

Problem: From the single proposition 𝑝 ∧ ( 𝑝 → 𝑞),

show that 𝑞 is the conclusion.
Solution:

Steps Reason

1. 𝑝 ∧ ( 𝑝 → 𝑞) Premise

2. 𝑝 Simplification using Step (1).

3. 𝑝 → 𝑞 Simplification using step (1).

4. 𝑞 Modus ponens using Steps (2) and (3).

120/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 2

Problem:
Given the following hypotheses:
1 It is not sunny this afternoon, and it is colder

than yesterday.
2 We will go swimming only if it is sunny.

3 If we do not go swimming, then we will take a

canoe trip.
4 If we take a canoe trip, then we will be home

by sunset.
Construct a valid argument for the conclusion:

We will be home by sunset.

121/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 2

Solution: Let the following propositions:

𝑝: It is sunny this afternoon

𝑞: It is colder than yesterday
𝑟: We will go swimming
𝑠: We will take a canoe trip
𝑡: We will be home by sunset

122/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 2

Solution: Let the following propositions:

𝑝: It is sunny this afternoon

𝑞: It is colder than yesterday
𝑟: We will go swimming
𝑠: We will take a canoe trip
𝑡: We will be home by sunset
Therefore, the premises becomes,
¬𝑝 ∧ 𝑞, 𝑟 → 𝑝, ¬𝑟 → 𝑠, 𝑠 → 𝑡.

and the conclusion is 𝑡.

122/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Soln 2: Construction of Valid Argument

Steps Reason

1. ¬𝑝 ∧ 𝑞 Premise

2. ¬𝑝 Simplification using Step (1)

3. 𝑟 → 𝑝 Premise

4. ¬𝑟 Modus tollen using Steps (2) and (3)

5. ¬𝑟 → 𝑠 Premise

6. 𝑠 Modus ponens using Steps (4) and (5)

7. 𝑠 → 𝑡 Premise

8. 𝑡 Modus ponens using Steps (6) and (7)

123/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Problem: Show that (𝑡 ∧ 𝑠) can be derived from the premises
𝑝 → 𝑞, 𝑞 → ¬𝑟, 𝑟, 𝑝 ∨ (𝑡 ∧ 𝑠).

124/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problem 3
Problem: Show that (𝑡 ∧ 𝑠) can be derived from the premises
𝑝 → 𝑞, 𝑞 → ¬𝑟, 𝑟, 𝑝 ∨ (𝑡 ∧ 𝑠).
Solution:

Steps Reason
1. 𝑝 → 𝑞 Premise

2. 𝑞 → ¬𝑟 Premise

3. 𝑝 → ¬𝑟 Hypothetical Syllogism using steps (1) and (2).

4. 𝑟 Premise

5. ¬𝑝 Modus Tollens using Steps (3) and (4).

6. 𝑝 ∨ (𝑡 ∧ 𝑠) Premise

7. 𝑡 ∧ 𝑠 Disjunction Syllogism using Steps (5) and (6).

124/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Methods

1 Direct Proof: By applying premises, rules of inference,

and equivalence laws, we will arrive at the conclusion.

2 Indirect Proof: If we have to prove 𝑝 1 ∧ 𝑝 2 . . . ∧ 𝑝 𝑛 =⇒ 𝑞,

then we will assume ¬q as an additional premise and
demonstrate that this assumption leads to a
contradiction.

3 Inconsistent: To prove inconsistency, we derive a

contradiction from the given premises.

4 Conditional Proof (CP) Rules: ( 𝑝 ∧ 𝑟) → 𝑠 ≡ 𝑝 → (𝑟 → 𝑠)

If a formula 𝑠 can be derived from another formula 𝑟 and
a set of premises, then the statement (𝑟 → 𝑠) can be
derived from the given premises alone.

125/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: Direct Proof

Problem 4: Give a direct proof for the implication:

𝑝 → (𝑞 → 𝑠), (¬𝑟 ∨ 𝑝), 𝑞 =⇒ (𝑟 → 𝑠).

Problem 5: Give a direct proof for the implication:

( 𝑝 → 𝑞)∧(𝑟 → 𝑠), (𝑞 → 𝑡)∧(𝑠 → 𝑢), ¬(𝑡∧𝑢), ( 𝑝 → 𝑟) =⇒ ¬𝑝.

126/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 4

Steps Reason
1. ¬𝑟 ∧ 𝑝 Premise

2. 𝑟 → 𝑝 Implication Law

3. 𝑝 → (𝑞 → 𝑠) Premise

4. 𝑟 → (𝑞 → 𝑠) Hypothetical syllogism using Steps (2) and (3)

5. ¬𝑟 ∨ (¬𝑞 ∨ 𝑠) Implication Law

6. 𝑞 Premise

7. 𝑞 ∧ (¬𝑟 ∨ ¬𝑞 ∨ 𝑠) Conjunction using Steps (5) and (6)

8. 𝑞 ∧ (¬𝑟 ∨ 𝑠) Dist., Neg., Domination Law

9. ¬𝑟 ∨ 𝑠 Simplification using Step (8)

10. 𝑟 → 𝑠 Implication Law

127/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 5

128/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: Indirect Proof

Problem 6: Use the indirect method to show the

implication:

𝑟 → ¬𝑞, 𝑟 ∨ 𝑠, 𝑠 → ¬𝑞, 𝑝 → 𝑞 =⇒ ¬𝑝.

Problem 7: Show that 𝑏 can be derived from the

premises 𝑎 → 𝑏, 𝑐 → 𝑏, 𝑑 → (𝑎 ∨ 𝑐), 𝑑, by the indirect
method.

129/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 6
Premises: 𝑟 → ¬𝑞, 𝑟 ∨ 𝑠, 𝑠 → ¬𝑞, 𝑝 → 𝑞, ¬(¬ 𝑝) ≡ 𝑝 (Additional)

130/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 6
Premises: 𝑟 → ¬𝑞, 𝑟 ∨ 𝑠, 𝑠 → ¬𝑞, 𝑝 → 𝑞, ¬(¬ 𝑝) ≡ 𝑝 (Additional)

Steps Reason
1. 𝑝 Premise (Additional)

2. 𝑝 → 𝑞 Premise

3. 𝑞 Modus Ponens using steps (1) and (2)

4. 𝑟 → ¬𝑞 Premise

5. 𝑠 → ¬𝑞 Premise

6. (𝑟 ∨ 𝑠) → ¬𝑞 Equivalence Laws using steps (4) and (5)

7. 𝑟 ∨ 𝑠 Premise

8. ¬𝑞 Modus Ponens using steps (6) and (7)

9. 𝑞 ∧ ¬𝑞 Conjunction using Steps (3) and (8)

10. F Negation Law

130/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 7

131/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: Inconsistent

Problem 8: Prove that the premises 𝑝 → 𝑞, 𝑞 → 𝑟,

𝑠 → ¬𝑟, 𝑝 ∧ 𝑠 are inconsistent.

Problem 9: show that the following set of

premises is inconsistent:
1 If Bean gets his degree, he will go for a job.

2 If he goes for a job, he will get married soon.

3 If he goes for higher study, he will not get

married.
4 Bean gets his degree and goes for higher

study.

132/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 8

Steps Reason
1. 𝑝 → 𝑞 Premise

2. 𝑞 → 𝑟 Premise

3. 𝑝 → 𝑟 Hypothetical Syllogism

4. 𝑠 → ¬𝑟 Premise

5. 𝑟 → ¬𝑠 Contra Positive

6. 𝑝 → ¬𝑠 Hypothetical syllogism using Steps (3) and (5)

7. ¬ 𝑝 ∨ ¬𝑠 Implication Law using Step (6)

8. ¬( 𝑝 ∧ 𝑠) De-Morgan’s Law using Step (7)

9. 𝑝 ∧ 𝑠 Premise

10. ¬( 𝑝 ∧ 𝑠) ∧ ( 𝑝 ∧ 𝑠) Conjunction using steps (8) and (9)

11. F Negation Law

133/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 9

134/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: CP Rules

Problem 10: Derive 𝑝 → (𝑞 → 𝑠) using the CP-Rule

from the premises 𝑝 → (𝑞 → 𝑟) and 𝑞 → (𝑟 → 𝑠).

Problem 11: Derive 𝑝 → 𝑠 using the CP-Rule from

the premises ¬𝑝 ∨ 𝑞, ¬𝑞 ∨ 𝑟, and 𝑟 → 𝑠

135/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 10
New premises are 𝑝 → (𝑞 → 𝑟 ), 𝑞 → (𝑟 → 𝑠), p and conclusion (𝑞 → 𝑠).

Steps Reason
1. 𝑝 Premise
2. 𝑝 → (𝑞 → 𝑟 ) Premise

3. (𝑞 → 𝑟 ) Modus Ponens using Steps (1) and (2)

4. ¬𝑞 ∨ 𝑟 Implication Law

5. 𝑞 → (𝑟 → 𝑠) Premise

6. ¬𝑞 ∨ (𝑟 → 𝑠) Implication Law

7. (¬𝑞 ∨ 𝑟 ) ∧ (¬𝑞 ∨ (𝑟 → 𝑠) ) Conjunction using steps (4) and (6)

8. ¬𝑞 ∨ (𝑟 ∧ (𝑟 → 𝑠) ) Distributive Law

9. ¬𝑞 ∨ 𝑠 Modus Ponens

10. 𝑞 → 𝑠 Equivalence Law

11. 𝑝 → (𝑞 → 𝑠) CP-Rule

136/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Solution 11

137/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Home/Hostel Work
Problems:
1 Show that:

(𝑎 → 𝑏) ∧ (𝑎 → 𝑐), ¬(𝑏 ∧ 𝑐), (𝑑 ∨ 𝑎) =⇒ 𝑑

2 Using indirect method/ CP Rules of proof,
derive 𝑝 → ¬𝑠 from the premises
𝑝 → (𝑞 ∨ 𝑟), 𝑞 → ¬𝑝, 𝑠 → ¬𝑟, 𝑝.
3 Construct an argument to show that the
following premises imply the conclusion "it
rained".
"If it does not rain or if there is no traffic
dislocation, then the sports day will be held,
and the cultural program will go on," "If the
sports day is held, the trophy will be awarded,"
and "The trophy was not awarded."

138/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Introduction to Proofs

Definition
• Proof: Proof is a valid argument that establishes the
truth of a mathematical statements.
• Theorem: Theorem is a statement that can be shown to
be true.
• Axioms or Postulates: Axoms are foundational
statements or propositions that are assumed to be true
without proof.
• Lemma: Lemmas are intermediate results used to prove
larger or more complex theorems.
• Corollary: Corollaries are statements that follow directly
from a theorem or lemma with minimal additional proof.
• Conjucture: A conjecture is a statement or proposition
in mathematics that is proposed to be true based on
observations, patterns, or empirical evidence but has not
yet been proven or formally established.
139/149 Sumangal Bhattacharya Shiv Nadar University Chennai
Method of Proving Theorems

1 Direct Proof: Straightforward logical reasoning.

2 Proof by Contraposition: Prove the contrapositive of the

statement.

3 Proof by Contradiction: Assume the negation and

derive a contradiction.

4 Proof by Counter examples Disprove a statement by

providing a counterexample.

5 Trivial Proof: The statement 𝑝 is proved because it is

obviously true or directly follows from definitions and
axioms.

6 Vacuous Proof: The statement "If 𝑝 → 𝑞 is proved by

showing that 𝑝 is false, making the implication true by
default.

140/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Direct Proof

1 A direct proof involves straightforward reasoning from

known facts, axioms, and previously proven theorems to
establish the truth of a statement.

2 To prove 𝑝 → 𝑞, we assume 𝑝 is true and use axioms,

definitions, and previously proven theorem together
with rules of inference to show that 𝑞 must be true.
3 Structure:
• Assumption: Start with assumptions or premises.
• Logic: Use logical steps and established results.
• Conclusion: Arrive at the desired conclusion.

141/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: Direct Proof

Problem 1: Give a direct proof of the theorem "If 𝑛 is an odd

integer, then 𝑛2 is odd."

Problem 2: Give a direct proof that "If 𝑚 and 𝑛 are both

perfect squares, then 𝑚𝑛 is also a perfect square."

142/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Proof by Contraposition

1 A proof by contraposition involves proving the

contrapositive of a statement. The contrapositive of
𝑝 → 𝑞 is ¬𝑞 → ¬𝑝

2 Structure:
• Statement: Prove ¬𝑞 → ¬𝑝 to establish 𝑝 → 𝑞.
• Logic: Show that if 𝑞 is false, then 𝑝 must also be false.

143/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: Contraposition

Problem 1: Prove that "if 𝑛 is an integer and 3𝑛 + 2 is odd, then

𝑛 is odd."

Problem 2: Prove that "if 𝑛2 is odd, then 𝑛 is odd."

Problem 3: Prove that "If 𝑚 and 𝑛 are integers and 𝑚 × 𝑛 is

even, then 𝑚 is even or 𝑛 is even."

144/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Proof by Contradiction

1 A proof by contradiction involves assuming the negation

of the statement to be proven and showing that this
assumption leads to a contradiction.

2 To prove a statement 𝑝, we assume its negation ¬𝑝 and

then derive a contradiction from this assumption.

3 Structure:
• Statement: Prove ¬𝑞 → ¬𝑝 to establish 𝑝 → 𝑞.
• Logic: Show that if 𝑞 is false, then 𝑝 must also be false.

145/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: contradiction

√
Problem 1: Prove that " 2 is an irrational number."

Problem 2: Prove that "If (3𝑛 + 2) is odd, then 𝑛 is odd."

146/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Proof by Counter Examples

1 A proof by counterexample involves demonstrating that

a statement is false by providing a specific example that
contradicts it.

2 Structure:
• Statement: Identify a statement that claims a general
property.
• Counterexample: Provide an example where the property
does not hold.

147/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Problems: Counterexamples

Problem 1: Show that the statement "All integers are even" is

false.

Problem 2: Show that the statement "Every positive integer

is the sum of the squares of two integers" is false.

Problem 3: Disprove the following statement using a

counterexample:
"If 𝐴 and 𝐵 are finite sets and | 𝐴 ∩ 𝐵| = | 𝐴| − 1, then |𝐵| = | 𝐴| − 1."

148/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Mistake in Proofs

Problem: What is wrong with this "proof" that ”1 = 2”?

"Proof": Let 𝑎 and 𝑏 be two equal positive integers.

Steps Reason
1. 𝑎 = 𝑏 Assume
2. 𝑎 2 = 𝑎𝑏 multiplying both side by 𝑎
3. 𝑎 2 − 𝑏 2 = 𝑎𝑏 − 𝑏 2 Subtracting both side by 𝑏 2
4. (𝑎 − 𝑏) (𝑎 + 𝑏) = 𝑏(𝑎 − 𝑏) Factorize
5. 𝑎 + 𝑏 = 𝑏 Dividing both sides by (𝑎 − 𝑏)
6. 2𝑏 = 𝑏 Using step 1
7. 2 = 1 dividing both side by 𝑏

149/149 Sumangal Bhattacharya Shiv Nadar University Chennai

Mistake in Proofs

Problem: What is wrong with this "proof" that ”1 = 2”?

"Proof": Let 𝑎 and 𝑏 be two equal positive integers.

Steps Reason
1. 𝑎 = 𝑏 Assume
2. 𝑎 2 = 𝑎𝑏 multiplying both side by 𝑎
3. 𝑎 2 − 𝑏 2 = 𝑎𝑏 − 𝑏 2 Subtracting both side by 𝑏 2
4. (𝑎 − 𝑏) (𝑎 + 𝑏) = 𝑏(𝑎 − 𝑏) Factorize
5. 𝑎 + 𝑏 = 𝑏 Dividing both sides by (𝑎 − 𝑏)
6. 2𝑏 = 𝑏 Using step 1
7. 2 = 1 dividing both side by 𝑏

Solution: All steps are correct except for Step 5, as it involves

dividing by 𝑎 − 𝑏 = 0, which is undefined.

149/149 Sumangal Bhattacharya Shiv Nadar University Chennai