These are the notes for CS Fundamentals for Placements, episode 5. We know how numbers become bits, but a chip is only tiny switches and wires. How do switches add 27 and 14, or remember anything? Here you build it yourself, one gate at a time: the logic gates AND, OR, NOT, NAND, NOR, XOR and XNOR with their truth tables, universal gates (everything from NAND alone), Boolean algebra and De Morgan's theorem, SOP and POS with minterms and maxterms, Karnaugh maps and don't-care conditions, the half adder, full adder and ripple carry adder, the multiplexer, demultiplexer, decoder and encoder, and finally circuits that remember: latches, SR, D, JK and T flip-flops, the clock signal, registers and counters. Every term is explained in plain words the first time it appears, and there is a full glossary at the end. All outputs below are real: every program was run with Python 3.13 and its output pasted as printed.
A quick refresher: a bit is one 0 or 1. In these notes 1 and 0 are also called true and false, or high and low.
The seven problems
| Problem | What it teaches |
|---|---|
| Make a switch decide | AND, OR, NOT, truth tables, all 7 gates |
| A factory that makes only one part | NAND and NOR are universal gates |
| A rule that is too long | Boolean laws, De Morgan's theorem, simplification |
| Three judges vote | Minterms, maxterms, SOP, POS, Karnaugh maps, don't-cares |
| Add with wires | Half adder, full adder, ripple carry adder, carry lookahead |
| Pick one of many | Multiplexer, demultiplexer, decoder, encoder |
| Remember a bit | Combinational vs sequential, latches, flip-flops, clock, registers, counters |
Problem 1: switches that decide (logic gates)
A chip is built from transistors. A transistor is a tiny electronic switch: a small voltage on one wire turns the path between two other wires on or off. On is 1, off is 0. Inside a circuit, 1 and 0 are two voltage ranges called logic levels: a high voltage means 1 and a low voltage (near zero) means 0.
How do we make switches decide? Look at rules you already use:
| Everyday rule | Logic gate | Rule |
|---|---|---|
| Bank locker: your key AND the bank's key | AND gate | output 1 only if all inputs are 1 |
| Doorbell at the front OR the back | OR gate | output 1 if any input is 1 |
| Night lamp: on when it is NOT bright | NOT gate (inverter) | output is the opposite of the input |
A logic gate is a tiny circuit that takes one or more bits in and gives one bit out by a fixed rule. Write the inputs as letters A and B. A Boolean expression is a formula built from such letters and gate operations, like A·B + C'. In Boolean notation:
- AND is written as a dot or nothing at all:
A·BorAB. Read "A and B". - OR is written as plus:
A + B. Read "A or B". (Here 1 + 1 = 1: it means "at least one is 1", not counting.) - NOT is written as a prime or a bar:
A'orĀ. Read "not A" or "A bar".
Truth tables: all seven gates
A truth table lists every possible input combination and the output for each. n inputs give 2ⁿ rows, so two inputs give 4 rows. Putting a NOT after a gate gives its opposite: NAND = NOT AND, NOR = NOT OR. XOR (exclusive OR) is 1 when the inputs are different, and XNOR (exclusive NOR) is 1 when they are equal, so XNOR is an equality checker.
| A | B | AND | OR | XOR | NAND | NOR | XNOR | NOT A |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
In Python, & is bitwise AND, | is bitwise OR and ^ is bitwise XOR (episode 3); on single bits they are exactly the gates, and 1 - a flips a single bit, so it is NOT. (We generated this table with exactly those operators.)
| Gate | Expression | Output is 1 when | Memory trick |
|---|---|---|---|
| AND | AB |
both inputs are 1 | locker with two keys |
| OR | A + B |
at least one input is 1 | doorbell with two buttons |
| NOT | A' |
the input is 0 | night lamp |
| NAND | (AB)' |
not both are 1 | AND, then flip |
| NOR | (A + B)' |
both are 0 | OR, then flip |
| XOR | A ⊕ B = A'B + AB' |
the inputs differ | stair light with two switches |
| XNOR | (A ⊕ B)' = AB + A'B' |
the inputs are equal | equality checker |
Gate symbols, described in words
In circuit diagrams each gate has a standard gate symbol (its drawing). Inputs enter on the left, the output leaves on the right.
- AND: a "D" shape: flat back on the left, round front on the right. OR: a shield shape: curved, hollow back and a pointed front.
- NOT: a triangle pointing right with a small circle at its tip. That circle is a bubble, and a bubble always means "NOT here". NAND and NOR are the AND and OR shapes with a bubble on the output.
- XOR: the OR shape with an extra curved line just behind its back. XNOR: XOR plus an output bubble. Gates may have more than two inputs: a 3-input AND is 1 only when all three are 1.
Problem 2: one gate to build them all (universal gates)
A chip factory must make seven kinds of gate, each with its own design. That is expensive. With LEGO, one kind of brick builds any shape. Can we make only NAND and build every other gate from it?
def NAND(a, b): return 0 if (a and b) else 1 # the only gate we build
def NOT(a): return NAND(a, a)
def AND(a, b): return NOT(NAND(a, b))
def OR(a, b): return NAND(NOT(a), NOT(b))
print("a b | NAND AND OR NOT a")
for a in (0, 1):
for b in (0, 1):
print(a, b, "|", NAND(a, b), " ", AND(a, b), " ", OR(a, b), " ", NOT(a))
Output:
a b | NAND AND OR NOT a
0 0 | 1 0 0 1
0 1 | 1 0 1 1
1 0 | 1 0 1 0
1 1 | 0 1 1 0
- NOT a = NAND(a, a): both inputs equal a, so (a·a)' = a'.
- AND = NOT(NAND): flipping a NAND undoes its flip.
- OR = NAND(NOT a, NOT b): (a'·b')' = a + b by De Morgan's theorem (Problem 3).
A gate that can build every other gate is a universal gate. NAND is universal, and so is NOR. This is why real chips are often built mostly from NAND gates, and why exams ask "how many NANDs does this need?" Let's count, adding XOR built from 4 NANDs:
count = 0
def NAND(a, b):
global count
count += 1
return 1 - (a & b)
NOT = lambda a: NAND(a, a) # 1 NAND
AND = lambda a, b: NOT(NAND(a, b)) # 2 NANDs
OR = lambda a, b: NAND(NOT(a), NOT(b)) # 3 NANDs
def XOR(a, b): # 4 NANDs
m = NAND(a, b)
return NAND(NAND(a, m), NAND(b, m))
for name, f, args in [("NOT", NOT, (1,)), ("AND", AND, (1, 1)), ("OR", OR, (0, 1)), ("XOR", XOR, (1, 0))]:
count = 0
f(*args)
print(f"{name}: {count} NAND gates")
print("XOR correct:", all(XOR(a, b) == a ^ b for a in (0, 1) for b in (0, 1)))
Output:
NOT: 1 NAND gates
AND: 2 NAND gates
OR: 3 NAND gates
XOR: 4 NAND gates
XOR correct: True
lambda a: ... is a short way to write a one-line function; global count lets NAND update the counter defined outside it.
| Gate to build | NAND gates needed | NOR gates needed |
|---|---|---|
| NOT | 1 | 1 |
| AND | 2 | 3 |
| OR | 3 | 2 |
| XOR | 4 | 5 |
| XNOR | 5 | 4 |
The XOR trick: with m = (AB)', the gate NAND(a, m) works out to (AB')' and NAND(b, m) to (A'B)'. The last NAND of those two gives AB' + A'B by De Morgan, which is XOR. Mirror it with NOR gates (m = NOR(a, b), then the same wiring) and 4 NORs give XNOR. NAND and NOR are mirror images: the costs of AND and OR swap.
Problem 3: a rule that is too long (Boolean algebra)
A shop owner's burglar alarm rule, in words: ring if the door is open and the alarm is armed, or if the door is open, the alarm is armed and it is night. Written directly that is D·A + D·A·N (D = door open, A = armed, N = night): two AND gates, an OR gate and their wires. Every gate costs money, space on the chip and power. Boolean algebra is the algebra of 0 and 1 that lets us shrink such rules before building them.
The Boolean laws
Every law has a dual: swap + with · and 0 with 1, and you get another true law.
| Law | OR form | AND form (dual) | Plain meaning |
|---|---|---|---|
| Identity | A + 0 = A | A · 1 = A | OR with 0, AND with 1: nothing changes |
| Null (domination) | A + 1 = 1 | A · 0 = 0 | a 1 in an OR, or a 0 in an AND, decides everything |
| Idempotent | A + A = A | A · A = A | repeating a term changes nothing |
| Complement | A + A' = 1 | A · A' = 0 | a thing or its opposite is always true; both at once never |
| Involution | (A')' = A | (same) | two NOTs cancel |
| Commutative | A + B = B + A | AB = BA | order does not matter |
| Associative | (A + B) + C = A + (B + C) | (AB)C = A(BC) | grouping does not matter |
| Distributive | A + BC = (A + B)(A + C) | A(B + C) = AB + AC | the first one has no school-algebra version |
| Absorption | A + AB = A | A(A + B) = A | if A decides, B is useless |
| De Morgan | (A + B)' = A'B' | (AB)' = A' + B' | break the bar, change the sign |
A Boolean law is easy to prove by truth table: try every input and compare both sides. The De Morgan program below does exactly that. A rule that only looks right, such as A + BC = (A + B)C, fails on at least one row (A = 1, C = 0).
Back to the alarm: D·A + D·A·N = DA + DA·N = DA by absorption (take X = DA: X + X·N = X). The night input was useless; we saved a gate.
De Morgan's theorem, live (and the wrong version)
De Morgan's theorem: the NOT of an AND is the OR of the NOTs, and the NOT of an OR is the AND of the NOTs. Recipe: break the bar, change the sign.
from itertools import product
ok = True
for a, b in product((0, 1), repeat=2):
left = 1 - (a & b) # NOT (a AND b)
right = (1 - a) | (1 - b) # (NOT a) OR (NOT b)
print(a, b, "->", left, right)
ok = ok and left == right
print("De Morgan holds:", ok)
wrong = all((1 - (a & b)) == ((1 - a) & (1 - b))
for a, b in product((0, 1), repeat=2))
print("NOT(a AND b) == NOT a AND NOT b ?", wrong)
Output:
0 0 -> 1 1
0 1 -> 1 1
1 0 -> 1 1
1 1 -> 0 0
De Morgan holds: True
NOT(a AND b) == NOT a AND NOT b ? False
Both columns match in every row, so De Morgan holds. The common mistake, removing the bar but keeping AND, gives a different circuit: False. De Morgan works for any number of inputs: (A + B + C)' = A'B'C'. Real-life reading: "not (raining and cold)" means "not raining, or not cold".
Step-by-step algebraic simplification
Simplify F = A'BC + AB'C + ABC' + ABC (the judges' function from Problem 4).
| Step | Expression | Law used |
|---|---|---|
| 1 | A'BC + AB'C + ABC' + ABC | start |
| 2 | A'BC + AB'C + ABC' + ABC + ABC + ABC | idempotent: ABC = ABC + ABC + ABC |
| 3 | (A'BC + ABC) + (AB'C + ABC) + (ABC' + ABC) | commutative, associative: regroup |
| 4 | BC(A' + A) + AC(B' + B) + AB(C' + C) | distributive: take out the common part |
| 5 | BC·1 + AC·1 + AB·1 | complement: X' + X = 1 |
| 6 | AB + BC + AC | identity: X·1 = X |
The trick in step 2 is to copy ABC so it can pair with each of the other three terms. Finding such tricks by hand is hard, which is why the K-map (next problem) exists. The program in the quiz section checks this result.
Problem 4: three judges vote (from a table to a circuit)
A talent show has three judges, A, B and C. Each presses yes (1) or no (0). An act passes if at least two say yes: a majority vote. We know the rule as a table. How do we turn a truth table into a circuit?
from itertools import product
# 3 judges: the act passes if at least 2 say yes
print("A B C | pass")
minterms = []
for i, (a, b, c) in enumerate(product((0, 1), repeat=3)):
out = 1 if a + b + c >= 2 else 0
print(a, b, c, "|", out)
if out: minterms.append(i)
print("minterms:", minterms)
# the simplified circuit from the K-map: AB + BC + AC
same = all((a & b | b & c | a & c) == (1 if a + b + c >= 2 else 0)
for a, b, c in product((0, 1), repeat=3))
print("AB + BC + AC matches:", same)
Output:
A B C | pass
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1
minterms: [3, 5, 6, 7]
AB + BC + AC matches: True
enumeratenumbers the rows 0 to 7; row i is just i written in binary (row 5 =101).- In Python
a & b | b & cmeans(a & b) | (b & c), because&binds tighter than|.
Minterms and SOP
A minterm is an AND term that contains every variable once (plain or primed) and is 1 for exactly one row. Rule: a variable that is 0 in the row gets a prime. Row 3 = 011 → A'BC. Minterm number i is written mᵢ. The rows where the output is 1 are "the minterms of F".
The four 1 rows give: row 3 = 011 → A'BC (m3), row 5 = 101 → AB'C (m5), row 6 = 110 → ABC' (m6), row 7 = 111 → ABC (m7).
OR the minterms together: F = A'BC + AB'C + ABC' + ABC = Σm(3, 5, 6, 7). An OR of AND terms is a Sum of Products (SOP). The Σ ("sigma", sum) list is a short way to write it. When every term has every variable it is the canonical SOP; after simplification, like AB + BC + AC, it is a minimal SOP. An SOP is built as two levels: a row of AND gates feeding one OR gate.
Maxterms and POS
Start from the 0 rows instead. A maxterm is an OR term that contains every variable once and is 0 for exactly one row. Rule: a variable that is 1 in the row gets a prime. Row 4 = 100 → (A' + B + C). Maxterm i is written Mᵢ, and Mᵢ = (mᵢ)'.
F is 0 in rows 0, 1, 2, 4, so F = (A + B + C)(A + B + C')(A + B' + C)(A' + B + C) = ΠM(0, 1, 2, 4). An AND of OR terms is a Product of Sums (POS). Π ("pi", product) lists the maxterms. The POS list is always the rows missing from the SOP list. Both describe the same circuit (checked by the quiz program below). But look at the size: four terms of three inputs each. Too many gates for a simple vote.
Karnaugh maps (K-maps)
A Karnaugh map (K-map) is the truth table drawn as a grid, arranged so that the simplification can be seen by eye. The columns go 00 01 11 10: this is Gray code order (episode 2), where neighbouring codes differ in exactly one bit. The map also wraps around: the left edge touches the right edge, and the top touches the bottom.
The judges' function (cell = output for that A, BC):
BC=00 01 11 10
A=0 0 0 1 0
A=1 0 1 1 1
Rules for grouping:
- Circle neighbouring 1s in rectangles of size 1, 2, 4, 8, 16 (powers of two). Diagonals do not count.
- Make each group as big as possible, and use as few groups as possible. Groups may overlap.
- Inside a group, any variable that changes drops out. A variable that stays 1 appears plain; one that stays 0 appears primed.
Groups here: column 11 (A changes, B = C = 1) → BC; cells A=1, BC=01 and 11 (B changes) → AC; cells A=1, BC=11 and 10 (C changes) → AB. So F = AB + BC + AC: three 2-input terms instead of four 3-input terms. The program above printed AB + BC + AC matches: True.
A group of 2ᵏ cells removes k variables. Each biggest-possible group is a prime implicant. A prime implicant that covers some 1 that no other group covers is an essential prime implicant; it must be in the answer.
3-variable K-map with wrap-around: F = Σm(0, 2, 5, 7)
This is the video's homework.
BC=00 01 11 10
A=0 1 0 0 1
A=1 0 1 1 0
- m0 and m2 sit at the two ends of the top row. Because the map wraps, they are neighbours: A = 0 and C = 0 stay, B changes → A'C'.
- m5 and m7 → A = 1, C = 1 → AC.
- F = A'C' + AC, which is XNOR of A and C (1 when A equals C).
4-variable K-map: F = Σm(0, 2, 5, 7, 8, 10, 13, 15)
Rows are AB and columns are CD, both in Gray order. Cell number = 8A + 4B + 2C + D.
CD=00 01 11 10
AB=00 1 0 0 1
AB=01 0 1 1 0
AB=11 0 1 1 0
AB=10 1 0 0 1
- The four corners (m0, m2, m8, m10) are all neighbours by wrap-around: B = 0 and D = 0 stay → B'D'.
- The centre square (m5, m7, m13, m15): B = 1, D = 1 → BD.
- F = B'D' + BD. Eight minterms of 4 variables collapsed into two 2-variable terms.
Don't-care conditions: a BCD input
BCD (binary-coded decimal) stores one decimal digit 0 to 9 in 4 bits. Codes 10 to 15 (1010 to 1111) never happen. Their outputs do not matter, so they are don't-care conditions, marked X. You may treat each X as 1 or 0, whichever makes bigger groups.
Example: output 1 if the BCD digit is 5 or more. F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15), where d lists the don't-cares.
CD=00 01 11 10
AB=00 0 0 0 0
AB=01 0 1 1 1
AB=11 X X X X
AB=10 1 1 X X
- The bottom two rows (A = 1): 8 cells, using the Xs as 1 → A.
- m5, m7, m13, m15 (B = 1, D = 1) → BD. m6, m7, m14, m15 (B = 1, C = 1) → BC.
- F = A + BD + BC.
Every K-map answer in these notes, checked against the truth table (check skips the don't-care rows and prints OK only if every other row matches):
from itertools import product
n = lambda x: 1 - x # NOT
def check(name, nvars, ones, expr, dont_care=()):
rows = [i for i in range(2 ** nvars) if i not in dont_care]
bits = list(product((0, 1), repeat=nvars))
ok = all(expr(*bits[i]) == (i in ones) for i in rows)
print(f"{name:38} {'OK' if ok else 'WRONG'}")
check("Σm(0,2,5,7) = A'C' + AC", 3, {0, 2, 5, 7},
lambda A, B, C: (n(A) & n(C)) | (A & C))
check("Σm(0,2,5,7,8,10,13,15) = B'D' + BD", 4, {0, 2, 5, 7, 8, 10, 13, 15},
lambda A, B, C, D: (n(B) & n(D)) | (B & D))
check("Σm(1,3,4,5,9,11,12,13) = BC' + B'D", 4, {1, 3, 4, 5, 9, 11, 12, 13},
lambda A, B, C, D: (B & n(C)) | (n(B) & D))
check("BCD >= 5 with X: A + BD + BC", 4, {5, 6, 7, 8, 9}, # d(10..15) skipped
lambda A, B, C, D: A | (B & D) | (B & C), dont_care=range(10, 16))
check("Σm(0,1,2,3,6) = A' + BC'", 3, {0, 1, 2, 3, 6},
lambda A, B, C: n(A) | (B & n(C)))
Output:
Σm(0,2,5,7) = A'C' + AC OK
Σm(0,2,5,7,8,10,13,15) = B'D' + BD OK
Σm(1,3,4,5,9,11,12,13) = BC' + B'D OK
BCD >= 5 with X: A + BD + BC OK
Σm(0,1,2,3,6) = A' + BC' OK
Without the don't-cares the best answer would be AB'C' + A'BD + A'BC, which is bigger.
K-maps for POS: group the 0s instead. Each group gives an OR term with the opposite rule (stays 0 → plain, stays 1 → primed), and you AND the groups.
Problem 5: adding with gates (adders)
Adding two single bits gives a sum bit and a carry bit:
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Sum is 1 when the bits differ: Sum = A ⊕ B (XOR). Carry is 1 only for 1 1: Carry = AB (AND). One XOR and one AND: this is a half adder.
Why "half"? From the second column on we add three bits: A, B and the carry-in coming from the column on the right. A half adder has no carry-in input. The fix: chain two half adders (first A + B, then add the carry-in) and OR their two carries. That is a full adder: three bits in, sum and carry-out out.
Full adder equations:
- S = A ⊕ B ⊕ Cin (1 when an odd number of inputs are 1)
- Cout = AB + Cin(A ⊕ B), which also equals the majority function AB + BCin + ACin from Problem 4.
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Chaining n full adders, each carry-out feeding the next column's carry-in, gives an n-bit ripple carry adder:
def half_adder(a, b):
return a ^ b, a & b # sum, carry
def full_adder(a, b, cin):
s1, c1 = half_adder(a, b)
s, c2 = half_adder(s1, cin)
return s, c1 | c2
def ripple_add(x, y, bits=8): # chain 8 full adders
carry, result = 0, 0
for i in range(bits): # LSB first
s, carry = full_adder((x >> i) & 1, (y >> i) & 1, carry)
result |= s << i
return result, carry
print("half_adder(1, 1) =", half_adder(1, 1))
print("full_adder(1, 1, 1) =", full_adder(1, 1, 1))
print("27 + 14 =", ripple_add(27, 14))
print("200 + 100 =", ripple_add(200, 100))
Output:
half_adder(1, 1) = (0, 1)
full_adder(1, 1, 1) = (1, 1)
27 + 14 = (41, 0)
200 + 100 = (44, 1)
(x >> i) & 1reads bit i of x;result |= s << iwrites the sum bit into position i (episode 3's shifts and masks).- 1 + 1 = sum 0, carry 1. 1 + 1 + 1 = sum 1, carry 1 (3 =
11). - 27 + 14 = 41, the same answer we worked by hand in episode 3. Gates can add.
- 200 + 100 = 300 does not fit in 8 bits (max 255). The 8-bit result is 300 - 256 = 44, and the carry-out of 1 is the unsigned overflow warning from episode 3.
- A full adder from gates: 2 XOR + 2 AND + 1 OR. An n-bit ripple adder needs n full adders (or a half adder in column 0 plus n - 1 full adders, since column 0 has no carry-in).
Why ripple carry is slow: propagation delay and carry lookahead
Every real gate takes a small time to react after its inputs change: its propagation delay. In a ripple carry adder, column 8 cannot finish until the carry has rippled through all 7 columns before it, so the delay grows with the number of bits.
A carry lookahead adder computes all carries in parallel. For each column define generate Gᵢ = AᵢBᵢ (this column makes a carry by itself) and propagate Pᵢ = Aᵢ ⊕ Bᵢ (this column passes an incoming carry on). Then:
- C1 = G0 + P0·C0
- C2 = G1 + P1·G0 + P1·P0·C0
- C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0
Each carry is a two-level AND-OR formula of the inputs only, so it does not wait for the previous column. The cost is more gates.
Subtraction reuses the adder: A - B = A + B' + 1 (episode 3's 2's complement), using XOR gates to flip B and a carry-in of 1. The mini project does exactly this.
Problem 6: choosing one of many (mux, demux, decoder, encoder)
Many signals, but only one wire to send on.
| Real life | Circuit | What it does |
|---|---|---|
| A TV remote picks 1 of 4 channels | Multiplexer (MUX) | many inputs → 1 output, chosen by select lines |
| A railway junction: one track to one of many | Demultiplexer (DEMUX) | 1 input → one of many outputs |
| Lift button 2 lights only lamp 2 | Decoder | n bits → exactly one of 2ⁿ lines is 1 |
Pressing key 5 sends 101 |
Encoder | one of 2ⁿ lines → its n-bit number |
A select line is a control input whose bits form the number of the input (or output) to use. A MUX with 2ⁿ data inputs needs n select lines: a 4-to-1 MUX has 2, an 8-to-1 has 3, a 16-to-1 has 4.
def mux4(inputs, s1, s0): # 4 inputs, 2 select lines -> 1 output
sel = 2 * s1 + s0
return inputs[sel]
def decoder2to4(s1, s0): # 2 inputs -> exactly one of 4 lines is 1
return [1 if 2 * s1 + s0 == i else 0 for i in range(4)]
channels = ["news", "cricket", "cartoons", "music"]
for s1, s0 in [(0, 0), (0, 1), (1, 0), (1, 1)]:
name = mux4(channels, s1, s0)
print(f"select {s1}{s0} -> {name:9} decoder {decoder2to4(s1, s0)}")
Output:
select 00 -> news decoder [1, 0, 0, 0]
select 01 -> cricket decoder [0, 1, 0, 0]
select 10 -> cartoons decoder [0, 0, 1, 0]
select 11 -> music decoder [0, 0, 0, 1]
2 * s1 + s0turns the two select bits into a number 0 to 3.{...:9}pads the channel name to 9 characters.- In gates, a 4-to-1 MUX is Y = S1'S0'·I0 + S1'S0·I1 + S1S0'·I2 + S1S0·I3: the decoder's lines each AND one input, then all are ORed. The decoder output lines are exactly the minterms of the select bits.
- CPUs use decoders to pick one memory location out of many (address decoding) and to pick which register to use.
A DEMUX is a decoder with a data input D: each decoder line is ANDed with D, so with select 10 and D = 1 the outputs are 0 0 1 0. An encoder does the reverse: line 2 active gives 10. A plain encoder breaks if two lines are 1 at once; a priority encoder lets the highest active line win and adds a "valid" output that says whether any line was 1.
The MUX as a universal function implementer
A 2ⁿ-to-1 MUX can implement any function of n variables: put the variables on the select lines and wire the function's truth-table column (constant 0s and 1s) to the data inputs. Even smaller: a 2ⁿ⁻¹-to-1 MUX works if you put one variable (or its NOT, or 0, or 1) on each data input. For the majority function with A, B on the select lines: when AB = 00 the output is 0; 01 → C; 10 → C; 11 → 1. So the inputs are 0, C, C, 1.
| A B (select) | Rows covered | F in those rows | Wire to the data input |
|---|---|---|---|
| 0 0 | 000, 001 | 0, 0 | 0 |
| 0 1 | 010, 011 | 0, 1 | C |
| 1 0 | 100, 101 | 0, 1 | C |
| 1 1 | 110, 111 | 1, 1 | 1 |
In the mini project below, mux4 picks between four ready-made answers in exactly this way. Similarly, a 3-to-8 decoder plus one OR gate implements any 3-variable SOP: OR together the decoder lines of the minterms (for the judges, lines 3, 5, 6, 7).
Problem 7: a circuit that remembers (sequential logic)
Everything so far forgets. Let go of a doorbell and it stops.
| Combinational circuit | Sequential circuit | |
|---|---|---|
| Real life | Doorbell: rings only while pressed | Light switch: stays on after you let go |
| Output depends on | the inputs right now only | the inputs now and the past (a stored state) |
| Has memory? | No | Yes |
| Feedback (output wired back to input)? | No | Yes |
| Examples | adders, MUX, DEMUX, decoder, encoder | latches, flip-flops, registers, counters |
The stored value is called the state, written Q. How can gates remember? Feedback: wire a gate's output back into an input.
The SR latch
Take two NOR gates and wire each one's output into the other's input. The outputs are Q and Q' (Q bar, which should be the opposite of Q). The inputs are S (set: make Q = 1) and R (reset: make Q = 0). This loop is an SR latch: one bit of memory. A latch is a memory circuit that responds to its inputs whenever they change (it is level-triggered).
def NOR(a, b): return 0 if (a or b) else 1
q, qbar = 0, 1 # the latch starts holding 0
def sr_latch(s, r):
global q, qbar
for _ in range(4): # let the feedback loop settle
q, qbar = NOR(r, qbar), NOR(s, q)
return q
print("press SET (S=1, R=0) -> Q =", sr_latch(1, 0))
print("let go (S=0, R=0) -> Q =", sr_latch(0, 0))
print("press RESET (S=0, R=1) -> Q =", sr_latch(0, 1))
print("let go (S=0, R=0) -> Q =", sr_latch(0, 0))
print("both (S=1, R=1): Q =", sr_latch(1, 1), " Qbar =", qbar)
Output:
press SET (S=1, R=0) -> Q = 1
let go (S=0, R=0) -> Q = 1
press RESET (S=0, R=1) -> Q = 0
let go (S=0, R=0) -> Q = 0
both (S=1, R=1): Q = 0 Qbar = 0
- The loop runs 4 times to imitate the signals travelling round the feedback loop until they stop changing ("settle").
- After SET, letting go keeps Q = 1. It remembered. Same for RESET.
- With S = R = 1, Q and Q' are both 0, which makes no sense. This is the forbidden state (invalid input). Worse, if S and R are then released at the same moment, the two gates "race" each other and the final Q is unpredictable: a race condition. Designs below avoid this input.
- An SR latch built from NAND gates works the same way but with active-low inputs (S' and R'): pressing means 0, and S' = R' = 0 is forbidden.
The clock signal and flip-flops
In a big chip, millions of latches changing at random moments would be chaos. So we add a clock signal: a wire that goes 0, 1, 0, 1 at a steady rate, a square wave like a heartbeat. One full 0-1 cycle is a clock period; the number of cycles per second is the clock frequency. The instant the clock goes 0 → 1 is the rising edge (positive edge); 1 → 0 is the falling edge (negative edge). Both are called clock edges.
A flip-flop is a memory cell that changes only at a clock edge (it is edge-triggered) and holds its value the rest of the time. Latch vs flip-flop in one line: a latch listens all the time; a flip-flop listens only at the instant of the edge. A gated (clocked) D latch sits in between: it copies D while the clock is high.
Two tables describe each flip-flop:
- A characteristic table says: given the inputs and the present state Q, what is the next state Q+ (the value after the next clock edge)? Its formula is the next-state equation (characteristic equation).
- An excitation table goes backwards: to move from Q to a wanted Q+, what inputs are needed? It is used when designing counters.
Characteristic tables (Q = present state, Q' = its opposite), with each flip-flop's next-state equation:
| Inputs | SR flip-flop: Q+ = S + R'Q (needs SR = 0) | JK flip-flop: Q+ = JQ' + K'Q |
|---|---|---|
| 0 0 | Q (hold) | Q (hold) |
| 0 1 | 0 (reset) | 0 (reset) |
| 1 0 | 1 (set) | 1 (set) |
| 1 1 | forbidden | Q' (toggle): SR with the forbidden case fixed |
| D | D (data) flip-flop: Q+ = D | T | T (toggle) flip-flop: Q+ = T ⊕ Q = TQ' + T'Q | |
|---|---|---|---|---|
| 0 | 0 | 0 | Q (hold) | |
| 1 | 1 (no forbidden input) | 1 | Q' (toggle) |
Excitation tables (X = don't care):
| Q → Q+ | S R | J K | D | T |
|---|---|---|---|---|
| 0 → 0 | 0 X | 0 X | 0 | 0 |
| 0 → 1 | 1 0 | 1 X | 1 | 1 |
| 1 → 0 | 0 1 | X 1 | 0 | 1 |
| 1 → 1 | X 0 | X 0 | 1 | 0 |
- D from JK: J = D, K = D'. T from JK: tie J = K = T. T from D: D = T ⊕ Q.
- Race-around condition: a JK built as a level-triggered latch with J = K = 1 keeps toggling again and again while the clock stays high. The fix is edge triggering, or a master-slave flip-flop (two latches in series, one listening while the clock is high, the other while it is low).
- Two timing words you will meet: setup time (the input must be steady a short time before the edge) and hold time (and stay steady a short time after it).
Registers
A register is a row of flip-flops sharing one clock, storing a multi-bit value. 8 D flip-flops side by side store a byte. A load control decides whether the register takes a new value at the edge or feeds its own Q back in to hold.
Example: load 41, then clock with load = 0: the register still holds 41, whatever is on its inputs. A shift register instead wires each flip-flop's Q to the next one's D, so the bits move one place per clock edge (serial in, parallel out).
Counters
T flip-flops in a chain, each flipping the next when it falls from 1 to 0 (just like a carry), count in binary:
# 3 T flip-flops: each one flips when the one before it falls 1 -> 0
q = [0, 0, 0] # q[0] is the LSB
def clock_tick():
i = 0
while i < 3:
q[i] ^= 1 # T = 1: toggle
if q[i] == 1: # it rose 0 -> 1: stop the ripple
break
i += 1 # it fell 1 -> 0: toggle the next one
for tick in range(10):
print(f"tick {tick}: {q[2]}{q[1]}{q[0]} = {q[2]*4 + q[1]*2 + q[0]}")
clock_tick()
Output:
tick 0: 000 = 0
tick 1: 001 = 1
tick 2: 010 = 2
tick 3: 011 = 3
tick 4: 100 = 4
tick 5: 101 = 5
tick 6: 110 = 6
tick 7: 111 = 7
tick 8: 000 = 0
tick 9: 001 = 1
A 3-bit counter has 8 states, 0 to 7, then wraps. For the homework (count 0 to 15), use q = [0, 0, 0, 0], while i < 4 and add q[3]*8 to the print: it then counts 0 to 15 and wraps (we ran it and got 0, 1, ..., 15, 0, 1).
Counter facts:
- A mod-N counter goes through N states and then wraps to 0. n flip-flops give at most 2ⁿ states (mod-2ⁿ), counting 0 to 2ⁿ - 1.
- A mod-N counter needs ⌈log₂ N⌉ flip-flops (log₂ rounded up): mod-10 needs 4, mod-12 needs 4, mod-5 needs 3. For N that is not a power of two, detect state N and reset to 0 (a mod-10 or decade counter uses 4 flip-flops and resets as soon as it reaches 10 =
1010, so it shows 0 to 9). - Ripple (asynchronous) counter: only the first flip-flop gets the clock; each other one is clocked by the previous flip-flop's output. Simple, but the delays add up, like the ripple adder.
- Synchronous counter: all flip-flops share the same clock and change together; extra gates decide which ones toggle (bit i toggles when all lower bits are 1). Faster, more gates.
- Each stage of a ripple counter runs at half the frequency of the one before it, so a counter is also a frequency divider (mod-2ⁿ divides by 2ⁿ).
- A ring counter of n flip-flops has n states; a Johnson (twisted ring) counter has 2n.
Common mistakes (and the real output)
| Mistake | Code | Output | Fix |
|---|---|---|---|
| De Morgan without changing the sign | NOT(a AND b) == NOT a AND NOT b |
False |
(AB)' = A' + B': break the bar, change the sign |
| Half adder in every column | add 27 + 14 with half adders only | 27 + 14 = 21 |
A half adder has no carry-in; use full adders after column 0 |
| SR latch with S = R = 1 | sr_latch(1, 1) |
Q = 0 Qbar = 0 |
Forbidden input; use a D or JK flip-flop |
| K-map columns in binary order | 00 01 10 11 |
binary [1, 2, 1, 2] bits change between neighbours |
Gray order 00 01 11 10: Gray [1, 1, 1, 1] |
Using Python's ~ as a 1-bit NOT |
a = 1; ~a |
-2 |
Use 1 - a or a ^ 1 (both give 0) |
| Confusing XOR with OR | 1 \| 1 vs 1 ^ 1 |
1 vs 0 |
XOR is 1 only when the inputs differ |
| Forgetting operator precedence | A ^ B & C with A=1, B=1, C=0 |
1 (but (A ^ B) & C is 0) |
& binds before ^ before \|: add brackets |
The program behind the table:
from itertools import product
print("1:", all(1 - (a & b) == (1 - a) & (1 - b) for a, b in product((0, 1), repeat=2)))
def add_with_half_adders(x, y, bits=8): # sum bits only: every carry is lost
return sum(((((x >> i) & 1) ^ ((y >> i) & 1)) << i) for i in range(bits))
print("2: 27 + 14 =", add_with_half_adders(27, 14))
a = 1
print("3: ~a =", ~a, " 1 - a =", 1 - a, " a ^ 1 =", a ^ 1)
def changes(order): # bits that change between neighbours (wrapping)
return [bin(int(x, 2) ^ int(y, 2)).count("1") for x, y in zip(order, order[1:] + order[:1])]
print("4: binary", changes(["00", "01", "10", "11"]), " Gray", changes(["00", "01", "11", "10"]))
print("5: 1 | 1 =", 1 | 1, " 1 ^ 1 =", 1 ^ 1)
A, B, C = 1, 1, 0 # & binds tighter than ^, ^ tighter than |
print("6: A ^ B & C =", A ^ B & C, " (A ^ B) & C =", (A ^ B) & C)
Output:
1: False
2: 27 + 14 = 21
3: ~a = -2 1 - a = 0 a ^ 1 = 0
4: binary [1, 2, 1, 2] Gray [1, 1, 1, 1]
5: 1 | 1 = 1 1 ^ 1 = 0
6: A ^ B & C = 1 (A ^ B) & C = 0
- Mistake 2: 27 + 14 with no carries is just 27 XOR 14 =
011011 ^ 001110=010101= 21. - Mistake 3: Python integers are not single bits;
~1flips every bit of a 2's complement integer, giving -2 (episode 3: ~x = -x - 1). - Mistake 4: the
changeslist wraps from the last code back to the first, since K-maps wrap too.
Mini project: a 4-bit ALU from NAND gates only
An ALU (arithmetic logic unit) is the part of a CPU that does arithmetic and logic. Ours is built from a single NAND function; every other gate, the full adders and the multiplexers are made from it. A 2-bit opcode (operation code) chooses the operation through a 4-to-1 MUX: 00 AND, 01 OR, 10 ADD, 11 SUB. It also outputs the carry C and a zero flag Z (1 when the result is 0).
# mini project: a 4-bit ALU built ONLY from a NAND function
nands = 0
def NAND(a, b):
global nands
nands += 1
return 1 - (a & b)
NOT = lambda a: NAND(a, a)
AND = lambda a, b: NOT(NAND(a, b))
OR = lambda a, b: NAND(NOT(a), NOT(b))
def XOR(a, b):
m = NAND(a, b)
return NAND(NAND(a, m), NAND(b, m))
def full_adder(a, b, cin): # S = A^B^Cin, Cout = AB + Cin(A^B)
s1 = XOR(a, b)
return XOR(s1, cin), OR(AND(a, b), AND(s1, cin))
mux2 = lambda d0, d1, s: OR(AND(d0, NOT(s)), AND(d1, s)) # Y = D0.S' + D1.S
mux4 = lambda d, s1, s0: mux2(mux2(d[0], d[1], s0), mux2(d[2], d[3], s0), s1)
def alu4(x, y, op): # op: 0 AND, 1 OR, 2 ADD, 3 SUB
s1, s0 = op >> 1, op & 1
sub = AND(s1, s0) # SUB: flip y and carry-in 1
carry, out = sub, 0
for i in range(4):
a, b = (x >> i) & 1, (y >> i) & 1
s, carry = full_adder(a, XOR(b, sub), carry)
out |= mux4([AND(a, b), OR(a, b), s, s], s1, s0) << i
bits = [(out >> i) & 1 for i in range(4)]
zero = NOT(OR(OR(bits[0], bits[1]), OR(bits[2], bits[3])))
return out, carry, zero
print("op x y result C Z")
for x, y, op in [(12, 10, 0), (12, 10, 1), (5, 6, 2), (9, 9, 2), (7, 3, 3), (3, 7, 3), (6, 6, 3)]:
nands = 0
r, c, z = alu4(x, y, op)
c = c if op >= 2 else "-" # carry only means something for ADD/SUB
print(f"{['AND', 'OR ', 'ADD', 'SUB'][op]} {x:04b} {y:04b} {r:04b} {c} {z} ({nands} NANDs)")
Output:
op x y result C Z
AND 1100 1010 1000 - 0 (204 NANDs)
OR 1100 1010 1110 - 0 (204 NANDs)
ADD 0101 0110 1011 0 0 (204 NANDs)
ADD 1001 1001 0010 1 0 (204 NANDs)
SUB 0111 0011 0100 1 0 (204 NANDs)
SUB 0011 0111 1100 0 0 (204 NANDs)
SUB 0110 0110 0000 1 1 (204 NANDs)
- 5 + 6 = 11 =
1011. 9 + 9 = 18 does not fit in 4 bits: result0010(2) with C = 1. - SUB is x + (NOT y) + 1: XOR with
subflips y's bits, andsubalso enters as carry-in 1. 7 - 3 = 4; 3 - 7 =1100= -4 in 4-bit 2's complement; 6 - 6 = 0 sets Z = 1. After SUB, C = 1 means "no borrow" (episode 3). - The NAND count is the same, 204, for every operation: like real hardware, all parts compute in parallel every time and the MUX only chooses which answer to show.
mux2is the formula Y = D0·S' + D1·S;mux4is three 2-to-1 MUXes in a tree.lambdadefines a one-line function.
Try extending it: add XOR as a fifth operation (you will need a third select bit), or a 7-segment decoder that turns the 4-bit result into the seven segments a to g of a digit display.
Practice
- Write the truth table of a 3-input XOR. When is it 1?
- Build XNOR using only NAND gates. How many do you need?
- How many NOR gates make an AND? An OR? A NOT?
- Simplify (A + B)(A + B') using Boolean laws.
- Simplify A + A'B. (Hint: distributive law, OR form.)
- Write the dual of A + 0 = A and of A(A + B) = A.
- Apply De Morgan: (A'B + C)'.
- Write F = Σm(1, 4, 7) of A, B, C in canonical SOP, and the same F as ΠM.
- Simplify F(A, B, C) = Σm(0, 1, 2, 3, 6) with a K-map.
- Simplify F(A, B, C, D) = Σm(1, 3, 4, 5, 9, 11, 12, 13) with a K-map.
- How many select lines does a 16-to-1 MUX need? How many 2-to-1 MUXes make an 8-to-1 MUX?
- How many output lines does a 3-to-8 decoder have, and how many are 1 at a time?
- How many full adders does a 16-bit ripple carry adder need? Why is it slow?
- A JK flip-flop has J = 1, K = 1, Q = 1. What is Q+ after the clock edge?
- Convert a JK flip-flop into a T flip-flop and into a D flip-flop.
- How many flip-flops are needed for a mod-12 counter? A mod-5 counter?
- Implement F(A, B, C) = Σm(1, 2, 6, 7) with a 4-to-1 MUX, A and B on the select lines.
Solutions
- A ⊕ B ⊕ C is 1 when an odd number of inputs are 1: rows 001, 010, 100, 111 (Σm(1, 2, 4, 7)). It is a parity checker.
- Build XOR with 4 NANDs, then a fifth NAND as NOT: 5 NANDs.
- NOR-only: NOT = 1, OR = 2 (NOR then NOT), AND = 3 (NOT both inputs, then NOR). (NOR mirrors NAND.)
- (A + B)(A + B') = A + BB' (distributive, OR form) = A + 0 (complement) = A.
- A + A'B = (A + A')(A + B) = 1·(A + B) = A + B.
- Dual of A + 0 = A is A·1 = A. Dual of A(A + B) = A is A + AB = A.
- (A'B + C)' = (A'B)'·C' = (A + B')C' (De Morgan twice, then involution).
- SOP: A'B'C + AB'C' + ABC. The 0 rows are 0, 2, 3, 5, 6, so ΠM(0, 2, 3, 5, 6) = (A+B+C)(A+B'+C)(A+B'+C')(A'+B+C')(A'+B'+C).
- Row A = 0 is all 1s → A'; m2 and m6 (column BC = 10) → BC'. F = A' + BC' (verified OK by the K-map program).
- m4, m5, m12, m13 → BC'; m1, m3, m9, m11 → B'D. F = BC' + B'D (verified OK).
- 2⁴ = 16, so 4 select lines. 8-to-1 from 2-to-1: 4 + 2 + 1 = 7.
- 8 lines; exactly one is 1 at a time.
- 16 full adders (or 15 plus one half adder for column 0). The carry must ripple through every column, so the delay grows with the width.
- Q+ = JQ' + K'Q = 1·0 + 0·1 = 0: J = K = 1 toggles.
- T: tie J = K = T. D: J = D, K = D' (via a NOT gate).
- mod-12: 2³ = 8 < 12 ≤ 16 = 2⁴, so 4. mod-5: 3.
- AB = 00: rows 000, 001 → F = 0, 1 → input C. AB = 01: rows 010, 011 → 1, 0 → C'. AB = 10: rows 100, 101 → 0, 0 → 0. AB = 11: rows 110, 111 → 1, 1 → 1. Inputs: C, C', 0, 1.
Quick quiz
Simplify using Boolean laws: F = A·B + A·B'. What is F?
- A. A
- B. B
- C. 1
- D. A·B
Answer
A. F = A. Take A out: F = A·(B + B') by the distributive law. B + B' = 1 by the complement law. A·1 = A by the identity law. B does not matter at all. Checked, together with the earlier simplifications:
from itertools import product
# quiz: F = AB + AB' ; and the step-by-step simplification of the majority SOP
print("AB + AB' == A:", all(((a & b) | (a & (1 - b))) == a for a, b in product((0, 1), repeat=2)))
sop = lambda A, B, C: ((1-A)&B&C) | (A&(1-B)&C) | (A&B&(1-C)) | (A&B&C)
print("A'BC + AB'C + ABC' + ABC == AB + BC + AC:",
all(sop(a, b, c) == ((a & b) | (b & c) | (a & c)) for a, b, c in product((0, 1), repeat=3)))
pos = lambda A, B, C: (A|B|C) & (A|B|(1-C)) & (A|(1-B)|C) & ((1-A)|B|C)
print("POS ΠM(0,1,2,4) == SOP Σm(3,5,6,7):",
all(pos(a, b, c) == sop(a, b, c) for a, b, c in product((0, 1), repeat=3)))
AB + AB' == A: True
A'BC + AB'C + ABC' + ABC == AB + BC + AC: True
POS ΠM(0,1,2,4) == SOP Σm(3,5,6,7): True
Interview questions
- Why are NAND and NOR called universal gates? Each alone can build NOT, AND and OR, and therefore any circuit.
- How many NAND gates for NOT, AND, OR, XOR? 1, 2, 3, 4.
- State De Morgan's theorem. (AB)' = A' + B' and (A + B)' = A'B': break the bar, change the sign.
- SOP vs POS? SOP ORs together AND terms from the 1 rows (minterms); POS ANDs together OR terms from the 0 rows (maxterms).
- Why does a K-map use Gray code order? So neighbouring cells differ in one variable, which is what lets a group drop that variable.
- Half adder vs full adder? A half adder adds 2 bits (S = A ⊕ B, C = AB); a full adder adds 3 bits including carry-in (S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B)).
- What is the drawback of a ripple carry adder, and the fix? The carry ripples through every stage, so delay grows with width; carry lookahead computes carries in parallel from generate and propagate signals.
- MUX vs DEMUX vs decoder vs encoder? MUX: many in, one out by select lines. DEMUX: one in, one of many out. Decoder: n bits to one of 2ⁿ lines. Encoder: one of 2ⁿ lines to n bits.
- Combinational vs sequential? Combinational output depends only on present inputs; sequential depends also on stored state, which needs feedback and usually a clock.
- Latch vs flip-flop? A latch is level-triggered (responds while enabled); a flip-flop is edge-triggered (responds only at a clock edge).
- Why is S = R = 1 forbidden in an SR latch? It forces Q = Q' = 0, and releasing both together causes a race with an unpredictable result.
- Ripple vs synchronous counter? Ripple: each flip-flop is clocked by the previous one, simple but delays add up. Synchronous: one shared clock, all change together, faster.
Glossary
| Term | Plain meaning | Example |
|---|---|---|
| Bit | One binary digit, 0 or 1 | a single wire is 0 or 1 |
| Transistor | A tiny electronic switch turned on or off by a voltage | millions form a chip |
| Logic level | The voltage range that counts as 1 (high) or 0 (low) | high voltage = 1 |
| Logic gate | A circuit that turns input bits into one output bit by a fixed rule | AND, OR, NOT |
| Boolean expression | A formula of variables and AND/OR/NOT | AB + C' |
| Truth table | A list of every input combination and its output | 2 inputs → 4 rows |
| AND gate | Output 1 only if all inputs are 1 | locker: both keys; 1·1 = 1, 1·0 = 0 |
| OR gate | Output 1 if at least one input is 1 | doorbell front or back; 0 + 1 = 1 |
| NOT gate (inverter) | Output is the opposite of the input | night lamp; 1' = 0 |
| NAND gate | NOT of AND: 0 only when all inputs are 1 | NAND(1, 1) = 0 |
| NOR gate | NOT of OR: 1 only when all inputs are 0 | NOR(0, 0) = 1 |
| XOR gate | 1 when the inputs differ | 1 ⊕ 0 = 1, 1 ⊕ 1 = 0 |
| XNOR gate | 1 when the inputs are equal (equality checker) | XNOR(1, 1) = 1 |
| Gate symbol, bubble | The standard drawing of a gate; a small circle (bubble) on it means NOT | AND: "D" shape; NAND = AND + bubble |
| Universal gate | A gate that can build every other gate alone | NAND, NOR |
| Boolean algebra | Algebra on 0 and 1 with AND (·), OR (+), NOT (') | A + A' = 1 |
| Identity law | A + 0 = A, A·1 = A | OR with 0 changes nothing |
| Null (domination) law | A + 1 = 1, A·0 = 0 | one 0 kills an AND |
| Idempotent law | A + A = A, A·A = A | ABC + ABC = ABC |
| Complement law | A + A' = 1, A·A' = 0 | B + B' = 1 |
| Involution law | (A')' = A | two NOTs cancel |
| Commutative / associative laws | Order and grouping do not matter | AB = BA |
| Absorption law | A + AB = A, A(A + B) = A | alarm: DA + DAN = DA |
| Distributive law | A(B + C) = AB + AC and A + BC = (A + B)(A + C) | A(B + B') = AB + AB' |
| Duality | Swap + with · and 0 with 1 to get another true law | A + 0 = A ↔ A·1 = A |
| De Morgan's theorem | (AB)' = A' + B', (A + B)' = A'B' | "not (rain and cold)" = "no rain or not cold" |
| Proof by truth table | Proving a law by checking every input row | the De Morgan demo |
| Minterm | AND of all variables, 1 for exactly one row (0 → primed) | row 3 = 011 → A'BC |
| Maxterm | OR of all variables, 0 for exactly one row (1 → primed) | row 4 = 100 → A' + B + C |
| SOP (sum of products) | OR of AND terms; canonical form = Σ of minterms | Σm(3, 5, 6, 7) |
| POS (product of sums) | AND of OR terms; canonical form = Π of maxterms | ΠM(0, 1, 2, 4) |
| Karnaugh map (K-map) | Truth table drawn as a Gray-ordered grid for grouping 1s | judges → AB + BC + AC |
| Gray code order | Order where neighbours differ in one bit | 00 01 11 10 |
| Prime implicant | A K-map group that cannot be made bigger | BC in the judges' map |
| Essential prime implicant | A prime implicant covering a 1 no other group covers | AB, BC, AC all essential |
| Don't-care condition (X) | Input that never happens; use as 0 or 1 freely | BCD codes 10 to 15 |
| BCD (binary-coded decimal) | One decimal digit stored in 4 bits | 7 = 0111 |
| Combinational circuit | Output depends only on present inputs | adder, MUX |
| Sequential circuit | Output depends on inputs and stored past state | flip-flop, counter |
| Half adder | Adds 2 bits: S = A ⊕ B, C = AB | 1 + 1 → S 0, C 1 |
| Full adder | Adds 3 bits: S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B) | 1 + 1 + 1 → S 1, C 1 |
| Carry-in / carry-out | Carry entering a column from the right / leaving to the left | 200 + 100: carry-out 1 |
| Ripple carry adder | Full adders chained so each carry-out feeds the next carry-in | 27 + 14 = 41 |
| Propagation delay | Time a gate takes to update its output after inputs change | ripple delay grows with bits |
| Carry lookahead | Computing all carries in parallel from G = AB and P = A ⊕ B | C1 = G0 + P0C0 |
| Multiplexer (MUX) | Many inputs → one output, chosen by select lines | TV remote, 4-to-1 |
| Select line | Control input whose bits number the input/output to use | 2 lines pick 1 of 4 |
| Demultiplexer (DEMUX) | One input → one of many outputs | railway junction |
| Decoder | n input bits → exactly one of 2ⁿ lines is 1 | 2-to-4: 10 → [0, 0, 1, 0] |
| Encoder / priority encoder | One active line of 2ⁿ → its n-bit number / highest active line wins | line 2 → 10 |
| Feedback, state (Q) | Wiring an output back into an input; the bit a memory circuit stores | SR latch loop; Q = 1 after SET |
| Latch | Level-triggered 1-bit memory | SR latch from 2 NORs |
| SR latch / flip-flop | Set/reset memory; Q+ = S + R'Q with SR = 0 | S = 1 → Q = 1 |
| Forbidden state | Input that breaks a circuit's rules | S = R = 1 → Q = Q' = 0 |
| Race condition | Result depends on which signal changes first | releasing S, R together |
| Clock signal | A steady 0,1,0,1 square wave that times the circuit | the "heartbeat" |
| Clock period / frequency | Time of one 0-1 cycle / cycles per second | half the period high |
| Clock edge | The instant the clock changes: rising (0→1) or falling (1→0) | D copied on the rising edge |
| Flip-flop | Edge-triggered 1-bit memory | D flip-flop |
| D flip-flop | Q+ = D at each edge | stores a data bit |
| JK flip-flop | Q+ = JQ' + K'Q; J = K = 1 toggles | J = K = 1, Q = 1 → 0 |
| T flip-flop | Q+ = T ⊕ Q; T = 1 flips | counters |
| Characteristic table | Inputs + present Q → next state Q+ | JK table above |
| Next-state equation | Formula for Q+ | Q+ = T ⊕ Q |
| Excitation table | Q → Q+ transition → inputs required | JK 0→1: J = 1, K = X |
| Race-around / master-slave | Repeated toggling of a level-triggered JK with J = K = 1 / the fix: two latches in series on opposite clock phases | J = K = 1, clock held high |
| Setup / hold time | Input must be steady just before / just after the edge | timing rules |
| Register | Flip-flops sharing a clock storing a multi-bit value | 8 D flip-flops = 1 byte |
| Shift register | Register whose bits move one place per clock edge | serial in, parallel out |
| Counter | Flip-flops that step through a sequence of states | 0, 1, ..., 7, 0 |
| Mod-N counter | Counter with N states before wrapping | mod-10 counts 0-9 |
| Ripple (asynchronous) counter | Each flip-flop clocked by the previous one's output | the 3-bit demo |
| Synchronous counter | All flip-flops share one clock | faster, more gates |
| Frequency divider | Each counter stage halves the frequency | a mod-8 counter divides by 8 |
| ALU, opcode, zero flag | CPU part doing arithmetic and logic; the bits choosing its operation; a bit that is 1 when the result is 0 | opcode 10 = ADD; 6 - 6 → Z = 1 |
Summary
- Gates: AND (all 1), OR (any 1), NOT (flip), NAND, NOR, XOR (differ), XNOR (equal). A truth table with n inputs has 2ⁿ rows.
- NAND and NOR are universal. NAND counts: NOT 1, AND 2, OR 3, XOR 4.
- Boolean laws (identity, null, idempotent, complement, involution, commutative, associative, distributive, absorption) each have a dual. De Morgan: break the bar, change the sign.
- SOP = Σ minterms (1 rows), POS = Π maxterms (0 rows). K-maps in Gray order: group 1, 2, 4, 8... neighbouring 1s, use don't-cares as 1 when it helps. Judges → AB + BC + AC.
- Half adder S = A ⊕ B, C = AB. Full adder S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B). Ripple carry is simple but slow; carry lookahead is fast.
- MUX (2ⁿ inputs, n select lines; implements any function), DEMUX, decoder (n → 2ⁿ), encoder (2ⁿ → n).
- Combinational forgets; sequential remembers via feedback. SR latch (S = R = 1 forbidden); flip-flops change at the clock edge: SR Q+ = S + R'Q, D Q+ = D, JK Q+ = JQ' + K'Q, T Q+ = T ⊕ Q.
- Registers store words; counters step through states: n flip-flops → up to 2ⁿ states, mod-N needs ⌈log₂ N⌉ flip-flops; ripple vs synchronous.
Next episode: Inside the CPU: registers, ALU, control unit and the instruction cycle. We put today's parts together, with buses and the fetch-decode-execute cycle, and run a tiny CPU.