4.1 Boolean Operators, Truth Tables & Logic Gates

Theory: Boolean Operators, Truth Tables & Logic Gates

Everything a computer does (adding, comparing, remembering, choosing the next instruction) is ultimately built from circuits that combine two-valued signals: high voltage / low voltage, true / false, $1$ / $0$. Boolean algebra (George Boole, 1854) is the mathematics of such two-valued quantities, and logic gates are the electronic devices that compute it. This page builds the vocabulary: the operators, how to describe them completely with truth tables, the gates that implement them, and why two special gates (NAND and NOR) are enough to build everything (Null & Lobur, Ch. 3).

Boolean Variables and Truth Tables

A Boolean variable can take only the values $0$ (false, low) or $1$ (true, high). A Boolean operator takes one or more Boolean inputs and produces a Boolean output.

Because every input has only two possible values, we can list every input combination and the output for each. This list is a truth table, and it describes an operator (or any Boolean function) completely.

• With $n$ inputs there are $2^n$ rows (each input doubles the number of combinations).
• Rows are conventionally listed in binary counting order: $00, 01, 10, 11$ for two inputs; $000$ to $111$ for three.

Mini-example

A function of 3 variables needs $2^3 = 8$ rows; a function of 4 variables needs $2^4 = 16$ rows. The rows for $x, y, z$ are $000, 001, 010, 011, 100, 101, 110, 111$, i.e. the numbers $0$ to $7$ in binary.

AND, OR and NOT

These are the three basic operators.

Operator	Written	Name in algebra	Output is 1 when…
AND	$xy$ or $x \cdot y$	Boolean product	both inputs are 1
OR	$x + y$	Boolean sum	at least one input is 1
NOT	$x'$ (also $\overline{x}$ or $\neg x$)	complement	the input is 0

The truth tables:

$x$	$y$	$xy$ (AND)	$x+y$ (OR)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

$x$	$x'$ (NOT)
0	1
1	0

Notation: Null & Lobur and many textbooks write the complement as an overbar $\overline{x}$; the lecture uses the prime $x'$, and so does this page. They mean exactly the same thing: $x' = \overline{x}$, and $(xy)' = \overline{xy}$. Some books also use the “elbow” $\neg x$.

Notice that AND really behaves like multiplication ($1 \cdot 1 = 1$, anything times $0$ is $0$) and OR behaves almost like addition, except that $1 + 1 = 1$ (there is no “2” in Boolean algebra).

Mini-example

With $x = 1$, $y = 0$: $\ xy = 1\cdot 0 = 0$, $\ x + y = 1 + 0 = 1$, $\ x' = 0$, $\ y' = 1$, $\ x + y' = 1 + 1 = 1$.

Logic Gates

A gate is an electronic device that computes a Boolean operator: it takes one or more input voltages and produces an output voltage. Physically, a single gate is built from roughly one to six transistors. An integrated circuit (IC), or chip, packages a collection of gates on one piece of silicon.

The standard gate symbols (you must be able to recognise and draw them):

Gate	Symbol shape	Output
AND	“D” shape: flat back, round front	$xy$
OR	curved “shield/arrowhead”: concave back, pointed front	$x + y$
NOT (inverter)	triangle pointing right with a small bubble at the tip	$x'$
XOR	OR shape with an extra curved line across its inputs	$x \oplus y$
NAND	AND shape with a bubble on the output	$(xy)'$
NOR	OR shape with a bubble on the output	$(x+y)'$

The bubble always means “complement here”. An AND gate followed by a bubble is a NAND; an OR followed by a bubble is a NOR. You will also see bubbles on inputs, meaning that input is complemented before entering the gate.

Exclusive OR (XOR)

XOR outputs 1 only when its inputs differ. Its symbol is $\oplus$.

$x$	$y$	$x \oplus y$
0	0	0
0	1	1
1	0	1
1	1	0

Two useful ways to see XOR:

• Modulo-2 sum: $x \oplus y$ is the last bit of $x + y$ in ordinary arithmetic ($1 + 1 = 2 = 10_2$, keep the $0$). This is exactly why XOR is the “sum” output of an adder.
• In terms of AND/OR/NOT: $x \oplus y = xy' + x'y$ (”$x$ but not $y$, or $y$ but not $x$”).

For more than two inputs, $x \oplus y \oplus z \oplus \cdots$ is 1 exactly when an odd number of inputs are 1, which makes XOR the natural parity generator (Lecture 3).

Mini-example

