Page 79 - Cs_withBlue_J_C11_Flipbook
P. 79
Example 1: Prove that a ∨ a' is a tautology.
Ans. The final column is 1 for all values of a. Hence, it is a tautology.
a a' a ∨ a'
0 1 1
1 0 1
Example 2: Prove that ((a → b) ∧ (b → c)) → (a → c) is a tautology.
Ans.
a b c (a → b) (b → c) (a → c) (a → b) ∧ (b → c) ((a → b) ∧ (b → c)) → (a → c)
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 1 1 1 1 1 1 1
1 0 0 0 1 0 0 1
1 0 1 0 1 1 0 1
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1
The final column results in 1. So, it is a tautology.
Example 3: Prove that a ∧ a' is a contradiction.
Ans. The final column is 0 for all values of a. Hence, it is a contradiction.
a a' a ∧ a'
0 1 0
1 0 0
Example 4: Prove that ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c) is a contradiction.
Ans. a b c (a → b) (b → c) a ∧ ~c (a → b) ∧ (b → c) ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c)
0 0 0 1 1 0 1 0
0 0 1 1 1 0 1 0
0 1 0 1 0 0 0 0
0 1 1 1 1 0 1 0
1 0 0 0 1 1 0 0
1 0 1 0 1 0 0 0
1 1 0 1 0 1 0 0
1 1 1 1 1 0 1 0
The final column results in 0. So, it is a contradiction.
Example 5: Prove that ∼(a ∨ b) is a contingency.
Ans. The values in the final column contain both 0 and 1.
Hence, it is a contingency.
a b a ∨ b ∼(a ∨ b)
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
77
Propositional Logic, Hardware Implementation, Arithmetic Operations 77

