Truth tables construction

What is a truth table? (WHAT)

WHY $2^n$ ? Each input can independently take 2 values (0 or 1). With $n$ independent inputs, by the multiplication principle the number of combinations is

\underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times}} = 2^n .

Formula Number of rows — derived, not memorised

Let $R(n)$ = number of input rows for $n$ inputs.

Base case: 1 input → values $\{0,1\}$ , so $R(1)=2$ .
Adding one input doubles the rows: every old combination appears once with the new input $=0$ and once with it $=1$ . So $R(n)=2\,R(n-1)$ .
Solving this recurrence: $R(n)=2\cdot 2\cdots 2 = ==2^{n}==$ .

inputs $n$	rows $2^n$
1	2
2	4
3	8
4	16

HOW to construct one — the recipe

Step-by-step method:

Count the inputs → decide the number of rows $= 2^n$ .
Make the input columns. A reliable pattern (standard convention): the rightmost column alternates $0,1,0,1,\dots$ ; the next column alternates in pairs $0,0,1,1$ ; the next in fours $0,0,0,0,1,1,1,1$ ; etc. Column from left = MSB.
Break the expression into intermediate columns (one per gate/sub-expression). This is the divide-and-conquer trick.
Evaluate row by row, filling intermediates first, then the final output.
Sanity-check the row count and a couple of extreme rows (all-0s, all-1s).

Worked example 1 — $F = A \cdot B$ (AND), 2 inputs

WHY start here: 2 inputs → $2^2 = 4$ rows. AND outputs 1 only when both are 1.

$A$	$B$	$F=A\cdot B$
0	0	0
0	1	0
1	0	0
1	1	1

Why this step (rows): $2^2=4$ , so exactly 4 rows — no more, no fewer.
Why the pattern: right column $0,1,0,1$ ; left column $0,0,1,1$ → all 4 combos appear once.
Why the outputs: AND = "all true", so only the last row (both 1) gives 1.

Worked example 2 — $F = \overline{A} + B$ , 2 inputs

We introduce an intermediate column $\overline{A}$ (NOT A), then OR it with $B$ .

$A$	$B$	$\overline{A}$	$F=\overline{A}+B$
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

Why the $\overline{A}$ column: we compute the inside of the expression first so the final OR is trivial (Feynman: solve the small piece, then combine).
Why row 3 = 0: $A=1 \Rightarrow \overline A =0$ , and $B=0$ , so $0+0=0$ . Every other row has at least one 1, so OR gives 1.
Insight: this table is identical to the material implication $A \Rightarrow B$ . Same table ⇒ logically the same function.

Worked example 3 — 3 inputs: $F = A\cdot B + \overline{C}$

WHY: 3 inputs → $2^3 = 8$ rows. We use two intermediate columns: $A\cdot B$ and $\overline C$ .

$A$	$B$	$C$	$A\cdot B$	$\overline C$	$F=A\cdot B+\overline C$
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

Why the column ordering: $C$ (rightmost) toggles every row $0,1,0,1\dots$ ; $B$ toggles every 2; $A$ every 4. Guarantees all 8 combos.
Why the last row = 1: $A\cdot B = 1$ , so OR is 1 regardless of $\overline C=0$ .
Why row 2 = 0: $A\cdot B=0$ and $\overline C = 0$ (since $C=1$ ) → $0+0=0$ .
80/20 takeaway: once you can build the intermediate columns, any expression becomes mechanical.

Common mistakes (Steel-man + fix)

Active recall

Recall Cover the answers and test yourself

How many rows for $n$ inputs? → $2^n$ .
Why $2^n$ and not $2n$ ? → independent inputs multiply choices.
What guarantees you list every combination once? → counting in binary $0\to 2^n-1$ .
What is the safest way to evaluate a complex expression? → build intermediate columns, NOT→AND→OR.
Two circuits have the same truth table — what does that mean? → they are logically equivalent.