$1 \oplus 1 \oplus 1$: $1 \oplus 1 = 0$, then $0 \oplus 1 = 1$. Three 1s is odd, so the result is $1$ ✓.

NAND and NOR

NAND = NOT-AND, NOR = NOT-OR. Each is simply the complement of the AND/OR column:

$x$	$y$	$(xy)'$ NAND	$(x+y)'$ NOR
0	0	1	1
0	1	1	0
1	0	1	0
1	1	0	0

• NAND is 0 only when all inputs are 1.
• NOR is 1 only when all inputs are 0.

Why Gates Are Naturally Inverting: the CMOS Idea

Modern chips are built in CMOS (Complementary Metal-Oxide-Semiconductor) technology. CMOS uses two kinds of transistor that act as voltage-controlled switches:

Transistor	Conducts (switch closed) when its input is…	Placed between
pMOS	0 (low)	output and +5 V (pulls output up to 1)
nMOS	1 (high)	output and 0 V ground (pulls output down to 0)

• CMOS NOT gate: one pMOS on top, one nMOS below, both driven by $A$. If $A = 0$, the pMOS conducts and connects $Y$ to +5 V, so $Y = 1$. If $A = 1$, the nMOS conducts and connects $Y$ to 0 V, so $Y = 0$. That is $Y = A'$ with just 2 transistors.
• CMOS NOR gate: two pMOS in series from +5 V to $Y$, and two nMOS in parallel from $Y$ to ground. $Y$ is pulled up only if both pMOS conduct, i.e. $A = 0$ and $B = 0$; if either input is 1, the corresponding nMOS pulls $Y$ down. So $Y = (A+B)'$ with 4 transistors.

Because a single transistor stage naturally inverts, NAND and NOR are the cheapest, fastest gates to build. An AND gate is in fact a NAND followed by an inverter (6 transistors).

Mini-example

CMOS NOR with $A = 0, B = 1$: top pMOS ($A = 0$) conducts, second pMOS ($B = 1$) is off, so the series path to +5 V is broken. The nMOS on $B$ conducts and pulls $Y$ to 0 V. $Y = 0 = (0 + 1)'$ ✓.

Universal Gates

NAND and NOR are called universal gates because:

1. Any Boolean function can be built using only NAND gates, or only NOR gates.
2. They are inexpensive to manufacture in large quantities (one gate type, mass production).
3. They are typically faster and use less power than other gate configurations (see the CMOS idea above).

To prove universality it is enough to build NOT, AND and OR, because every Boolean function can be written using those three.

Using only NAND:

