Perfect induction is proof by trying everything. Because Boolean variables have only two values, an equation with n variables has just 2ⁿ cases. Check them all and you have a complete proof.
The method:
- Build a truth table with a row for every input combination.
- Add a column for each side of the equation.
- If the columns match in every row, the identity is true. If any row differs, that row is a counterexample and the identity is false.
It is how the basic laws are justified in the first place. For = 1: A = 0 gives 0 + 1 = 1, A = 1 gives 1 + 1 = 1. Both rows give 1, so the law holds.
Strengths: completely mechanical, impossible to fool, and a good way to rebuild a law you have forgotten.
Weakness: the table doubles with every variable. Fine for 2 or 3 variables, tedious at 5, impractical beyond that. That is why an algebraic proof using the laws is usually preferred for bigger expressions.
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |