Truth tables construction: Question bank — Hardware deep dive

Before you start, recall the three load-bearing ideas: rows $=== 2^{n} ==$ because inputs are independent; you list combinations by counting in binary so nothing is skipped or repeated; and you evaluate with precedence NOT → AND → OR using intermediate columns.

True or false — justify

Every line below is a full claim. Decide true/false and say why before revealing.

A truth table for

4

inputs has

8

rows.

False. Rows are

2^{n}

, so

2^{4} = 16

; the trap is doing

2 \times 4 = 8

, but independent inputs multiply choices, they do not add.

If two Boolean expressions have the same truth table, they are logically equivalent.

True. The table is the complete promise of behaviour; matching every row means matching every possible input, so the functions are identical however differently they are written — this is how Boolean Algebra Laws are proven.

Changing the order of the rows changes what function the table represents.

False. The function is the set of (input → output) pairs; a different row order is the same set, hence the same function. Order only matters as a discipline so you don't skip or duplicate a case.

3

-input table and a

2

-input table can never describe the same function.

True in the strict sense — they have different input sets. But a

3

-input function can ignore one input (its output never depends on it), making it behave like a

2

-input function on the inputs that matter.

The rightmost input column always alternates

0, 1, 0, 1, \dots

every single row.

True in the standard convention. It is the least significant bit of the binary count, and the last bit flips on every increment.

The expression

A + B \cdot C

is evaluated as

(A + B) \cdot C

False. AND (

\cdot

) binds tighter than OR (

+

), exactly like

\times

before

+

in arithmetic, so it means

A + (B \cdot C)

An all-

0

input row can still produce output

1

True. If the expression contains a NOT (e.g.

\overline{A}

) or a constant

1

, the output for all-zero inputs can be

1

; the output depends on the rule, not on the inputs being zero.

Two circuits that use different gates must have different truth tables.

False. Different physical constructions can implement the same function — e.g.

\overline{A} + B

and

A \Rightarrow B

have the same table despite looking unrelated.

If a function's output column is all

1

s, the function is the constant

1

(a tautology).

True. Every input combination maps to

1

, so the output never depends on the inputs — it is the constant "always true" function.

Adding one more input to a circuit adds one more row to its table.

False. Each new input doubles the rows (every old combination reappears with the new input

= 0

and

= 1

), so

R (n) = 2 R (n - 1)

, giving

2^{n}

, not

R (n - 1) + 1

Spot the error

Each statement contains a flaw. Name the flaw and correct it.

"For

F = A \cdot B + \overline{C}

with

A = 1, B = 1, C = 1

, the output is

0

because

\overline{C} = 0

Error: it ignored the AND term.

A \cdot B = 1

, and OR is

1

if either side is

1

, so

F = 1 + 0 = 1

. Never let one

0

decide an OR.

"I'll write the input rows in whatever order I like; as long as all combinations appear, the table is correct."

The claim about values is fine, but the practice is dangerous: without the binary-counting checksum you are very likely to skip or duplicate a combination. Count in binary

0 \to 2^{n} - 1

to guarantee completeness.

F = \overline{A \cdot B}

is the same as

\overline{A} \cdot \overline{B}

, so I can NOT each variable separately."

Error: NOT does not distribute over AND like that. By De Morgan's law

\overline{A \cdot B} = \overline{A} + \overline{B}

(the AND flips to OR). Build both tables and they differ — a classic trap.

2

-input XOR is

1

when at least one input is

1

That describes OR, not XOR. XOR outputs

1

when the inputs differ (exactly one is

1

); for both-

1

it gives

0

, so its column is

0, 1, 1, 0

"To evaluate

A + B \cdot \overline{C}

I do the NOT last since it's written last."

Error: position in writing does not set precedence. NOT is evaluated first, then AND, then OR — so compute

\overline{C}

, then

B \cdot \overline{C}

, then the final OR.

"Since AND outputs

1

only in one row, OR must output

1

in only one row too."

False parallel. For

2