Build	Construction	Why it works
NOT $x$	NAND with both inputs tied to $x$	$(x \cdot x)' = x'$
$x$ AND $y$	NAND($x, y$), then a NAND-inverter	$((xy)')' = xy$
$x$ OR $y$	invert $x$ and $y$ with NAND-inverters, then NAND them	$(x' y')' = x'' + y'' = x + y$ (DeMorgan)

Using only NOR:

Build	Construction	Why it works
NOT $x$	NOR with both inputs tied to $x$	$(x + x)' = x'$
$x$ OR $y$	NOR($x, y$), then a NOR-inverter	$((x+y)')' = x + y$
$x$ AND $y$	invert $x$ and $y$ with NOR-inverters, then NOR them	$(x' + y')' = x'' y'' = xy$ (DeMorgan)

Mini-example

NAND-OR check, $x = 0, y = 1$: first stage gives $x' = 1$, $y' = 0$; final NAND gives $(1 \cdot 0)' = 0' = 1 = 0 + 1$ ✓.

Multi-Input Gates and Complemented Outputs

Gates are not limited to two inputs. A 3-input OR outputs $x + y + z$; a 3-input AND outputs $xyz$. AND and OR are associative, so a 3-input AND is the same as two 2-input ANDs chained. Inputs can be complemented on the way in: an AND gate fed $x$, $y'$, $z$ produces $xy'z$.

A gate can also have more than one output: a common component provides both the result $Q$ and its complement $Q'$ (written $\overline{Q}$ in the textbook). We will meet this again on flip-flops.

NAND and NOR are not associative. A “3-input NAND” means $(xyz)'$, which is not the same as chaining two 2-input NANDs: $((xy)' z)'$ is a different function (see Worked Example 6).

Integrated Circuits: SSI Chips

SSI (Small-Scale Integration) chips hold a handful of gates (roughly up to 10). The classic example is the 7400 quad 2-input NAND chip: a 14-pin package in which two pins supply power (+5 V) and ground, and the remaining 12 pins serve 4 NAND gates × 3 pins (two inputs and one output each). A notch on one end marks pin orientation. Larger scales (MSI, LSI, VLSI) pack hundreds up to billions of gates.

Mini-example

A design needs 10 two-input NAND gates. Each 7400 holds 4, so we need $\lceil 10/4 \rceil = 3$ chips, leaving $12 - 10 = 2$ gates unused.

---

Worked Examples

Exercise 1

Let $A = 10110010$ and $B = 01101011$. Apply each operator bit by bit (as a processor’s logic instructions do) and give: $A$ AND $B$, $A$ OR $B$, $A$ XOR $B$, NOT $A$, $A$ NAND $B$, and $A$ NOR $B$.

Show solution ↓Hide solution ↑

Solution

Line the bits up in columns and apply the truth table to each column independently.

	b7	b6	b5	b4	b3	b2	b1	b0
$A$	1	0	1	1	0	0	1	0
$B$	0	1	1	0	1	0	1	1
AND (both 1)	0	0	1	0	0	0	1	0
OR (at least one 1)	1	1	1	1	1	0	1	1
XOR (differ)	1	1	0	1	1	0	0	1
NOT $A$	0	1	0	0	1	1	0	1
NAND (complement of AND)	1	1	0	1	1	1	0	1
NOR (complement of OR)	0	0	0	0	0	1	0	0

So $A \cdot B = 00100010$, $A + B = 11111011$, $A \oplus B = 11011001$, $A' = 01001101$, $(AB)' = 11011101$, $(A+B)' = 00000100$.

Checks:

• NAND must be the bitwise complement of AND: $00100010 \to 11011101$ ✓.
• NOR must be the complement of OR: $11111011 \to 00000100$ ✓.
• XOR = OR minus the columns where both are 1 (columns b5 and b1): $11111011$ with b5, b1 cleared gives $11011001$ ✓.

Exercise 2

Construct the truth table of $F = x \oplus y \oplus z$ (include the intermediate column $x \oplus y$). Describe in words when $F = 1$, and explain how this relates to parity bits.

Show solution ↓Hide solution ↑

Solution

Work column by column: first $x \oplus y$, then XOR that with $z$.

$x$	$y$	$z$	$x \oplus y$	$F = (x \oplus y) \oplus z$	number of 1s in $xyz$
0	0	0	0	0	0
0	0	1	0	1	1
0	1	0	1	1	1
0	1	1	1	0	2
1	0	0	1	1	1
1	0	1	1	0	2
1	1	0	0	0	2
1	1	1	0	1	3

$F = 1$ exactly in the rows with an odd number of 1s (1 or 3). This is the modulo-2 sum of the three bits.

Parity: to give a 3-bit word even parity we append the bit $P = x \oplus y \oplus z$; then the total number of 1s (including $P$) is always even. For example, for $101$: $P = 1 \oplus 0 \oplus 1 = 0$, and $1010$ has two 1s ✓. For odd parity append $P'$ instead.

Exercise 3

Show how to build NOT, AND and OR using only NOR gates. Verify each construction with a truth table showing every intermediate signal.

Show solution ↓Hide solution ↑

Solution

NOT: tie both inputs of one NOR to $x$. Output $(x + x)' = x'$ (Idempotent law $x + x = x$).

$x$	$(x+x)'$
0	1
1	0

Matches NOT ✓.

OR (2 gates): $n_1 = (x + y)'$, then $n_2 = (n_1 + n_1)' = n_1' = x + y$.

$x$	$y$	$n_1 = (x+y)'$	$n_2 = n_1'$
0	0	1	0
0	1	0	1
1	0	0	1
1	1	0	1

$n_2$ column $= 0,1,1,1$ = OR ✓.

AND (3 gates): $a = (x+x)' = x'$, $b = (y+y)' = y'$, then $out = (a + b)' = (x' + y')' = x''y'' = xy$ by DeMorgan and Double Complement.

$x$	$y$	$a = x'$	$b = y'$	$out = (a+b)'$
0	0	1	1	0
0	1	1	0	0
1	0	0	1	0
1	1	0	0	1

$out = 0,0,0,1$ = AND ✓.

Since NOR alone gives NOT, AND and OR, NOR is universal.

Exercise 4

Implement $F = xy + z$ using only 2-input NAND gates. How many gates are needed? Verify for all 8 input combinations.

Show solution ↓Hide solution ↑

Solution

Idea: a sum of products becomes a NAND-NAND circuit. By Double Complement and DeMorgan:

$$F = xy + z = \big((xy + z)'\big)' = \big((xy)' \cdot z'\big)'$$

So:

• Gate 1: $g_1 = \text{NAND}(x, y) = (xy)'$
• Gate 2: $g_2 = \text{NAND}(z, z) = z'$ (inverter)
• Gate 3: $F = \text{NAND}(g_1, g_2) = (g_1 g_2)'$

3 NAND gates in total.

Verification:

$x$	$y$	$z$	$g_1 = (xy)'$	$g_2 = z'$	$F = (g_1 g_2)'$	$xy + z$
0	0	0	1	1	0	0
0	0	1	1	0	1	1
0	1	0	1	1	0	0
0	1	1	1	0	1	1
1	0	0	1	1	0	0
1	0	1	1	0	1	1
1	1	0	0	1	1	1
1	1	1	0	0	1	1

The last two columns agree in every row ✓. All 3 gates fit on one 7400 chip with one gate to spare.

Exercise 5

(a) How many rows does the truth table of a 5-input function have?

(b) How many different Boolean functions of 2 variables exist?

(c) A circuit needs 6 NAND gates and 5 NOR gates, all 2-input. Using 7400 (quad NAND) and 7402 (quad NOR) chips, how many chips are needed and how many gates are left unused?

Show solution ↓Hide solution ↑

Solution

(a) Each input doubles the count: $2^5 = 32$ rows.

(b) A 2-variable truth table has $2^2 = 4$ rows. A function is any choice of output column, and each of the 4 output bits can independently be 0 or 1: $2^4 = 16$ functions. (AND, OR, XOR, NAND, NOR, XNOR, $x$, $y$, $x'$, $y'$, constant 0, constant 1 … are among them.) In general there are $2^{2^n}$ functions of $n$ variables.

(c) Gates of different types cannot share a chip.

• NAND: $\lceil 6/4 \rceil = 2$ chips (8 gates), $8 - 6 = 2$ unused.
• NOR: $\lceil 5/4 \rceil = 2$ chips (8 gates), $8 - 5 = 3$ unused.

Total 4 chips, 5 unused gates. (This is one practical reason to build everything from a single universal gate type: with NAND only, 11 gates would need $\lceil 11/4 \rceil = 3$ chips.)

Exercise 6

Show that NAND is not associative: compare the 3-input NAND $(xyz)'$ with the chained circuit $\text{NAND}(\text{NAND}(x, y), z) = ((xy)'z)'$.

Show solution ↓Hide solution ↑

Solution

Build both columns.

$x$	$y$	$z$	$(xy)'$	$((xy)'z)'$	$(xyz)'$
0	0	0	1	1	1
0	0	1	1	0	1
0	1	0	1	1	1
0	1	1	1	0	1
1	0	0	1	1	1
1	0	1	1	0	1
1	1	0	0	1	1
1	1	1	0	1	0

