Page 23 - Computer science 868 Class 12
P. 23
From the above table, it is clear that both columns (a → b) ∧ (b → a) and a ↔ b have the same values (1, 0, 0, 1) for
the same combinations of a and b. Hence proved. This rule is also called Bi-conditional elimination.
Example 4: Prove using truth table a → b = b' → a'.
Solution:
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
From the above table, it is clear that both columns a → b and b' → a' have identical values (1, 1, 0, 1), for the same
combinations of a and b, hence they are equivalent. This rule is also called transportation (logic).
Example 5: From the premises a and a → b infer b
Or
Prove that (a ∧ (a → b)) → b = 1.
Solution: Let us draw the truth table of a and a → b, i.e., (a ∧ (a → b)). Now inference is to be drawn on b which means
the expression is:
if (a ∧ (a → b)) then b or (a ʌ (a → b)) → b which is a tautology as seen in the truth table given below. Hence,
(a ∧ (a → b)) → b) = 1 is also proved.
The above rule is also called Modus Ponens.
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
Example 6: If p → q and q → r are two propositions, then derive p → r
Solution:
Premises 1: p → q
Premises 2: q → r
Inference to be drawn on p → r
Let us draw the truth table of p → q and q → r, i.e., (p → q) ʌ (q → r)
To derive a conclusion on p → r, we write:
if p → q and q → r then p → r
Or
(p → q) ʌ (q → r) → p → r which is a tautology as derived from the truth table given below.
We can thus conclude p → q and q → r infers p → r
The above proposition is called the Chain rule or law of syllogism.
21
Boolean Algebra 21

