Learn › Topic 2

Boolean algebra: laws, De Morgan and simplification

7 min read · bitGateLab Team

Boolean algebra is the language used to describe and transform digital circuits. Every expression corresponds to an arrangement of gates, and every law you apply to simplify it translates into gates you save. Here you will review the postulates, the most useful laws, De Morgan's theorems and how to simplify an expression step by step, justifying every move.

Variables and operations

A Boolean variable takes only the values 0 and 1. There are three basic operations: the complement (A, NOT gate), the logical product (A·B or AB, AND gate) and the logical sum (A + B, OR gate). When there are no parentheses, the order of precedence is: complement first, then product, and sum last. So A + BC means A + (B·C), just as in ordinary algebra.

Postulates

The whole algebra rests on a handful of postulates. Notice that they come in pairs: one for the sum and one for the product.

Postulate	Sum form	Product form
Identity element	A + 0 = A	A · 1 = A
Commutative	A + B = B + A	AB = BA
Distributive	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
Complement	A + A = 1	A · A = 0

Duality principle: if an identity is true, so is the one you get by swapping + with ·, and 0 with 1 (without touching the variables or their bars). That is why every law has a "twin" version. Look at the distributive law of the sum, A + BC = (A + B)(A + C): it does not exist in the algebra of real numbers, but here it is perfectly valid.

Useful laws and theorems

These rules follow from the postulates, and they are the ones you will use most when simplifying:

Law	Sum form	Product form
Idempotence	A + A = A	AA = A
Null element	A + 1 = 1	A · 0 = 0
Involution	A = A
Associative	A + (B + C) = (A + B) + C	A(BC) = (AB)C
Absorption	A + AB = A	A(A + B) = A
Complement absorption	A + AB = A + B	A(A + B) = AB
Adjacency	AB + AB = A	(A + B)(A + B) = A
Consensus	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

Any of these laws can be checked with a truth table: if the two columns match in every row, the identity is true. For example, for A + AB = A: with A = 0 both sides are 0 regardless of B; with A = 1 both are 1. Complement absorption is proved like this: A + AB = (A + A)(A + B) = 1·(A + B) = A + B, using the distributive law of the sum.

De Morgan's theorems

These two theorems tell you how to "break" a long bar:

A · B = A + B (the complement of a product is the sum of the complements).
A + B = A · B (the complement of a sum is the product of the complements).

The rule of thumb: when you split the bar, change the operation that was underneath it (· to + or + to ·) and complement each term. It works for any number of variables: ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

In circuits, De Morgan says that a NAND is equivalent to an OR with bubbles on its inputs, and a NOR is equivalent to an AND with bubbles on its inputs. This is the basis for converting any design to NAND-only or NOR-only logic, as explained in logic gates.

Example 1: applying De Morgan. Simplify F = AB + C.

The long bar covers a sum: AB + C = AB · C.
Break the bar over the product: AB = A + B.
Result: F = (A + B)C = AC + BC.

Check with A = 1, B = 1, C = 0: the original gives 1 + 0 = 0; the result gives (0 + 0)·1 = 0. With A = 0, B = 1, C = 0: original 0 + 0 = 1; result (1 + 0)·1 = 1.

Step-by-step algebraic simplification

To simplify is to reduce the number of terms and literals (each appearance of a variable, complemented or not). Fewer literals mean fewer gate inputs. Pure algebra offers no single algorithm; these tactics work almost every time:

Look for pairs of terms that differ in a single variable and apply adjacency.
Factor out the common part and look for a hidden A + A = 1.
If one term is contained in another, remove it by absorption.
You can duplicate a term (idempotence) to combine it with two different neighbors.

Example 2. Simplify F = AB + AB + AB.

Factor the first two: AB + AB = A(B + B) = A·1 = A.
That leaves F = A + AB.
Complement absorption: A + AB = A + B.

F = A + B. You went from three AND gates, one three-input OR and two inverters to a single OR.

Example 3: majority function. Simplify F = ABC + ABC + ABC + ABC.

By idempotence, ABC = ABC + ABC + ABC. Write three copies so each one can be combined with a neighbor.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. It is 1 when at least two of the three inputs are 1: it is a voting circuit. You will see that it is also the carry output of the full adder.

Example 4: distributive law of the sum. Simplify F = (A + B)(A + C).

Multiply out: AA + AC + AB + BC = A + AC + AB + BC.
Factor out A: A(1 + C + B) + BC.
Null element: 1 + C + B = 1, so what remains is A + BC.

It is precisely the distributive postulate of the sum read backwards.

Common mistakes

Applying De Morgan without changing the operation: AB is not AB, it is A + B.
"Cancelling" terms as in ordinary algebra. Boolean algebra has no subtraction or division: A + B = A + C does not imply that B = C.
Forgetting precedence: A + BC is not (A + B)C.
Breaking only part of a long bar. The bar in AB + C applies to the whole sum; work from the outermost bar inwards.
Stopping too soon. After every step, check whether something can still be absorbed or whether a redundant consensus term is left.

Try it in the simulator

A correct simplification yields a circuit with exactly the same truth table as the original. The simulator lets you check this without writing out the table by hand.

In the editor, build the original circuit from one of the examples, such as AB + AB + AB, with its inputs and its output.
Generate its truth table and write it down.
On another output on the same canvas, build the simplified version (A + B) using the same inputs.
Step the inputs through every combination and watch that both outputs always match.
Ask for the simplified expression from the table and compare it with the one you obtained by hand.

Exercises

Simplify F = AB + AB + AB.
Answer
AB + AB = A. Then A + AB = A + B (complement absorption). F = A + B = AB: it is a NAND.
Simplify F = A + B.
Answer
De Morgan: A · B = AB.
Simplify F = A(A + B) + B(B + C).
Answer
By absorption, A(A + B) = A and B(B + C) = B. F = A + B.
Prove the consensus theorem: AB + AC + BC = AB + AC.
Answer
Write BC = BC(A + A) = ABC + ABC. Then AB + ABC = AB (absorption) and AC + ABC = AC (absorption). What remains is AB + AC.