The two last columns differ in rows $001$, $011$, $101$, so the chained circuit is not a 3-input NAND.

Algebraically: $((xy)'z)' = (xy)'' + z' = xy + z'$ (DeMorgan, Double Complement), while $(xyz)' = x' + y' + z'$. These are different functions.

To make a 3-input NAND from 2-input gates, form $xy$ first with an AND (NAND + inverter), then NAND with $z$: $((xy)z)' = (xyz)'$.

Exercise 7

In the CMOS NOR gate (two pMOS in series from +5 V to $Y$, two nMOS in parallel from $Y$ to ground), list for each input combination $A B$ which transistors conduct and the resulting output $Y$.

Show solution ↓Hide solution ↑

Solution

Rule: a pMOS conducts when its input is 0; an nMOS conducts when its input is 1. $Y = 1$ if there is a complete path to +5 V; $Y = 0$ if there is a path to ground.

$A$	$B$	pMOS($A$)	pMOS($B$)	series path to +5 V?	nMOS($A$)	nMOS($B$)	path to ground?	$Y$
0	0	on	on	yes	off	off	no	1
0	1	on	off	no	off	on	yes	0
1	0	off	on	no	on	off	yes	0
1	1	off	off	no	on	on	yes	0

The output column $1, 0, 0, 0$ is the NOR truth table ✓. Note that in every row exactly one of the two networks conducts, so the output is never connected to both supplies at once (this is what “complementary” means, and why CMOS draws almost no static power).