Page 74 - ComputerScience_Class_11

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.

These laws can be proved using the truth tables. Some commonly used equivalence laws are given below:

S.No 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:
a. a ∨ (a ∧ b) = a

b. a ∧ (a ∨ b) = a

Answer: 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.

72 Touchpad Computer Science (Ver. 3.0)-XI