Boolean Axioms, Canonical SOP/POS & Universal Logic Implementation
Idea in plain words
Boolean Postulates: Commutative, Associative, Distributive (A + BC = (A + B)(A + C)), Identity (A + 0 = A, A · 1 = A), and Complement (A + A' = 1, A · A' = 0).
Exam tip
High-yield exam topic (Very High).
Explanation
Boolean algebra provides the mathematical framework for modeling two-state switching circuits. Any logic function can be expressed in canonical Sum of Minterms (SOP) or Product of Maxterms (POS). Since NAND and NOR gates form functionally complete sets, any multi-level AND-OR circuit can be transformed into a NAND-NAND or NOR-NOR equivalent by inserting bubble inversions and applying De Morgan's identities without changing circuit latency.
Key points
- Principle of Duality: Any valid Boolean algebraic identity remains valid if AND and OR operators are interchanged, and 0 and 1 are interchanged.
- De Morgan's Laws: (A + B)' = A' · B' and (A · B)' = A' + B'.
- Canonical Forms: Minterm (m_i) is a product of all literals where variable is unprimed for 1 and primed for 0; Maxterm (M_i) is a sum where variable is primed for 1 and unprimed for 0.
- Universal Gates: NAND and NOR gates can implement all three primary operations (NOT, AND, OR) individually, making single-gate-type silicon manufacturing practical.
Example
Example
Convert F(A, B, C) = AB + A'C to canonical SOP: F = AB(C + C') + A'(B + B')C = ABC + ABC' + A'BC + A'B'C = ∑m(1, 3, 6, 7). Maxterm form: ∏M(0, 2, 4, 5).
Code examples
// Realization of Basic Gates Using Only 2-Input NAND Gates:
// 1. NOT Gate:
// Y = A' = (A · A)' => 1 NAND gate
// 2. AND Gate:
// Y = A · B = ((A · B)')' => 2 NAND gates
// 3. OR Gate:
// Y = A + B = (A' · B')' => 3 NAND gates (Invert inputs, then NAND)
// 4. XOR Gate:
// Y = A ⊕ B = A'B + AB' = (A · (A · B)')' · (B · (A · B)')'
// => 4 NAND gates:
// N1 = (A · B)'
// N2 = (A · N1)'
// N3 = (B · N1)'
// N4 = (N2 · N3)' = A ⊕ B
Exam questions
- [8 Marks] State and prove De Morgan's theorems. Implement F(w, x, y, z) = ∑m(0, 2, 8, 10, 14) using NAND gates only.
- [7 Marks] Convert the Boolean expression F = (A + B)(B + C)(A + C) into standard SOP and canonical POS forms.
- [7 Marks] Prove algebraically that A + A'B = A + B and AB + A'C + BC = AB + A'C (Consensus Theorem).