Mathematics for Computer Science

4.5. Finite Cardinality 99

Hint:PORQORRis equivalent to

.PANDQ/OR.QANDR/OR.RANDP/OR.PANDQANDR/:

Problem 4.9.
Union distributes over the intersection of two sets:

A[.B\C/D.A[B/\.A[C/ (4.11)

(see Problem 4.4).
Use (4.11) and the Well Ordering Principle to prove the Distributive Law of
union over the intersection ofnsets:

A[.B 1 \


\Bn 1 \Bn/D.A[B 1 /\


\.A[Bn 1 /\.A[Bn/ (4.12)

Extending formulas to an arbitrary number of terms is a common (if mundane)
application of the WOP.

Exam Problems

Problem 4.10.
You’ve seen how certain set identities follow from corresponding propositional
equivalences. For example, you proved by a chain of iff’s that

.AB/[.A\B/DA

using the fact that the propositional formula.PANDQ/OR.PANDQ/is equivalent
toP.
State a similar propositional equivalence that would justify the key step in a proof
for the following set equality organized as a chain of iff’s:

ABD

AC

[.B\C/[

A[B

\C

(4.13)

(You arenotbeing asked to write out an iff-proof of the equality or to write out
a proof of the propositional equivalence. Just state the equivalence.)

Problem 4.11.
You’ve seen how certain set identities follow from corresponding propositional
equivalences. For example, you proved by a chain of iff’s that

.AB/[.A\B/DA