The seven basic gates
A logic gate is a circuit with one or more binary inputs and one binary output, where the output is a fixed function of the inputs. There are only seven gate functions needed as vocabulary before anything else in digital design makes sense: NOT, AND, OR, NAND, NOR, XOR and XNOR. Four of these (NAND, NOR, XOR, XNOR) are built from the other three by adding an inversion or a different kind of combination, so really there are three shapes to learn and one trick – the bubble, which always means "invert this."
XOR is worth one extra sentence: it outputs 1 when its inputs differ, and 0 when they match – "exclusive OR," since unlike plain OR, the case where both inputs are 1 is excluded from the 1 output. XNOR is its exact opposite, outputting 1 when the inputs match. XOR will be seen again almost immediately, as the core of a binary adder's sum bit, and again later as the building block behind equality and parity checks.
| A | B | AND | OR | NAND | NOR | XOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Why NAND and NOR are "universal"
A gate, or a small set of gates, is called functionally complete – or universal – if every possible Boolean function can be built using only copies of it. NAND alone is universal, and so is NOR alone. This matters in practice, not just in theory: standard-cell libraries are built around NAND2 and NOR2 as their smallest, fastest, lowest-transistor-count primitives, and a synthesis tool maps almost everything in a design down to them.
NOT A: tie both NAND inputs to A. NAND(A,A) = (A·A)′ = A′.
A AND B: a NAND followed by a NOT, itself a NAND with both inputs tied together. NAND(NAND(A,B), NAND(A,B)) = ((AB)′)′ = AB.
A OR B: invert both inputs first, then NAND them. This is De Morgan's law expressed in gates, covered in the next section. NAND(A′,B′) = (A′B′)′ = A+B.
Why does NAND win over AND as the "basic" cell in CMOS? An AND gate needs a NAND stage followed by an inverter stage – two stages, more transistors, more delay – while NAND is a single stage on its own. Thus, the AND symbol is how a designer thinks about the function on paper, but the NAND gate is what the silicon actually builds first, with AND assembled on top of it only when the tool genuinely needs an AND.
Boolean algebra: the rules for simplifying an expression by hand
Boolean algebra is the algebra of variables that take only the values 0 and 1, combined with AND (written as multiplication, AB), OR (written as addition, A+B) and NOT (written as a prime, A′). It has its own set of theorems, each provable by checking every input combination in a truth table, but far faster to use once memorized than re-deriving from scratch each time.
| Name | OR form | AND form |
|---|---|---|
| Identity | A + 0 = A | A · 1 = A |
| Null | A + 1 = 1 | A · 0 = 0 |
| Idempotent | A + A = A | A · A = A |
| Complement | A + A′ = 1 | A · A′ = 0 |
| Commutative | A + B = B + A | AB = BA |
| Associative | (A+B)+C = A+(B+C) | (AB)C = A(BC) |
| Distributive | A+BC = (A+B)(A+C) | A(B+C) = AB+AC |
| Absorption | A + AB = A | A(A+B) = A |
| De Morgan's | (A+B)′ = A′B′ | (AB)′ = A′+B′ |
Every row above comes in an OR form and an AND form that mirror each other: swap every AND for an OR, every OR for an AND, every 0 for a 1 and every 1 for a 0, and one form turns into the other. This is the principle of duality, and it is the reason the table only needs to be memorized half as hard as it looks – learn one column, and the other follows for free.
(AB)′ = A′+B′. "NOT (A and B)" is the same statement as "(NOT A) or (NOT B)." Flip every variable, flip AND to OR (or OR to AND), and move the inversion from outside the whole expression to each individual term instead. This is the identity that lets a term built as an OR of inverted signals be replaced by a single NAND, which is exactly how the NAND-only OR gate above was built.
Simplify F = AB + AB′ + A′B.
Group the first two terms and factor: AB + AB′ = A(B+B′) = A·1 = A, applying distributive, then complement, then identity in turn.
So F = A + A′B. Apply absorption in its slightly extended form, A + A′B = A + B – this is easy to check directly: if A=1, both sides equal 1; if A=0, both sides reduce to B.
F = A + B, reduced from three AND terms and two inversions down to a single OR gate.
Boolean functions, truth tables and canonical forms
Any Boolean function can be written directly from its truth table in a completely mechanical way, with no algebra required, using two standard forms.
A minterm is an AND term that includes every variable of the function, each either true or complemented, chosen so the term equals 1 for exactly one row of the truth table. A sum of minterms (SOP, sum-of-products) is built by OR-ing together the minterm for every row where the output is 1. Let us read one off a truth table directly.
| A | B | C | F | Minterm |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | — |
| 0 | 0 | 1 | 1 | A′B′C |
| 0 | 1 | 0 | 0 | — |
| 0 | 1 | 1 | 0 | — |
| 1 | 0 | 0 | 1 | AB′C′ |
| 1 | 0 | 1 | 0 | — |
| 1 | 1 | 0 | 0 | — |
| 1 | 1 | 1 | 1 | ABC |
Reading the minterm rows off gives F = A′B′C + AB′C′ + ABC. This canonical SOP form is guaranteed correct by construction. It is almost never the simplest form – that is exactly the problem the next lesson's Karnaugh maps exist to solve – but it is always a valid starting point, and it is what a truth table, or a hardware description language case statement, implies by default.
The dual construction gives the product of maxterms (POS, product-of-sums): a maxterm is an OR term built from every row where the output is 0, and the full function is the AND of all those maxterm OR-terms. SOP and POS describe the same function; which one ends up the cheaper circuit depends on whether the function has more 1s or more 0s in its truth table.
From Boolean expression to CMOS gate
A standard-cell library's NAND2 and NOR2 cells are built from two kinds of CMOS transistor, connected directly in series or in parallel: a pull-up network of PMOS transistors between the output and the supply, and a pull-down network of NMOS transistors between the output and ground, with the pull-down network wired as the logical dual of the pull-up network. A 2-input NAND needs only two NMOS in series for the pull-down and two PMOS in parallel for the pull-up – four transistors total, typically the smallest gate a standard-cell library ships. The same logical AND function, built directly rather than as NAND-plus-inverter, would need six, on account of the extra inverter stage. This four-versus-six-transistor gap, repeated across billions of gates, is the real physical reason synthesis tools map a design's Boolean logic down to NAND and NOR primitives rather than leaving ANDs and ORs in the netlist.
Key takeaways
- Seven gates, but really three shapes (NOT, and the AND/OR body) plus one rule: a bubble on the output means invert.
- XOR outputs 1 when inputs differ; XNOR outputs 1 when they match. XOR is the heart of a binary adder's sum bit.
- NAND alone, or NOR alone, is functionally complete: every other gate can be built from copies of it.
- Boolean identities come in OR/AND dual pairs; learn one side, and the other follows for free.
- De Morgan's law converts an inverted OR into an AND of inversions, and vice versa; it is the identity behind building any gate from NAND alone.
- Canonical SOP (sum of minterms) and POS (product of maxterms) can always be read directly off a truth table, but are rarely the simplest circuit – that is the next lesson's job.
- NAND and NOR are a standard cell library's cheapest gates by raw transistor count, which is why tools map logic onto them rather than onto AND/OR directly.