CMSC 250

Quiz #10 ANSWERS

Wed., Nov. 3, 2004

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [12 pnts.] Assuming set $A = \{a,b,c\}$ and set $B=\{1,a\}$ do each of the following:
   1. List the elements of $A \times B$.
      
      
      
      $A \times B = \{(a,1),(a,a),(b,1),(b,a),(c,1),(c,a)\}$
      
      
      
      
   2. Give the power set of $B$.
      
      
      
      $P(B) = \{\emptyset, \{1\}, \{a\}, \{1,a\}\}$
      
      
      
      
   3. 
      
      
      
      
      
      
      Assuming B is the alphabet of some language (in other words let $B = \Sigma$), give the values of $\Sigma^2$.
      
      
      
      $B^2 = \Sigma^2$ = 11, 1a, a1, aa
      
      
      
      
2. [8 pnts.] List the elements in each of the sets ($A$ and $B$) assuming
   $A-B = \{b,d\}$, $B-A = \{c\}$ and $A \cap B = \{a,e\}$. A = $\{a,b,d,e\}$ B = $\{a,c,e \}$
3. [10 pnts.] Prove or give a counter example to the following. For all sets A, B and C.
   $A \subseteq C \wedge B \subseteq C \rightarrow A \times B \subseteq C \times C$ Proof:
   Let A,B and C be arbitrary sets.
   $\vert$Assume $A \subseteq C \wedge B \subseteq C$
   $\vert$ by def of subset we know $\forall x \in U, x \in A \rightarrow x \in C$
   $\vert$ and we know $forall y \in U, y \in B \rightarrow y \in C$
   $\vert$
   $\vert$ Let $(m,n)$ be arbitrary in $U \times U$
   $\vert$ $\vert$ Assume $(m,n) \in A \times B$
   $\vert$ $\vert m \in A \wedge m \in B$ by definition of Cartesian Product
   $\vert$ $\vert$ Since $m \in A$, we know $m \in C$ by universal modus ponens on def of subset above
   $\vert$ $\vert$ Since $n \in B$, we know $n \in C$ by universal modus ponens on def of subset above
   $\vert$ $\vert$ Since $m \in C \wedge n \in C$ by conjunctive addition
   $\vert$ $\vert$ we know that $(m,n) \in C \times C$ by definition of Cartesian Product
   $\vert \forall (m,n) \in U \times U, (m,n) \in A \times B \rightarrow (m,n) \in C \times C$ by CCW and gen from Generic Particular
   $\vert A \times B \subseteq C \times C$ by definition of subset
   $\vert$
   $A \subseteq C \wedge B \subseteq C \rightarrow (A \times B) \subseteq (C \times C)$ by CCW
   $\forall A,B,C \in Sets, A \subseteq C \wedge B \subseteq C \rightarrow A \times B \subseteq C\times C$
   

Web Accessibility