Boolean Algebra Theorems

Boolean algebra theorems are the shortcuts that let engineers collapse dozens of gates into a handful. Every modern synthesizer from Synopsys Design Compiler to open-source Yosys applies these rules millions of times per second during logic optimization.

Core Concept

The commutative theorem says the order of inputs to a gate does not matter. A·B equals B·A. This seems obvious, but it justifies reordering literals to spot common factors in complex expressions.

De Morgan's theorem is the most tested result in GATE. It converts an AND into a NOR and an OR into a NAND. A 74HC00 quad-NAND package and a 74HC02 quad-NOR package are duals of each other in exactly this sense. The 74HC00 runs at 2–6 V with t_pd ≈ 6 ns and fan-out of 10.

The consensus theorem allows removal of a redundant term. If A·B and A'·C are both present, the term B·C is redundant and can be dropped without changing the function. This reduces gate count directly.

Boolean Expression

De Morgan's law in two directions: (A·B)' = A'+B' and (A+B)' = A'·B'. The redundancy theorem states A+A'·B = A+B. These two results together cover the majority of simplification steps seen in university exam papers.

Given:
  F = A·B + A'·B + A·B'

Formula / Rule:
  Apply commutative, distributive, complement, and identity axioms

Step by step:
  Step 1: Group first two terms: A·B + A'·B = B·(A + A')    [distributive]
  Step 2: A + A' = 1                                          [complement axiom]
  Step 3: B·(A + A') = B·1 = B                               [identity]
  Step 4: F = B + A·B'                                        [substitute]
  Step 5: Apply redundancy: B + A·B' = B + A                  [redundancy theorem]
          (set X=B, Y=A: X + X'·Y becomes X+Y where X'=B')
          Verify: B + A·B' — use distributive: (B+A)·(B+B') = (B+A)·1 = A+B

Final Answer:
  F = A + B

Exam Tip: De Morgan's theorem is applied in two directions. Breaking a complement over AND flips to OR, and vice versa. A common trap is writing (A·B)' = A'·B' — this is wrong; the correct result is A'+B'. Also, the OR distributive law A+(B·C)=(A+B)·(A+C) is non-obvious and often confused with the AND form. Both are valid in Boolean algebra but not in ordinary arithmetic.

Key Properties

• Commutative: gate input order is interchangeable — useful when routing signals on a PCB
• Associative: grouping of three or more inputs does not affect result — justifies multi-input gates
• Distributive over OR: A·(B+C)=A·B+A·C — mirrors arithmetic; Distributive over AND: A+(B·C)=(A+B)·(A+C) — has no arithmetic parallel
• Absorption: A+A·B=A removes the redundant A·B term, reducing gate count by one AND gate
• De Morgan: (A·B)'=A'+B' — 74HC00 NAND output equals NOR of complemented inputs
• Consensus: B·C is redundant when A·B and A'·C both exist in a sum-of-products
• 74HC02 quad-NOR: Vcc 2–6 V, t_pd ≈ 7 ns, fan-out 10, I_cc ≈ 0.08 mA — dual of 74HC00

Quick Revision

• Seven main theorems: commutative, associative, distributive, absorption, De Morgan, consensus, redundancy
• De Morgan: complement flips AND↔OR and complements each variable
• Absorption: A+A·B=A and A·(A+B)=A — the longer term vanishes
• Redundancy: A+A'·B=A+B — complement of A releases the lock on B
• Consensus term B·C can always be dropped when A·B and A'·C are present
• OR distributive has no arithmetic analogue — memorise it separately
• Exam trap: (A+B)'=A'+B' is wrong; correct form is A'·B' — De Morgan flips the operator