6.3 Cause-Effect Graphs & the ATM Example

Theory: Cause-Effect Graphs & the ATM Example

A decision table (6.2) can still be big: $2^K$ rules before you start merging. A cause-effect graph helps you focus only on the input combinations that matter. It is a picture of the specification’s logic, and the decision table is then read straight off the picture.

The Idea

Think of starting a modern car: the key is in and your foot is on the brake are two causes; the engine starts is the effect, and it needs both causes together. A cause-effect graph draws exactly that: what can happen on the left, what results on the right, and lines saying how one leads to the other.

Causes (inputs, conditions) are nodes on the left.
Effects (outputs, actions) are nodes on the right.
Intermediate nodes in the middle make complex logic easier to draw and read.
Edges connect them, and an edge always means “if cause, then effect”.

Exam radar: the normal workflow is cause-effect graph (keep only what matters) → decision table (built from the graph) → test cases (one per rule) → optionally, code and automated tests. The professor said: the decision table does not come from nowhere. It is the product of your cause-effect graph.

The Basic Symbols

Symbol	Meaning	Read it as
Identity: a line from a to e	e follows a	if a then e
NOT: a line from a to e marked with a small ~	e follows the opposite of a	if NOT a then e
AND: lines from a and b joined by an AND node	e needs both	if a AND b then e
OR: lines from a and b joined by an OR node	e needs at least one	if a OR b then e

Diagram loads as you scroll.

You can also use NAND and NOR: an AND or OR followed by a NOT. The professor said there is no single standard way to draw these graphs, so the most important thing is that your drawing is clear.

De Morgan’s Law: Your Helper

Inside one rule (one column) of a decision table, all the entries are joined by AND. There is no way to write an OR inside a single column. So we often need to turn an OR into an AND, and De Morgan’s law does exactly that:

\overline{A \land B} = \overline{A} \lor \overline{B} \qquad \overline{A \lor B} = \overline{A} \land \overline{B}

In words: NOT (A AND B) = (NOT A) OR (NOT B), and NOT (A OR B) = (NOT A) AND (NOT B). The easy way to remember it: break the line, change the sign. The NOT bar breaks into two, and AND becomes OR, OR becomes AND.

Common mistake: writing an OR inside one decision-table column. A column is an AND of its entries. An OR must either be turned into an AND with De Morgan (as for E1) or split into separate rules, one per alternative (as you will see in 6.4).

Constraints: Which Causes Can Be True Together?

Sometimes causes are connected. A bank command cannot be “credit” and “debit” at the same time, the same way a traffic light cannot be red and green at once. We show this with a constraint drawn between the causes. The professor taught three:

Constraint on causes A, B	Meaning	A=0, B=0	A=0, B=1	A=1, B=0	A=1, B=1
E (Exclusive)	at most one can be 1	yes	yes	yes	no
O (One and only one)	exactly one is 1	no	yes	yes	no
I (Inclusive)	at least one is 1	no	yes	yes	yes

The difference between E and O is only one box: with E, both can be 0; with O, they cannot. With I, both can be 1, but they can never both be 0.

From the slides: two more constraints from the classic textbook. R (Requires): if A is 1, then B must be 1. M (Mask): if effect E1 is 1, effect E2 is forced to 0 (M works between effects, not causes). The professor taught only E, O and I in class, and said you will not use the others often.

Example: The ATM

The professor’s example is a simple ATM transaction system.

Causes (inputs)	Effects (outputs)
C1: the command is credit	E1: print “invalid command”
C2: the command is debit	E2: print “invalid account number”
C3: the account number is valid	E3: print “debit amount not valid”
C4: the transaction amount is valid	E4: debit the account
	E5: credit the account

C1 and C2 cannot both be true (a command is either credit or debit, or something else), so there is an E constraint between them. The graph:

Diagram loads as you scroll.

As formulas:

Effect	Logic
E1	NOT (C1 OR C2)
E2	C1 AND NOT C3
E3	C2 AND C3 AND NOT C4
E4	C2 AND C3 AND C4
E5	C1 AND C3 AND C4

Reading E1 with De Morgan

E1 comes from C1 and C2 through an OR followed by a NOT: a NOR. Read directly, it says “NOT (credit OR debit)”, which sounds strange. Apply De Morgan:

\overline{C_1 \lor C_2} = \overline{C_1} \land \overline{C_2}

= “the command is not credit and the command is not debit” → print “invalid command”. Now it makes sense, and it is in AND form, ready for a decision-table column.

Reading E2

The professor read E2 as: the command is credit (C1) and the account number is not valid (NOT C3) → print “invalid account number”.

From the Graph to the Decision Table

Each AND group becomes one rule. A cause that is not in the group gets an X. The professor wrote R1 on the board and asked the class to complete R2 to R5:

