Exercises — Boolean variables and operations (AND, OR, NOT)

WHAT: apply NOT = "flip". WHY: NOT is the one-input operation that outputs the opposite.

• (a) $\overline{0}=1-0=1$.
• (b) $\overline{1}=1-1=0$. Both answers sit on a dot at 0 or 1 — good.

• $1\cdot 0=0$ — AND needs all inputs 1; one zero kills it.
• $1+0=1$ — OR needs at least one 1.
• $1+1=1$ — OR saturates; it does not become 2.
• $0\cdot 0=0$ — no 1s at all, so AND is 0.

WHY the formula $2^n$: each input independently doubles the count of combinations.

• 3 inputs: $2^3=8$ rows.
• 4 inputs: $2^4=16$ rows.

Step 1 (WHAT): NOT first — $\overline{A}=\overline{1}=0$. WHY: NOT binds tightest. Step 2: OR — $0+0=0$. WHY: neither operand is 1, so OR is 0. Answer: 0.

Step 1: NOT — $\overline{C}=\overline{1}=0$. Step 2: AND — $A\cdot B=1\cdot 1=1$ (both operands 1). WHY before OR: AND has higher precedence. Step 3: OR — $1+0=1$. Answer: 1.

WHY inside-out: the bar is a grouping symbol, so we finish everything under it first. Step 1: $A\cdot B=1\cdot 0=0$. Step 2: NOT the result — $\overline{0}=1$. Answer: 1. (This is exactly what a NAND gate does — see NAND and NOR gates.)

WHY 4 rows: 2 inputs $\Rightarrow 2^2=4$ combinations.

In words: $F$ is 0 only in the single row $A=0,B=1$. So $F$ means "A is true, OR B is false" — equivalently "it is NOT the case that (A is 0 and B is 1)".

WHY 8 rows: 3 inputs $\Rightarrow 2^3=8$.

Notice: $G=1$ exactly when $A=1$ and at least one of $B,C$ is 1. That is $A\cdot (B+C)$ — a preview of the distributive law in Boolean Algebra Laws.

WHAT: tabulate both and compare column by column.

Verdict: NOT equal — rows 2 and 3 differ ($P=0$ but $Q=1$). The correct partner of $P$ is $\overline{A}\cdot \overline{B}$ (De Morgan). Check: row 2 gives $1\cdot 0=0=P$ ✓. See De Morgan's Laws.

WHAT the words map to: "key AND pin" $\to K\cdot P$; "OR override" $\to +M$. $\text{Unlock}=K\cdot P+M.$ WHY this shape: the two conditions are alternatives (OR), and inside the first, both parts are required (AND).

Sanity check: every row with $M=1$ unlocks (override works). Among $M=0$ rows, only $K=P=1$ unlocks. Matches the story.

WHY this construction: "exactly one" splits into two mutually exclusive stories: (i) $A=1$ and $B=0$ $\to A\cdot \overline{B}$; (ii) $A=0$ and $B=1$ $\to \overline{A}\cdot B$. Either story is acceptable, so join them with OR: $\text{XOR}=A\cdot \overline{B}+\overline{A}\cdot B.$

Answer confirmed: 1 exactly when the inputs differ. This is proof the three basic operations are functionally complete — even XOR is just shorthand for them.

WHAT: list all $2^3=8$ votes, mark rows with $\ge 2$ ones.

WHY the expression: write one AND-term for each "at least this pair agrees": $\text{Pass}=A\cdot B+A\cdot C+B\cdot C.$ Each term is 1 when a specific pair both vote yes; the OR fires if any pair agrees — which is exactly "2 or 3 yes votes". Verify: row $A=1,B=1,C=0$ gives $1+0+0=1$ ✓; the all-yes row gives $1+1+1=1$ ✓ (OR saturates).

Idea: feed the same signal into both inputs. WHY: with $B=A$, the product $A\cdot A$ is just $A$ (a variable ANDed with itself is unchanged — check: $0\cdot 0=0$, $1\cdot 1=1$). $A\uparrow A=\overline{A\cdot A}=\overline{A}.$ Table:

The output column is $\overline{A}$ exactly — so NAND alone gives NOT, and from NOT + NAND you can rebuild AND and OR too. This is the deep reason chips are mass-produced from NAND gates; more in NAND and NOR gates.

How many rows for $n$ inputs? ::: $2^n$ $\overline{A+B}$ simplifies to? ::: $\overline{A}\cdot \overline{B}$ (De Morgan) XOR in terms of AND/OR/NOT? ::: $A\cdot \overline{B}+\overline{A}\cdot B$ Majority-of-3 expression? ::: $A\cdot B+A\cdot C+B\cdot C$ How does NAND make NOT? ::: $A\uparrow A=\overline{A}$ Absorption law? ::: $A+A\cdot B=A$