The short list
Boolean algebra has many identities. For minimization you need only a few, and you need them fluently. Each one comes in a pair: swap AND with OR and 0 with 1 and you get its dual, which is also true.
| Name | AND form | OR form |
|---|---|---|
| Identity | X · 1 = X | X + 0 = X |
| Null | X · 0 = 0 | X + 1 = 1 |
| Idempotence | X · X = X | X + X = X |
| Complement | X · X = 0 | X + X = 1 |
| Distributive | X(Y + Z) = XY + XZ | X + YZ = (X + Y)(X + Z) |
| Absorption | X(X + Y) = X | X + XY = X |
| De Morgan | XY = X + Y | X + Y = X · Y |
| Combining | (X + Y)(X + Y) = X | XY + XY = X |
| Consensus | (X + Y)(X + Z)(Y + Z) = (X + Y)(X + Z) | XY + XZ + YZ = XY + XZ |
The second distributive law, X + YZ = (X + Y)(X + Z), looks wrong if you are thinking of ordinary algebra. It is true here. Prove any identity the honest way: fill in a truth table for both sides.
The one that does the work: combining
XY + XY = X
Why it is true: XY + XY = X(Y + Y) = X · 1 = X.
What it means: if two product terms are identical except that one variable appears plain in one and complemented in the other, that variable does not matter. The two terms merge into one, with one fewer literal.
In bit patterns, where a dash marks an eliminated variable:
ABC + ABC = BC 011 + 111 → -11
This is the whole game. A Karnaugh map makes combinable terms sit next to each other so you can see them. Quine–McCluskey finds them by comparing bit patterns. The Scheinman tree finds them by splitting on one variable at a time. All three are organized ways of applying XY + XY = X until it cannot be applied any more.
Worked example: the majority function, by algebra
Start from the canonical SOP of lesson 2:
M = ABC + ABC + ABC + ABC
The term ABC can combine with each of the other three, but it appears only once. Idempotence, X + X = X, lets you write it as many times as you need:
M = (ABC + ABC) + (ABC + ABC) + (ABC + ABC)
Now combine each pair:
M = BC + AC + AB
Two lessons hide in this small example. First, a minterm may be used in more than one group. Second, algebra gives you no signal that you are finished or that you chose the best pairs — which is why the systematic methods exist.
Consensus: the term you can drop
In XY + XZ + YZ, the term YZ is redundant. Whenever YZ is 1, either X = 1 and then XY is already 1, or X = 0 and then XZ is already 1. You will meet this again in the cover chart: a perfectly good prime implicant that is simply not needed.
Check yourself
- Simplify ABC + ABC.
Show answer
The terms differ only in C: AB(C + C) = AB. - Simplify A + AB. (Hint: use the second distributive law.)
Show answer
A + AB = (A + A)(A + B) = 1 · (A + B) = A + B. - Which term of AB + AC + BC is redundant, and why?
Show answer
BC, by consensus with X = A, Y = B, Z = C. So AB + AC + BC = AB + AC. - Can
0110and0101be combined?Show answer
No. They differ in two positions (the last two bits), and combining needs exactly one.0110combines with0111,0100,0010or1110. - Use De Morgan to write the complement of AB + C as a product of sums.
Show answer
Complement the OR: the complement of AB AND the complement of C. The complement of AB is A + B, so the result is (A + B)C.