Truth tables — all 16 binary operations

WHAT is a truth table?

HOW we name them: Read the output column top-to-bottom for rows $00,01,10,11$ as a 4-bit binary number. E.g. AND outputs $0,0,0,1 \to 0001_2 = 1$ , so AND is "function #1".

WHY there are $2^{2^n}$ operations (derivation from scratch)

Formula Counting logic functions

Step 1 — Why $2^n$ rows? Each of the $n$ inputs is independently $0$ or $1$ . By the multiplication principle, the number of input combinations is $\underbrace{2 \times 2 \times \cdots \times 2}_{n} = 2^n.$ Why this step? Each input doubles the number of cases.

Step 2 — Why $2^{(2^n)}$ functions? The output column has $2^n$ rows. Each row's output is an independent choice of $0$ or $1$ . So the number of distinct output columns is $\underbrace{2 \times 2 \times \cdots \times 2}_{2^n \text{ slots}} = 2^{(2^n)}.$ Why this step? A "function" IS its output column — two functions are the same iff they agree on all rows.

For $n=2$ : $2^{(2^2)} = 2^4 = ==16==$ .

The complete table of all 16 operations

Inputs ordered $AB = 00, 01, 10, 11$ . The 4 output bits (top→bottom) form the index.

#	Name	00	01	10	11	Expression
0	FALSE (contradiction)	0	0	0	0	$0$
1	AND	0	0	0	1	$A\cdot B$
2	A AND NOT B (inhibit)	0	0	1	0	$A\bar B$
3	A (left projection)	0	0	1	1	$A$
4	NOT A AND B	0	1	0	0	$\bar A B$
5	B (right projection)	0	1	0	1	$B$
6	XOR	0	1	1	0	$A\oplus B$
7	OR	0	1	1	1	$A+B$
8	NOR	1	0	0	0	$\overline{A+B}$
9	XNOR (equivalence)	1	0	0	1	$\overline{A\oplus B}$
10	NOT B	1	0	1	0	$\bar B$
11	B → A (if B then A)	1	0	1	1	$A + \bar B$
12	NOT A	1	1	0	0	$\bar A$
13	A → B (implication)	1	1	0	1	$\bar A + B$
14	NAND	1	1	1	0	$\overline{A\cdot B}$
15	TRUE (tautology)	1	1	1	1	$1$

Figure — Truth tables — all 16 binary operations

WHY NAND alone rules them all (functional completeness)

Worked examples

Worked example Example 2 — Verify implication

$A \to B = \bar A + B$ Implication is false ONLY when premise true but conclusion false ( $A=1,B=0$ ).

$A$	$B$	$\bar A$	$\bar A + B$
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1
Output $1,1,0,1$ → function #13. Why this matches? Only row $A=1,B=0$ gives 0, exactly as required. ✓

Common mistakes

Flashcards

How many distinct 2-input binary logic operations exist, and why?

2^{(2^2)} = 16

; the 4-row output column has

2^4

possible fillings.

General formula for the number of

n

-input Boolean functions?

2^{(2^n)}

Which row distinguishes XOR from OR?

The

11

row: OR

=1

, XOR

=0

Output column of AND for rows 00,01,10,11?

0,0,0,1

(function #1).

How do you make NOT from a single NAND gate?

\text{NAND}(A,A)=\bar A

How do you make OR from NAND (using De Morgan)?

A+B=\text{NAND}(\bar A,\bar B)

What makes a gate "functionally complete"?

You can build every Boolean function using only that gate (e.g. NAND, NOR).

Which function is output column

1,0,0,1

XNOR / equivalence (#9), true when

A=B

Relationship between function #

k

and #

(15-k)

They are complements (all output bits flipped).

Truth table of implication

A\to B

— when is it 0?

Only when

A=1,B=0

Recall Feynman: explain to a 12-year-old

Imagine two light switches, $A$ and $B$ , and one bulb. The bulb is either ON or OFF. There are only 4 ways to set the two switches: both off, one off one on (two ways), both on. For each of those 4 settings you decide ON or OFF for the bulb. Since each of the 4 settings is its own yes/no choice, there are $2\times2\times2\times2 = 16$ possible "rule books" for the bulb. Each rule book has a name like AND ("on only when both switches are on") or OR ("on when at least one is on"). That's all 16 logic operations — there can never be a 17th.

Connections

Boolean algebra — the symbolic rules ( $A+B$ , $A\cdot B$ , $\bar A$ ) behind these tables
Logic gates — physical components implementing each function
De Morgan's laws — why $\overline{A+B}=\bar A\bar B$ , key to NAND/NOR universality
Binary numbers — why $00,01,10,11$ and the $2^n$ counting
Functional completeness — NAND/NOR as universal gates
Adders and the ALU — XOR + AND combine to do binary addition

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab humare paas sirf do input bits hote hain ( $A$ aur $B$ ), to har bit ya to $0$ hoga ya $1$ . Iska matlab total input combinations sirf $4$ hain: $00, 01, 10, 11$ . Ab ek logic operation ka kaam hai har combination ke liye ek output bit dena. To output column mein bhi sirf $4$ slots hain. Har slot mein $0$ ya $1$ — yani $2^4 = 16$ tareeke. Isliye duniya mein two-input ke total operations sirf 16 hain, na ek zyada na ek kam. Yeh hai poora universe of logic gates!

In 16 mein se sabse famous hain: AND (dono on hone par 1), OR (kam se kam ek on hone par 1), XOR (sirf ek on hone par 1), aur unke ulte versions NAND, NOR, XNOR. Ek mast trick yeh hai ki function $\#k$ aur $\#(15-k)$ ek dusre ke opposite hote hain — saare output bits flip ho jaate hain. Isiliye AND (#1) ka ulta NAND (#14) hai.

Sabse important practical baat: NAND akela hi sab kuch bana sakta hai. $\text{NAND}(A,A)$ se NOT milta hai, fir double-NAND se AND, aur De Morgan se OR. Isiliye real chips mein engineers bohot saare NAND gates lagaate hain — ek hi cheap gate se poora computer ban jaata hai! Yeh "functional completeness" ka jaadu hai, aur yahi reason hai ki yeh chhota sa concept itna powerful hai.

Test yourself — How Computers Work

Connections