Prashnikaप्रश्निका
Code
About
‹ Back to the paper
Computer Science20263 marksDerivationBoolean AlgebraTool: Boolean algebra solver

Prove the following.

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

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

Given: $[(a=>b) \cdot (b=>c)]$

To show: (a=>c)

Open in the Boolean algebra solver

Answer

Answer

Proof of Chain Rule using Boolean laws: LHS = [(a => b) • (b => c)] => (a => c) = [(a' + b) • (b' + c)] => (a' + c) (Conditional Elimination: x => y = x' + y) = [(a' + b) • (b' + c)]' + (a' + c) (Conditional Elimination) = (a' + b)' + (b' + c)' + a' + c (De Morgan's Law) = (a • b') + (b • c') + a' + c (De Morgan's Law & Involution) = (a' + a • b') + (c + b • c') (Commutative & Associative Laws) = (a' + b') + (c + b) (Redundancy Law / Distributive Law) = a' + c + (b' + b) (Associative Law) = a' + c + 1 (Complement Law: b' + b = 1) = 1 (Properties of 1: x + 1 = 1) Since LHS simplifies to 1 (tautology), the rule is proved.
  1. Step 1: Write implication using conditional law: [(a' + b) • (b' + c)] => (a' + c)
  2. Step 2: Express the outer implication using x => y = x' + y: [(a' + b) • (b' + c)]' + (a' + c)
  3. Step 3: Apply De Morgan's Law to the first term: (a' + b)' + (b' + c)' + a' + c
  4. Step 4: Apply De Morgan's Law and Involution to each subterm: (a • b') + (b • c') + a' + c
  5. Step 5: Rearrange terms using Commutative and Associative laws: (a' + a • b') + (c + b • c')
  6. Step 6: Apply Absorption / Distributive Law (x' + x • y = x' + y): (a' + b') + (c + b)
  7. Step 7: Rearrange terms: a' + c + (b' + b)
  8. Step 8: Apply Complement Law (b' + b = 1): a' + c + 1
  9. Step 9: Apply Properties of 1 (x + 1 = 1): 1
  10. Step 10: Since the expression evaluates to 1, [(a=>b) • (b=>c)] => (a=>c) is identically true.