3.5 MC/DC & the Table Method

Theory: MC/DC & the Table Method

The top of the coverage ladder (3.4) left us with a dilemma: multiple condition coverage is thorough but needs $2^n$ tests, while the cheaper coverages let bugs hide behind short circuits. MC/DC is the way out, and the professor was blunt about its importance: it appears very often in the exam. This lesson explains what MC/DC asks, then teaches the table method, a five-step procedure that solves every MC/DC question the same way.

MC/DC: the Best Balance

MC/DC stands for Modified Condition/Decision Coverage. It sits in the middle of the ladder:

• stronger than the cheap coverages, because it deals with short circuits and masking;
• much cheaper than multiple condition coverage: about $n + 1$ tests instead of $2^n$.

The professor pointed out that MC/DC is trusted for safety-critical software, and that organisations such as DARPA (the research agency of the US Department of Defense) accept it.

The MC/DC rule: each condition must be shown to independently affect the outcome of the decision.

What “independently affect” means: the ATM again

Remember the ATM from 3.3: it gives money only if the PIN is correct and the balance is enough. Suppose the programmer forgot to check the PIN. How can a test catch that?

Use two tests that are identical except for the PIN:

	PIN correct?	Balance enough?	Correct ATM	Broken ATM (no PIN check)
Test 1	yes	yes	money	money
Test 2	no	yes	no money	money

Only the PIN changed, and on a correct ATM the decision changed with it. So the PIN condition has an independent effect on the decision. On the broken ATM, Test 2 gives money: bug found!

Two tests like this, which differ in one condition only and give different decisions, are called an independence pair. MC/DC needs one independence pair for every condition.

Exam radar: memorise two sentences.

1. MC/DC requires each condition to be shown to independently affect the outcome of the decision.
2. A decision with $n$ conditions needs at least $n + 1$ tests: 2 conditions → 3 tests, 3 conditions → 4 tests, 4 conditions → 5 tests.

If you cannot reach $n + 1$, try $n + 2$, then $n + 3$. But never fewer than $n + 1$.

The Table Method, Learnt on A AND B

The method has five steps, and they are the same every time. Learn them once and use them forever.

Step 1: build the truth table in the right order

Write every combination of T and F. Two conditions give $2^2 = 4$ rows.

• Every column starts with F.
• The last variable (B) changes on every row: F, T, F, T.
• The one before it (A) changes every 2 rows: F, F, T, T. (With three variables, the first one changes every 4 rows, and so on.)
• Number the rows 1, 2, 3, 4.

Exam radar: the row order rule. The professor forces this row order “for your own good and my own good”. If your rows are in a different order, your row 2 is not the professor’s row 2, and a correct answer looks wrong.

Step 2: fill the result

A AND B is true only when both are true, so only row 4 is T.

Step 3: add one extended column per condition

The rule for the “A varies” column: A varies, every other condition is fixed. Look for two rows that differ only in A; if the result changes between them, they are a pair, and you write each row’s partner row number in the other.

• A column, B fixed at F: rows 1 and 3 give F and F. No change, no pair.
• A column, B fixed at T: rows 2 and 4 give F and T. Changed: A pair {2, 4}. Write 4 in row 2 and 2 in row 4.
• B column, A fixed at F: rows 1 and 2 give F and F. No pair.
• B column, A fixed at T: rows 3 and 4 give F and T: B pair {3, 4}.

Row	A	B	A AND B	A varies	B varies
1	F	F	F
2	F	T	F	4
3	T	F	F		4
4	T	T	T	2	3

Step 4: choose the smallest set

Take at least one full pair from every extended column: A pair {2, 4} and B pair {3, 4}. Row 4 is in both; the professor calls this a cross. So we only need rows 2, 3, 4, which is $n + 1 = 3$. (Chosen rows are in bold above.)

Step 5: turn rows back into test cases

Row 2 = (F, T), row 3 = (T, F), row 4 = (T, T). So the answer is {FT, TF, TT}, with expected results F, F, T.

In ATM language: wrong PIN + enough money (no money), correct PIN + not enough money (no money), correct PIN + enough money (money).

How to write the answer: show your work. The professor said he does not trust an answer if he cannot see how you got it. So always:

• draw the full extended table;
• write the partner row numbers in the extended columns;
• mark each pair with its own colour, or with shapes (circle, triangle, star) if you have no colours;
• list the chosen rows and translate them to T and F, with the expected result.

