A nested Boolean expression becomes easy when you evaluate it in small pieces, one column at a time. Every expression uses only NOT, AND and OR, and each column applies just one of them.
This lesson opens Boolean logic and representation. The basics are in reading Boolean expressions and truth tables.
How do I build the table?
Follow four steps, and do not skip the second.
- Write the inputs and list all 2ⁿ combinations in binary counting order.
- Split the expression into its smallest parts, and give each a helper column.
- Evaluate each helper column from left to right, using only the columns before it.
- The last column is the expression. Copy it out as the answer.
The order of evaluation is brackets first, then NOT, then AND, then OR.
Worked example
Build the table for X = (A AND B) OR NOT C. The inputs are A, B and C, so there are 8 rows. The helper columns are A AND B and NOT C.
| A | B | C | A AND B | NOT C | X |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |
X is 1 in five rows, and it is 0 only when C is 1 and A AND B is 0. Read the column out loud to test it: X is false exactly when C is on and A and B are not both on.
The mistake: ignoring precedence
The common slip is to read the expression left to right. Take A AND (B OR NOT C), which differs from the one above only in its brackets.
Evaluate the same three rows with the two expressions.
| A | B | C | (A AND B) OR NOT C | A AND (B OR NOT C) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
In row 1, A is 0, so the second expression is 0 whatever is inside the bracket. The first expression is 1 because NOT C is 1. The two expressions give different answers in a row where C is 0 and A is 0, so brackets change the function, not only its appearance.
Checking your table
Three quick checks catch most errors.
- Count the rows: is there one row for every input combination?
- Test one row by hand, from the original expression and not from your columns.
- Check that no helper column uses a value from a column to its right.
Use the Boolean expression and truth-table explorer to compare your final column after you have finished.
Check yourself
Build the truth table for Y = NOT (A OR B) AND C. List all rows and give the number of rows where Y is 1.
Answer
There are 3 inputs, so 8 rows. Helper columns: A OR B, NOT (A OR B), then Y.
| A | B | C | A OR B | NOT (A OR B) | Y |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Y is 1 in exactly 1 row: A = 0, B = 0, C = 1. The NOT applies to the whole bracket (A OR B), so it is evaluated after the OR inside the bracket.
What to study next
The next lesson uses the same tables to test a claim: checking a claimed equivalence with all input combinations. Then test the cluster in the integrated practice set.
If you want a teacher to check your helper columns with you, see online one-to-one Computer Science tuition.