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

CMSC 250

Final Exam

Monday, May 19, 2003

Write all answers legibly on the paper provided. If you need extra paper, raise your hand and request a blank paper - you must put your name on and hand-in any paper you receive. The number of points possible for each question is indicated in square brackets - the total number of points on the exam is 200, and you will have exactly 2 hours to complete this exam. You may not use calculators, textbooks or any other aids during this exam. The formula sheet is attached - this can be removed from the back of the exam and does not need to be handed in at the end.

Grades for this exam and for the semester will be posted on the web site as soon as we can get the material graded.

1. [15 pnts.] For each of the following English sentences, translate the meaning into formal notation using the logic symbols ($\exists$, $\forall$, $\wedge$, $\vee$, $\sim$, and $\rightarrow$). In addition to these, you may also use mathematical, grouping and set notations symbols as needed. On the next line write the negation of the original statement using formal notation. Note: On the negation, no quantifier nor quantitified expression (parentheses) may be negated in the final answer.

   There are more than two people with green hair.

   Domain: P = {All people}

   Predicate: G(x) = ``x has green hair''

   statement:

   negation:

   There are not two people who both like the same person.

   Domains: P = {All people}

   Predicate: L(x,y) = ``person x likes person y''

   statement:

   negation:

   Every dog has a month.

   Domains: D = {all dogs}, M = {all months}

   Predicate: H(d,m) = ``dog d has month m''

   statement:

   negation:

   
   

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

   
   
   
   
   

   
   

   

   
   

2. [20 pnts.] Use only those rules given on the ``cheatsheet'' to prove that the following is a valid argument. It is a valid argument - you only need to prove that it is.

   P1	$\forall a \in D, F(a) \rightarrow (M(a) \vee \sim N(a))$
   P2	$\forall b \in D, (M(b) \wedge Y(b)) \rightarrow \sim N(b)$
   P3	$\exists b \in D, Y(b) \wedge Z(b)$
   P4	$\forall c \in D, Z(c) \rightarrow N(c)$
   	Therefore $\exists g \in D, F(g) \rightarrow \sim Z(g)$

   line	Statement	Reason	Line #s
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

3. [20 pnts.] Prove or give a counter example for the following statement. You can only use induction if you can't do this problem deductively, and you only use strong induction if you can't use regular induction for this proof.

   
   

   $$\forall n \geq 1, {2n \choose n} \leq 2^{2n-1}$$
   
   

4. [20 pnts.]Prove or give a counter example. You can only use induction if you can't do this problem deductively, and you only use strong induction if you can't use regular induction for this proof.

   Assume the values are defined according to this:

   Let $a_{2}=1.5, a_{3}=2.3$, $\forall n\geq 4, a_{n}=\sqrt{a_{\lfloor \frac{n}{2}\rfloor}a_{\lceil\frac{n}{2}\rceil}}$

   Prove or give a counter example for the statement:
   

   $$\forall n\geq 2, a_{n}\leq n$$
   
   
   .

5. [20 pnts.]Prove or give a counter example for the following statement: You can only use induction if you can't do this problem deductively, and you only use strong induction if you can't use regular induction for this proof.

   Let $a, b, c, r, s, k \in\bf Z^{+}$.

   
   

   $$(a \equiv_r b) \wedge (b \equiv_s c) \wedge (k\vert r) \wedge (k \vert s) \rightarrow (a \equiv_k c)$$
   
   

6. [12 pnts.] Answer the following questions about your sock drawer. You only need to get the answer into a form that involves ONLY factorials, exponents, fractions, addition, subtraction and multiplication.

   You own 10 black socks, 10 brown socks, and 10 orange socks. Assume socks of the same color are indistinguishable.

   1. How many ways are there to randomly select 5 socks to put into your suitcase?

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   2. How many ways are there to put ALL of your socks in a row on the clothesline?

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   3. You put ALL of your socks into the dryer knowing that the dryer will randomly consume 4 of them. What is the probability that the dryer will consume two socks of one color and two socks of another color.

