De Morgan Theorem 1

De Morgan's theorems are among the most important and widely applied results in Boolean algebra. The first theorem states that the complement of a product equals the sum of the complements: (A.B)' = A' + B'. In logic gate terms, this means a NAND gate is equivalent to an OR gate with inverted inputs. This equivalence is not just a mathematical curiosity but a fundamental tool for logic circuit conversion, NAND-only and NOR-only implementation, and bubble logic analysis, all of which are critical topics in GATE digital electronics.

Core Concept: What the First Theorem States

De Morgan's first theorem in Boolean algebra states that complementing a product (AND operation) of variables is equivalent to taking the OR of the complements of each variable individually. Formally: (A . B)' = A' + B'. The theorem generalizes to any number of variables: (A . B . C . ... . N)' = A' + B' + C' + ... + N'. The complement of a product of n variables equals the OR sum of n individual complements.

The physical interpretation is straightforward. A NAND gate outputs 0 only when all inputs are 1. It outputs 1 whenever at least one input is 0, which is exactly what an OR gate does when given the complements (inverted versions) of the inputs. If even one input to the AND is 0 (meaning its complement is 1), the OR of complements produces 1, matching the NAND output. Both circuits produce the same truth table for all input combinations, confirming the theorem.

It is important to understand what this theorem does NOT say. It does not say that A' + B' = (A + B)'. The complement of a product is NOT the same as the complement of a sum. The complement distribution rule cannot be applied the way students sometimes assume. The theorem precisely maps product to sum (and vice versa in the second theorem) when the complement operation is applied to the entire expression, not just to individual terms independently.

Mathematical Expression: Proof of (A.B)' = A' + B'

The proof uses the complement axioms and uniqueness of Boolean complements. To prove (A.B)' = A' + B', it is sufficient to show that (A.B) AND (A' + B') = 0 and (A.B) OR (A' + B') = 1. If these two conditions hold, then A' + B' is the unique Boolean complement of A.B, which means (A.B)' = A' + B'.

Verification of condition 1: (A.B).(A' + B') = A.B.A' + A.B.B' = A.A'.B + A.B.B' = 0.B + A.0 = 0 + 0 = 0. Condition 1 satisfied. Verification of condition 2: A.B + A' + B'. By the null law, A + A' = 1, so A.B + A' = A' + A.B = A' + B (simplification theorem). Then A' + B + B' = A' + 1 = 1. Condition 2 satisfied. Therefore (A.B)' = A' + B' is proven. This algebraic proof method is known as the complement uniqueness proof method.

Practical Understanding: Gate Equivalence and Bubble Logic

The most direct application of De Morgan's first theorem is in logic gate conversion. A NAND gate is represented as AND followed by inversion. The theorem says this is equivalent to an OR gate preceded by inversions on each input (bubbled-input OR gate). This equivalence has two important practical uses. First, it allows NAND-gate-based logic design where every operation is implemented using only NAND gates, simplifying manufacturing since a single gate type is needed. Second, it enables bubble pushing, a graphical technique to trace complementation through logic diagrams without computing truth tables.

In two-level logic design, a Sum of Products (SOP) expression can be implemented with NAND-NAND logic by applying De Morgan's theorem. A SOP expression like F = A.B + C.D is implemented using AND gates followed by an OR gate. If NAND gates are used at the first level (each implementing one product term) and a NAND at the second level (implementing the final OR), the two-level NAND-NAND circuit is functionally identical to the AND-OR circuit. This is because (A.B)'' = A.B (double complement cancels) and the outer NAND on NAND effectively performs OR by De Morgan.

In integrated circuit design, especially with CMOS technology, NAND gates are preferred over AND gates because a CMOS NAND gate requires fewer transistors (4 transistors) compared to an AND gate (6 transistors, since AND = NAND followed by NOT). De Morgan's theorem enables the designer to freely convert between AND-OR and NAND-NAND realizations, optimizing transistor count without changing circuit functionality.

Numerical Example

Apply De Morgan's first theorem to find the complement of F = A.B.C and verify using truth table for A=1, B=0, C=1.

Given:
F = A.B.C
Values: A=1, B=0, C=1

Why this formula applies:
De Morgan's first theorem generalizes to three variables:
(A.B.C)' = A' + B' + C'

Formula:
(A.B.C)' = A' + B' + C'

Substitution (direct evaluation):
F = A.B.C = 1 . 0 . 1 = 0
F' = (A.B.C)' = 0' = 1

Verification via De Morgan:
A' + B' + C' = 1' + 0' + 1'
= 0 + 1 + 0
= 1

Calculation:
Direct complement = 1
De Morgan result = 0 + 1 + 0 = 1

Final Answer:
Both methods give F' = 1
De Morgan theorem verified for A=1, B=0, C=1.

Exam Tip: When applying De Morgan to a complex expression, always complement the ENTIRE expression first, then swap AND with OR and complement each variable. Do not complement each variable first and leave the operators unchanged. The correct order is: flip the operator (AND to OR), then complement each literal. For example, (A.B + C)' is NOT A'.B' + C'. It is (A.B)'.(C') = (A' + B').C' after applying both theorems step by step.

Quick Revision

• De Morgan Theorem 1: (A.B)' = A' + B'. Complement of product = sum of complements.
• Generalization to n variables: (A.B.C...N)' = A' + B' + C' + ... + N'.
• Gate equivalence: NAND = OR with bubbled (inverted) inputs. This is the standard NAND-to-bubbled-OR conversion.
• Two-level implementation: AND-OR circuit = NAND-NAND circuit. Both produce identical SOP functions.
• CMOS advantage: NAND gates use 4 transistors vs AND gate's 6, making NAND-NAND preferred in IC design.
• Exam trap: (A.B)' is NOT A'.B'. It is A' + B'. Distributing complement into a product changes AND to OR.
• Application method: To complement any expression, apply De Morgan repeatedly from outermost to innermost parentheses, swapping operators and complementing literals at each step.