De Morgan Theorem 2

De Morgan's Second Theorem states that the complement of a sum equals the product of the complements, expressed as (A+B)' = A'B'. This identity is one of the most frequently tested results in digital electronics and forms the theoretical basis for converting OR-based logic into NAND/NOR gate networks. Understanding this theorem deeply allows engineers to simplify logic expressions and redesign circuits using a minimal set of universal gates.

Core Concept Explanation

The second De Morgan theorem tells us something physically intuitive: a NOR gate (OR followed by inversion) produces exactly the same output as feeding the inverted inputs into an AND gate. This is not just a mathematical curiosity. It reveals a deep duality in Boolean algebra between OR and AND operations, tied together by complementation.

To understand why (A+B)' = A'B', consider what (A+B)' means. The OR output A+B is logic 1 whenever at least one input is 1. Complementing it gives logic 0 whenever at least one input is 1, and logic 1 only when both inputs are 0. Now consider A'B': A' is 1 only when A is 0, and B' is 1 only when B is 0. Their AND is 1 only when both A and B are 0 simultaneously. Both expressions produce 1 under exactly the same condition, confirming the theorem.

The theorem extends naturally to more than two variables. For three variables, (A+B+C)' = A'B'C'. The pattern holds for any number of variables: complement the whole sum, and you get the AND of all individual complements. This generalization is critical for multi-input gate conversions in digital design.

In gate-level design, this theorem enables a powerful technique called **bubble pushing**. A NOR gate symbol can be redrawn as an AND gate with bubbles (inverters) on both inputs. This equivalence allows designers to simplify schematic reading by converting gates to match signal polarities without changing the underlying logic function.

Mathematical Expression

The formal statement of the second De Morgan theorem for two variables is written as (A + B)' = A' · B'. The left side applies OR first, then NOT. The right side applies NOT to each variable individually, then AND. The theorem can be proved rigorously using a complete truth table enumeration, which covers all 2^n input combinations for n variables. For the two-variable case, all four rows confirm equality. The algebraic proof uses the principle of duality and the complementation laws of Boolean algebra.

The generalized form for n variables is written as (A1 + A2 + ... + An)' = A1' · A2' · ... · An'. This is the cornerstone of NOR-to-NAND conversion and is used extensively in logic minimization and circuit synthesis tools.

Practical Understanding

In real digital circuits, NOR gates are universal gates. Using De Morgan's second theorem, any logic function built from AND, OR, and NOT gates can be converted into an equivalent NOR-only circuit. This has practical value in CMOS design where NOR gates have favorable pull-down network characteristics depending on the technology node.

When reading logic schematics, engineers frequently encounter gates with bubbles on inputs or outputs. De Morgan's theorem provides the rule to interpret these correctly. A gate with bubbles on both inputs and a changed gate type (AND to OR or vice versa) is always the De Morgan equivalent of the original gate. Misreading these leads to circuit implementation errors.

Given:
A = 1, B = 0

Why this formula applies:
We verify (A+B)' = A'·B' for specific input values

Formula:
(A+B)' = A'·B'

Substitution:
Left side: (1+0)' = (1)' = 0
Right side: (1)'·(0)' = 0·1 = 0

Calculation:
Left side = 0
Right side = 0

Final Answer:
Both sides equal 0. Theorem is verified for A=1, B=0.

Exam Tip: In GATE, a NOR gate drawn as an AND gate with inverted inputs is the De Morgan equivalent. When asked to identify the gate from a symbol with input bubbles and an AND body, the answer is NOR. Do not confuse this with XNOR.

Gate Equivalence Using De Morgan Second Theorem

• (A+B)' outputs 1 only when both A and B are 0, same as A'B'.
• A NOR gate is functionally identical to an AND gate with inverted inputs.
• Bubble pushing: move a bubble from output to all inputs and swap the gate type (OR becomes AND).
• The theorem generalizes: (A+B+C)' = A'B'C' for any number of variables.
• NOR is a universal gate because any logic function can be built using only NOR gates by applying this theorem repeatedly.

Quick Revision

• De Morgan Second Theorem: (A+B)' = A'B'. Complement of sum equals product of complements.
• Verified by truth table: only when A=0 and B=0 does (A+B)' give 1, same as A'B'.
• Gate equivalence: NOR gate = AND gate with bubbles on both inputs.
• Bubble pushing rule: shift output bubble to all inputs and change OR to AND.
• Generalized form: (A1+A2+...+An)' = A1'·A2'·...·An'.
• Exam trap: Do not apply De Morgan partially. Complement must cover the entire sum expression, not individual terms.
• NOR is universal: any Boolean function can be realized using only NOR gates via De Morgan's theorem.