Skip to main content

De Morgan's laws; XOR from NAND gates

Short answer

De Morgan's laws allow complementing expressions, converting SOP/POS forms for NAND/NOR realization, and simplifying circuits. A two-input XOR uses four NAND gates: Y = NAND( NAND(A, NAND(A,B)), NAND(B, NAND(A,B)) ).

What is the importance of De-Morgan's laws? Show how a two-input XOR gate can be constructed from a two-input NAND gate with required expressions.

Importance of De Morgan's laws

De Morgan's laws, A+B‾=AˉBˉ\overline{A+B} = \bar A \bar B and AB‾=Aˉ+Bˉ\overline{AB} = \bar A + \bar B, are important because:

  1. They let us complement any Boolean expression (break the bar, change AND ↔ OR).
  2. They convert SOP forms to NAND-NAND and POS forms to NOR-NOR circuits, so any circuit can be built with one type of universal gate, which reduces IC types and cost.
  3. They show gate equivalences: NAND = bubbled OR, NOR = bubbled AND; useful for reading and drawing circuits with active-low signals.
  4. They help in simplifying expressions and in proving positive/negative logic equivalences.

XOR from 2-input NAND gates

Y=A⊕B=ABˉ+AˉBY = A \oplus B = A\bar B + \bar A B needs four 2-input NAND gates.

Y=ABˉ+AˉB=A(Aˉ+Bˉ)+B(Aˉ+Bˉ)(since AAˉ=BBˉ=0)=A AB‾+B AB‾=A AB‾‾⋅B AB‾‾‾(De Morgan)\begin{aligned} Y &= A\bar B + \bar A B \\ &= A(\bar A + \bar B) + B(\bar A + \bar B) \quad (\text{since } A\bar A = B\bar B = 0) \\ &= A\,\overline{AB} + B\,\overline{AB} \\ &= \overline{\overline{A\,\overline{AB}} \cdot \overline{B\,\overline{AB}}} \quad (\text{De Morgan}) \end{aligned}

Gates: G1=AB‾G_1 = \overline{AB}, G2=AG1‾G_2 = \overline{A G_1}, G3=BG1‾G_3 = \overline{B G_1}, Y=G2G3‾Y = \overline{G_2 G_3}.

 A --+---------------[NAND G2]--+
     |                 |        |
     +--[NAND G1]--G1--+        +--[NAND G4]-- Y
     |                 |        |
 B --+---------------[NAND G3]--+
ABG1G_1G2G_2G3G_3Y
001110
011101
101011
110110

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Digital Logic chapter 2 questions →