Mathematics for Computer Science

4.5. Finite Cardinality 97

Class Problems

Problem 4.3.
Set Formulas and Propositional Formulas.
(a)Verify that the propositional formula.PANDQ/OR.PANDQ/is equivalent
toP.

(b)Prove that

AD.AB/[.A\B/

for all sets,A;B, by showing

x 2 AIFFx 2 .AB/[.A\B/

for all elements,x, using the equivalence of part (a) in a chain ofIFF’s.

Problem 4.4.
Prove

Theorem(Distributivity of union over intersection).

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

for all sets,A;B;C, by using a chain of iff’s to show that

x 2 A[.B\C/IFFx 2 .A[B/\.A[C/

for all elements,x. You may assume the corresponding propositional equivalence
Theorem 3.4.2.

Problem 4.5.
Prove De Morgan’s Law for set equality

A\BDA[B: (4.9)

by showing with a chain ofIFF’s thatx 2 the left hand side of (4.9) iffx 2 the right
hand side. You may assume the propositional version (3.11) of De Morgan’s Law.

Problem 4.6.
Powerset Properties.
LetAandBbe sets.