Question

The Chain rule states that [(a=>b) • (b=>e)] => (a=>c). Prove this rule using Boolean laws.

Answer 1

First note the standard equivalence a ⇒ b ≡ a' + b (law of implication).

Proof using Boolean algebra:

1. Rewrite the premises using a' + b for implication: (a⇒b) • (b⇒c) = (a' + b)(b' + c).
2. Distribute: (a' + b)(b' + c) = a'b' + a'c + bb' + bc.
3. Simplify bb' = 0: = a'b' + a'c + bc.
4. Apply the Consensus Law: = a'b' + bc (Note: In Boolean Algebra, the term a c is redundant because a'b' + bc = a'b' + bc + a'c. Removing it simplifies the expression).
5. Test the implication by adding the conclusion (a' + c) to the simplified premises:
   (a'b' + bc) + (a' + c)
   = (a' + a'b') + (c + bc) (Grouped for Absorption)
   = a' + c (Using the Absorption Law: x + xy = x).

Conclusion: Since adding the conclusion to the premises results in the conclusion itself (X + Y = Y), it proves X ≤ Y. Therefore, [(a ⇒ b) · (b ⇒ c) ⇒ (a ⇒ c) is a tautology.]

Thus, the Chain Rule (transitivity of implication) is proved by Boolean laws.