There are three basic tools in boolean algebra that when used together, can help you solve complex logical problems or puzzles: operators, laws, and truth tables. This is the opening topic of Wladston Ferreira Filho’s Computer Science Distilled. Another excellent resource on the topic is this collection over at Electronics Tutorials. They have a nice set of examples that will walk through how to use these tools step-by-step. The wikipedia page is also good, but see my note on notation.
Operators
These are the basic building blocks of boolean algebra functions. In circuitry, they are logic gates. In programming, they are boolean operators. There are three basic operators from which more complex operators can be constructed: NOT, AND, and OR.
NOT operator
NOT is the negative of a term. In boolean algebra NOT is denoted either by a bar above the affected term(s) or “NOT” in all caps.
(e.g. NOT true = false)
AND operator
AND is only true when terms on both sides are true. In boolean algebra AND is denoted either by a multiplication of term(s) or “AND” in all caps.
(e.g. true • false = false)
OR operator
OR is true when at least one term on either side is true. In boolean algebra OR is denoted either by an addition of term(s) or “OR” in all caps.
(e.g. true + false = true)
Others
NAND (an AND followed by a NOT)
NOR (an OR followed by a NOT)
X-OR (an OR that is false if both inputs are true)
A note on notation
I prefer the + and • symbols for OR and AND. These are what were used when I was taught. You may see them as ∧ and ∨, also. I avoid this notation, because ∧ is used to denote the X-OR operator in many programming languages. For me the + and • symbols are also easier to remember too, because they correspond to the addition and multiplication operators you would use in probability problems involving multiple independent events.
Laws of Boolean Algebra
| Law | Expression |
|---|---|
| Annulment | A + 1 = 1 |
| Identity | A + 0 = A |
| Identity | A • 1 = A |
| Annulment | A • 0 = 0 |
| Idempotent | A + A = A |
| Idempotent | A • A = A |
| Double Negative | NOT Ā = A |
| Complement | A + Ā = 1 |
| Complement | A • Ā = 0 |
| Commutative | A + B = B + A |
| Commutative | A • B = B • A |
| de Morgan's Theorem | NOT (A + B) = (NOT A) • (NOT B) |
| de Morgan's Theorem | NOT (A • B) = (NOT A) + (NOT B) |
| Distributive | A • (B + C) = A • B + A • C |
| Distributive | A + (B • C) = (A + B) • (A + C) |
| Absorptive | A + (A • B) = A |
| Absorptive | A • (A + B) = A |
| Associative | A + (B + C) = (A + B) + C = A + B + C |
| Associative | A • (B • C) = (A • B) • C = A • B • C |
These laws behave similarly to those of the algebra taught in grade school. They are a set of rules which can be used to equate and simplify expressions. The ability to simplify complex logic comes in handy for finding a more general solution when you know what the output for each case should be. It can also help identify redundant logic. By simplifying your logic, your code may become cleaner.
Truth Tables
A truth table is simply a list of all inputs and the corresponding outputs for a given boolean expression. For values within the table 0 is used to represent false, and 1 for true (low and high, respectively, if you are doing hardware). To ensure all possible combinations of inputs are accounted for, it is common practice to list inputs by counting in binary. Then you can fill in each output by doing the operation. For example, here is the truth table for an OR operation:
| A | B | A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Truth tables help check to make sure a solution is valid before it is implemented. By forcing all states to be accounted for, you reduce the chance of incorrect behavior slipping into code or hardware unnoticed.