Now A OR B

Try to predict the answer before reading on.

• The result is F only in row 1 (F, F).
• A column: rows 1 and 3 (B = F) give F and T, so A pair {1, 3}. Rows 2 and 4 are both T: no pair.
• B column: rows 1 and 2 (A = F) give F and T, so B pair {1, 2}. Rows 3 and 4: no pair.
• Row 1 is shared. Answer: rows {1, 2, 3} = {FF, FT, TF}.

Row	A	B	A OR B	A varies	B varies
1	F	F	F	3	2
2	F	T	T		1
3	T	F	T	1
4	T	T	T

A memory trick for checking

• AND: “all true” + for each condition, one case where only that one is false.
• OR: “all false” + for each condition, one case where only that one is true.

For A AND B that gives TT, FT, TF; for A OR B it gives FF, TF, FT, matching both tables. Use the trick to check an answer; in the exam, still show the full table.

The Class Worksheet: A AND (B OR C)

This was the back page of the class worksheet. Before starting, predict the shape of the answer:

• 3 conditions → $2 \times 2 \times 2 = 8$ rows;
• 3 extended columns;
• a minimum set of $n + 1 = 4$ rows.

The professor’s hint: the A column has three pairs, and the B and C columns have one pair each.

Step 1 (truth table). All columns start with F. C changes every row, B every 2 rows, A every 4 rows.

Step 2 (result). True only when A is T and at least one of B or C is T: rows 6, 7, 8. Careful: row 5 is F, because B and C are both F there.

Step 3 (extended columns).

• A varies (compare rows 1–5, 2–6, 3–7, 4–8): pairs {2, 6}, {3, 7}, {4, 8}. Three pairs, as the hint said.
• B varies (compare 1–3, 2–4, 5–7, 6–8): only {5, 7}.
• C varies (compare 1–2, 3–4, 5–6, 7–8): only {5, 6}.

Row	A	B	C	Result	A varies	B varies	C varies
1	F	F	F	F
2	F	F	T	F	6
3	F	T	F	F	7
4	F	T	T	F	8
5	T	F	F	F		7	6
6	T	F	T	T	2		5
7	T	T	F	T	3	5
8	T	T	T	T	4

Step 4 (choose). Start with the columns that give no choice. B forces {5, 7} and C forces {5, 6}, so rows 5, 6, 7 are always in. Now add one A pair that reuses a row already chosen:

• {2, 6} reuses 6 → add row 2 → {2, 5, 6, 7};
• {3, 7} reuses 7 → add row 3 → {3, 5, 6, 7};
• {4, 8} needs two new rows → 5 rows → not minimum.

The bold rows above show {2, 5, 6, 7}: A pair {2, 6}, B pair {5, 7}, C pair {5, 6}.

Step 5 (translate).

Row	A	B	C	Expected result
2	F	F	T	F
5	T	F	F	F
6	T	F	T	T
7	T	T	F	T

The other minimum answer, {3, 5, 6, 7}, is the same except that row 2 becomes row 3 = (F, T, F) → F. Both are correct.

Common mistake: before handing in, check three things. Does every column start with F, and does C change on every row? Is row 5 = F? Did you choose 4 rows, not 5? A set like {4, 5, 6, 7, 8} is still a valid MC/DC test set, but it is not minimum.

The Same Method as an Exam Checklist

1. Identify the atomic conditions. With $n$ conditions, prepare $2^n$ truth-table rows (in the professor’s order).
2. Evaluate the complete decision for every row.
3. For each condition, compare the rows that differ only in that condition.
4. Keep the pair only if the complete decision also changes.
5. Choose at least one complete independence pair for every condition, reusing overlapping rows to minimise the set.
6. Aim for $n + 1$ tests, but verify the pairs: the correct count alone does not prove MC/DC.
7. Convert the selected row numbers into input values and expected decisions.

The trap behind step 6: a five-row set for four conditions, or a four-row set for three conditions, can still fail MC/DC if one condition has no complete independence pair. Lecture 4 (4.2, 4.3) is built around exactly this trap.

Your Practice: A XOR B

The front page of the worksheet was XOR, which is true when A and B are different: (F, F) → F, (F, T) → T, (T, F) → T, (T, T) → F. Two conditions, so aim for 3 rows.

