Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Exam #3

Friday, Dec. 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 exam is 100, and you will have exactly 50 minutes to complete this exam. You may not use calculators, textbooks or any other aids during this exam. If you need more space for any answer, ask for an extra paper - these extra papers must be turned in and you must mark them so we can find the answer corresponding to a question. The ``cheatsheet'' (which is the last page of the exam) can be ripped off and used during the exam. Leave the paper closed this side up on your desk until you are told to start. Make sure you are in your assigned seat with all cellphones and pagers turned off. Make sure you have writing instruments and your picture ID out on your desk.

**** This area is for grading purposes (points lost per problem)- Do not write below this line ****

1. [14 pnts] For each of the following functions write either yes or no into the blank provided as indicated and then justify your answer when requested. JUSTIFICATION IS NEEDED FOR BOTH YES AND NO ANSWERS. Justification for a universal statement that is true means that you must have a formal proof.
   1. $f: Z \rightarrow Z$ where $f(x) = 2x -1$
      
      
      1. Is this a total function ?(yes or no).
         
         
         
      2. Is this function onto? (yes or no)
         
         
      3. JUSTIFY YOUR ANSWER:
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
      4. Is this function one-to-one? (yes or no)
         
         
      5. JUSTIFY YOUR ANSWER:
   2. $g: R \rightarrow R^{\leq 0}$ where $g(x) = - x^2$
      
      
      1. Is this a total function ?(yes or no).
         
         
         
      2. Is this function onto? (yes or no)
         
         
      3. JUSTIFY YOUR ANSWER:
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
      4. Is this function one-to-one? (yes or no)
         
         
      5. JUSTIFY YOUR ANSWER:
2. [10 pnts.] Assume you have two finite sets X and Y. The set X has 10 members, and the set Y has 5 members.
   
   
   
   1. Assume you have created a set named F which is the set of all possible total functions from X to Y. What is the size of the set F?
      
      
      
      
      
      
   2. Assume you have created another set named R which is the set of all possible relations from X to Y. What is the size of the set R?
      
      
      
      
      
      
3. [9 points] For each of the following mark which properties the relation has with a Y if it has that property or a N if it does not.
   • Relation R over the set $\{1,2,3,4\}$ where $R = \{(1,1),(1,3),(2,2),(2,4),(3,3),(3,1)\}$
     
     
     
     Reflexive Symmetric Transitive
     
     $$----------------------------------------------------$$
     
     

   • Relation T over the set $R$ where $xTy \leftrightarrow x \leq y$
     
     
     
     Reflexive Symmetric Transitive
     
     $$----------------------------------------------------$$
     
     

   • Relation S over the set $Z^+$ where $xSy \leftrightarrow x \vert 2y$
     
     
     
     Reflexive Symmetric Transitive
4. [20 pnts] Prove that the following statement is true or give a specific counter example to show that it is false. When doing a proof, you must give reasons for all steps.
   
   $$\forall A,B,C,D \in \{sets\}, (A \cap B) \times (C-D) \subseteq (A \times C) \cup (B \times C)$$
   
   

