Notes / Unit 5 · Module 4 · Final

Boolean Algebra and Logic Gates

Boolean algebra is the arithmetic of 0 and 1 that digital circuits run on. The exam asks you to read a circuit into an expression, write a function as minterms or maxterms from its truth table, and simplify an expression step by step, naming the law each step uses.

5.1Boolean values and operations

A Boolean variable takes one of two values: 1 or 0 (true or false, on or off, high or low). A Boolean function combines variables with operators and always outputs 0 or 1.

OR (Boolean sum): A + B is 1 when at least one input is 1: 0 + 0 = 0, every other sum is 1, and 1 + 1 = 1.
AND (Boolean product): AB, also written A · B, is 1 only when every input is 1.
NOT (complement): A′ flips the value: 0′ = 1, 1′ = 0. Some books draw an overbar or write ~A. The course uses the prime.
Literal: A variable or its complement: A, A′.
Product term: Literals ANDed together, e.g. AB′C. It is 1 only if every literal is 1.
Sum term: Literals ORed together, e.g. A + B′ + C. It is 0 only if every literal is 0.

Precedence: NOT first, then AND, then OR, just as multiplication comes before addition. A + BC′ means A + (B(C′)).

With n variables a truth table has 2ⁿ rows, listed in binary order with A as the leftmost (most significant) bit: 000, 001, … 111 for three variables.

Trap1 + 1 = 1 in Boolean algebra, not 2 and not 0. OR only asks whether anything is 1.

5.2The laws of Boolean algebra

Most laws come in an AND form and an OR form. These are the names the course uses:

Law	AND form	OR form
Identity	`1A = A`	`0 + A = A`
Null	`0A = 0`	`1 + A = 1`
Idempotent	`AA = A`	`A + A = A`
Inverse	`AA′ = 0`	`A + A′ = 1`
Commutative	`AB = BA`	`A + B = B + A`
Associative	`(AB)C = A(BC)`	`(A + B) + C = A + (B + C)`
Distributive	`A + BC = (A + B)(A + C)`	`A(B + C) = AB + AC`
Absorption	`A(A + B) = A`	`A + AB = A`
De Morgan's	`(AB)′ = A′ + B′`	`(A + B)′ = A′B′`
Double Complement	`(A′)′ = A`	—

Two more rules come up constantly. Both follow from the laws above: A + A′B = A + B and (A + B)(A + C) = A + BC. The second is the distributive law read backwards.

Duality: swap every AND with OR and every 0 with 1, and leave the variables alone. A true identity gives a true identity. The AND and OR columns above are duals of each other.

TrapOR distributes over AND in Boolean algebra (A + BC = (A + B)(A + C)), which ordinary arithmetic doesn't allow. Students who only learned the arithmetic version miss it as a simplification step.

TrapThe dual is not the complement. The dual of A + 0 = A is A · 1 = A. Priming the variables as well gives the complement.

5.3De Morgan's law and complements

De Morgan's law: the complement of a product is the sum of the complements, and the complement of a sum is the product of the complements. It works for any number of variables: (ABC)′ = A′ + B′ + C′.

To complement a whole function, complement every variable and swap every AND with OR (De Morgan applied all the way through). Keep the original grouping in parentheses.

Worked example

Complement F = x + y′z

1Swap the operators: the OR becomes AND, the product y′z becomes a sum.
2Complement each literal: x → x′, y′ → y, z → z′.
3F′ = x′(y + z′).

TrapTwo changes, every time: flip the operator AND prime each literal. (AB)′ = A′B′ (forgot to change AND to OR) and (AB)′ = A′ + B (forgot a prime) both lose the mark.

TrapA literal that is already primed loses its prime: (A′B)′ = A + B′, by double complement.

5.4Logic gates

Every circuit is built from gates. AND, OR and NOT are the three basic ones. The rest are combinations of them:

Gate	Symbol	Expression	Output is 1 when
NOT (inverter)	Triangle with a bubble	`X = A′`	the input is 0
AND	D shape	`X = AB`	all inputs are 1
OR	Curved shield	`X = A + B`	at least one input is 1
NAND	AND with an output bubble	`X = (AB)′`	not all inputs are 1
NOR	OR with an output bubble	`X = (A + B)′`	every input is 0
XOR	OR with an extra curve at the input	`X = A ⊕ B = A′B + AB′`	the inputs differ
XNOR	XOR with an output bubble	`X = (A ⊕ B)′ = A′B′ + AB`	the inputs are equal

NOT · X = A′
AND · X = AB
OR · X = A + B
NAND · X = (AB)′
NOR · X = (A + B)′
XOR · X = A ⊕ B
XNOR · X = (A ⊕ B)′

A bubble on a gate means inversion. By De Morgan's law a NAND is the same as an OR with both inputs inverted (a negative-OR), and a NOR is the same as a negative-AND.

NAND and NOR are universal: either one alone can build NOT (tie both inputs together: (AA)′ = A′), then AND and OR, so it can build any circuit.

Trap(AB)′ is not A′B′. The prime over the whole product is a NAND. Priming each input separately and ANDing them gives a NOR.

5.5Reading and building circuits

Start at the inputs on the left.
Write the expression at the output of each gate, using the expressions feeding it as its inputs.
Work rightward until you reach the final gate. Its expression is the circuit's output.
For the truth table, evaluate that expression on every input row in binary order.

Worked example

The course's circuit: AND of C and D, ORed with B, ANDed with A

1First AND gate: CD.
2OR gate: B + CD.
3Final AND gate: A(B + CD).
4It is 1 when A = 1 and either B = 1 or C = D = 1, so 5 of its 16 rows are 1.

