Visual
Key formulas
| Name | Formula | Variables / Notes |
|---|---|---|
| Boolean SOP | F = sum(minterms) | F: output function; minterms: product terms where F=1 |
| Boolean POS | F = product(maxterms) | F: output function; maxterms: sum terms where F=0 |
| De Morgan 1 | (A + B)' = A'B' | A, B: Boolean variables; ': complement operator |
| De Morgan 2 | (AB)' = A' + B' | A, B: Boolean variables; ': complement operator |
| XOR definition | A XOR B = A'B + AB' | A, B: Boolean inputs; output is 1 when inputs differ |
| XNOR definition | A XNOR B = AB + A'B' | A, B: Boolean inputs; output is 1 when inputs are equal |
Key concepts
Minterm vs Maxterm
A minterm is a product term that is 1 for exactly one input combination. A maxterm is a sum term that is 0 for exactly one input combination. For n variables there are 2^n minterms and 2^n maxterms.
Karnaugh Map grouping
Groups must be powers of 2 (1, 2, 4, 8). Larger groups give simpler expressions. Groups can wrap around edges. A cell can be part of multiple groups to achieve minimization.
Flip-flop setup and hold time
Setup time is the minimum interval the data input must be stable before the clock edge. Hold time is the minimum interval data must remain stable after the clock edge. Violating either causes metastability.
Two's complement
To negate a number: invert all bits and add 1. For an n-bit number the range is -2^(n-1) to 2^(n-1)-1. The MSB acts as a sign bit with weight -2^(n-1).
Universal gates
NAND and NOR are each sufficient to implement any Boolean function. Any gate (AND, OR, NOT, XOR) can be built using only NAND gates or only NOR gates.
Propagation delay
The time from a logic input change to the resulting output change. Total path delay is the sum of individual gate delays along the critical path. This limits maximum clock frequency.
Tables
Basic Logic Gate Truth Table (2-input)
| A | B | AND | OR | NAND | NOR | XOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
Flip-Flop Excitation Table
| Flip-Flop | Q(t) | Q(t+1) | Required Input |
|---|---|---|---|
| SR | 0 | 0 | S=0 R=X |
| SR | 0 | 1 | S=1 R=0 |
| SR | 1 | 0 | S=0 R=1 |
| SR | 1 | 1 | S=X R=0 |
| JK | 0 | 0 | J=0 K=X |
| JK | 0 | 1 | J=1 K=X |
| JK | 1 | 0 | J=X K=1 |
| JK | 1 | 1 | J=X K=0 |
| D | 0 | 0 | D=0 |
| D | 0 | 1 | D=1 |
| T | 0 | 0 | T=0 |
| T | 0 | 1 | T=1 |
Number System Conversion Reference
| Decimal | Binary | Octal | Hex |
|---|---|---|---|
| 0 | 0000 | 0 | 0 |
| 5 | 0101 | 5 | 5 |
| 8 | 1000 | 10 | 8 |
| 10 | 1010 | 12 | A |
| 15 | 1111 | 17 | F |
| 16 | 10000 | 20 | 10 |
Quick facts
- A 4-variable K-map has 16 cells. A group of 8 eliminates 3 variables from the expression.
- The JK flip-flop with J=K=1 toggles on every clock edge, behaving like a T flip-flop.
- An n-bit binary counter can count from 0 to 2^n - 1 and requires n flip-flops.
- 2's complement of 0 is 0 for any bit width. There is no positive equivalent of -2^(n-1).
- A half adder has 2 inputs (A, B) and 2 outputs: Sum = A XOR B, Carry = A AND B.
- A full adder has 3 inputs (A, B, Cin) and 2 outputs: Sum = A XOR B XOR Cin, Cout = majority function.
- Propagation delay of a CMOS gate is typically 0.1 ns to 1 ns at 1.8 V supply.
- A multiplexer with n select lines can route 2^n data inputs to one output.
Exam shortcuts
- K-map grouping trick: to find the simplified expression directly, identify which variables change within each group. Those variables are eliminated. Variables that remain constant give the literal for that group. Example: a group containing cells m4, m5, m6, m7 has A=1 constant and B, C varying, so the term is simply A.
- De Morgan shortcut for NAND/NOR: a NAND gate equals an OR gate with inverted inputs. Draw the alternate symbol directly to read the Boolean expression without extra steps. (A NAND B) = A' + B'.
- 2's complement subtraction: to compute A - B, find 2's complement of B then add to A. If carry out of MSB occurs, discard it. Example: 7 - 3 in 4-bit: 0111 + 1101 = (1)0100, discard carry, result = 4.
- Gray code conversion: MSB of Gray = MSB of binary. Each subsequent Gray bit = XOR of corresponding binary bit and the preceding binary bit. Reverse for decoding. No arithmetic needed.
- For don't care conditions in K-maps, always include a don't care cell in a group if it enlarges the group, and never include one if it does not. This maximizes group size and minimizes the SOP.