Mathematics for Computer Science

15.13. A Magic Trick 503

Problem 15.29.
Let’s develop a proof of the Inclusion-Exclusion formula using high school algebra.

(a)Most high school students will get freaked by the following formula, even
though they actually know the rule it expresses. How would you explain it to them?

Yn

iD 1

. 1 xi/D

X

If1;:::;ng

.1/jIj

Y

j 2 I

xj: (15.12)

Hint:Show them an example.

For any set,S, letMSbe themembershipfunction ofS:

MS.x/D

(

1 ifx 2 S;

0 ifx...S:

LetS 1 ;:::;Snbe a sequence of finite sets, and abbreviateMSiasMi. Let the
domain of discourse,D, be the union of theSi’s. That is, we let

DWWD

[n

iD 1

Si;

and take complements with respect toD, that is,

TWWDDT;

forT D.

(b)Verify that forTDandIf1;:::ng,

MTD 1 MT; (15.13)

M.Ti 2 ISi/D

Y

i 2 I

MSi; (15.14)

M.Si 2 ISi/D 1 

Y

i 2 I

.1Mi/: (15.15)

(Note that (15.14) holds whenIis empty because, by convention, an empty product
equals 1, and an empty intersection equals the domain of discourse,D.)

(c)Use (15.12) and (15.15) to prove

MDD

X

;¤If1;:::;ng

.1/jIjC^1

Y

j 2 I

Mj: (15.16)