The algebra of 0s and 1s: laws, De Morgan's theorem, and turning any truth table into an expression you can simplify.
Interactive·Boolean Algebra Playground
Toggle inputs and pick an operator — watch the live truth table update. Step through Boolean laws on the right.
·=0
A
B
Out
0
0
0
0
1
0
1
0
0
1
1
1
Boolean Laws
A + 0=A
Identity (OR)
Why an algebra for logic
Every gate costs chip area, power and delay, so we want the fewest gates that do the job. Boolean algebra lets you rewrite a logic expression into a simpler one that behaves identically. It works like school algebra, except that variables are only ever 0 or 1.
For example, a·b + a·b' needs two ANDs, an OR and a NOT. But whatever b is, one of those two terms matches, so the whole thing is just a. No gates at all.
> Loading the circuit…
The two lights are always equal: a·b + a·b' and plain a are the same function.
Try all four input combinations. The lights never disagree.
Flip b and notice that neither light changes. b doesn't matter.
A quick note on writing. AND is written like multiplication (ab or a·b), OR like addition (a + b), and NOT with a prime (a'). AND binds tighter than OR, as with × and +, so ab + c means (ab) + c.
The laws
You can prove each of these by checking every row of its truth table, since there are so few. Each law comes in a pair: swap AND with OR and 0 with 1, and you get the other half. That's the principle of duality, and it means you only have to learn half of them.
Law
AND form
OR form
Identity
a·1 = a
a + 0 = a
Null
a·0 = 0
a + 1 = 1
Idempotent
a·a = a
a + a = a
Complement
a·a' = 0
a + a' = 1
Involution
(a')' = a
Commutative
ab = ba
a + b = b + a
Associative
(ab)c = a(bc)
(a + b) + c = a + (b + c)
Distributive
a(b + c) = ab + ac
a + bc = (a + b)(a + c)
Absorption
a(a + b) = a
a + ab = a
De Morgan
(ab)' = a' + b'
(a + b)' = a'b'
Watch outTwo of these have no equivalent in ordinary algebra, so watch for them: a + 1 = 1, and a + bc = (a + b)(a + c). Yes, OR distributes over AND.
De Morgan's theorem, as a picture
De Morgan's theorem is the one you'll use most. To invert a whole expression, invert each variable and swap AND with OR. "Not both" means the same as "not the first, or not the second".
> Loading the animation…
Try the Not equal preset. A common mistake is to break the bar without swapping the operator, and (AB)' is not A'B'. The two pictures show the difference at once.
Practice
What is (a + b'c)' by De Morgan?
Simplifying step by step
There's no single recipe, but these moves cover most problems: factor out what terms share, use a + a' = 1 and a + a'b = a + b, and multiply out only when you must. Press Play and read each law as it's used.
Algebra is half the story. Often you start from a truth table, describing what you want, and need an expression. There's a mechanical way that always works.
A minterm is an AND of all the variables, each inverted or not, that is 1 on exactly one row. For the row A=0, B=1, C=0 the minterm is A'BC'. Number the rows by their binary value, and that one is m₂.
Row
A
B
C
F
Minterm
Maxterm
0
0
0
0
0
A'B'C'
A + B + C
1
0
0
1
1
A'B'C
A + B + C'
2
0
1
0
1
A'BC'
A + B' + C
3
0
1
1
0
A'BC
A + B' + C'
4
1
0
0
0
AB'C'
A' + B + C
5
1
0
1
0
AB'C
A' + B + C'
6
1
1
0
1
ABC'
A' + B' + C
7
1
1
1
0
ABC
A' + B' + C'
Sum of products (SOP): OR together the minterms of the rows where F = 1. F = A'B'C + A'BC' + ABC', written F = Σm(1, 2, 6).
Product of sums (POS): AND together the maxterms of the rows where F = 0. A maxterm is an OR that is 0 on exactly one row. F = ΠM(0, 3, 4, 5, 7).
TipGoing between the two is quick: the numbers in Σ and Π together list every row exactly once. In a maxterm, a variable is inverted where its bit is 1, the opposite of a minterm.
Now simplify Σm(1, 2, 6)
A'B'C + A'BC' + ABC'the sum of minterms
Step 1 of 3
Spotting which minterms to combine gets hard by eye, and the next chapter's K-maps turn it into a picture.
Consensus, and counting functionsGATE: fine to skip at first
The consensus theorem removes a term you might not suspect is redundant: AB + A'C + BC = AB + A'C. The term BC adds nothing, because when B and C are both 1, either A or A' must also be 1.
Proof of the consensus theorem
AB + A'C + BCthe starting point
Step 1 of 5
A truth table with n inputs has 2ⁿ rows, and each row's output can be 0 or 1, so there are 2^(2ⁿ) different Boolean functions of n variables. For n = 2 that's 16, and for n = 3 it's 256.
A function is self-dual if swapping AND with OR and 0 with 1 gives the same function. Equivalently, inverting all the inputs inverts the output. Half of each truth table then fixes the other half, so there are 2^(2ⁿ⁻¹) of them. Majority is the classic example.
Practice · GATE-style
How many different Boolean functions of 3 variables are there?
Practice · GATE-style
Which is equal to XY + X'Z + YZ?
Practice · GATE-style
How many self-dual functions of 3 variables are there?