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.

Three Expressions, One Truth TableOne input row per step, abcd from 0000 to 1111. Each line is the output of one form of the expression.
0123456789101112131415a b c d0000000100100011010001010110011110001001101010111100110111101111ab'c + abc + a'b + a'bcd' (12 literals)ac + a'b + a'bcd' (8 literals)ac + a'b (4 literals)
Scroll horizontally ↔
  1. Cycle 4

    The row 0100: a is 0 and b is 1, so the term a'b is 1. All three forms give 1.

  2. 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.

  3. 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.

OperationAlgebraSystemVerilogRead as
ANDab or a·ba & ba and b
ORa + ba | ba or b
NOTa'~anot 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.

LawKindAND formOR form
Identityaxioma·1 = aa + 0 = a
Null elementtheorema·0 = 0a + 1 = 1
Idempotenttheorema·a = aa + a = a
Complementaxioma·a' = 0a + a' = 1
Involutiontheorem(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

LawKindOne formIts dual
Commutativeaxiomab = baa + b = b + a
Associativetheorem(ab)c = a(bc)(a + b) + c = a + (b + c)
Distributiveaxioma(b + c) = ab + aca + bc = (a + b)(a + c)
Absorptiontheorema + ab = aa(a + b) = a
Combiningtheoremab + ab' = a(a + b)(a + b') = a
Simplificationtheorema + a'b = a + ba(a' + b) = ab
Consensustheoremab + 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.

ababa + abequal to a?
0000yes
0100yes
1001yes
1111yes

Absorption, a + ab = a, proven on all four rows.

Two Ways to Prove That Two Expressions Are EqualArrows show the path of a proof. Perfect induction compares the two truth tables. Algebra rewrites one expression into the other, law by law.
  • Neutral
  • Step
  • Result
  • Structure
CallValueReturnWaiting
Two ways to prove that two expressions are equalArrows show the path of a proof. Perfect induction compares the two truth tables. Algebra rewrites one expression into the other, law by law. neutral Left side a + bc neutral Right side (a + b)(a + c) step Every row two columns of 2^Nbits step Laws one rewrite per step result Equal proven evaluateevaluatesame columnrewritereaches the left side
  1. neutral Left sidea + bc
    • evaluate → Every row
  2. neutral Right side(a + b)(a + c)
    • evaluate → Every row
    • rewrite → Laws
  3. step Every rowtwo columns of 2^N bits
    • same column → Equal
  4. result Equalproven
  5. step Lawsone rewrite per step
    • reaches the left side → Equal
  1. 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
    1. data 00011111: Left side → Every row
    2. data 00011111: Right side → Every row
  2. 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
    1. 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 likeEquationRows that agree
the distributive lawa + bc = (a + b)c6 of 8
absorptiona + a'b = a3 of 4
consensusab + a'c + bc = ab + bc7 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.

StepExpressionLaw usedLiteralsOutput column, abcd = 0000 to 1111
0ab'c + abc + a'b + a'bcd'the expression as given120000111100110011
1ac + a'b + a'bcd'combining: ab'c + abc = ac(b' + b) = ac80000111100110011
2ac + a'babsorption: a'b + a'b·cd' = a'b40000111100110011

The column never changes. Each step only removes literals.

Before: Four Terms, Twelve Literals
abcdf
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Before: Four Terms, Twelve Literalsn5 · NOTn5=1n4 · ANDn4=0n3 · ANDn3=0n7 · ANDn7=0n6 · ANDn6=0n2 · ORn2=0n9 · NOTn9=1n8 · ANDn8=0n1 · ORn1=0n13 · NOTn13=1n12 · ANDn12=0n11 · ANDn11=0n14 · NOTn14=1n10 · ANDn10=0n0 · ORn0=0a=0b=0c=0d=0
a=0 b=0 c=0 d=0
n5 · NOTb=0 → n5=1
n4 · ANDa=0, n5=1 → n4=0
n3 · ANDn4=0, c=0 → n3=0
n7 · ANDa=0, b=0 → n7=0
n6 · ANDn7=0, c=0 → n6=0
n2 · ORn3=0, n6=0 → n2=0
n9 · NOTa=0 → n9=1
n8 · ANDn9=1, b=0 → n8=0
n1 · ORn2=0, n8=0 → n1=0
n13 · NOTa=0 → n13=1
n12 · ANDn13=1, b=0 → n12=0
n11 · ANDn12=0, c=0 → n11=0
n14 · NOTd=0 → n14=1
n10 · ANDn11=0, n14=1 → n10=0
n0 · ORn1=0, n10=0 → n0=0
Read the connections
GateKindInputsOutput
n5NOTbn5
n4ANDa, n5n4
n3ANDn4, cn3
n7ANDa, bn7
n6ANDn7, cn6
n2ORn3, n6n2
n9NOTan9
n8ANDn9, bn8
n1ORn2, n8n1
n13NOTan13
n12ANDn13, bn12
n11ANDn12, cn11
n14NOTdn14
n10ANDn11, n14n10
n0ORn1, n10n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

The expression as given. Count the gate inputs.

After: Two Terms, Four Literals
abcdf
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
After: Two Terms, Four Literalsn1 · ANDn1=0n3 · NOTn3=1n2 · ANDn2=0n0 · ORn0=0a=0b=0c=0d=0
a=0 b=0 c=0 d=0
n1 · ANDa=0, c=0 → n1=0
n3 · NOTa=0 → n3=1
n2 · ANDn3=1, b=0 → n2=0
n0 · ORn1=0, n2=0 → n0=0
Read the connections
GateKindInputsOutput
n1ANDa, cn1
n3NOTan3
n2ANDn3, bn2
n0ORn1, n2n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

The same output column with three gates and one inverter. Type your own expression to compare its table with the one above.

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
  1. 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.

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: differ at abcd = 1100: original 0, simplified 1 differ at abcd = 1101: original 0, simplified 1 equal on 14 of 16
Read 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

Predict the outputThe program compares a + b'c with (a + b')(a + c) on all eight rows. Predict the exact line it prints.
module tb;
  logic a, b, c;
  int   equal = 0;
  initial begin
    for (int i = 0; i < 8; i++) begin
      {a, b, c} = i[2:0];
      if ((a | (~b & c)) === ((a | ~b) & (a | c))) equal++;
    end
    $display("equal on %0d of 8", equal);
  end
endmodule
ConceptWhat is the dual of a + bc?
ConceptWhich term of xy + x'z + yz can be removed without changing the function?
ConceptWhich law turns ab'c + abc into ac?
ConceptWhat does a + a'b simplify to?

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.

Before
y = (a | b) & c;          // wrong for abc = 100 and 110
After
y = (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.

Practice

Report a problem with this page