CMSC 250 Spring 2003 Final Exam Answers

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:

   $\exists x, y, z\in P G(x)\wedge G(y)\wedge G(z)\wedge x\neq y\wedge x\neq z\wedge y\neq z$

   negation:

   $\forall x,y,z (G(x)\wedge G(y)\wedge G(z))\rightarrow (x=y\vee x=z \vee y = z)$

   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:

   $\forall x, y, p\in P (L(x,p)\wedge L(y,p))\rightarrow (x=y)$.

   negation:

   $\exists x,y,z\in P L(x,p)\wedge L(y,p)\wedge x\neq y$.

   Every dog has a month.

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

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

   statement:

   $\forall d\in D\exists m\in M H(d,m)$

   negation:

   $\exists d\in D\forall m\in M \sim H(d,m)$.

   
   

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
   	$Y(a)\wedge Z(a)$	$\exists$ Inst.	P3
   2
   	$Y(a)$	$\wedge$ Simp.	1
   3
   	$Z(a)$	$\wedge$ Simp.	1
   4
   	$N(a)$	$\forall$ MP	2, P4
   5
   	$\sim (M(a)\wedge Y(a)$	$\forall$ MT	4, P2
   6
   	$\sim M(a)\vee \sim Y(a)$	De Morgan's	5
   7
   	$\sim M(a)$	$\vee$ Syll.	2, 6
   8
   	$\sim M(a)\wedge N(a)$	$\wedge$ +	4, 7
   9
   	$\sim (M(a)\vee \sim N(a)$	De Morgan's	8
   10
   	$\sim F(a)$	$\forall$ MT	9, P1
   11
   	$\sim F(a)\vee \sim Z(a)$	$\vee$ +	10
   12
   	$F(a)\rightarrow \sim Z(a)$	Alt. Def. $\rightarrow$	11
   13
   	$\exists g \in D, F(g) \rightarrow \sim Z(g)$	$\exists$ Gen.	12
   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}$$
   
   

   Base Case: $n=1$
   	${2\choose 1} = \frac{2!}{1!1!}=2$ and $2^{2(1)-1} = 2^{1} = 2$.
   Inductive Hypothesis:$n=k$
   	${2k\choose k}\leq 2^{2k-1}$
   Inductive Step:$n=k+1$
   Show:
   	${2(k+1)\choose (k+1)}\leq 2^{2(k+1)-1}=2^{2k+1}$.
   Proof:
   	${2(k+1)\choose (k+1)}=\frac{(2(k+1))!}{(k+1)!(k+1)!}$.
   	$(2(k+1))!=(2k+2)!=(2k+2)(2k+1)(2k)!$, and
   	$(k+1)! = (k+1)k!$.
   	Hence, ${2(k+1)\choose (k+1)}=\frac{(2k+2)(2k+1)(2k)!}{(k+1)k!(k+1)k!}$.
   	= $\frac{(2k+2)(2k+1)}{(k+1)^{2}}{2k\choose k}$.
   	Since $2k+1 < 2k+2$, we can replace the $2k+1$ term in the fraction with $2k+2$, and we will not decrease the size of the fraction:
   	$\frac{(2k+2)(2k+1)}{(k+1)^{2}}\leq \frac{(2k+2)(2k+2)}{(k+1)^{2}}=\frac{4(k+1)^{2}}{(k+1)^2}=4.$.
   	By the IH, ${2k\choose k}\leq 2^{2k-1}$.
   	Substituting these two inequalities into the value of ${2(k+1)\choose (k+1)}$, it follows that
   	${2(k+1)\choose (k+1)} = \frac{(2k+2)(2k+1)}{(k+1)^{2}}{2k\choose k}\leq 4*2^{2k-1}=2^{2}2^{2k-1}=2^{2k+1}=2^{2(k+1)-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$$
   
   
   .

   Base Case:$n=2,3$
   	$a_{2}=1.5$ and $1.5\leq 2$. $a_{3}=2.3$ and $2.3\leq 3$.
   Inductive Hypothesis: $n=i, 4\leq i< k$
   	$a_{i}\leq i$.
   Inductive Step: $n=k$.
   Show:
   	$a_{k}\leq k$.
   Proof:
   	$a_{k}= \sqrt{a_{\lfloor \frac{k}{2}\rfloor}a_{\lceil\frac{k}{2}\rceil}}$
   	Since $\lfloor \frac{k}{2}\rfloor\leq \frac{k}{2}$, by the IH, $a_{\lfloor \frac{k}{2}\rfloor}\leq \frac{k}{2}.$
   	Since $\lceil \frac{k}{2}\rceil\leq \frac{k}{2}+1$, by the IH, $a_{\lceil \frac{k}{2}\rceil}\leq \frac{k}{2}+1$.
   	Hence, $a_{\lfloor \frac{k}{2}\rfloor}a_{\lceil\frac{k}{2}\rceil}\leq \frac{k}{2}(\frac{k}{2}+1)$.
   	Since $4\leq n$, $1 \leq \frac{k}{4}$, so $1\leq \frac{k}{2}$, so $1+\frac{k}{2}\leq \frac{k}{2}+\frac{k}{2}=k.$
   	Hence, $a_{k}\leq\sqrt{\frac{n}{2}n}=\frac{n}{\sqrt{2}}\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)$$
   
   

   The statement is true.

   Proof:

   Let $a, b, c, r, s, k \in\bf Z^{+}$ be arbitrarily chosen such that $(a \equiv_r b) \wedge (b \equiv_s c) \wedge (k\vert r) \wedge (k \vert s)$.

   Since $a\equiv_{r} b$, by the definition of $\equiv_{r}$, $r\vert a-b$, so by the definition of divides, $\exists l\in\bf Z$, $a-b=rl$.

   Since $k\vert r$, by the definition of divides, $\exists n\in\bf Z$ $nk=r$.

   Substituting $nk=r$ into the equation $a-b=rl$, we obtain $a-b=(nk)l$.

   Since $b\equiv_{s} c$, by the definition of $\equiv_{s}$, $s\vert b-c$, so by the definition of divides, $\exists m\in\bf Z$, $b-c=sm$.

   Since $k\vert s$, by the definition of divides, $\exists j\in\bf Z$ $jk=s$.

   Substituting $jk=s$ into the equation $b-c=sm$, we obtain $b-c=(jk)m$.

   Now, we add the two equations: $a-b=(nk)l$ and $b-c=(jk)m$ to obtain

   
   

   $$(a-b)+(b-c)=nkl+jkm$$
   
   

   
   

   $$a-b+b-c=k(nl+jm)$$
   
   

   
   

   $$a-c=k(nl+jm).$$
   
   

   Since $j, l, m, n\in\bf Z$ and $\bf Z$ is closed under addition and multiplication, so by the definition of divides $k\vert a-c$, so by the definition of $\equiv_{k}$, $a\equiv_{k}c$.

   By the definition of $\equiv_{k}$,

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?

      ANSWER:

      This is a problem where we have 3 categories of things and we select 5 of them so we are placing 5 numbers into 3 categories. Therefore, this is a combination with repetition (an X's and |'s problem), so the formula is

      ${5+3-1\choose 3-1}={7\choose 2}=\frac{7!}{2!5!}$, or ${5+3-1\choose 5}={7\choose 5}=\frac{7!}{5!2!}$.

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

      ANSWER:

      This is a permutation with repetition problem. The idea is you first pick 10 spaces out of 30 for the black socks, then 10 spaces out of 20 for the brown and then the orange socks go into the last 10 spots.

      ${30\choose 10}{20\choose 10}{10\choose 10}=\frac{30!}{20!10!}\frac{20!}{10!10!}\frac{10!}{0!10!}= \frac{30!}{10!10!10!}$ after cancellation of terms.

   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.

      ANSWER:

      The total number of ways to do choose 4 socks from the 30 here is ${30\choose 4}$, so that is our denominator.

      The number of ways to pick 2 socks of 2 different colors is as follows:

      First, pick the two colors of socks we will pick socks from. There are ${3\choose 2}$ ways to do this.

      Then, within each color, we have ${10\choose 2}$ ways to pick 2 socks out of the 10 that are there. We must pick 2 socks from 2 colors, so we will square this amount in the final answer:

      
      

      $$\frac{{3\choose 2}{10\choose 2}{10\choose 2}}{{30\choose 4}}=... ...c{3!}{2!1!}\frac{10!}{2!8!}\frac{10!}{2!8!}}{\frac{30!}{4!26!}}$$
      
      

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

      ANSWER:

      We pick 9 people out of the 24 and order doesn't matter so it's a combination.

      ${24\choose 9}$.

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

      ANSWER:

      We pick 9 people out of the 24, and now order does matter, so it's a permutation.

      $P(24,9)$.

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

      ANSWER:

      If both of the players are on the same team, the number of ways they can be put onto the team is $P(9,2)$.

      That leaves 7 positions left over for 22 players to fill, and the number of ways that those positions can be filled is $P(22,7)$.

      So, the total number of ways to avoid having them on the same team is:

      $P(24,9)-P(9,2)P(22,7)$.

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

   True.

   Proof by contrapositive:

   Let $A,B\in \{sets\}$ be arbitrarily chosen such that $P(A)\subseteq P(B')$.

   Suppose that $B\not\subseteq A'$.

   Then, $\exists x\in B$, $x\not\in A'$.

   By the definition of complement, $x\in A$.

   Therefore $\{x\} \subseteq A$,

   and so by the definition of power set, $\{x\}\in P(A)$.

   Since $x\in B$, $x\not\in B'$, by the definition of complement.

   So $\{x\}\not\subseteq B'$, which means that $\{x\}\not\in P(B')$.

   Since $\{x\}\in P(A)$ and $\{x\}\not\in P(B')$,

   $\exists X\in\{sets\} X\in P(A)\wedge X\not\in P(B')$.

   The negation of this statement is

   $\forall X\in\{sets\} X\in P(A)\rightarrow X\in P(B')$, which is the definition of $P(A)\subseteq P(B')$.

   Since the negation of the statement is true, $P(A)\not\subseteq P(B')$.

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.

      ANSWER:

      It is not 1-1 because $f(0,0)=0$ and $f(1,-2)=0$, which means that two elements of the domain map to the same element of the codomain.

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

      ANSWER:

      $f$ is onto because $\forall y\in Z, f(0,y)=2(0)+y=y$.

      Hence, given any integer $y$, there is an $(a,b)\in\bf Z\times\bf Z$ such that $f(a,b)=y$. In particular, that element is $(0,y)$. (Although there are many other possi

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

      ANSWER:

      $f$ is not a bijection because bijections are 1-1 and onto, and $f$ is not 1-1.

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:

    (Assume the sets are finite.)

    A is a set of elements.
    $n(A) = m$
    B is another set of elements.
    $n(B) = x$
    
    $C = A \times P(A)$ size: $m*2^{m}$
    $D = C \times C$ size: $m^{2}2^{2m}$
    $E = A \times A$ size: $m^{2}$
    $F = E \times P(B)$ size: $m^{2}2^{x}$.

    G is a function from D to F, so the function maps from a set of size $m^{2}2^{2m}$, to a set of size $m^{2}2^{x}$.

    The ratio of the sizes of the two sets (domain/codomain) is: $\frac{m^{2}2^{2m}}{m^{2}2^{x}}=\frac{2^{2m}}{2^{x}}=2^{2m-x}.$

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

       ANSWER:

       If the function is onto, then the domain must be as large as the codomain, so we need $2^{2m-x}\geq 1$, or $2m-x\geq 0$, or $2m\geq x$.

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

       ANSWER:

       If the function is 1-1, then the domain must be no larger than the codomain, so in this case, we need $2^{2m-x}\leq 1$, or $2m-x\leq 0$, or $2m\leq x$.

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

       ANSWER:

       In this case, the domain and the codomain must have the same size.

       In this case, we need $2^{2m-x}=1$, or $2m-x=0$, or $2m=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(Yes or No) Is this relation transitive?
       

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

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

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

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

       
       
       
       
       
       
       
       

    6. NO (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''?

       ANSWER:

       Reflexive, Antisymmetric, Transitive.

       
       
       
       
       
       
       
       

    7. YES (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''?

       Reflexive, Symmetric, Transitive.

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:

       

About this document ...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.61)

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 -show_section_numbers -split 0 -no_navigation -no_footnode finalans

The translation was initiated by Fawzi Emad on 2003-05-31

Web Accessibility