Page 25 - Computer science 868 Class 12
P. 25
Example 2: Prove that ((a → b) ∧ (b → c)) → (a → c) is a tautology.
Solution:
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.
Solution: a a' a ∧ a'
The final column is 0 for all values of a. Hence, it is a contradiction. 0 1 0
1 0 0
Example 4: Prove that ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c) is a contradiction.
Solution:
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. a b a ∨ b ∼(a ∨ b)
Solution: 0 0 0 1
The values in the final column contain both 0 and 1. 0 1 1 0
Hence, it is a contingency. 1 0 1 0
1 1 1 0
Example 6: Prove that (a ∧ (a → b)) → ∼a is a contingency.
Solution:
a b ∼a a → b a ∧ (a → b) (a ∧ (a → b)) → ∼a
0 0 1 1 0 1
0 1 1 1 0 1
1 0 0 0 0 1
1 1 0 1 1 0
The last column has both 0 and 1 as truth values. So, it is a contingency.
23
Boolean Algebra 23

