Theory
The lift that refuses to move
A lift moves (output 1) only under this rule: the door is closed (A) AND someone pressed a floor button (B).
Door open, button pressed? Stays. Door closed, no button? Stays. Door closed and button pressed? Moves.
That rule, inputs in, one 0/1 decision out, is a Boolean function, and every digital device is a bundle of thousands of them.
Theory
A decision box
Picture a sealed box with n input wires and exactly one output wire, each carrying 0 or 1. Feed any input pattern and the box answers 0 or 1, the same answer for the same pattern every time. The box's complete personality is just its answer list, and that list is finite: 2ⁿ rows.
Theory
The definition
A Boolean function of n variables maps every combination in {0,1}ⁿ to a single value in {0,1}.
Two inputs → 2² = 4 combinations. Three inputs → 2³ = 8. Each combination gets exactly one output, so the whole function fits in a table with 2ⁿ rows.
The lift: f(A, B) = A·B. Four rows, output 1 in exactly one of them.
Theory
Expression → truth table
Take f(A, B) = A·B + ¬A·B. Build columns step by step:
A B A·B ¬A·B f
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
1 1 1 0 1
Intermediate columns first, final OR last. (Spot it? f is 1 exactly when B is 1, so this whole expression simplifies to just B. Simplification is the next topic.)
Quiz
A Boolean function has 4 input variables. How many rows does its complete truth table need?
- 4
- 8
- 16
- It depends on the expression
Show the answer
16
Each of the 4 variables independently takes 0 or 1, so combinations multiply: 2⁴ = 16. Doubling per variable is the pattern (2, 4, 8, 16...). The expression's complexity changes the intermediate columns, never the row count; only the number of variables does.
Theory
Truth table → expression (sum of products)
Going backwards is a recipe:
1. Find every row where the output is 1
2. For each such row, AND all variables: plain if the variable is 1 in that row, complemented if 0
3. OR those terms together
Example: output is 1 only in rows (A=0, B=1) and (A=1, B=1) → f = ¬A·B + A·B. This sum-of-products form reproduces the table exactly.
Think first
A function of A and B outputs 1 in exactly one row: A = 1, B = 0.
Build its sum-of-products expression in your head, then tap.
Show the answer
f = A·¬B
One output-1 row means one term. A is 1 in that row so it stays plain; B is 0 so it appears complemented. Read the term back to check: A·¬B is 1 exactly when A = 1 and B = 0. The row IS the term, that is the whole trick.
Theory
The named functions worth recognising
Some two-variable functions are so useful they have names: AND, OR, NAND (NOT of AND), NOR (NOT of OR), XOR (1 when inputs differ), XNOR (1 when inputs match).
With three variables, the majority function outputs 1 when at least two inputs are 1: f = A·B + B·C + A·C. Real chips vote with it.
Quiz
XOR of A and B outputs 1 exactly when the inputs differ. What is its sum-of-products expression?
- A·B + ¬A·¬B
- ¬A·B + A·¬B
- A + B
- A·B
Show the answer
¬A·B + A·¬B
"Inputs differ" happens in two rows: (0,1) giving term ¬A·B, and (1,0) giving A·¬B; OR them. Option A is XNOR, the rows where inputs MATCH, the classic reversal. A + B fails because it is also 1 when both are 1, where XOR is 0.
Watch out
Where sum-of-products goes wrong
Three slips to police: writing a term for output-0 rows (only 1-rows get terms), forgetting to complement the variables that are 0 in the row, and missing rows entirely because the combinations were not listed systematically (00, 01, 10, 11 in order, every time).
Theory
Where you will meet this again
Every processor instruction is Boolean functions etched in silicon, and XOR alone powers parity checks, RAID storage and simple encryption. The very next topics take today's sum-of-products output and shrink it: representation and minimization, where fewer terms mean cheaper circuits.
Summary
Key takeaways
- A Boolean function maps each of the 2ⁿ input combinations to one 0/1 output.
- Expression to table: evaluate row by row with intermediate columns.
- Table to expression: one AND term per output-1 row (plain for 1, complemented for 0), OR the terms: sum of products.
- Know the named functions: AND, OR, NAND, NOR, XOR (differ), XNOR (match), majority.
- Memory hook: the row IS the term.