Discrete Mathematics for Computer Science

32 CHAPTER 1 Sets, Proof Templates, and Induction

4. Let X = {2, 4}, Y = {1, 4}, and Z = {0, 4, 8}. Construct the following sets:
   (a) X x Y
   (b) X x Y x Z
   (c) Y x Z
   (d) ZxYxX
   (e) ZxXxY


5. Prove Theorem l(d).


6. Prove Theorem 2(d).


7. (a) Draw Venn diagrams to illustrate Theorems 3(a) and 3(b).
   (b) Prove Theorem 3(a).
   (c) Prove Theorem 3(b).


8. (a) Draw Venn diagrams to illustrate Theorems 4(c) and 4(d).
   (b) Prove Theorem 4(c).
   (c) Prove Theorem 4(d).


9. Find three sets A, B, and C where A C B U C but A 7 B and A • C.


10. (a) Draw Venn diagrams illustrating the four parts of Theorem 6.
    (b) Prove Theorem 6(a).
    (c) Prove Theorem 6(b).
    (d) Prove Theorem 6(c).
    (e) Prove Theorem 6(d).


11. Prove Theorem 7(c).


12. (a) Prove Theorem 9(b) using as a model the proof of Theorem 9(a).
    (b) Prove Theorem 9(b) using Theorem 7(c).

13. Let A = {1, 2, {{l, 2}}}.

(a) How many elements does A have? How many elements does 'P(A) have? How

many elements does 7P(P (A)) have?

In parts (b)-(m) determine, whether each of the following is true, and if not,

explain why not.

(b) I E A

(c) {1,2leA

(d) {{1,21) E A

(e) 0EA

(f) Ie EP(A)

(g) {1,2} e P(A)

(h) {{1,2)} e P(A)

(i) 0 E P(A)

(j) 1 E P(P (A))

(k) {1, 2} E P(P (A))

(1) {{1, 211 E P(P(A))

(m) 0 e P'(P(A))

14. For each of the following statements, find the corresponding inverse, converse, and
    contrapositive.
    (a) If the stars are shining, then it is the middle of the night.
    (b) If the Wizards won, then they scored at least 100 points.
    (c) If the exam is hard, then the highest grade is less than 90.