7. [8 pnts.] Answer the following questions about the positions of the baseball team.

   You are the manager of 24 baseball players. There are 9 unique "positions" (jobs) that make up a single baseball team. You do not have to do the arithmetic, you can leave the answer in a format that includes combinations using the format ${x \choose y}$, permutations using the format $P(x,y)$, addition, subtraction, multiplication, division,exponents and/or factorials.

   1. In how many ways can you select a team? (Assume the team is just a group of nine players - the ``position'' each team member is playing doesn't matter.)

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   2. In how many ways can you select a team? (Assume the team here is defined as which position each player is assigned to - for example Joe playing on your team as the catcher and Bill as the pitcher should be considered a different team than if Bill is the catcher and Joe the pitcher.)

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   3. If Jerry Hairston and Jay Gibbons (two of the 24 players you may select from) refuse to play on the same team, then how many ways can you select a team? (Assume for this question the second definition of team - where teams are distinct based on the ``positions'' of the players.)

8. [20 pnts.] Prove or give a counterexample to the statement assuming that $X'$ indicates the complement of the set $X$ and $P(X)$ indicates the powerset of $X$:

   
   

   $$\forall A,B \in \{sets\}, P(A) \subseteq P(B') \rightarrow B \subseteq A'$$
   
   

9. [15 pnts.] Let $f: Z \times Z \rightarrow Z$ be defined as follows:

   
   

   $$\forall (a,b) \in Z \times Z, f((a,b)) = 2a+b$$
   
   
   1. Either prove that f is one-to-one or explain why it isn't.

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   2. Either prove that f is onto or explain why it isn't.

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   3. Either prove that f is a bijection or explain why it isn't.

10. [20 pnts.] Assume there is a function $G:D\rightarrow F$ where the sets needed are defined below assuming $n(X)$ indicates the size of the set X:

    A is a set of elements.
    $n(A) = m$
    B is another set of elements.
    $n(B) = x$
    
    $C = A \times P(A)$
    $D = C \times C$
    $E = A \times A$
    $F = E \times P(B)$

    1. If G is onto, what relationship must hold between $m$ and $x$?
       
       
       
       
       
       
       
       
       
       
       
       
       
       

    2. If G is one-to-one, what relationship must hold between $m$ and $x$?
       
       
       
       
       
       
       
       
       
       
       
       
       
       

    3. If G is a bijection, what relationship must hold between $m$ and $x$?
       
       
       
       
       
       
       
       
       
       
       
       
       
       

11. [20 pnts.] Given the relation named $R$ over the set given as $A$, answer each of the following questions.

    
    

    $$A = \{a,b,c,d,e\}$$
    
    
    
    
    $$R = \{(a,a),(a,b),(a,c),(b,b),(b,a),(c,c),(c,a),(b,c),(d,d),(e,e),(c,b)\}$$
    
    
    1. (Yes or No) Is this relation transitive?
       

    2. (Yes or No) Is this relation irreflexive?
       

    3. (Yes or No) Is this relation symmetric?
       

    4. (Yes or No) Is this relation reflexive?
       

    5. (Yes or No) Is this relation antisymmetric?
       

       
       
       
       
       
       
       
       

    6. (Yes or No) Is this relation a ``partial order relation''?
       Which of the above properties do you have to consider to determine if it is a ``partial order relation''?

       
       
       
       
       
       
       
       

    7. (Yes or No) Is this relation an ``equivalence relation''?
       Which of the above properties do you have to consider to determine if it is an ``equivalence relation''?

12. [10pnts] Give the following relation (which is a partial order relation), answer the following questions:

    
    

    $$A = \{1,2,3,4,5,6\}$$
    
    
    
    
    $$X = \{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,6),(1,5),(2,5),(2,3),(3,4),(2,4)\}$$
    
    
    1. Draw the directed graph that represents this relation:

       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       

    2. Draw the Hasse diagram that represents this partial order relation:

       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       

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. 39

Modus	$p \rightarrow q$		Disjunctive	$p \vee q$	$p \vee q$
Ponens	$p$		Syllogism	$\sim q$	$\sim p$
	Therefore $q$			Therefore $p$	Therefore $q$
Modus	$p \rightarrow q$		Hypothetical	$p \rightarrow q$
Tollens	$\sim q$		Syllogism	$q \rightarrow r$
	Therefore $\sim p$			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$
Conjunctive	$p$
Addition	$q$
	Therefore $p \wedge q$

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 Instantiation	$\forall x \in D, P(x)$	$\rightarrow$	$P(a)$
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)$
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$

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 - Properties of $\emptyset$

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$

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}$

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation -antialias_text -antialias spring2003final

The translation was initiated by Phillip Kirlin on 2003-12-05

Web Accessibility