X = A(B + CD): a dot joins a wire to an input line, and a crossing without a dot is not a join

Going the other way, from an expression to a circuit, start from the innermost parentheses. Each sum or product becomes a gate, a prime over a group becomes a NAND/NOR or an inverter after the gate, and the last operator to be applied is the output gate.

TrapA NOT on an input and a bubble on a gate's output are different things. (A + B)′C puts the NOT after the OR gate. A′ + B′ inverts the inputs before it.

5.6Sum of products and product of sums

SOP (sum of products): Product terms ORed together, e.g. AB + B′CD + AC′. Built as AND gates feeding one OR gate.
POS (product of sums): Sum terms ANDed together, e.g. (A + B)(B′ + C + D). Built as OR gates feeding one AND gate.
Standard (canonical) form: Every term contains every variable of the domain, primed or not.
Minterm mᵢ: A product of all the variables that is 1 on row i only. Prime a variable where the row has a 0.
Maxterm Mᵢ: A sum of all the variables that is 0 on row i only. Prime a variable where the row has a 1.

Row	A B C	Minterm	Maxterm
0	0 0 0	`m0 = A′B′C′`	`M0 = A + B + C`
1	0 0 1	`m1 = A′B′C`	`M1 = A + B + C′`
2	0 1 0	`m2 = A′BC′`	`M2 = A + B′ + C`
3	0 1 1	`m3 = A′BC`	`M3 = A + B′ + C′`
4	1 0 0	`m4 = AB′C′`	`M4 = A′ + B + C`
5	1 0 1	`m5 = AB′C`	`M5 = A′ + B + C′`
6	1 1 0	`m6 = ABC′`	`M6 = A′ + B′ + C`
7	1 1 1	`m7 = ABC`	`M7 = A′ + B′ + C′`

Number the rows of the truth table 0 to 2ⁿ − 1 by reading the inputs as a binary number.
SOP: take the rows where F = 1, write each one's minterm and OR them: F = ∑(those rows).
POS: take the rows where F = 0, write each one's maxterm and AND them: F = ∏(those rows).
To convert between them, swap ∑ and ∏ and list the row numbers that are missing.

Worked example

F is 1 on rows 001, 100 and 111

1SOP: F = A′B′C + AB′C′ + ABC = m1 + m4 + m7, so F(A, B, C) = ∑(1, 4, 7).
2The 0 rows are 0, 2, 3, 5, 6, so F = M0M2M3M5M6 = ∏(0, 2, 3, 5, 6).
3The complement swaps them: F′ = ∑(0, 2, 3, 5, 6).

To expand a non-standard term, AND it with (X + X′) for each missing variable X. Each missing variable doubles the number of terms: in F(A, B, C) the term A becomes AB′C′ + AB′C + ABC′ + ABC. For POS, OR in XX′ and distribute.

TrapSOP uses the 1 rows and POS uses the 0 rows, and the literal rule flips between them. In a minterm a 0 bit means primed. In a maxterm a 1 bit means primed. Row 101 is AB′C as a minterm and A′ + B + C′ as a maxterm.

5.7Simplifying expressions

Every truth table has exactly one canonical form but many equivalent expressions. A simpler expression needs fewer gates, so the circuit is cheaper, uses less power and runs faster. Simplify by applying the laws one step at a time and naming each law.

Worked example

AB + A(B + C) + B(B + C)

1= AB + AB + AC + BB + BC: Distributive.
2= AB + AB + AC + B + BC: Idempotent (BB = B).
3= AB + AC + B + BC: Idempotent (AB + AB = AB).
4= AB + AC + B: Absorption (B + BC = B).
5= B + AC: Absorption (B + AB = B). Five gates are down to two.

Worked example

ABC + ABC′ + A′C

1= AB(C + C′) + A′C: Distributive (factor out AB).
2= AB · 1 + A′C: Inverse.
3= AB + A′C: Identity.

Worked example

x(x + y) = x

1= xx + xy: Distributive.
2= x + xy: Idempotent.
3= x(1 + y): Distributive (factor out x).
4= x · 1: Null.
5= x: Identity.

Worked example

(A′B)′A

1= ((A′)′ + B′)A: De Morgan's.
2= (A + B′)A: Double Complement.
3= AA + AB′: Distributive.
4= A + AB′: Idempotent.
5= A: Absorption.

Patterns worth spotting on sight: XY + XY′ = X (combine terms that differ in one variable), X + XY = X (absorption), X + X′Y = X + Y, and XY + X′Z + YZ = XY + X′Z (the YZ term is redundant). A Karnaugh map does the same combining visually, grouping adjacent 1s in blocks of 1, 2, 4 or 8.

TrapClear the primes over groups (De Morgan) before you try to absorb anything. In (XY)′ + X the X does not absorb the first term. It becomes X′ + Y′ + X = 1.

TrapA + A′B is A + B, not B. The A′ doesn't cancel the A. Check any shortcut on the row A = 1.

Check yourself

Answer these out loud, without scrolling up. Any you can't, reread that section — then let the drill mark you.

1.Write both forms of De Morgan's law, and complement F = AB′ + C.
2.Name the law behind each of these: A + AB = A, A + A′ = 1, A · 0 = 0, (A′)′ = A.
3.A circuit has G1 = NAND(A, B), G2 = NOT(C) and X = OR(G1, G2). Write X as an expression and give its value when A = B = C = 1.
4.For F(A, B, C) = ∑(1, 3, 6), write the minterm for row 6, the maxterm for row 0, and F as a product of maxterms.
5.Simplify AB + A(B + C) + B(B + C), naming the law at each step.
6.How do you make a NOT gate from a NAND gate, and why does that make NAND universal?