Boolean Algebra: Axioms, Theorems and Proof
Simplify a logic expression one law at a time, and prove that two expressions are equal on every input row.
You Will Be Able To
- Read and write expressions in Boolean algebra notation.
- Apply the laws up to absorption, combining and consensus.
- Prove an equation by perfect induction.
- Write the dual of an expression.
- Lesson
- G2.4
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A lamp controller was written as four product terms with 12 literals. A colleague replaced it with two terms and 4 literals, and nobody dared to ship it. Algebra shows that both are the same function, and a 16-row run confirms it.
- Cycle 4
The row 0100: a is 0 and b is 1, so the term a'b is 1. All three forms give 1.
- Cycle 10
The row 1010: a and c are 1. The first form gets its 1 from ab'c. The short forms get it from ac.
- Cycle 15
All 16 rows agree. The three expressions are one function, written with 12, 8 and 4 literals.
Computed from the three expressions and confirmed by the lab below. A literal is one use of a variable, plain or inverted.
Notation, Axioms and the First Theorems
Boolean algebra is the algebra of the values 0 and 1. It has three operations. Books and whiteboards write them shorter than code does.
| Operation | Algebra | SystemVerilog | Read as |
|---|---|---|---|
| AND | ab or a·b | a & b | a and b |
| OR | a + b | a | b | a or b |
| NOT | a' | ~a | not a |
AND binds tighter than OR, as times binds tighter than plus: a + bc means a + (bc).
An algebra starts from axioms: a few laws that are assumed, not proved. Mano and Ciletti use Huntington's postulates: identity, complement, commutative and distributive, each in two forms. Two more say the set is closed and holds two distinct values. Everything else follows from them.
Every other law is a theorem. It is proved from the axioms, or by checking every row. The tables below mark which is which.
The first laws need one variable. Each law comes in two forms. Swap AND with OR and swap 0 with 1, and one form turns into the other.
| Law | Kind | AND form | OR form |
|---|---|---|---|
| Identity | axiom | a·1 = a | a + 0 = a |
| Null element | theorem | a·0 = 0 | a + 1 = 1 |
| Idempotent | theorem | a·a = a | a + a = a |
| Complement | axiom | a·a' = 0 | a + a' = 1 |
| Involution | theorem | (a')' = a | (a')' = a |
Each equation was checked on every input row. Null element, idempotent and involution follow from the axioms.
This swap is called duality. The dual of a true equation is also true. So every law you learn gives you a second law for free.
Laws with Two and Three Variables
| Law | Kind | One form | Its dual |
|---|---|---|---|
| Commutative | axiom | ab = ba | a + b = b + a |
| Associative | theorem | (ab)c = a(bc) | (a + b) + c = a + (b + c) |
| Distributive | axiom | a(b + c) = ab + ac | a + bc = (a + b)(a + c) |
| Absorption | theorem | a + ab = a | a(a + b) = a |
| Combining | theorem | ab + ab' = a | (a + b)(a + b') = a |
| Simplification | theorem | a + a'b = a + b | a(a' + b) = ab |
| Consensus | theorem | ab + a'c + bc = ab + a'c | (a + b)(a' + c)(b + c) = (a + b)(a' + c) |
Each equation was checked on every input row. The dual of the distributive law has no match in ordinary algebra.
Three of these do most of the simplifying work. Combining removes a variable that appears both ways. Absorption removes a longer term that a shorter term already covers.
Consensus removes a term that the two others cover between them. In ab + a'c + bc, the term bc is 1 only when ab or a'c is already 1.
Proof by Perfect Induction
A Boolean variable has only two values. So you can prove an equation by trying every input row. This is perfect induction: a proof by truth table.
| a | b | ab | a + ab | equal to a? |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | yes |
| 0 | 1 | 0 | 0 | yes |
| 1 | 0 | 0 | 1 | yes |
| 1 | 1 | 1 | 1 | yes |
Absorption, a + ab = a, proven on all four rows.
- Neutral
- Step
- Result
- Structure
- By truth table
Evaluate both sides on all eight rows. Both give the column 00011111, so they are equal.
Follow the calls, values and waits
- data 00011111: Left side → Every row
- data 00011111: Right side → Every row
- By algebra
Multiply out the right side: aa + ac + ab + bc. Then aa = a, and a absorbs ac and ab. What stays is a + bc.
Follow the calls, values and waits
- data aa + ac + ab + bc: Right side → Laws
Read the diagram as text
- Left side: a + bc
- Right side: (a + b)(a + c)
- Every row: two columns of 2^N bits
- Laws: one rewrite per step
- Equal: proven
- Left side → Every row: evaluate
- Right side → Every row: evaluate
- Every row → Equal: same column
- Right side → Laws: rewrite
- Laws → Equal: reaches the left side
A truth table always works but doubles with each variable. Algebra stays short, but you must find the steps.
A few rows are not a proof. These three equations look like laws. Each one fails on at least one row.
| Looks like | Equation | Rows that agree |
|---|---|---|
| the distributive law | a + bc = (a + b)c | 6 of 8 |
| absorption | a + a'b = a | 3 of 4 |
| consensus | ab + a'c + bc = ab + bc | 7 of 8 |
Measured on the simulator. One disagreeing row is enough to refute an equation. That row is a counterexample.
Simplify One Law at a Time
To simplify, apply one law, write the result, and repeat. After each step the truth table must be the same as before.
| Step | Expression | Law used | Literals | Output column, abcd = 0000 to 1111 |
|---|---|---|---|---|
| 0 | ab'c + abc + a'b + a'bcd' | the expression as given | 12 | 0000111100110011 |
| 1 | ac + a'b + a'bcd' | combining: ab'c + abc = ac(b' + b) = ac | 8 | 0000111100110011 |
| 2 | ac + a'b | absorption: a'b + a'b·cd' = a'b | 4 | 0000111100110011 |
The column never changes. Each step only removes literals.
Fewer literals mean fewer gate inputs, so a smaller and often faster circuit. Lesson G3.1 shows a method that finds the smallest two-level form without trial and error.
Asked in interviews
State and prove the consensus theorem.
ab + a'c + bc = ab + a'c. Proof: bc = bc(a + a') = abc + a'bc. The term abc is absorbed by ab, and a'bc is absorbed by a'c. So bc adds nothing.
What is the principle of duality?
Swap AND with OR and swap 0 with 1 in a true equation, and the result is also true. Variables and inversions stay as they are. So every theorem has a dual that needs no new proof.
How do you check that a simplification is correct?
Compare the two expressions on every input row, by hand or with a small bench. For many inputs, use an equivalence checking tool. Trying a few rows is not enough.
Try It
The module simplified holds a first try, (a & c) | b. The bench finds two rows where it differs from the original. Each is a counterexample.
In both rows a and b are 1 and c is 0. The term b alone is too generous: the original needs ~a with it.
Change the line to assign g = (a & c) | (~a & b); and run again. The bench prints equal on 16 of 16.
Try your own steps. Type any expression you believe is equal, and let the 16 rows decide.
differ at abcd = 1100: original 0, simplified 1 differ at abcd = 1101: original 0, simplified 1 equal on 14 of 16Read included file: tb.sv
// tb.sv: the equivalence bench (read-only). It tries all 16 rows.
module tb;
logic a, b, c, d;
logic f, g;
int equal = 0;
original u_f (.a(a), .b(b), .c(c), .d(d), .f(f));
simplified u_g (.a(a), .b(b), .c(c), .d(d), .g(g));
initial begin
for (int i = 0; i < 16; i++) begin
{a, b, c, d} = i[3:0];
#1;
if (f === g) equal++;
else $display("differ at abcd = %b%b%b%b: original %b, simplified %b", a, b, c, d, f, g);
end
$display("equal on %0d of 16", equal);
end
endmodule
Check Yourself
Common Mistakes
Wrong Use the second distributive law backwards: a + bc = (a + b)c.
The law gives two sums: a + bc = (a + b)(a + c). The short form is wrong on 2 of the 8 rows.
Fix OR distributes over AND into both factors. Check with a truth table when unsure.
y = (a | b) & c; // wrong for abc = 100 and 110y = (a | b) & (a | c); // equal to a | (b & c)Wrong Call two expressions equal after trying two input rows.
A wrong law can agree on most rows. The false consensus ab + a'c + bc = ab + bc agrees on 7 of 8.
Fix Compare on every row, or reach one side from the other with proven laws.
Wrong Shorten a + a'b to a.
Absorption needs the same variable in both terms: a + ab = a. With a' the law is a + a'b = a + b.
Fix Look at the polarity. a + ab = a, but a + a'b = a + b.
Wrong Drop the wrong term when you use consensus.
In ab + a'c + bc the term bc is the redundant one. It holds neither a nor a'.
Fix Find the variable that appears as x and as x'. The consensus term is made of the other literals.
Remember
- ab is AND, a + b is OR, a' is NOT. AND binds tighter than OR.
- Every law has a dual: swap AND with OR and 0 with 1.
- Combining: ab + ab' = a. Absorption: a + ab = a. Consensus: ab + a'c + bc = ab + a'c.
- Perfect induction proves an equation by checking every row. A few rows prove nothing.
- Simplify one law at a time. The truth table must stay the same after each step.