Page 22 - Computer science 868 Class 12
P. 22
a. (a ∨ b) ∨ c = a ∨ (b ∨ c)
7. Associative law b. (a ∧ b) ∧ c = a ∧ (b ∧ c)
a. a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
8. Distributive law
b. a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
a. (a ∧ b)' = a' ∨ b'
9. De Morgan’s law
b. (a ∨ b)' = a' ∧ b'
10. Conditional elimination a. a → b = a' ∨ b
11. Bi-conditional elimination a. a ↔ b = (a → b) ∧ (b → a)
Let us understand equivalence laws with the help of some examples.
Example 1: Prove the following using the truth table:
i. a ∨ (a ∧ b) = a
ii. a ∧ (a ∨ b) = a
Solution: The truth table for the given propositions is as follows:
a b (a ∧ b) a ∨ (a ∧ b) (a ∨ b) a ∧ (a ∨ b)
0 0 0 0 0 0
0 1 0 0 1 0
1 0 0 1 1 1
1 1 1 1 1 1
From the above table, we see that the fourth column a ∨ (a ∧ b) and the sixth column a ∧ (a ∨ b) have the same value
(0, 0, 1, 1) as that of column a. Hence proved. This law is called Absorption law.
Example 2: Prove using truth table a → b = a' ∨ b.
Solution:
a b a' a → b a' ∨ b
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1
From the table, we conclude a → b = a' ∨ b as both columns have the same value (1, 1, 0, 1) for the same combinations of
a and b. This law is called Conditional elimination.
Example 3: Prove using truth table a ↔ b = (a → b) ∧ (b → a).
Solution: a b a ↔ b a → b b → a (a → b) ∧ (b → a)
0 0 1 1 1 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 1 1 1 1
2020 Touchpad Computer Science-XII