inputs, AND is

1

1

row (both

1

), but OR is

1

3

rows (any input

1

); they are opposite in how "generous" they are.

Why questions

Answer with a reason, not a definition.

Why is the number of rows

2^{n}

rather than

n^{2}

2 n

Because the

n

inputs are independent and each has

2

choices, the multiplication principle gives

2 \times 2 \times \dots = 2^{n}

; neither adding nor squaring reflects "independent choices multiply".

Why do we build intermediate columns instead of evaluating the whole expression at once?

Splitting into small sub-expressions forces correct precedence and turns a mistake-prone mental leap into a mechanical fill-in, dramatically cutting evaluation errors — see Logic Gates AND OR NOT where each gate is one small column.

Why is counting in binary the "safe" way to list input combinations?

The binary numbers

0

2^{n} - 1

are all distinct and cover every value in that range exactly once, so padding each to

n

bits produces every combination with no gaps and no repeats — a built-in checksum. This is exactly the Binary Number System doing the bookkeeping.

Why can a truth table serve as the "ground truth" for simplification?

Because the table captures behaviour completely and uniquely; any simplified expression is only valid if it reproduces the same table, so the table is the reference every Boolean Algebra Laws step must respect.

Why does NOT get evaluated before AND and OR?

NOT acts on a single value to produce the operand that AND/OR then combine; you must know each variable's actual value (possibly inverted) before combining, so inversion has to come first — mirroring how unary minus resolves before

\times

and

+

Why does the rows-double argument prove

R (n) = 2^{n}

so cleanly?

Starting from

R (1) = 2

and

R (n) = 2 R (n - 1)

, each step multiplies by

2

; applying it

n - 1

times from the base gives

2 \cdot 2 \dots 2 = 2^{n}

, a clean geometric growth rather than a guess.

Why can the rows where output

= 1

be read directly as a Sum of Products?

Each

1

-row corresponds to one exact input combination, written as an ANDed product; ORing all such products gives an expression that is

1

on precisely those rows and nowhere else — the basis of Sum of Products (SOP).

Edge cases

Boundary and degenerate scenarios the topic quietly assumes you've considered.

How many rows does a truth table with

0

inputs (a constant) have?

2^{0} = 1

row. A constant function still has one "empty" input combination with a fixed output — the formula holds even at the smallest case.

What does the truth table of the constant function

F = 1

look like?

Every row's output is

1

regardless of inputs; the output column is all

1

s because the expression never references any input.

If an expression contains a variable that never affects the output (e.g.

F = A + \overline{A} = 1

), what happens in the table?

The output column is identical for that variable's

0

and

1

values in every otherwise-matching row, so the variable is redundant — the function ignores it entirely.

For a

1

-input NOT gate, what are the two rows and outputs?

With

2^{1} = 2

rows: input

0 \to

output

1

, and input

1 \to

output

0

; NOT simply flips the single input.

If two adjacent rows differ in output despite differing in only one input bit, what does that tell you?

That single input bit does affect the output — a signal used by Karnaugh Maps, where such adjacent differing cells mark where the function is "sensitive" and cannot be merged.

What is the largest input combination (as a binary count) in an

n

-input table, and why?

It is

2^{n} - 1

(all

1

s), because counting starts at

0

; you list

0, 1, \dots, 2^{n} - 1

, so the final row is the all-ones combination.

If you accidentally write

2^{n} + 1

rows, what must have gone wrong?

You duplicated at least one input combination, since the exhaustive list has exactly

2^{n}

distinct combinations — any extra row is a repeat, caught by re-counting in binary.

Connections

Logic Gates AND OR NOT — each gate is one atomic truth table you combine.
Boolean Algebra Laws — every law is a claim that two tables match.
Sum of Products (SOP) — read straight off the output- $1$ rows.
Karnaugh Maps — the same table redrawn to expose adjacent-row structure.
Binary Number System — the counting that guarantees complete input rows.
Combinational Logic Circuits — the hardware a truth table describes.