Recall Feynman: explain to a 12-year-old

Imagine a light that turns on depending on some switches. A truth table is just a list of every way you could flip the switches, and for each way it tells you: is the light ON or OFF? To make sure you don't forget any switch-pattern, you count "0,1,2,3…" but in the robot's counting system (binary), where digits are only 0 and 1. Each count = one row. Then you check the rule for each row and write ON (1) or OFF (0). That's the whole magic — no guessing, everything is listed.

Connections

Logic Gates AND OR NOT — each gate defines one small truth table you combine.
Boolean Algebra Laws — proven by showing two expressions share a truth table.
Sum of Products (SOP) — read directly off the rows where output = 1.
Karnaugh Maps — a truth table re-drawn as a grid for simplification.
Binary Number System — the counting that generates the input rows.
Combinational Logic Circuits — the physical thing a truth table describes.

How many rows does a truth table with

n

inputs have?

2^n

Why is it

2^n

and not

2n

Each input is independent with 2 possible values, so choices multiply:

2\times2\times\cdots=2^n

What is the reliable method to list all input combinations exactly once?

Count in binary from

0

2^n-1

, padding each number to

n

bits.

In the standard column pattern, how does the rightmost input column vary?

It alternates

0,1,0,1,\dots

every single row.

What is the correct operator precedence when evaluating?

NOT first, then AND, then OR.

Why use intermediate columns when constructing a table?

They break the expression into small pieces, respect precedence, and reduce evaluation errors.

Two different circuits produce the same truth table — what can you conclude?

They are logically equivalent (perform the same function).

Give the output column of

F=A\cdot B

for inputs (00,01,10,11).

0,0,0,1

Give the output column of XOR

A\oplus B

for (00,01,10,11).

0,1,1,0 (1 when inputs differ).

How many rows for a 4-input function?

2^4 = 16

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, ek truth table basically ek poori list hai har possible input combination ki, aur har combination ke liye output kya hoga — 0 ya 1. Agar circuit me $n$ inputs hain, to total rows $2^n$ hote hain, kyunki har input independently 2 values (0 ya 1) le sakta hai, to choices multiply hoti hain: $2\times2\times\dots = 2^n$ . Yaad rakhna — $2n$ nahi, $2^n$ ! Ye sabse common galti hai.

Banane ka easy tarika: binary me count karo 0 se lekar $2^n-1$ tak. Har number ek row ban jaata hai, aur is se guarantee hota hai ki koi combination na chhoote na repeat ho. Convention: sabse right wala column $0,1,0,1$ toggle karta hai har row, uske left wala $0,0,1,1$ (pairs me), phir $0,0,0,0,1,1,1,1$ (fours me). Ye pattern hamesha kaam karta hai.

Jab expression bada ho (jaise $A\cdot B + \overline{C}$ ), to seedhe mat solve karo — intermediate columns banao. Pehle $A\cdot B$ ka column, phir $\overline{C}$ ka column, phir dono ko OR karke final $F$ . Precedence yaad rakho: pehle NOT, phir AND, phir OR (bilkul jaise maths me pehle multiply phir add). Isse mistakes kam ho jaati hain.

Ye topic kyun important hai? Kyunki agar do circuits ka truth table same hai, to wo logically equivalent hain — chahe dikhne me alag hon. Isi liye Boolean laws prove karne, K-map banane, aur SOP nikaalne me truth table hi foundation hai. Ek baar table bana lo, baaki sab mechanical ho jaata hai — that's the 80/20 power move!

What is a truth table? (WHAT)

HOW to construct one — the recipe

Worked example 1 — $F = A \cdot B$ (AND), 2 inputs

Worked example 2 — $F = \overline{A} + B$ , 2 inputs

Worked example 3 — 3 inputs: $F = A\cdot B + \overline{C}$

Common mistakes (Steel-man + fix)

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Boolean Algebra & Logic Gates

Connections