5. [20 pnts] Assume you are working for a charity group and your assignment is to buy and distribute toys to the children of an orphanage. You may assume there are 20 children, 12 girls and 8 boys (and all the children are distinguishable). Answer each of the following questions. The specific details given in one question do not affect the others questions in any way. Partial credit is possible only if you describe what you are thinking. Your answer does not need to be taken to an numeric value, but it does need to be given in a form that has only addition, subtraction, multiplication, division, factorials and exponents.
   1. Assume you purchase the correct number of toys so that each child gets exactly one where each of the boys will receive a truck and each of the girls will receive a doll. The trucks are indistinguishable from each other (you purchased 8 copies of the same truck). The dolls are distinguishable from each other (they are all different). How many ways can you distribute these to the children assuming a girl must receive a doll and a boy must receive a truck?
      
      
      
      
      
      
      
      
      
      
      
      
      
   2. You are at the toy store where there is a supply of at least 20 of each of the 5 kinds of toys they sell (they have yo-yo's, slinkies, jacks, balls and jumpropes). All of these toys are appropriate for either boys or girls. How many ways can you walk out of the toystore carrying enough toys so that each child gets exactly one gift?
      
      
      
      
      
      
      
      
      
      
      
      
      
   3. You have had 25 toys donated. All 25 toys are different from each other. How many ways can you distribute the 25 toys to the 20 children if you want each child to get one and only one toy. Assume you are not concerned with what toy the child might like or what toy is age appropriate for that child and that you get to keep the remaining 5 toys yourself.
   4. Assume instead of bringing toys to these children, you are planning to take them in groups of size 5 to the toy store to pick out their own toys. How many ways can you divide them into groups of 5?
      
      
      
      
      
      
      
      
      
      
      
      
      
   5. Assume you are having a large group picture taken of all of the children with their toys (for promotional purposes for your charity). You have 10 children that are tall who will be in the back row of the picture and 10 children who are short who will be in the front row of the picture. (You have exactly 2 rows of children in the picture.) How many different ways can you position the children for the picture?
      
      
      
      
      
      
      
      
      
      
      
      
      
   6. Assuming the picture line up from the previous question but you have a problem that three of the short children Alex, Barry and Carl are difficult and cause problems if all of these three are standing together during the photo session. What is the probability that these three are standing together if you assume that you have arranged the children completely randomly for the picture?
6. [15 pnts] Prove that the following statement is true or give a specific counter example to show that it is false. If you decide to prove it true, you may use all of the rules on the attached sheet and do not need to prove it at by using the member level and the additional definitions that do not appear on the sheet. When doing a proof, you must give reasons for each step.
   
   $$\forall A,B,C \in \{sets\}, (A - B) - (A - C) = A \cap (C - B)$$
   
   

7. [12 pnts] Assume you are creating a subset from the set of the 1 digit positive integers $\{1,2,3,4,5,6,7,8,9\}$. Answer the following sequence of steps to show how you can use the pigeon hole principle to answer the question about how many you would need to have in your subset to know for sure that you have two in the subset that sum to 8.
   1. Describe the contents of the domain you would like to use.
      
      
      
      
      
      
      
   2. Describe the contents of the codomain you would like to use.
      
      
      
      
      
      
      
   3. What is the size of that codomain that you just described?
      
      
      
      
      
      
      
   4. Describe a total function that maps elements in the domain you just described to elements in the codomain you just described.
      
      
      
      
      
      
      
   5. Now apply the pigeon hole principle and answer the question `` what is the minimum size the domain can be where you are sure you know that you must have two distinct numbers whose sum is 8?''

This Page Intentionally Blank
This Page is to be used for Scratch Paper ONLY



NOTHING ON THIS PAGE WILL BE GRADED

Theorem 1.1.1 - Epp Textbook p. 14

Given any statement variables $p$, $q$, and $r$, a tautology $t$ and a contradiction $c$,
the following logical equivalences hold:
1. Commutative laws:	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
2. Associative laws:	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
3. Distributive laws:	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
4. Identity laws:	$p \wedge t \equiv p$	$p \vee c \equiv p$
5. Negation laws:	$p \vee \sim p \equiv t$	$p \wedge \sim p \equiv c$
6. Double Negative law:	$\sim (\sim p) \equiv p$
7. Idempotent laws:	$p \wedge p \equiv p$	$p \vee p \equiv p$
8. DeMorgan's laws:	$\sim (p \wedge q) \equiv \sim p \vee \sim q$	$\sim (p \vee q) \equiv \sim p \wedge \sim q$
9. Universal bounds laws:	$p \vee t \equiv t$	$p \wedge c \equiv c$
10. Absorption laws:	$p \vee (p \wedge q) \equiv p$	$p \wedge (p \vee q) \equiv p$
11. Negations of t and c:	$\sim t \equiv c$	$\sim c \equiv t$

Table 1.3.1 - Epp Textbook p. 40

Modus Ponens	Modus Tollens		Disjunctive	$p \vee q$	$p \vee q$
$p \rightarrow q$	$p \rightarrow q$		Syllogism	$\sim q$	$\sim p$
$p$	$\sim q$			Therefore $p$	Therefore $q$
Therefore $q$	Therefore $\sim p$
Conjunctive	$p$		Hypothetical	$p \rightarrow q$
Addition	$q$		Syllogism	$q \rightarrow r$
	Therefore $p \wedge q$			Therefore $p \rightarrow r$
Disjunctive	$p$	$q$	Dilemma:	$p \vee q$
Addition	Therefore $p \vee q$	Therefore $p \vee q$	Proof by	$p \rightarrow r$
			Division	$q \rightarrow r$
			into Cases	Therefore $r$
Conjunctive	$p \wedge q$	$p \wedge q$	Rule of	$\sim p \rightarrow c$
Simplification	Therefore $p$	Therefore $q$	Contradiction	Therefore $p$
Closing C.W.	$\vert p$ Assumed		Closing C.W.	$\vert p$ Assumed
without	$\vert q$ derived		with	$\vert x \wedge \sim x$ derived
contradiction	Therefore $p \rightarrow q$		contradiction	Therefore $\sim p$

Other Equivalences and Other Rules of Inference

Definition	$p \rightarrow q$	$\equiv$	$\sim p \vee q$
of Implication	$\sim (p \rightarrow q)$	$\equiv$	$p \wedge \sim q$
Definition of	$A \leftrightarrow B$	$\equiv$	$(A \rightarrow B) \wedge (B \rightarrow A)$
Biconditional	$\sim (A \leftrightarrow B)$	$\equiv$	$(A \wedge \sim B) \vee (B \wedge \sim A)$
Negation of	$\sim \forall x\,\, P(x)$	$\equiv$	$\exists x \,\, \sim P(x)$
Quantifiers	$\sim \exists x\,\, P(x)$	$\equiv$	$\forall x \,\, \sim P(x)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Ponens	$P(a)$	$\rightarrow$	$Q(a)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Tollens	$\sim Q(a)$	$\rightarrow$	$\sim P(a)$
Universal Instantiation	$\forall x \in D, P(x)$	$\rightarrow$	$P(a)$
Existential Generalization	$P(a)$ where $a \in D$	$\rightarrow$	$\exists x \in D, P(x)$
Universal Generalization**	$P(a)$ where $a \in D$	$\rightarrow$	$\forall x \in D, P(x)$
Existential Instantiation **	$\exists x \in D, P(x)$	$\rightarrow$	$P(a)$ where $a \in D$

** NOTE: Remember the special circumstances required for the rules marked by the stars.

Table 5.2.1 - Subset Relations

Given any sets $A$, $B$, and $C$:
1. Inclusion for Intersection:	$(A \cap B) \subseteq A$
	$(A \cap B) \subseteq B$
2. Inclusion for Union:	$A \subseteq (A \cup B)$
	$B \subseteq (A \cup B)$
3. Transitive Property of Subsets:	$(A \subseteq B)\wedge (B \subseteq C) \rightarrow A \subseteq C$

Theorem 5.2.2 - Set Identities

Given any sets $A$, $B$, and $C$, the universal set $U$ and the empty set $\emptyset$:
1. Commutative laws:	$A \cap B = B \cap A$
	$A \cup B = B \cup A$
2. Associative laws:	$(A \cap B) \cap C = A \cap (B \cap C)$
	$(A \cup B) \cup C = A \cup (B \cup C)$
3. Distributive laws:	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
4. Intersection with U (Identity):	$A \cap U = A$
5. Double Complement law:	$(A')' = A$
6. Idempotent laws:	$A \cap A = A$
	$A \cup A = A$
7. De Morgan's laws:	$(A \cup B)' = A' \cap B'$
	$(A \cap B)' = A' \cup B'$
8. Union with U (Universals Bounds):	$A \cup U = U$
9. Absorption laws:	$A \cup (A \cap B) = A$
	$A \cap (A \cup B) = A$
10. Alternative Representation for Set Diff:	$A - B = A \cap B'$

Table 5.2.3 - Subset Intersection and Union

Given any sets $A$, $B$ :
1. $A \subseteq B \rightarrow (A \cap B = A)$	Intersection with Subset
2. $A \subseteq B \rightarrow (A \cup B = B)$	Union with Subset

Table 5.3.3 (plus others) - Properties of $\emptyset$ and Universal set

Given any sets $A$, $B$, and $C$, the universal set $U$ and the empty set $\emptyset$:
1. Union with $\emptyset$:	$A \cup \emptyset = A$
2. Intersection and Union with Complement	$A \cap A' = \emptyset$
	$A \cup A' = U$
3. Intersection with $\emptyset$ :	$A \cap \emptyset = \emptyset$
4. Complement of Union and $\emptyset$:	$U' = \emptyset$
	$\emptyset' = U$
5. Every set is subset of Universal	$\forall A \in \{Sets\}, A \subseteq U$
6. Empty set is subset of every set	$\forall A \in \{Sets\}, \emptyset \subseteq A$
7. Definition of Empty Set	$\forall A \in \{Sets\}, A = \emptyset \leftrightarrow \forall x \in U, x \not \in A$

Things from Ch. 4

Theorem 4.1.1	$\sum_{k=m}^n a_k + \sum_{k=m}^n b_k = \sum_{k=m}^n (a_k+b_k)$
Theorem 4.1.1	$c \cdot \sum_{k=m}^n a_k = \sum_{k=m}^n (c \cdot a_k)$
Theorem 4.1.1	$\prod_{k=m}^n a_k \cdot \prod_{k=m}^n b_k = \prod_{k=m}^n (a_k \cdot b_k)$
Theorem 4.2.2	$\sum_{i=1}^m i = \frac{m(m+1)}{2}$
Theorem 4.2.3	$\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r - 1}$

Web Accessibility