CMSC 250 Fall 2005 Homework 10 solutions

0201 & 0202

1. $(A-B) \cap C^c$	Alt. Rep. of Set Diff.
   $(A \cap B^c) \cap C^c$	Alt. Rep. of Set Diff.
   $(A \cap C^c) \cap B^c$	Associatve and Commutative
   $(A\cap C^{c})-B$	Alt. Rep. of Set Diff.
   $(A-C)-B$	Alt. Rep. of Set Diff.

2. $(A-B)\cup (B-A)$	Given.
   $=(A \cap B^c) \cup (B \cap A^c)$	Alt. Rep. of Set Diff.
   $=((A \cap B^c) \cup B) \cap ((A \cap B^c) \cup A^c)$	Distributive
   $=(((A\cup B)\cap (B\cup B^{c}))\cap ((A\cup A^{c})\cap (B^{c}\cup A^{c})))$	Distributive
   $=((A\cup B)\cap (B^{c}\cup A^{c})\cap (A\cup A^{c}) \cap (B\cup B^{c}))$	Distrib. and Assoc.
   $=((A\cup B)\cap (B^{c}\cup A^{c})\cap U\cap U)$	Union with complement.
   $=((A\cup B)\cap (B^{c}\cup A^{c}))$	Intersect w/ $U$
   $=((A\cup B) \cap (B\cap A)^{c})$	De Morgan's
   $=((A\cup B) - (A\cap B)$	Alt. Def. of Set Diff. and Commut.

3. $B \cap (B^c - A)^c$	DeMorgans law
   $B \cap ( B^c \cap A^c)^c$	Alt. Rep. of Set Diff.
   $B \cap (B \cup A)$	DeMorgans law
   B	Absorption law

4. 1. Counterexample: Let $U = \{1,2,3,4,5,6\},$ $A= \{1,2,3\}, B= \{1,2,3,4\}, C=\{3,4,5\}$ then $B \cap C = \{3,4\},$ so that $(B \cap C)^c = \{1,2,5,6\}$ and $A \cap (B \cap C)^c = \{1,2,3\} \cap \{1,2,5,6\} = \{1,2\} \neq \emptyset$
   2. Let $A$ and $B$ be sets such that B$\subseteq A^c$. Suppose that $A \cap B \neq \emptyset$, that is, suppose there is an element $x$ such that $x \in A \cap B.$ Then $x \in B$ and $x \in A$ by the definition of intersection. But $A \subseteq B$ by hypothesis, so since $x \in B$, $x \in A^c$ by definition of subset. Thus x$\in A$ and also $x \in A^c$, which is a contradiction. Hence our supposition is false which means that $A \cap B = \emptyset$
5. 1. $P(\emptyset) = \{\emptyset\}$
   2. $P(P(\emptyset)) = \{\emptyset,\{\emptyset\}\}$
   3. $P(P(P(\emptyset))) = \{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\}$
6. 1. Yes, since $A_1$ and $A_2$ and $A_3$ have no elements in common.
   2. By inspection, $A = A_1 \cup A_2 \cup A_3$, and the sets are mutually disjoint.
   3. For example, $A_{3}=\{e\}$, then none of the sets contain $f$. Another example, $A_{3}=\{d,e,f\}$ and $A_{2}\cap A_{3}\neq \emptyset$, so the sets are no longer mutually disjoint.
7. 1. Break up the problem in 9-step operation and there is a fixed number of ways to perform each step.In our case it is 10, So by the rule of multiplication there are $10^9 = 1,000,000,000$ SSN's in all.
   2. Now there are 10 different ways to select the first digit,9 different ways to select the second digit, and so on, Thus multiplication rule can be applied to conclude that there are $10*9*8*7*6*5*4*3*2*1 = 3628800$ different SSN's with no repeated symbol. Thus the probability the a SSN chosen at random contain no repeated numbers is $3628800 / 1,000,000,000 = 0.00362$ therefore approximately 0.36

Web Accessibility