Week 3: Boolean Logic

From numbers to the operations that transform them. AND, OR, NOT, XOR, NAND, and NOR are the six basic operations. They are also enough to build every circuit that has ever existed in a digital computer.

Theme

George Boole (1815-1864) described an algebra where variables have exactly two values: true and false. Claude Shannon (1916-2001) proved in his 1937 MIT master's thesis that Boole's algebra maps directly to electrical circuits: you can build a circuit that computes AND, OR, and NOT using switches and wires. Every digital computer you have ever used is a physical implementation of Boolean algebra.

This week you learn the six operations, fill in truth tables, verify algebraic identities, and prove to yourself that NAND is universal: you can build AND, OR, and NOT from NAND alone. That means you could build a complete computer out of nothing but NAND gates.

Reading list (~1 hour)

1. Petzold CODE, Ch 10 ("Logic and Switches"): relays as logic gates; AND, OR, NOT from switches; the invention of combinational logic
2. Petzold CODE, Ch 11 ("Gates"): gates as a layer of abstraction above switches; the six common gate types
3. Optional: Khan Academy, "Logic gates" (free online) as a visual supplement to Petzold's text

Lecture outline (~2 hours)

Section 1: Truth tables

• A truth table lists all possible input combinations and the corresponding output
• For 1 input (NOT): 2 rows. For 2 inputs (AND, OR, etc.): 4 rows. For 3 inputs: 8 rows.
• The number of rows is always 2^n where n is the number of inputs
• Convention: 0 = false, 1 = true; or LOW/HIGH in electrical terms

Truth tables for the six operations (two inputs A and B, except NOT):

NOT A: output is 1 when A is 0, and 0 when A is 1.

Section 2: Boolean algebra identities

• AND is commutative: A AND B = B AND A
• AND is associative: (A AND B) AND C = A AND (B AND C)
• OR is commutative and associative similarly
• De Morgan's laws (very important): NOT(A AND B) = (NOT A) OR (NOT B); NOT(A OR B) = (NOT A) AND (NOT B)
• Double negation: NOT(NOT A) = A
• Identity laws: A AND 1 = A; A OR 0 = A
• Annihilation: A AND 0 = 0; A OR 1 = 1
• Idempotent: A AND A = A; A OR A = A
• Complement: A AND (NOT A) = 0; A OR (NOT A) = 1

These identities let you simplify complex Boolean expressions, which directly reduces circuit complexity and cost.

Section 3: XOR and its uses

• XOR (exclusive or): output is 1 when inputs differ; output is 0 when they match
• XOR and equality: A XOR B = 0 if and only if A = B
• Parity: XOR of a set of bits gives a "parity bit" that summarizes whether the count of 1-bits is odd or even; used for simple error detection
• XOR in cryptography: XOR with a key byte is the basis of stream ciphers (preview for later courses)
• XOR in swap tricks: A = A XOR B; B = A XOR B; A = A XOR B swaps two values without a temporary variable (fun but confusing)

Section 4: NAND universality

• NAND is NOT(A AND B); it is the inverse of AND
• NAND is functionally complete: you can express any Boolean function using only NAND gates
• Proof by example, building each gate from NAND:
  • NOT A = A NAND A (both inputs tied together)
  • A AND B = NOT(A NAND B) = (A NAND B) NAND (A NAND B)
  • A OR B = (NOT A) NAND (NOT B) by De Morgan's law = (A NAND A) NAND (B NAND B)
• Physical implication: NAND is cheap and fast to manufacture in CMOS (one gate type covers all logic). This is why NAND flash, NAND logic, and NAND-based computation are everywhere.

Section 5: Logical puzzles as Boolean algebra

• "Knights always tell the truth; Knaves always lie" problems are Boolean satisfiability in disguise
• A statement by a character is a Boolean expression involving the character's type
• Solving the puzzle is finding a truth assignment that satisfies all constraints simultaneously
• This is structurally identical to what a SAT solver does in automated reasoning and security research

Labs (~90 minutes)

Lab 3.1: Truth Tables (labs/lab-3-1-truth-tables.md)

• Fill in truth tables for AND, OR, XOR, NAND by hand
• Verify De Morgan's law numerically for all 4 input combinations
• Prove NAND universality by constructing OR from NAND gates (on paper)

Lab 3.2: Logic Puzzle (Knights and Knaves) (labs/lab-3-2-logic-puzzle.md)

• Solve 3 classic Knights-and-Knaves puzzles
• For each: write the Boolean expressions for each character's statements and solve systematically

Independent practice (~4 hours)

1. Write truth tables for (A AND B) OR (NOT C) and for NOT((A OR B) AND C); simplify each using Boolean identities
2. Prove that NOR is also functionally complete (NOR can build NOT, AND, OR)
3. Implement a 2-input XOR using only NAND gates: draw the circuit diagram
4. Read about De Morgan's law applied to programming: in Python, not (a and b) equals (not a) or (not b). Test this with a few values
5. Optional: read the Wikipedia article "Functional completeness" to see other universal gate sets

Reflection prompts (~30 minutes)

1. You have seen AND, OR, NOT, XOR, NAND, NOR. Which operation surprised you the most? Why?
2. NAND is universal: any circuit can be built from NAND alone. Is this "impressive" to you, or does it feel like a mathematical curiosity? Explain your reaction.
3. De Morgan's law says NOT(A AND B) = (NOT A) OR (NOT B). In English: "it is not the case that both A and B are true" is the same as "either A is false or B is false." Give a real-world sentence that illustrates this.
4. The Knights-and-Knaves puzzles are solvable by systematic Boolean algebra. Before this week, how did you approach these puzzles (if you had encountered them)? Has the algebraic framing changed your approach?
5. What do you think a logic gate actually is, physically? (Guess; week 4 will confirm or correct.)

What comes next

Week 4 takes Boolean logic into hardware. You will see how AND, OR, and NOT gates combine to form a circuit that adds binary numbers, the half-adder. You will then chain half-adders into a 4-bit ripple-carry adder, which is the direct ancestor of the ALU in your computer.