Rule P: Introduce
Inference Rule:
Rule T: Derivation
P
Modus Ponens: P→Q
Q
∼Q
Modus Tollens: P→Q
∼P
∼P ∼Q
Disjunctive Syllogism: P∨Q and P ∨ Q
Q P
P∧Q
Simplification:
P or Q
P, Q
Conjunction:
P∧Q
P −→ Q
Hypothetical Syllogism: Q −→ R
P −→ R
Dilemma P ∨ Q, P → R, Q → R ⇒ R
[Link] Jaison MAT1002 March 30, 2021 52 / 199
Example 2.1.1
Prove that S is a valid conclusion from the premises P →∼ Q, Q ∨ R, ∼ S → P
and ∼ R.
Steps Statement Rule Step in- Justification
formula volved
1 ∼R P - -
2 Q∨R P - -
3 Q T 1,2 Disjunctive Syllogism
4 P →∼ Q P - -
5 ∼P T 3,4 Modus Tollens
6 ∼S→P P - -
7 ∼ (∼ S) T 5,6 Modus Tollens
8 S T 7 Double Negation
[Link] Jaison MAT1002 March 30, 2021 53 / 199
Example 2.1.2
Prove that R ∧ (P ∨ Q) is a valid conclusion from the premises P ∨ Q, Q → R,
P → M, ∼ M.
Steps Statement Rule Step in- Justification
formula volved
1 ∼M P - -
2 P→M P - -
3 ∼P T 1,2 Modus Tollens
4 P∨Q P - -
5 Q T 3,4 Disjunctive Syllogism
6 Q→R P - -
7 R T 5,6 Modus Ponnens
8 R ∧ (P ∨ Q) T 4,7 Conjunction
[Link] Jaison MAT1002 March 30, 2021 54 / 199
Definition 2.2.1 (Rules for k-map simplification)
1 Groups may not contain zero.
2 We can group 1, 2, 4, 8, . . . or 2n , n = 0, 1, 2, . . . cells.
3 Each group should be as large as possible.
4 Cells containing 1 must be grouped.
5 Groups may overlap.
6 Opposite grouping and other grouping is allowed.
7 There should be as few groups as possible.
[Link] Jaison MAT1002 March 30, 2021 55 / 199
Example 2.2.2
Simplify A + AB using K-map.
A B A + AB X
0 0 0+1.0 0
0 1 0+1.1 1
1 0 1+0.0 1
1 1 1+0.1 1
B
0 1
0 0 1
A
1 1 1
Grouping I Grouping II
A B A B
1 0 0 1
1 1 1 1
Answer: A+B
[Link] Jaison MAT1002 March 30, 2021 56 / 199
Example 2.2.3
Simplify f = ABC + ABC + AB + C using K-map.
A B C ABC +ABC +AB+C X
0 0 0 001+010+10+1 1
0 0 1 000+011+10+0 0
0 1 0 011+000+11+1 1
0 1 1 010+001+11+0 1
1 0 0 101+110+00+1 1
1 0 1 100+111+00+0 1
1 1 0 111+100+01+1 1
1 1 1 110+101+01+0 1
[Link] Jaison MAT1002 March 30, 2021 57 / 199
BC
00 01 11 10
0 1 0 1 1
A
1 1 1 1 1
Grouping I Grouping II Grouping III
A B C A B C A B C
1 0 1 0 1 1 0 1 0
1 1 1 0 1 0 0 0 0
1 1 0 1 1 1 1 1 0
1 0 0 1 1 0 1 0 0
A B C
f =A+B+C
[Link] Jaison MAT1002 March 30, 2021 58 / 199
Example 2.2.4
Simplify f = ĀB̄C + ĀBC + BC̄ + B̄C̄ using K-map.
A B C ĀB̄C + ĀBC + BC̄ + B̄C̄ X
0 0 0 110+100+01+11 1
0 0 1 110+101+00+10 1
0 1 0 100+110+11+01 1
0 1 1 101+111+10+00 1
1 0 0 010+000+01+11 1
1 0 1 011+001+00+10 0
1 1 0 000+010+11+01 1
1 1 1 001+011+10+00 0
[Link] Jaison MAT1002 March 30, 2021 59 / 199
BC
00 01 11 10
A 0 1 1 1 1
1 1 0 0 1
Grouping-I Grouping-II
A B C A B C
0 0 0 0 0 0
0 0 1 1 0 0
0 1 1 0 1 0
0 1 0 1 1 0
A C
F =A+C
[Link] Jaison MAT1002 March 30, 2021 60 / 199
Definition 2.3.1 (Logical statement or proposition)
A statement or a proposition is a sentence which is either true or false but not
both.
A statement which is both true and false simultaneously is not a statement,
rather it is a paradox.
Example 2.3.2 (True statement)
1 Delhi is the capital of India.
2 The earth is a planet.
Example 2.3.3 (Paradox)
1 Where are you going.
2 Switch on light.
[Link] Jaison MAT1002 March 30, 2021 61 / 199
Definition 2.3.4 (True value of a statement)
The truth value or falsity of a statement is called its truth value. If a statement
is true, we say that its truth value is TRUE, or T and if it is false. We say that
its truth value is FALSE or F.
Example 2.3.5
TRUE Delhi is the capital of India.
FALSE Earth is a star.
Definition 2.3.6 (Simple statement)
A statement is said to be simple statement if it can not be brocken into two or
more statements.
Example 2.3.7
Rose is a flower.
[Link] Jaison MAT1002 March 30, 2021 62 / 199
Definition 2.3.8 (Compound statement)
If a statement in the combination of two or more simple statements, then it is
said to be compound statement.
Example 2.3.9
It is raining and it is cold.
Truth value of compound statement determine by the truth value of its sub-
statements together.
[Link] Jaison MAT1002 March 30, 2021 63 / 199
Definition 2.3.10 (Connectives)
The word which combine simple statements to form compound statements are
called connectives. Some of the connectives are ‘and’, ‘or’ etc.
Definition 2.3.11 (Conjunction)
If two simple statement p and q are connected by the word ‘and’, then the
resulting compound statement ‘p and q’ is called the conjunction of p and q, it
is written in the symbolic form as ‘p ∧ q0 .
Example 2.3.12
p: Rahul is intelligent.
q: Ravi is handsome.
p ∧ q: Rahul is intelligent and Ravi is handsome.
[Link] Jaison MAT1002 March 30, 2021 64 / 199
Definition 2.3.13 (Convert the statement into symbolic form)
Mala and Kala are going to school. Then the statement can be written as
p : Mala is going to school.
q : Kala is going to school.
p ∧ q: is the symbolic form of Mala and Kala are going to school.
Definition 2.3.14 (Disconjunction)
If two simple statements p and q are connected by the word ‘or’, then the
resulting compound statement ‘p and q’ is called the disconjunction of p and q
is written in symbolic form as p ∨ q.
[Link] Jaison MAT1002 March 30, 2021 65 / 199
Definition 2.3.15 (Negation)
The negation of a statement is generally formed by introducing the word ‘not’
at some proper place in the statement or by prefixing the statement with ‘It is
not the case that’ or ‘It is false that’.
If p denotes a statement, then the negation of p is written a p.
p : Boys playing cricket.
∼ p : Not all boys playing cricket.
[Link] Jaison MAT1002 March 30, 2021 66 / 199
Logic - Equivalence - Implications
(i) Truth table for ‘and’, ‘×0 or (p ∧ q)
p q p∧q
T T T
T F F
F T F
F F F
(ii) Truth table for ‘or’, ‘+0 or (p ∨ q)
p q p∨q
T T T
T F T
F T T
F F F
[Link] Jaison MAT1002 March 30, 2021 67 / 199
(iii) Truth table for negation.
p ∼p
T F
F T
(iV) Truth table for Logical implication.
p q p→q
T T T
T F F
F T T
F F T
(V) Truth table for Logical implication.
p q p↔q
T T T
T F F
F T F
F F T
[Link] Jaison MAT1002 March 30, 2021 68 / 199
(i) Draw the truth table for (∼ p) ∨ (∼ q)
p q ∼p ∼q ∼ p∨ ∼ q
T T F F F
T F F T T
F T T F T
F F T T T
(ii) Draw the truth table for ∼ ((∼ p) ∧ q)
p q ∼p (∼ p) ∧ q ∼ ((∼ p) ∧ q)
T T F F T
T F F F T
F T T T F
F F T F T
[Link] Jaison MAT1002 March 30, 2021 69 / 199
(iii) Draw the truth table for ∼ ((∼ p) ∧ (∼ q))
p q ∼p ∼q ((∼ p) ∧ (∼ q)) ∼ ((∼ p) ∧ (∼ q))
T T F F F T
T F F T F T
F T T F F T
F F T T T F
[Link] Jaison MAT1002 March 30, 2021 70 / 199
(iv) Draw the truth table for (∼ W)(X + Y)Z
W X Y Z ∼W X+Y (∼ W)(X + Y) (∼ W)(X + Y)Z
F F F F T F F F
F F F T T F F F
F F T F T T T F
F F T T T T T T
F T F F T T T F
F T F T T T T T
F T T F T T T F
F T T T T T T T
T F F F F F F F
T F F T F F F F
T F T F F T F F
T F T T F T F F
T T F F F T F F
T T F T F T F F
T T T F F T F F
T T T T F T F F
[Link] Jaison MAT1002 March 30, 2021 71 / 199
Example 2.4.1
Draw a truth table for the following expressions
Example Solution
A + BC 11111000
A(B + D) 11100000
(A + B)(A + C) 11111000
W(X + Y)Z 0000000010101000
PT(P + Z) 00110000
[Link] Jaison MAT1002 March 30, 2021 72 / 199
Definition 2.4.2 (Tautology)
A statement form which is always true. The truth does not rely upon the values
of the individual statements substituted for the statement variables, but upon
the logical structure of the statement itself. (i.e., You will get an A in this class,
or you will not.).
Example 2.4.3
p q p→q q→p (p → q) ∨ (q → p)
T T T T T
T F F T T
F T T F T
F F T T T
[Link] Jaison MAT1002 March 30, 2021 73 / 199
Definition 2.4.4 (Contradiction)
A statement form which is always false. Like a tautology, the falsity does
not lie in the individual statement variables, but in the logical structure of the
statement itself. (i.e., I always tell lies.).
Example 2.4.5
p q p→q ∼ (p → q) q∧ ∼ (p → q)
T T T F F
T F F T F
F T T F F
F F T F F
[Link] Jaison MAT1002 March 30, 2021 74 / 199
Definition 2.4.6 (Logical equivalence)
Two compound statements A and B are said to be logically equivalent, if they
identical last column in their truth table. In this case we write A ≡ B.
∼ (p ∨ q) ≡ (∼ p) ∧ (∼ q)
Example 2.4.7
Show that P → Q and ∼ P ∨ Q are logically equivalent.
p q p→q ∼p ∼p∨q
T T T F T
T F F F F
F T T T T
F F T T T
[Link] Jaison MAT1002 March 30, 2021 75 / 199
Example 2.4.8
Prove that each of the following logical equivalencies
1 (∼ P → (Q∧ ∼ Q)) ≡ P
2 (P ↔ Q) ≡ (∼ P ∨ Q) ∧ (∼ Q ∨ P)
3 ∼ (P ↔ Q) ≡ (P∧ ∼ Q) ∨ (Q∧ ∼ P)
4 (P → Q) → R ≡ (P∧ ∼ Q) ∨ R
5 (P → Q) → R ≡ (∼ P → R) ∧ (Q → R)
6 [(P ∧ Q) → (R ∨ S)] ≡ [(∼ R∧ ∼ S) → (∼ P∨ ∼ Q)]
7 [(P ∧ Q) → (R ∨ S)] ≡ [(P ∧ Q∧ ∼ R) → S]
8 [(P ∧ Q) → (R ∨ S)] ≡ (∼ P∨ ∼ Q ∨ R ∨ S)
9 ∼ [(P ∧ Q) → (R ∨ S)] ≡ (P ∧ Q∧ ∼ R∧ ∼ S)
[Link] Jaison MAT1002 March 30, 2021 76 / 199
Equivalent law
Obsorbtion law P ∧ (P ∨ Q) = P
Double Negation ∼ (∼ P) ⇔ P
Conditional equivalence P → Q ⇔∼ P ∨ Q
Idempotent P∧P⇔P
P∨P⇔P
Commutative P∧Q⇔Q∧P
P∨Q⇔Q∨P
Identities P∧T ⇔P
P∨F ⇔P
Dominance Law P∨T ⇔T
P∧F ⇔F
Complement P∧ ∼ P ⇔ F
P∨ ∼ P ⇔ T
Associative law P ∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R
P ∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R
Distributive law P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)
DeMorgan’s law ∼ P∧ ∼ Q ⇔∼ (P ∨ Q)
∼ P∨ ∼ Q ⇔∼ (P ∧ Q)
[Link] Jaison MAT1002 March 30, 2021 77 / 199
Variations in distributive law
(P ∧ Q) ∨ (R ∧ S) = (P ∨ R) ∧ (P ∨ S) ∧ (Q ∨ R) ∧ (Q ∨ S)
(P ∧ Q) ∨ (R ∨ S) = (P ∨ (R ∨ S)) ∧ (Q ∨ R ∨ S)
[Link] Jaison MAT1002 March 30, 2021 78 / 199
Example 2.5.1
Show that [(P ∨ Q)∧ ∼ (∼ P ∧ (∼ Q∨ ∼ R))]∨[(∼ P∧ ∼ Q) ∨ (∼ P∧ ∼ R)]
is a tautology without using truth table. (Using equivalence law)
Statement
[(P ∨ Q)∧ ∼ (∼ P ∧ (∼ Q∨ ∼ R))] ∨ [(∼ P∧ ∼ Q) ∨ (∼ P∧ ∼ R)]
DeMorgans law
[(P ∨ Q)∧ ∼ (∼ P∧ ∼ (Q ∧ R))] ∨ [(∼ P∧ ∼ Q) ∨ (∼ P∧ ∼ R)]
Distributive law
[(P ∨ Q)∧ ∼ (∼ P∧ ∼ (Q ∧ R))] ∨ [∼ P ∧ (∼ Q∨ ∼ R)]
DeMorgans law
[(P ∨ Q)∧ ∼ × ∼ (P ∨ (Q ∧ R))] ∨ [∼ P∧ ∼ (Q ∧ R)]
Double negation, DeMorgans law
[(P ∨ Q) ∧ (P ∨ (Q ∧ R))] ∨ ∼ [P ∨ (Q ∧ R)]
Distributive law
[(P ∨ Q) ∧ {(P ∨ Q) ∧ (P ∨ R)}] ∨ ∼ [P ∨ (Q ∧ R)]
Associative law
[{(P ∨ Q) ∧ (P ∨ Q)} ∧ (P ∨ R)] ∨ ∼ [P ∨ (Q ∧ R)]
[Link] Jaison MAT1002 March 30, 2021 79 / 199
Idempotent
[(P ∨ Q) ∧ (P ∨ R)] ∨ ∼ [P ∨ (Q ∧ R)]
Distributive law
[P ∨ (Q ∧ R)] ∨ ∼ [P ∨ (Q ∧ R)]
Complement ⇔ T
[Link] Jaison MAT1002 March 30, 2021 80 / 199
Example 2.5.2
Prove that [∼ P ∧ (∼ Q ∧ R)] ∨ [(Q ∧ R) ∨ (P ∧ R)] ⇔ R without using truth
table. (Using equivalence law)
Statement
[∼ P ∧ (∼ Q ∧ R)] ∨ [(Q ∧ R) ∨ (P ∧ R)]
Associative law, Distributive law
[(∼ P∧ ∼ Q) ∧ R] ∨ [(Q ∨ P) ∧ R]
DeMorgans law
[∼ (P ∨ Q) ∧ R] ∨ [(P ∨ Q) ∧ R]
Distributive law
[∼ (P ∨ Q) ∨ (P ∨ Q)] ∧ R
Complement
T ∧R
Identities
R
[Link] Jaison MAT1002 March 30, 2021 81 / 199
Example 2.5.3
Prove that ((P → R) ∧ (Q → R)) ⇒ ((P ∨ Q) → R)
A ⇒ B if A → B is a Tautology.
So we need to prove that ((P → R) ∧ (Q → R)) → ((P ∨ Q) → R) is a Tau-
tology.
Statement
((P → R) ∧ (Q → R)) → ((P ∨ Q) → R)
Conditional equivalence
((∼ P ∨ R) ∧ (∼ Q ∨ R)) → ((P ∨ Q) → R)
Distributive law
[(∼ P∧ ∼ Q) ∨ R] → ((P ∨ Q) → R)
DeMorgan’s law
[∼ (P ∨ Q) ∨ R] → ((P ∨ Q) → R)
Conditional equivalence
[(P ∨ Q) → R] → [(P ∨ Q) → R]
Conditional equivalence
∼ [(P ∨ Q) → R] ∨ ((P ∨ Q) → R)
Complement
T
[Link] Jaison MAT1002 March 30, 2021 82 / 199
Example 2.5.4
Using the laws of logic, show that the following expression are logically equiv-
alent
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [(Q ∧ R) ∨ (Q∧ ∼ R)] ≡∼ P → Q
Statement
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [(Q ∧ R) ∨ (Q∧ ∼ R)]
Distributive
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [Q ∧ (R∨ ∼ R)]
Complement
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [Q ∧ T]
Identities
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [Q]
[Link] Jaison MAT1002 March 30, 2021 83 / 199
Associative
[P ∧ (P ∨ (∼ R ∨ Q))] ∨ [Q]
Obsorbtion law
P∨Q
Double Negation
∼ [∼ P] ∨ Q
Conditional equivalence
∼P→Q
[Link] Jaison MAT1002 March 30, 2021 84 / 199
Example 2.5.5
Without using truth table, prove that the following relation is Tautology
((A → B) ∧ A) → B
Statement
((A → B) ∧ A) → B
Conditional equivalence
((∼ A ∨ B) ∧ A) → B
Conditional equivalence
∼ ((∼ A ∨ B) ∧ A) ∨ B
DeMorgan’s law
(∼ (∼ A ∨ B)∨ ∼ A) ∨ B
DeMorgan’s law
((A∧ ∼ B)∨ ∼ A) ∨ B
[Link] Jaison MAT1002 March 30, 2021 85 / 199
Distributive
((A∨ ∼ A) ∧ (∼ B∨ ∼ A)) ∨ B
Complement
(T ∧ (∼ B∨ ∼ A)) ∨ B
Identities
(∼ B∨ ∼ A) ∨ B
Associative
∼ B ∨ (∼ A ∨ B)
Commutative
∼ B ∨ (B∨ ∼ A)
Associative
(∼ B ∨ B) ∨ ∼ A
Complement
T∨ ∼ A
Dominance Law
T
[Link] Jaison MAT1002 March 30, 2021 86 / 199