Exercises — Truth tables construction

The number of rows is $2^n$ because each input independently chooses between $2$ values, so the choices multiply. $2^5=2\cdot 2\cdot 2\cdot 2\cdot 2=32.$ Answer: 32 rows.

OR is $1$ whenever at least one input is $1$. The only way to get $0$ is if no input is $1$. That is the row $A=0,B=0$.

Answer: the single row $A=0,B=0$.

Convention: rightmost column ($C$) toggles every 1 row ($0,1,0,1,\dots$); the middle column ($B$) toggles every 2 rows; the leftmost ($A$) every 4. So $B$ is: $0,0,1,1,0,0,1,1.$ Answer: $0,0,1,1,0,0,1,1$.

First compute the inside piece $\overline{A}$, then AND it with $B$ (Feynman: small piece first, then combine).

Only row 2 gives $1$: there $\overline{A}=1$ and $B=1$, so AND is $1$. Everywhere else at least one factor is $0$. Answer output column (top→bottom): $0,1,0,0$.

Intermediate column $\overline{B}$ first, then OR with $A$.

Only row 2 is $0$: there $A=0$ and $\overline{B}=0$ (since $B=1$), so $0+0=0$. Answer output column: $1,0,1,1$.

XOR outputs $1$ exactly when the two inputs are not equal.

Answer output column: $0,1,1,0$.

Columns: $C$ toggles every row, $B$ every 2, $A$ every 4. Intermediates: $A\cdot B$ and $\overline{C}$, then OR them.

Count the $1$s: rows 1,3,5,7,8 → 5 rows where $F=1$. Answer: $F=1$ on 5 of the 8 rows.

Implication $A\Rightarrow B$ is defined as "false only when $A$ true but $B$ false". Compare:

Both columns read $1,1,0,1$ — identical. Same table ⇒ logically equivalent. Answer: yes, they are the same function ($1,1,0,1$).

Build both sides column by column.

Left side $\overline{A\cdot B}=1,1,1,0$. Right side $\overline{A}+\overline{B}=1,1,1,0$. Identical ⇒ the law holds. See Boolean Algebra Laws. Answer: both sides $=1,1,1,0$; the law is verified.

Count how many of $A,B,C$ are $1$ in each row; output $1$ if that count is odd ($1$ or $3$).

This is exactly $A\oplus B\oplus C$ (three-input XOR / parity). Answer output column: $0,1,1,0,1,0,0,1$.

Equal means both $0$ or both $1$.

Output column $1,0,0,1$ is the exact opposite of XOR ($0,1,1,0$), so $F=\overline{A\oplus B}$ (called XNOR). Reading the two $1$-rows off the table as a Sum of Products: $F=\overline{A}\overline{B}+AB$. Answer: output $1,0,0,1$; $F=\overline{A}\overline{B}+AB=\overline{A\oplus B}$.

Intermediates $A+B$ and $\overline{C}$, then AND them.

$F=1$ needs $(A+B)=1$ and $C=0$. That happens on rows 3,5,7 → 3 rows. Answer: $F=1$ on 3 rows; output column $0,0,1,0,1,0,1,0$.

Read $ABCD$ as a number $=8A+4B+2C+D$. Mark $F=1$ where that number is $0,3,6,9,12,15$ (the multiples of 3 from 0 to 15).

Count of $1$s: values $0,3,6,9,12,15$ → 6 rows. Answer: $F=1$ on 6 rows (values $0,3,6,9,12,15$).

Build both sides fully.

LHS column $=0,0,0,0,0,1,1,1$. RHS column $=0,0,0,0,0,1,1,1$. Identical on all 8 rows ⇒ the law holds. See Boolean Algebra Laws. Answer: both sides $=0,0,0,0,0,1,1,1$; distributive law verified.

Output $1$ where the number of $1$s is $\ge 2$.

The four $1$-rows are $011,101,110,111$. As SOP and after grouping: $F=\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC=AB+BC+AC.$ Answer: $F=1$ on 4 rows; $F=AB+BC+AC$.

• L1: rows $=2^n$; recognise gate outputs.
• L2: build small tables with one intermediate column.
• L3: multi-gate tables, verify equivalences and laws.
• L4: design a table from a word-spec (parity, equality, gated OR).
• L5: 4-input specs, prove laws, read SOP from a voter.