Page 75 - ComputerScience_Class_11

Example 2: Prove using truth table a → b = a' ∨ b.
Answer:
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 values (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).

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

Both columns (a → b) ∧ (b → a) and a ↔ b have same values (1, 0, 0, 1) for the same combinations of a and b. Hence
proved. This rule is also called Biconditional elimination.

Example 4: Prove using truth table a → b = b' → a'.
Answer: a b a' b' a → b b' → a'

0 0 1 1 1 1
0 1 1 0 1 1

1 0 0 1 0 0
1 1 0 0 1 1
Columns a → b and b' → a' have identical values (1, 1, 0, 1), hence they are equivalent. This rule is also called
Transportation (logic).
Example 5: Prove that (a ∧ (a → b)) → b = 1.

Answer:
a b a → b a ∧ (a → b) (a ∧ (a → b)) → b
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1

1 1 1 1 1
Here, (a ∧ (a → b)) → b has value (1, 1, 1, 1) for all combinations of a and b. Hence, we conclude (a ∧ (a → b)) → b = 1.
The above rule is also called Modus Ponens.

3.6 TAUTOLOGY, CONTRADICTION AND CONTINGENCY
In logic, tautology, contradiction and contingency are terms used to describe different types of logical propositions or
statements based on their truth values across all possible cases.

Propositional Logic, Hardware Implementation, Arithmetic Operations 73