CIS 125

17 – Set Properties

In each exercise, write “true” if the statement is true, otherwise give a counterexample. Counterexamples may take the form of Venn diagrams, symbolic expression, or an example set.

The sets X, Y, and Z are subsets of a universal set U.

For counterexamples, let U={1,2,3,4,5,6,7,8,9,10}, X={1,4,7,10}, Y={1,2,3,4,5}, and Z={2,4,6,8}. Create solutions for each side of the equal sign. If they are different, then they are not equal.

1. X ( Y – Z) ≡ (X Y ) – ( X Z )

2. ( X – Y ) ( Y – X ) ≡ for all sets X and Y.

3. ~( X – Y ) ≡ ~( Y – X ) for all sets X and Y.

4. X – ( Y Z ) ≡( X – Y ) Z

5. ( X Y ) ( Y – X ) ≡ Y for all sets X and Y.

Associative laws: ( A B ) C = A ( B C ) ( A B ) C = A ( B C )	Commutative laws: A B = B A A B = B A
Distributive laws: A ( B C ) = (A B) (A C ) A ( B C ) = (A B) (A C )	Identity laws: A = A A U = A
Complement laws: A ~A = U A ~A =	Idempotent laws: A A = A A A = A
Bound laws: A U = U A =	Absorption laws: A ( A B ) = A A ( A B ) = A
Involution law: ~(~A) = A	0/1 laws: ~ = U ~U =
DeMorgan’s laws for sets: ~(A B) = ~A ~B ~(A B) = ~A ~B	Note: A – B = A ~B

In exercises 6-7, write the relation as a set of ordered pairs, e.g. (x, y).

6.

Sally Math

Ruth Physics

Sam Econ

7.

a 3

b 1

b 4

c 1

In exercises 8-9, write the relation as a table.

8. R = { (a, 6), (b,2), (a,1), (c,1) }

9. R = { (Roger, Music), (Pat, History), (Ben, Math), (Pat, Music) }