Build the extended table yourself before Lecture 4. XOR is special: it has more than one minimum set, so find as many as you can. The full solution is in 4.1.

---

Worked Examples

Exercise 1

What is the minimum number of MC/DC tests for a decision with 4 conditions? What do you do if you cannot find a set of that size?

Show solution ↓Hide solution ↑

Solution

A decision with $n$ conditions needs at least $n + 1$ tests, so with 4 conditions the minimum is

$$n + 1 = 4 + 1 = 5.$$

If no valid set of 5 exists, try 6 ($n + 2$), then 7 ($n + 3$), and so on, but never fewer than 5: with fewer rows there are not enough tests to give every condition its own independence pair.

Exercise 2

State the MC/DC rule. Then give an independence pair, in ATM terms, for the condition “balance is enough”, and explain what bug it would catch.

Show solution ↓Hide solution ↑

Solution

The rule: each condition must be shown to independently affect the outcome of the decision.

For “balance is enough”, keep the PIN fixed (correct) and change only the balance:

• Test 1: correct PIN, enough money → money comes out.
• Test 2: correct PIN, not enough money → no money.

Only the balance changed, and the decision changed: an independence pair. If the programmer forgot to check the balance, the broken ATM would give money in Test 2, so the bug is caught. (In the A AND B table this is B pair {3, 4}.)

Exercise 3

For A AND B, is {1, 2, 3, 4} an MC/DC test set? Is it minimum?

Show solution ↓Hide solution ↑

Solution

Look for a full pair from each extended column inside the set. The A column needs {2, 4}: rows 2 and 4 are both in the set ✓. The B column needs {3, 4}: both in the set ✓.

So yes, it is a test set. But it is not minimum: it has 4 rows, while the minimum is $n + 1 = 3$, namely {2, 3, 4}. Row 1 adds nothing, because it belongs to no pair.

Exercise 4

Using the professor’s row order for three conditions A, B, C, which row number is (T, F, T)? Which row is (F, T, T)?

Show solution ↓Hide solution ↑

Solution

In the professor’s order every column starts with F, C changes every row, B every 2 rows and A every 4 rows. So rows 1–4 have A = F and rows 5–8 have A = T; within each half, B = F for the first two rows and T for the next two; C alternates F, T.

• (T, F, T): A = T → rows 5–8; B = F → rows 5–6; C = T → row 6.
• (F, T, T): A = F → rows 1–4; B = T → rows 3–4; C = T → row 4.

Check with the full table: row 6 = T F T and row 4 = F T T ✓.

Exercise 5

Find a minimum MC/DC test set for A OR (B AND C). Show the full extended table.

Show solution ↓Hide solution ↑

Solution

Step 1–2. Eight rows in the professor’s order. The result is T whenever A is T (rows 5–8); when A is F it equals B AND C, so only row 4 is T. The result is F in rows 1, 2, 3.

Step 3. Compare rows that differ in one variable only:

• A varies (1–5, 2–6, 3–7, 4–8): 1–5 is F/T, 2–6 is F/T, 3–7 is F/T, 4–8 is T/T. Pairs {1, 5}, {2, 6}, {3, 7}.
• B varies (1–3, 2–4, 5–7, 6–8): only 2–4 changes (F/T). Pair {2, 4}.
• C varies (1–2, 3–4, 5–6, 7–8): only 3–4 changes (F/T). Pair {3, 4}.

Row	A	B	C	Result	A varies	B varies	C varies
1	F	F	F	F	5
2	F	F	T	F	6	4
3	F	T	F	F	7		4
4	F	T	T	T		2	3
5	T	F	F	T	1
6	T	F	T	T	2
7	T	T	F	T	3
8	T	T	T	T

Step 4. B and C have no choice: {2, 4} and {3, 4} force rows 2, 3, 4. Add an A pair that reuses one of them: {2, 6} adds row 6, or {3, 7} adds row 7 ({1, 5} would need two new rows).

Step 5. Answer: {2, 3, 4, 6} = (F,F,T) → F, (F,T,F) → F, (F,T,T) → T, (T,F,T) → T. The other correct answer is {2, 3, 4, 7}, with row 7 = (T,T,F) → T.

Check: A pair {2, 6}, B pair {2, 4}, C pair {3, 4}, and $4 = n + 1$ rows ✓. This is the mirror image of A AND (B OR C).

Exercise 6

Find all minimum MC/DC test sets for (A OR B) AND C.

