The professor told the class that this question came from a past exam, so study it carefully. It combines everything from Lectures 3 and 4: a four-variable truth table, extended columns, checking a given set (with the size trap from 4.2), and finding a new minimum set with the colour path (4.1).
Past exam question. Given the expression , determine whether the following test cases satisfy MC/DC coverage. If they do not, find a minimum MC/DC test set.
Test case A B C D Z TC1 T T F F F TC2 T F F F T TC3 F T F F F TC4 F T F T T TC5 F T T F T
There are 4 variables, A, B, C and D. So a minimum test set needs rows. The given set has 5 rows, so the size is OK. But remember the size trap (4.2): we must still check the pairs.
Four variables give rows, in the professor’s order (D changes every row, C every 2, B every 4, A every 8). To fill Z quickly, the professor made two helper columns, one for each part of the expression:
| Row | A | B | C | D | A AND NOT B | C XOR D | Z |
|---|---|---|---|---|---|---|---|
| 1 | F | F | F | F | F | F | F |
| 2 | F | F | F | T | F | T | T |
| 3 | F | F | T | F | F | T | T |
| 4 | F | F | T | T | F | F | F |
| 5 | F | T | F | F | F | F | F |
| 6 | F | T | F | T | F | T | T |
| 7 | F | T | T | F | F | T | T |
| 8 | F | T | T | T | F | F | F |
| 9 | T | F | F | F | T | F | T |
| 10 | T | F | F | T | T | T | T |
| 11 | T | F | T | F | T | T | T |
| 12 | T | F | T | T | T | F | T |
| 13 | T | T | F | F | F | F | F |
| 14 | T | T | F | T | F | T | T |
| 15 | T | T | T | F | F | T | T |
| 16 | T | T | T | T | F | F | F |
Match each test case to its row:
| Test case | A | B | C | D | Z | Row |
|---|---|---|---|---|---|---|
| TC1 | T | T | F | F | F | 13 |
| TC2 | T | F | F | F | T | 9 |
| TC3 | F | T | F | F | F | 5 |
| TC4 | F | T | F | T | T | 6 |
| TC5 | F | T | T | F | T | 7 |
So the given set is {5, 6, 7, 9, 13}. (Notice that the Z values given in the question agree with the table, a cheap check worth doing.)
Finding rows fast: think of T as 1 and F as 0. Then
For TC1 (T, T, F, F): . This shortcut works because the professor’s row order is simply counting in binary. In the exam, still confirm the row in your table.
Use the usual rule: one variable varies, the other three are fixed. A partners are 8 rows apart, B partners 4 apart, C partners 2 apart, D partners are neighbours. Bold rows are the given test cases.
| Row | A | B | C | D | Z | A varies | B varies | C varies | D varies |
|---|---|---|---|---|---|---|---|---|---|
| 1 | F | F | F | F | F | 9 | 3 | 2 | |
| 2 | F | F | F | T | T | 4 | 1 | ||
| 3 | F | F | T | F | T | 1 | 4 | ||
| 4 | F | F | T | T | F | 12 | 2 | 3 | |
| 5 | F | T | F | F | F | 7 | 6 | ||
| 6 | F | T | F | T | T | 8 | 5 | ||
| 7 | F | T | T | F | T | 5 | 8 | ||
| 8 | F | T | T | T | F | 6 | 7 | ||
| 9 | T | F | F | F | T | 1 | 13 | ||
| 10 | T | F | F | T | T | ||||
| 11 | T | F | T | F | T | ||||
| 12 | T | F | T | T | T | 4 | 16 | ||
| 13 | T | T | F | F | F | 9 | 15 | 14 | |
| 14 | T | T | F | T | T | 16 | 13 | ||
| 15 | T | T | T | F | T | 13 | 16 | ||
| 16 | T | T | T | T | F | 12 | 14 | 15 |
Notice how different the columns are:
The given set is {5, 6, 7, 9, 13}. Start with column A, because it has the fewest pairs. It needs {1, 9} or {4, 12}. The set has 9, but not 1. It has neither 4 nor 12. So column A has no pair. The professor pointed out that you can see this by looking at column A alone.
For completeness: column B has {9, 13}, column C has {5, 7}, and column D has {5, 6}. Only A fails, but one failure is enough.
How to write the first answer: “No. The given test cases do not satisfy MC/DC, because there is no independence pair for condition A. Column A needs rows {1, 9} or {4, 12}, and neither pair is in the given set {5, 6, 7, 9, 13}.”
The question does not ask you to keep the old set, so start fresh, and follow the colour path from the column with the fewest pairs:
The new set is {1, 9, 13, 14, 15}. It has 5 rows, which is , and it has a pair in every column, so it is a minimum test set. Row 13 is the hero here: it is shared by three pairs.
| Row | A | B | C | D | Z (expected) | What it proves |
|---|---|---|---|---|---|---|
| 1 | F | F | F | F | F | with row 9: proves A |
| 9 | T | F | F | F | T | with row 1: A; with row 13: B |
| 13 | T | T | F | F | F | the shared row for B, C and D |
| 14 | T | T | F | T | T | with row 13: proves D |
| 15 | T | T | T | F | T | with row 13: proves C |
Write the final answer as true/false values with the expected output Z, not only as row numbers: the professor reminded the class that a test case must have both the input and the expected output.
There are 16 different minimum sets for this question. You only need to give one, unless the question asks for all of them.
Common mistake: seeing that the given set has exactly 5 rows and answering “Yes, it is a minimum MC/DC set”. The count only matters after every column has a whole pair, and here column A has none.
For , how many rows must a minimum test set have? Why?
There are variables (A, B, C, D), and a minimum MC/DC test set has rows:
So a minimum test set has 5 rows: at least one independence pair per variable, with enough overlap that four pairs fit into five rows.
For the same Z, is {4, 12, 13, 14, 16} a minimum test set?
Question 1 (pairs).
Question 2 (size). 5 rows ✓.
Yes, it is a minimum test set. As test cases: row 4 (F,F,T,T) → F, row 12 (T,F,T,T) → T, row 13 (T,T,F,F) → F, row 14 (T,T,F,T) → T, row 16 (T,T,T,T) → F.
A set has exactly rows. Does that mean it is a minimum test set?
No. First it must be a test set, with a full independence pair in every extended column. Only then does the size make it minimum.
The past exam question is an example: the given set {5, 6, 7, 9, 13} has 5 rows, exactly , but column A has no pair (it needs {1, 9} or {4, 12}), so it is not an MC/DC test set at all.
Use the row formula to find the row numbers of (F, T, T, F) and (T, F, T, T). Then read their Z values from the table.
With T = 1 and F = 0, .
Both agree with the truth table ✓.
Find a different minimum test set by following the colour path from the other A pair, {4, 12}. Give the answer as test cases with expected Z.
The set is {4, 12, 14, 15, 16}, with row 16 shared by three pairs.
| Row | A | B | C | D | Expected Z |
|---|---|---|---|---|---|
| 4 | F | F | T | T | F |
| 12 | T | F | T | T | T |
| 14 | T | T | F | T | T |
| 15 | T | T | T | F | T |
| 16 | T | T | T | T | F |
Check: A {4, 12} ✓, B {12, 16} ✓, C {14, 16} ✓, D {15, 16} ✓, 5 rows ✓.
For the same Z, check each set: (a) {1, 2, 9, 13, 15}; (b) {9, 13, 14, 15, 16}; (c) {1, 9, 13, 14, 15, 16}.
Start with column A each time, since it has the fewest pairs ({1, 9}, {4, 12}).
Rows 10 and 11 of the extended table have no partner in any column. Explain why, using the helper columns.
In rows 10 (T, F, F, T) and 11 (T, F, T, F), both helper columns are true: A AND NOT B is T, and C XOR D is T. Z is an OR of the two helpers, so to make Z false, both helpers would have to become false.
Changing one variable can only affect one helper: A or B touches only A AND NOT B, and C or D touches only C XOR D. The other helper stays true, so Z stays T. No single change flips Z, so these rows have no independence partner in any column. Such rows can never be part of a pair and never need to be chosen.
A similar exam question: for , do the rows {6, 8, 10, 12, 14} satisfy MC/DC? If not, find a minimum MC/DC test set.
Count first. 4 variables, so a minimum set has 5 rows. The given set has 5 rows, but the pairs must still be checked.
Truth table and extended columns. Z is T when A and B are both T (rows 13–16) or C and D are both T (rows 4, 8, 12, 16).
| Row | A | B | C | D | Z | A varies | B varies | C varies | D varies |
|---|---|---|---|---|---|---|---|---|---|
| 1 | F | F | F | F | F | ||||
| 2 | F | F | F | T | F | 4 | |||
| 3 | F | F | T | F | F | 4 | |||
| 4 | F | F | T | T | T | 2 | 3 | ||
| 5 | F | T | F | F | F | 13 | |||
| 6 | F | T | F | T | F | 14 | 8 | ||
| 7 | F | T | T | F | F | 15 | 8 | ||
| 8 | F | T | T | T | T | 6 | 7 | ||
| 9 | T | F | F | F | F | 13 | |||
| 10 | T | F | F | T | F | 14 | 12 | ||
| 11 | T | F | T | F | F | 15 | 12 | ||
| 12 | T | F | T | T | T | 10 | 11 | ||
| 13 | T | T | F | F | T | 5 | 9 | ||
| 14 | T | T | F | T | T | 6 | 10 | ||
| 15 | T | T | T | F | T | 7 | 11 | ||
| 16 | T | T | T | T | T |
Pairs: A {5, 13}, {6, 14}, {7, 15}; B {9, 13}, {10, 14}, {11, 15}; C {2, 4}, {6, 8}, {10, 12}; D {3, 4}, {7, 8}, {11, 12}.
Check the given set {6, 8, 10, 12, 14}. A has {6, 14} ✓, B has {10, 14} ✓, C has {6, 8} and {10, 12} ✓. But D needs {3, 4}, {7, 8} or {11, 12}: 8 is present without 7, and 12 without 11. No. The rows do not satisfy MC/DC, because condition D has no independence pair.
New minimum set (colour path). Every column has three pairs, so start anywhere, e.g. A {6, 14}. Stand on row 6: column C says 8, take {6, 8}. Stand on row 8: column D says 7, take {7, 8}. Stand on row 14: column B says 10, take {10, 14}. The set is {6, 7, 8, 10, 14}:
| Row | A | B | C | D | Expected Z |
|---|---|---|---|---|---|
| 6 | F | T | F | T | F |
| 7 | F | T | T | F | F |
| 8 | F | T | T | T | T |
| 10 | T | F | F | T | F |
| 14 | T | T | F | T | T |
Check: A {6, 14}, B {10, 14}, C {6, 8}, D {7, 8}, and 5 rows ✓.