Page 77 - Cs_withBlue_J_C11_Flipbook
P. 77
3.5 EQUIVALENCE PROPOSITIONAL LAWS
Two statements are said to be equivalent if they have the same truth values for all the possible combinations of their
variables. Thus, if the values of a and b are true in the same set of models, then they are said to be logically equivalent.
Some commonly used equivalence laws are given below. These laws can be proved using the truth tables:
Name Expression
a. a ∨ 0 = a
1. Properties of 0
b. a ∧ 0 = 0
a. a ∨ 1 = 1
2. Properties of 1
b. a ∧ 1 = a
3. Involution law a. (a')' = a
a. a ∨ a = a
4. Idempotent law
b. a ∧ a = a
a. a ∨ a' = 1
5. Complementarity law
b. a ∧ a' = 0
a. a ∨ b = b ∨ a
6. Commutative law
b. a ∧ b = b ∧ a
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. Biconditional elimination a. a ↔ b = (a → b) ∧ (b → a)
Example 1: Prove the following using the truth table:
i. a ∨ (a ∧ b) = a
ii. a ∧ (a ∨ b) = a
Ans.
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 table, we see column a ∨ (a ∧ b) and 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.
Ans.
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
75
Propositional Logic, Hardware Implementation, Arithmetic Operations 75