Conditions / Effects	R1	R2	R3	R4	R5
C1 credit	0	1	X	X	1
C2 debit	0	X	1	1	X
C3 account valid	X	0	1	1	1
C4 amount valid	X	X	0	1	1
E1 invalid command	1	0	0	0	0
E2 invalid account	0	1	0	0	0
E3 debit amount invalid	0	0	1	0	0
E4 debit account	0	0	0	1	0
E5 credit account	0	0	0	0	1

R1 is exactly E1 after De Morgan: C1 = 0, C2 = 0, the rest X. Each later column copies one AND group from the graph. Then one test case per rule.

Exam-style answer: From the ATM cause-effect graph, write the decision table rules for E1 (invalid command) and E3 (debit amount not valid).

R1 R3
C1 credit 0 X
C2 debit 0 1
C3 account valid X 1
C4 amount valid X 0
E1 1 0
E3 0 1

E1: NOT(C1 OR C2) = C1’ AND C2’ (De Morgan), so C1 = 0, C2 = 0, the others X. E3: C2 AND C3 AND NOT C4. Why this gets marks: the De Morgan step is shown, X is used for causes that are not in the rule, and it is clear which effect is 1.

Worked Examples

Exercise 1

What is the difference between the E and the O constraint? Give the allowed (A, B) values for each.

Show solution ↓

Solution

Both forbid (1, 1). The difference is (0, 0):

E (Exclusive), at most one is 1: allowed (0, 0), (0, 1), (1, 0).
O (One and only one), exactly one is 1: allowed only (0, 1), (1, 0).

So E allows (0, 0), but O does not: with O, exactly one must be 1.

Exercise 2

Why do we usually draw the cause-effect graph before the decision table?

Show solution ↓

Solution

A full decision table has $2^K$ rules, most of which may not matter. The graph shows only the input combinations that actually lead to an effect, so the decision table built from it is small, and each rule gives exactly one test case. The table does not come from nowhere: it is read off the graph, and the tests are read off the table.

Exercise 3

(a) Causes A and B have an O constraint. Which values of (A, B) are possible? (b) Rewrite NOT (C1 OR C2) using AND. (c) Causes P and Q have an I constraint. Which combination is forbidden?

Show solution ↓

Solution

(a) Exactly one must be 1, so only (0, 1) and (1, 0).

(b) By De Morgan (“break the line, change the sign”):

\overline{C_1 \lor C_2} = \overline{C_1} \land \overline{C_2}

NOT (C1 OR C2) = (NOT C1) AND (NOT C2).

Exercise 4

Rewrite NOT (C3 AND C4) as an OR, and say in words what it means for the ATM (“C3: account valid”, “C4: amount valid”). Can this condition be written as a single decision-table column?

Show solution ↓

Solution

De Morgan: break the line, change the sign.

\overline{C_3 \land C_4} = \overline{C_3} \lor \overline{C_4}

In words: the account is not valid, or the amount is not valid (at least one of them is wrong).

It is an OR, so it cannot be one column: a column is an AND of its entries. It needs two rules: one with C3 = 0, C4 = X, and one with C3 = 1, C4 = 0. Together they cover the three combinations where at least one is 0.

Exercise 5

Turn the ATM decision table rules R1 to R5 into concrete test cases with expected outputs.

Show solution ↓

Solution

Pick one concrete input that satisfies each rule (any value for an X):

Rule	Command	Account	Amount	Expected output
R1	`transfer` (neither credit nor debit)	any	any	“invalid command” (E1)
R2	credit	invalid	any	“invalid account number” (E2)
R3	debit	valid	invalid	“debit amount not valid” (E3)
R4	debit	valid	valid	the account is debited (E4)
R5	credit	valid	valid	the account is credited (E5)

Five test cases, one per rule, each with its expected output. ✓ Each row matches exactly one rule.

Exercise 6

Is the ATM decision table (R1 to R5) complete? Check every possible input, taking into account the E constraint between C1 and C2. If it is not complete, say how you would fix it.

Show solution ↓

Solution

Because of the E constraint, the command is credit (C1 = 1, C2 = 0), debit (C1 = 0, C2 = 1) or neither (0, 0). Combine each with the four values of (C3, C4):

Command	C3	C4	Matching rule
neither	any	any	R1
credit	0	any	R2
credit	1	1	R5
credit	1	0	none
debit	1	0	R3
debit	1	1	R4
debit	0	any	none

No, it is not complete. Two situations match no rule:

A debit with an invalid account (C2 = 1, C3 = 0). The natural fix is to give it E2, “invalid account number”, with a new rule (C2 = 1, C3 = 0 → E2). R2 and the new rule together mean

E_2 = (C_1 \lor C_2) \land \overline{C_3}

so in the graph, C1 and C2 would join through an OR before the AND with NOT C3.

A credit with a valid account but an invalid amount (C1 = 1, C3 = 1, C4 = 0). E3 speaks only about debit amounts, so the specification does not say what should happen. A tester does not guess: ask whether credits need an amount check, and add the rule once the answer is known.

This is the completeness property (rules cover every combination) in action: checking it finds gaps in the specification before any code is run.