COT3100C-01, Spring 2000                               Assigned: 2/2/2000                   S. Lang Assignment #2 (40 pts.)                            Due:2/9, within the first 10 minutes of the lecture
                                                                                                          class (receive 2 bonus  points);
                                                                                                          or turn it in during your lab on 2/10 or /11 (no
bonus points)
  1. (12 pts.) Prove each of the following statements in Parts (a) - (f), assuming the symbols A, B, and C represent (arbitrary) sets. Your proof must be based on the appropriate definitions and the laws and theorems listed below (but only these). Be sure to explain each step of your proof.
(Commutative Law) A ÈB = B ÈA, A Ç B = B Ç A.

(Associative Law) (A ÈB)ÈC = A È(B ÈC), (A Ç B) Ç C = A Ç(B Ç C).

(Distributive Law) A È(B Ç C) = (A ÈB)Ç(A ÈC) , A Ç(B È C) = (A Ç B) È(A Ç C) .

(Idempotent Property) A ÈA = A, A Ç A = A.

(De Morgan’s Law) Ø (A ÈB) = ØA ÇØB, Ø (A ÇB) = ØA ÈØ B.

(Double Negation) Ø (ØA) = A.

(Complementary Property) A ÇØA = Æ , A ÈØ A = U, where U denotes the universe.

Theorem: (a) A Ç B ÌA. (b) A ÌA È B. (c) A ÇÆ = Æ . (d) A È Æ= A. (e) A ÌB iff ØBÌØA

(f) A ÌB iff A ÇØ B = Æ . (g) A -B = A ÇØB. (h) (A ÌB and B ÌC) implies A ÌC. (i) A ÌB implies A ÈC ÌB È C. (j) A ÌB implies A ÇC ÌB Ç C.
  1. If A Ç B = C, then CÌA and C ÌB.
  2. Ø (A ÇØB) = ØAÈB.
  3. (A - B) ÇB = Æ . (Note: One way to prove a set C = Æ is to assume xÎC, then prove this leads to a contradiction.)
  4. A Ì A ÈB ÈC. (Note: A ÈB ÈC means either (A ÈB)ÈC or A È(B ÈC); they are equal by the associative law.)
  5. If B Ì C, then A´BÌA ´C.
  6. (A ÈB) ÇA = (A Ç B) ÈA.
  1. (4 pts.) Disprove each of the following statements by using a "small" counter- example, where symbols A, B, and C represent sets.
  1. If A Ç B = Æ , then B = Æ .
  2. If A Ì B ÈC, then A Ì B or AÌC.
  1. (12 pts.) Prove each of the following statements by using the same instructions as in Question 1.
  1. If B Ì C, then A-C ÌA-B.
  2. If A ´ B = Æ , then A = Æ or B = Æ .
  3. A - (B ÈC) = (A - B) -C.
  4. If Power(A) Ì Power(B), then A Ì B. (Note:AÎ Power(A).)
  1. (6 pts.) Suppose the symbols A, B, and C represent three arbitrary finite sets. Answer the following two questions:
  1. If |A Ç B| = 3 and |A-B| = 5, determine |A| and explain your answer.
  2. Suppose |A Ç B| = 3, |BÇC| = 2, |A ÇC| = 1, |AÇ B ÇC| = 0, |A - B| = 5, |B -C| = 8, and |C - B| = 4. Determine |A ÈB ÈC| and explain your answer.
  1. (6 pts.) Let A denote a non-empty set of symbols (i.e., an alphabet), and let W, X, and Y denote sets of strings over A, i.e., W Ì A*, XÌA*, and Y ÌA*.
  1. Prove that if WY Ç XY = Æ , then W ÇX = Æ or Y = Æ . (Hint: Use indirect proof.)
  2. If W Ì Y, then prove W* ÈY* = Y*.