Week 2 — Quick Revision

Start here Week 2 on one page: from a problem in words to a Boolean formula.

• First write a functional specification (what output for each input) and a timing specification (how fast).
• Combinational logic has no memory; sequential logic remembers (from Week 7).
• A truth table has 2ⁿ rows. It gets huge fast, so we use Boolean algebra.
• Gates: NOT (flip), AND (all 1), OR (any 1), NAND, NOR, XOR (different / odd number of 1s), XNOR (same).
• Precedence: NOT → AND → OR.
• Laws come in dual pairs (swap + ↔︎ ·, 0 ↔︎ 1). Shortcuts: $X Y + X \overline{Y} = X$, $X + X Y = X$, $X + Y Z = \left(X + Y\right) \left(X + Z\right)$.
• De Morgan: $\overline{\left(A + B\right)} = \overline{A} \overline{B}$ and $\overline{\left(A B\right)} = \overline{A} + \overline{B}$. $\operatorname{NOR} = \operatorname{AND}$ with flipped inputs; $\operatorname{NAND} = \operatorname{OR}$ with flipped inputs.
• SOP: for each row with $F = 1$, write a minterm (1 → letter, 0 → barred letter) and OR them. Short form $\Sigma m \left(\ldots \right)$.