Lecture 4 was a make-up class held for one reason. At the end of Lecture 3, most groups could build the extended truth table, but many got stuck at the last step: choosing the minimum test set. So the professor spent the whole class practising that one step. This lesson reviews the method, gives two words their exact meaning, solves the XOR worksheet in full, and introduces the professor’s tool for choosing rows: the colour path.
The method from 3.5 always has the same five steps:
Exam radar: two key words. Know them exactly.
- In this course, a test set means a set that satisfies MC/DC: it contains at least one full pair in every extended column.
- A minimum test set is a test set with exactly rows, where is the number of variables.
XOR is true when A and B are different, and false when they are the same. Think of a light on a staircase with a switch at the bottom and one at the top: flipping either switch changes the light, whatever the other switch is doing.
Steps 1 and 2. Four rows in the professor’s order; the result is T in rows 2 and 3.
Steps 3 and 4. In the A column, B is fixed. Rows 1 and 3 (B = F) give F and T, so they are a pair. Rows 2 and 4 (B = T) give T and F, so they are a pair too. In the B column, A is fixed. Rows 1 and 2 (A = F) are a pair, and rows 3 and 4 (A = T) are a pair.
| Row | A | B | A XOR B | A varies | B varies |
|---|---|---|---|---|---|
| 1 | F | F | F | 3 | 2 |
| 2 | F | T | T | 4 | 1 |
| 3 | T | F | T | 1 | 4 |
| 4 | T | T | F | 2 | 3 |
So: A pairs {1, 3} and {2, 4}; B pairs {1, 2} and {3, 4}.
Exam radar: check your XOR table. The professor said that for XOR, every cell in the extended columns must be filled. Why? In XOR, changing any one input always changes the result (the staircase light). So if you see an empty cell in your XOR table, you made a mistake.
We have 2 variables, so we want rows. But one A pair plus one B pair is 4 rows. So the two pairs must share one row. This shared row is called the overlap.
The professor gave two rules for choosing:
Take the B pair {1, 2}. Stand on row 1 and look at the A column: it says 3. So the A pair is {1, 3}, and the set is {1, 2, 3}.
Now go back and stand on row 2 instead. The A column says 4. So the A pair is {2, 4}, and the set is {1, 2, 4}.
Starting from the other B pair, {3, 4}, the same walk gives {1, 3, 4} (stand on row 3) and {2, 3, 4} (stand on row 4).
Here is a nice way to see all the answers at once. Draw the 4 rows as the corners of a square. The A pairs are the vertical sides; the B pairs are the horizontal sides. A minimum test set is one A side and one B side that touch at a corner: an L shape.
A square has 4 corners, so there are 4 minimum test sets: {1, 2, 3}, {1, 2, 4}, {1, 3, 4} and {2, 3, 4}. The professor said that any one of them is a correct answer, unless the question asks you to list all of them.
Common mistake: taking half of one pair and half of another. In XOR, rows 1 and 4 both have numbers in every extended column, but {1, 4} is not a pair of anything: 1’s A partner is 3 and 4’s A partner is 2. A row “having a number” in a column does not prove that column; only a whole pair inside your set does.
For A XOR B, how many minimum test sets are there? Name two, and give one as test cases with expected results.
There are 4: {1, 2, 3}, {1, 2, 4}, {1, 3, 4} and {2, 3, 4}. Each one is an A pair and a B pair that share one row (an L shape on the square).
As test cases, {1, 2, 3} is (F, F) → F, (F, T) → T, (T, F) → T. Check: A pair {1, 3} changes F → T with only A changing ✓; B pair {1, 2} changes F → T with only B changing ✓; 3 rows ✓.
In the XOR table, start from the B pair {3, 4} and use the colour path to find two minimum test sets. Explain each step.
The colour path: stand on a row of the chosen pair and look across that row to the other extended column.
Both have 3 rows and a whole pair in each column ✓.
For A XOR B, decide for each set whether it is a test set and whether it is a minimum test set: (a) {1, 2, 3, 4}, (b) {2, 3}, (c) {2, 3, 4}.
Use the definitions: a test set has a whole pair in every extended column; a minimum test set is a test set with exactly rows.
A student solving A AND (B OR C) (pairs: A {2, 6}, {3, 7}, {4, 8}; B {5, 7}; C {5, 6}) answers {2, 5, 7, 8}, explaining: “rows 2, 7 and 8 all have numbers in the A column, so A is covered; 5 and 7 cover B; and row 5 has a number in the C column, so C is covered.” What is wrong?
The student broke the first choosing rule: always take a whole pair.
So {2, 5, 7, 8} is not an MC/DC test set, even though it has rows. A correct minimum answer is {2, 5, 6, 7}.
Build the extended table for NOT (A XOR B) (true when A and B are the same) and list all minimum test sets.
The result is the opposite of XOR: T in rows 1 and 4, F in rows 2 and 3. Changing any one input still always changes the result, so every extended cell is filled, just as in XOR.
| Row | A | B | NOT (A XOR B) | A varies | B varies |
|---|---|---|---|---|---|
| 1 | F | F | T | 3 | 2 |
| 2 | F | T | F | 4 | 1 |
| 3 | T | F | F | 1 | 4 |
| 4 | T | T | T | 2 | 3 |
The pairs are the same as for XOR (A {1, 3}, {2, 4}; B {1, 2}, {3, 4}), because a pair only needs the result to change, not to go in a particular direction. So the same square appears, and there are 4 minimum sets: {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}. Only the expected results differ, e.g. {1, 2, 3} = (F, F) → T, (F, T) → F, (T, F) → F.
Build the extended table for A XOR B XOR C (true when an odd number of inputs are true). Use the colour path, starting from the A pair {1, 5}, to find a minimum test set.
Truth table and result. Count the T’s in each row: odd → T, even → F.
Extended columns. Flipping any single input changes the number of T’s by one, so it always flips the result: every cell is filled. A partners are 4 rows apart, B partners 2 rows apart within each half, C partners neighbours.
| Row | A | B | C | Result | A varies | B varies | C varies |
|---|---|---|---|---|---|---|---|
| 1 | F | F | F | F | 5 | 3 | 2 |
| 2 | F | F | T | T | 6 | 4 | 1 |
| 3 | F | T | F | T | 7 | 1 | 4 |
| 4 | F | T | T | F | 8 | 2 | 3 |
| 5 | T | F | F | T | 1 | 7 | 6 |
| 6 | T | F | T | F | 2 | 8 | 5 |
| 7 | T | T | F | F | 3 | 5 | 8 |
| 8 | T | T | T | T | 4 | 6 | 7 |
Colour path. Take A pair {1, 5}. Stand on row 1 and look across: the B column says 3, so take {1, 3}; the C column says 2, so take {1, 2}. The set is {1, 2, 3, 5}, with row 1 shared by all three pairs.
As test cases: (F,F,F) → F, (F,F,T) → T, (F,T,F) → T, (T,F,F) → T. Check: 4 rows , and A {1, 5}, B {1, 3}, C {1, 2} are all whole pairs ✓. (Many other minimum sets exist, because every column has four pairs; any one is correct unless all are asked for.)
A student’s XOR table has an empty cell in row 3 of the “A varies” column. Without looking at the rest of the table, how do you know it is wrong?
In XOR, changing any one input always changes the result: if A and B were different they become equal, and vice versa. So every row has a partner in every extended column, and no cell can be empty.
Row 3 is (T, F) → T. Its A partner is row 1, (F, F) → F: only A changed and the result changed, so the cell must contain 1.