1. The NAND Gate

Definition – NAND

NAND = NOT AND: an AND followed by a NOT.

0001
0101
1001
1110

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).

xy(xy)‘xyx’+y’NAND: AND-invertNAND: invert-ORxy(x+y)‘xyx’y’NOR: OR-invertNOR: invert-AND

⚠️ 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.

0001
0110
1010
1110

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

FunctionExpression
NOT
AND
OR

xx’NOTxyxyANDxyx+yOR

With NOR Gates

FunctionExpression
NOT
AND
OR

xx’NOTxyxyANDxyx+yOR


4. Two-Level NAND Implementation (from SoP)

Procedure

  1. Simplify the function and write it as a sum of products.
  2. 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).
  3. 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:

ABCDF = AB + CD

Example –

00011110
0111
1111

K-map → . The single literal enters the output NAND as :

xy’x’yz’F = xy’ + x’y + z

⚠️ 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)

  1. Replace every AND by a NAND drawn as AND-invert.
  2. Replace every OR by a NAND drawn as invert-OR.
  3. 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:

CDB’ABC’F = A(CD+B) + BC’

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 ):

CDB’AF = A(CD+B)


6. NOR Implementations

Two-Level NOR (from PoS)

  1. Simplify the function and write it as a product of sums.
  2. First level: one NOR per sum term with ≥ 2 literals. A single-literal term needs an inverter (enters complemented).
  3. Second level: one NOR.

Why it works: OR–AND = NOR–NOR, since .

Example –

ABCDE’F = (A+B)(C+D)E

The single literal enters the output NOR as .

Multi-Level NOR (Bubble Pushing)

  1. Replace every AND by a NOR drawn as invert-AND.
  2. Replace every OR by a NOR drawn as OR-invert.
  3. 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(, ).

A’BAB’CD’F = (AB’+A’B)(C+D’)

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

000
011
101
110

if and only if .

Theorem – XOR Identities

IdentityProof
exercise
exercise
exercise

Exercise – Prove

, and ✓.

XOR Circuits

With AND/OR/NOT:

xyx ⊕ y = xy’ + x’y

With 4 NAND gates:

xyx ⊕ y

Check: the first NAND gives ; the middle NANDs give and ; the output is ✓.


8. The XNOR Gate

Definition – Exclusive-NOR (Equivalence)

001
010
100
111

Output 1 when both inputs are equal → also called equivalence ().

xyx ⊕ yxy(x ⊕ y)‘XORXNOR

⚠️ 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 1seven number of 1s
Even function ()even number of 1sodd 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:

ABCD(A⊕B⊕C⊕D)’ (even)

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:

000001010011100101110111
01101001

is 1 exactly when has an odd number of 1s → .

ABCP = A⊕B⊕C

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:

00011110
0011
0111
1111
1011

WXYZC = W⊕X⊕Y⊕Z

⚠️ 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).