Logic Gates

Digital Logic 101 · 10 min read

The seven canonical gates

AND

Y = A \cdot B

A	B	Y
0	0	0
0	1	0
1	0	0
1	1	1

Y = A + B

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	1

NOT

Y = \overline{A}

A	Y
0	1
1	0

NAND

Y = \overline{A \cdot B}

A	B	Y
0	0	1
0	1	1
1	0	1
1	1	0

NOR

Y = \overline{A + B}

A	B	Y
0	0	1
0	1	0
1	0	0
1	1	0

XOR

Y = A \oplus B

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

XNOR

Y = \overline{A \oplus B}

A	B	Y
0	0	1
0	1	0
1	0	0
1	1	1

Figure 1. IEEE distinctive-shape symbols and 2-input truth tables for the seven canonical gates. NAND, NOR, and XNOR are negations of AND, OR, and XOR — the inversion is shown as a small bubble on the output.

A combinational logic gate is a small Boolean function: pure inputs to pure output, no internal state. AND/OR/NOT form a complete set — every Boolean function can be written in those three.

The other four (NAND, NOR, XOR, XNOR) are convenience gates. NAND and NOR are cheaper in CMOS than AND and OR; XOR and XNOR detect inequality and equality respectively, and show up everywhere in adders and comparators.

IEEE vs IEC symbols

Figure 2. Two standards for the same AND function. IEEE 91-1984 (left) uses distinctive shapes — D-shape for AND, shield for OR, triangle for NOT. IEC 60617-12 (right) uses uniform rectangles with a function label.

Most US schematics and textbooks use IEEE distinctive shapes; European and ISO drawings tend to use IEC rectangles. The truth tables are identical — only the drawing convention differs.

The inversion bubble

Figure 3. The output bubble is a NOT. Adding it to AND gives NAND; to OR gives NOR; to XOR gives XNOR. The bubble can also live on an input pin to mean 'invert this input before the gate'.

A small circle on a pin always means invert. NAND is literally an AND followed by a NOT, drawn compactly as one symbol. The convention saves a gate body and makes DeMorgan rewrites easy to read at a glance.

NAND is universal

Figure 4. Every Boolean function can be built from NAND gates alone. NOT is a NAND with both inputs tied; AND is a NAND followed by a NAND-as-NOT; OR uses three NANDs by inverting both inputs first (DeMorgan).

One transistor pattern, one mask, one gate: that's why standard-cell libraries are built around NAND (and NOR). Designers compile arbitrary logic onto a sea of identical NAND cells before mapping to silicon.

NOR is universal too

Figure 5. The NOR family is the dual: NOT is a NOR with tied inputs; OR is NOR followed by NOR-as-NOT; AND is three NORs (invert each input, then NOR).

NOR-only logic was the foundation of early TTL families and is still common in CMOS standard cells. Either NAND-only or NOR-only is enough — the choice is process- and layout-driven, not theoretical.

Any combinational function can be implemented with NAND gates alone, or with NOR gates alone. AND/OR/NOT span the space; NAND and NOR each span it on their own — that's what makes them functionally complete.