Mathematics for Computer Science

14.11. References 615

Now to start proving (14.15), letMSbe themembershipfunction for any setS:

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; (14.16)

M.Ti 2 ISi/D

Y

i 2 I

Mi; (14.17)

M.Si 2 ISi/D 1 

Y

i 2 I

.1Mi/: (14.18)

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

(c)Use (14.15) and (14.18) to prove

MDD

X

;¤If1;:::;ng

.1/jIjC^1

Y

j 2 I

Mj: (14.19)

(d)Prove that

jTjD

X

u 2 D

MT.u/: (14.20)

(e)Now use the previous parts to prove

jDjD

X

;¤If1;:::;ng

.1/jIjC^1

ˇˇ

ˇˇ

ˇ

\

i 2 I

Si

ˇˇ

ˇˇ

ˇ

(14.21)