1. The NAND Gate
Definition – NAND
NAND = NOT AND: an AND followed by a NOT.
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
The output is 0 only when all inputs are 1. The bubble on the symbol means “invert”.
Two Equivalent Symbols
By De Morgan, , so a NAND can be drawn as:
- AND-invert (AND body + output bubble), or
- invert-OR (OR body + bubbles on the inputs).
⚠️ NAND is not associative: . A 3-input NAND is , not two 2-input NANDs chained.
2. The NOR Gate
Definition – NOR
NOR = NOT OR: an OR followed by a NOT.
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
The output is 1 only when all inputs are 0.
Two equivalent symbols (De Morgan: ): OR-invert and invert-AND (see figure above). NOR is also not associative.
3. Universal Gates
NAND and NOR are easier to fabricate than AND/OR and are the basic gates of every IC logic family. They are universal: any logic circuit can be built from NANDs only, or from NORs only — it suffices to build NOT, AND and OR.
With NAND Gates
| Function | Expression |
|---|---|
| NOT | |
| AND | |
| OR |
With NOR Gates
| Function | Expression |
|---|---|
| NOT | |
| AND | |
| OR |
4. Two-Level NAND Implementation (from SoP)
Procedure
- Simplify the function and write it as a sum of products.
- First level: one NAND per product term with ≥ 2 literals (inputs = its literals). A single-literal term needs an inverter (i.e. it enters the second level complemented).
- Second level: one NAND whose inputs are the first-level outputs.
Why it works: AND–OR = NAND–NAND, since (De Morgan).
Example –
AND–OR, NAND–(invert-OR) and NAND–NAND are three equivalent drawings. NAND–NAND version:
Example –
| 00 | 01 | 11 | 10 | |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 |
K-map → . The single literal enters the output NAND as :
⚠️ A single-literal term going straight into the second-level NAND must be complemented — otherwise the output NAND inverts it the wrong way.
5. Multi-Level NAND Implementation
Procedure (Bubble Pushing)
- Replace every AND by a NAND drawn as AND-invert.
- Replace every OR by a NAND drawn as invert-OR.
- Check every bubble: a bubble not cancelled by another bubble on the same line must be compensated by an inverter (or by complementing the input literal).
Example 1 –
AND–OR structure: AND(,) → OR(·, ) → AND(·, ) → OR(·, AND(,)).
After steps 1–2, the bubble pairs on internal wires cancel. The input enters an invert-OR gate directly, so its input bubble is not compensated → feed instead:
Check: ; then ; with the output NAND gives ✓.
Example 2 –
Same chain, but the last gate is an AND (AND-invert) whose output bubble is not compensated → add an inverter at the output (and again use ):
6. NOR Implementations
Two-Level NOR (from PoS)
- Simplify the function and write it as a product of sums.
- First level: one NOR per sum term with ≥ 2 literals. A single-literal term needs an inverter (enters complemented).
- Second level: one NOR.
Why it works: OR–AND = NOR–NOR, since .
Example –
The single literal enters the output NOR as .
Multi-Level NOR (Bubble Pushing)
- Replace every AND by a NOR drawn as invert-AND.
- Replace every OR by a NOR drawn as OR-invert.
- Compensate every unpaired bubble with an inverter (or complement the input literal).
Example –
The first-level AND gates become invert-AND, so their inputs are complemented: → NOR(, ), → NOR(, ).
Check: NOR(,) , NOR(,) , so the middle NOR gives ; the lower NOR gives ; the output NOR gives ✓.
flowchart LR S["SoP"] --> N["NAND–NAND"] P["PoS"] --> R["NOR–NOR"] M["Any AND/OR circuit"] -->|"AND→AND-invert, OR→invert-OR"| N2["NAND only"] M -->|"AND→invert-AND, OR→OR-invert"| R2["NOR only"]
7. The XOR Gate
Definition – Exclusive-OR
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
if and only if .
Theorem – XOR Identities
| Identity | Proof |
|---|---|
| exercise | |
| exercise | |
| exercise |
Exercise – Prove
, and ✓.
XOR Circuits
With AND/OR/NOT:
With 4 NAND gates:
Check: the first NAND gives ; the middle NANDs give and ; the output is ✓.
8. The XNOR Gate
Definition – Exclusive-NOR (Equivalence)
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Output 1 when both inputs are equal → also called equivalence ().
⚠️ XOR/XNOR symbols exist for two inputs only in hardware; multi-input XOR/XNOR gates are hard to fabricate, so they are built as trees of 2-input gates.
9. Odd and Even Functions
Theorem – Multi-Input XOR is the Odd Function
Expanding the 3-variable XOR:
It is 1 when one or all three variables are 1 — i.e. an odd number of 1s.
Definition – Odd and Even Functions
| Output 1 when… | Output 0 when… | |
|---|---|---|
| Odd function () | odd number of 1s | even number of 1s |
| Even function () | even number of 1s | odd number of 1s |
The complement of an odd function is an even function.
Example – 3- and 4-Input Odd Functions
(two chained XORs) and (tree of three XORs).
Example – 4-Input Even Function
→ two XORs feeding one XNOR:
XOR/XNOR are building blocks for adders, subtractors, multipliers, counters, incrementers/decrementers and parity circuits.
10. Parity Generators and Checkers
Definition – Parity Bit
A parity bit is an extra bit added to a binary message so that the total number of 1s is even (even parity) or odd (odd parity). The receiver recomputes parity; a mismatch means an error (a bit flipped in transmission).
flowchart LR D["n-bit data"] --> G["Parity<br/>generator"] G -->|"(n+1)-bit message"| C["Parity<br/>checker"] C --> E["error flag"] D -.->|"data"| C
Example – 3-Bit Even-Parity Generator
makes the total number of 1s in even:
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
is 1 exactly when has an odd number of 1s → .
Example – 4-Bit Even-Parity Checker
The receiver gets (). With even parity, a correct message has an even number of 1s. The checker output (error) when the number of 1s is odd:
Its K-map is a checkerboard — no two 1s are adjacent, so no SoP simplification is possible, which is why XOR gates are used:
| 00 | 01 | 11 | 10 | |
|---|---|---|---|---|
| 00 | 1 | 1 | ||
| 01 | 1 | 1 | ||
| 11 | 1 | 1 | ||
| 10 | 1 | 1 |
⚠️ A single parity bit detects any odd number of flipped bits, but misses an even number (e.g. two bit errors).
Exercises: in the slides — prove , , and associativity of XOR (§7).