The basic laws
Seven small rules that are always true, each proved by a truth table you can click through.
What a law is
Two expressions can look different and still be the same circuit. a ∧ b and b ∧ a are wired differently on paper and give the same output on every row of the truth table. When that happens the two expressions are equivalent, and either can be swapped for the other anywhere it appears without anything changing. A law is an equivalence that holds no matter what the letters stand for, so it can be used again and again on any expression. The laws are how a big expression is turned into a smaller one that does the same job, which in a circuit means fewer gates.
This lesson takes the seven simplest laws. Each has a one-line reason, and each is proved by a truth table you can click through. The names are the ones the laws page on this site uses; other books sometimes use different ones, and those are noted where it matters.
Identity and annulment: the constants
Identity: a ∧ 1 = a and a ∨ 0 = a. ANDing with 1 changes nothing, because the AND's output is then decided entirely by a. ORing with 0 changes nothing, because a 0 adds nothing to an OR. In a circuit, an AND gate with one input tied to 1 is just a wire.
Annulment: a ∧ 0 = 0 and a ∨ 1 = 1. A single 0 into an AND forces the output to 0 whatever a is, and a single 1 into an OR forces it to 1. Some books call this the null law or the domination law. It is the reason a wire stuck at the wrong value can switch off a whole section of a circuit.
Idempotence and complement: a signal with itself
Idempotence: a ∧ a = a and a ∨ a = a. The word means "same power": doing the operation with the same signal twice is no different from once. Feed one wire into both inputs of an AND gate and you have built a wire.
Common mistake: a ∨ a is not 2a
In ordinary algebra a + a is 2a, and habit wants to write the same here. There is no 2 in boolean algebra. The only values are 0 and 1, and 1 ∨ 1 is 1. So a ∨ a is a, a ∧ a is a, and there is nothing to carry or double. Whenever school algebra and boolean algebra disagree, the truth table decides, and the truth table has only two rows here.
Complement: a ∧ ¬a = 0 and a ∨ ¬a = 1. Exactly one of a and ¬a is 1 at any moment, so the AND can never fire and the OR always does. This law is what makes a term vanish, or an expression collapse to a constant, in the middle of a simplification.
Double negation: two NOTs cancel
Double negation: ¬¬a = a. Inverting a signal twice gives it back. Some books call this involution. It looks too obvious to need a name, but it is used constantly, because other laws often leave two NOTs stacked on one letter and this is what tidies them away.
Commutativity and associativity: order and grouping
Commutativity: a ∧ b = b ∧ a and a ∨ b = b ∨ a. Swapping the inputs of a gate changes nothing, because a gate has no idea which of its inputs is which.
Associativity: (a ∧ b) ∧ c = a ∧ (b ∧ c) and the same for OR. When the same operation is used twice in a row, it does not matter which pair is done first, so the brackets can be dropped and a ∧ b ∧ c means the same whichever way it is grouped. This is why a three-input AND gate is a sensible thing to draw, and why a wide OR can be built from a chain of two-input ones.
How a truth table proves a law
A law is a claim about every possible input, so to prove one you check every possible input. With one letter there are two rows, with two letters four, with three letters eight: 2n rows for n letters, as you saw in the first stage. Work out both sides on every row. If the two columns match all the way down, the law is proved, and not just tested, because there are no other cases to try.
Worked example. Prove that a ∨ ¬a = 1.
There is one letter, so two rows. When a = 0: ¬a is 1, and 0 ∨ 1 is 1. When a = 1: ¬a is 0, and 1 ∨ 0 is 1. The left side is 1 on both rows, and the right side is the constant 1, which is 1 on both rows too. The columns match, so the law holds. That is the whole proof: two rows, no cleverness needed.
Why?: if a table settles it, why learn laws?
Because a table only answers yes or no about two expressions you already have. It cannot tell you what the smaller expression is; it can only confirm one once you have guessed it. The laws are how you find it. They also scale: a table for ten inputs has 1024 rows, but a law is one line whatever the number of inputs.
What to remember
- Equivalent expressions have the same truth table. A law is an equivalence that always holds.
- Identity: 1 in an AND or 0 in an OR changes nothing. Annulment: 0 in an AND or 1 in an OR decides everything.
- Idempotence: a with itself is a. Complement: a with ¬a is 0 for AND and 1 for OR.
- Double negation: two NOTs cancel. Commutativity: order does not matter. Associativity: grouping does not matter.
- A truth table with all 2n rows checked is a complete proof.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
Simplify this expression as far as it goes.
¬¬d
Already know this? and come back to the quiz any time.