Show solution ↓Hide solution ↑

Solution

Result column. The result needs C = T and at least one of A, B true: rows 4, 6, 8 are T, all others F.

Extended columns.

• A varies (1–5, 2–6, 3–7, 4–8): only 2–6 changes (F/T). Pair {2, 6}.
• B varies (1–3, 2–4, 5–7, 6–8): only 2–4 changes (F/T). Pair {2, 4}.
• C varies (1–2, 3–4, 5–6, 7–8): 1–2 is F/F (no pair), but 3–4, 5–6 and 7–8 all change. Pairs {3, 4}, {5, 6}, {7, 8}.

Row	A	B	C	Result	A varies	B varies	C varies
1	F	F	F	F
2	F	F	T	F	6	4
3	F	T	F	F			4
4	F	T	T	T		2	3
5	T	F	F	F			6
6	T	F	T	T	2		5
7	T	T	F	F			8
8	T	T	T	T			7

Choosing. A and B have no choice: {2, 6} and {2, 4} force rows 2, 4, 6. Now one C pair that reuses a chosen row:

• {3, 4} reuses 4 → add 3 → {2, 3, 4, 6} (bold above);
• {5, 6} reuses 6 → add 5 → {2, 4, 5, 6};
• {7, 8} needs two new rows → not minimum.

So there are exactly two minimum sets: {2, 3, 4, 6} and {2, 4, 5, 6}. As test cases, {2, 3, 4, 6} is (F,F,T) → F, (F,T,F) → F, (F,T,T) → T, (T,F,T) → T.

Exercise 7

Find a minimum MC/DC test set for A AND B AND C, then check it with the memory trick.

Show solution ↓Hide solution ↑

Solution

The result is T only in row 8 (T, T, T). A row and its partner must differ in one variable and in the result, so every pair must contain row 8:

• A varies: 4–8 (F,T,T vs T,T,T) gives F/T. Pair {4, 8}.
• B varies: 6–8 gives F/T. Pair {6, 8}.
• C varies: 7–8 gives F/T. Pair {7, 8}.

Row	A	B	C	Result	A varies	B varies	C varies
1	F	F	F	F
2	F	F	T	F
3	F	T	F	F
4	F	T	T	F	8
5	T	F	F	F
6	T	F	T	F		8
7	T	T	F	F			8
8	T	T	T	T	4	6	7

Every column has only one pair, so there is no choice: {4, 6, 7, 8} = FTT → F, TFT → F, TTF → F, TTT → T. Four rows $= n + 1$ ✓.

Memory trick for AND: “all true” (TTT) plus, for each condition, the case where only that one is false (FTT, TFT, TTF). Exactly the same four rows ✓.

Exercise 8

Find all minimum MC/DC test sets for (A AND B) OR C.

Show solution ↓Hide solution ↑

Solution

Result column. True when C is T (rows 2, 4, 6, 8) or when A and B are both T (rows 7, 8). False in rows 1, 3, 5.

Extended columns.

• A varies (1–5, 2–6, 3–7, 4–8): only 3–7 changes (F/T). Pair {3, 7}.
• B varies (1–3, 2–4, 5–7, 6–8): only 5–7 changes (F/T). Pair {5, 7}.
• C varies (1–2, 3–4, 5–6, 7–8): 1–2, 3–4 and 5–6 change; 7–8 is T/T. Pairs {1, 2}, {3, 4}, {5, 6}.

Row	A	B	C	Result	A varies	B varies	C varies
1	F	F	F	F			2
2	F	F	T	T			1
3	F	T	F	F	7		4
4	F	T	T	T			3
5	T	F	F	F		7	6
6	T	F	T	T			5
7	T	T	F	T	3	5
8	T	T	T	T

Choosing. A and B force rows 3, 5, 7. Add one C pair that reuses a chosen row:

• {3, 4} reuses 3 → {3, 4, 5, 7} (bold above);
• {5, 6} reuses 5 → {3, 5, 6, 7};
• {1, 2} needs two new rows → not minimum.

Answer: {3, 4, 5, 7} or {3, 5, 6, 7}. As test cases, {3, 4, 5, 7} is (F,T,F) → F, (F,T,T) → T, (T,F,F) → F, (T,T,F) → T. Check: A {3, 7}, B {5, 7}, C {3, 4}, 4 rows $= n + 1$ ✓.