---
title: "Prove De Morgan's theorems; XOR using NAND"
subject: "Digital Logic"
chapter: 2
key: "semester_3/digital_logic:demorgan-prove-xor-nand"
source: https://www.bctengineer.com/q/semester_3/digital_logic/demorgan-prove-xor-nand
site: BCT Engineering
---

# Prove De Morgan's theorems; XOR using NAND

Digital Logic · Chapter 2: Digital Logic

- Asked in: 2080 Bhadra, 2+3 marks; 2080 Baisakh, 5+3 marks; 2078 Bhadra, 2+4 marks (asked 3 times)
- Video: [Lec-30   X-OR using NAND gates, DeMorgan theorom applied, Boolean exp. irshad academy](https://www.youtube.com/watch?v=VsuA-XKlzv4) — Irshad Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/digital_logic/demorgan-prove-xor-nand
- Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-2

## Question

State and prove De-Morgan's theorems with necessary diagrams. Construct XOR gate using minimum number of NAND gates.

## Short answer

De Morgan's theorems: (A+B)' = A'·B' and (A·B)' = A'+B'. An XOR gate can be built with 4 NAND gates: Y = (A·(AB)')' · (B·(AB)')' = A⊕B.

## Answer

#### De Morgan's theorems
De Morgan's theorems tell how to complement a sum or a product of variables.

**Theorem 1:** The complement of a sum equals the product of the complements.
$$
\overline{A + B} = \bar{A} \cdot \bar{B}
$$
So a **NOR gate equals a bubbled AND gate** (AND with inverted inputs).

**Theorem 2:** The complement of a product equals the sum of the complements.
$$
\overline{A \cdot B} = \bar{A} + \bar{B}
$$
So a **NAND gate equals a bubbled OR gate** (OR with inverted inputs).

**Proof by truth table**

| A | B | $A+B$ | $\overline{A+B}$ | $\bar A \bar B$ | $AB$ | $\overline{AB}$ | $\bar A + \bar B$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |

Column 4 = column 5 and column 7 = column 8 for every input, so both theorems are proved.

**Algebraic proof of Theorem 1:** if $X = A + B$ and $Y = \bar A \bar B$, then $X + Y = A + B + \bar A \bar B = A + B + \bar B = 1$ and $X \cdot Y = A \bar A \bar B + B \bar A \bar B = 0$. Since $X + Y = 1$ and $XY = 0$, Y is the complement of X. Theorem 2 follows by duality.

**Diagrams**

```text
 Theorem 1: NOR = bubbled AND
 A --|‾‾‾\             A --o|‾‾‾\
     | OR  )o-- Y   =       | AND )-- Y
 B --|___/             B --o|___/

 Theorem 2: NAND = bubbled OR
 A --|‾‾‾\             A --o|‾‾‾\
     | AND )o-- Y   =       | OR  )-- Y
 B --|___/             B --o|___/

 (o = inversion bubble)
```

#### XOR using minimum NAND gates
$Y = A \oplus B = A\bar B + \bar A B$. It can be built with **4 two-input NAND gates**:

$$
\begin{aligned} G_1 &= \overline{AB} \\ G_2 &= \overline{A \cdot G_1} = \overline{A \cdot \overline{AB}} \\ G_3 &= \overline{B \cdot G_1} = \overline{B \cdot \overline{AB}} \\ Y &= \overline{G_2 \cdot G_3} = A\,\overline{AB} + B\,\overline{AB} \\ &= A(\bar A + \bar B) + B(\bar A + \bar B) \\ &= A\bar B + \bar A B = A \oplus B \end{aligned}
$$

```text
 A --+-------------[NAND G2]--+
     |              |         |
     +--[NAND G1]---+         +--[NAND G4]-- Y
     |              |         |
 B --+-------------[NAND G3]--+
```

G1 output feeds one input of both G2 and G3; A goes to G2, B goes to G3; G2 and G3 feed G4.

| A | B | G1 | G2 | G3 | Y |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is De Morgan's first theorem?
   A. (A+B)' = A'B'
   B. (A+B)' = A'+B'
   C. (AB)' = A'B'
   D. (A+B)' = AB
   Answer: A. The complement of a sum is the product of complements. (Key point: Theorem 1)

2. What is the second theorem?
   A. (AB)' = A'B'
   B. (AB)' = A+B
   C. (AB)' = AB'
   D. (AB)' = A' + B'
   Answer: D. The complement of a product is the sum of complements. (Key point: Theorem 2)

3. NAND equals which gate form?
   A. Bubbled AND
   B. Plain AND
   C. Bubbled OR (OR with inverted inputs)
   D. Plain OR
   Answer: C. NAND = A' + B'. (Key point: Gate equivalence)

4. How many 2-input NAND gates form XOR at minimum?
   A. 2
   B. 4
   C. 3
   D. 6
   Answer: B. G1=(AB)', G2=(A G1)', G3=(B G1)', Y=(G2 G3)'. (Key point: XOR with NAND)

## Related in Digital Logic

- [XOR gate using minimum NAND gates](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Axor-using-nand-only) — Digital Logic, chapter 2, asked 2×
- [De Morgan's laws; XOR from NAND gates](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Ademorgan-importance-xor-nand) — Digital Logic, chapter 2
- [De Morgan's laws; XOR using 3-input NAND](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Ademorgan-xor-three-input-nand) — Digital Logic, chapter 2
- [De Morgan; NOR gate from NAND gates](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Ademorgan-importance-nor-from-nand) — Digital Logic, chapter 2
- [De Morgan; positive NAND equals negative NOR](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Ademorgan-positive-nand-negative-nor) — Digital Logic, chapter 2
- [De Morgan's laws; XNOR using NOR gates](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Ademorgan-xnor-nor) — Digital Logic, chapter 2

## Related in other subjects

- [State and prove De Morgan's theorems](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Ade-morgan-state-prove) — Basic Electronics Engineering, chapter 6, asked 4×
- [X-OR gate using NAND gates only](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Axor-using-nand) — Basic Electronics Engineering, chapter 6
- [Encoder; NAND and XOR truth tables](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Aencoder-truth-tables) — Basic Electronics Engineering, chapter 6
- [De Morgan's theorem and duality theorem](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Ade-morgan-duality) — Basic Electronics Engineering, chapter 6