CMSC 250

Quiz #6 ANSWERS

Wed., Oct. 6, 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. [22 pnts.] Disprove by counter example or Prove each of the following:
   1. For any two consecutive integers, their product is even. (For this you may assume a fact proven in class that a number that is not even is indeed odd and a number that is not odd is even, but note that we have not proven that when you have two consecutive integers one is even and one is odd.)

      $\forall m,n \in Z, m=n+1 \rightarrow m*n \in Z^{even}$

      Proof:

      Let m and n be arbitrary integers.

      Assume m = n+1.

      $m*n = (n+1) * n$ by substitution.

      $= n^2 + n$ by multiplying through the n.

      Case 1: ( $n \in Z^{even}$)

      $\exists k \in Z, n = 2k$ by definition of even.

      $m * n = n^2 +n$ by substitution from above.

      $= (2k)^2 + 2k$ by substitution.

      $= 4k^2 + 2k$ by multiplying out the square.

      $= 2(2k^2+k)$ by distributing out the 2.

      Since $2k^2+k \in Z$ by closure of Z in multiplication and addition,

      $2(2k^2+k) \in Z^{even}$ by definition of even.

      and $m*n \in Z^{even}$ by substitution.

      Case 2: ($n \in Z^{odd}$)

      $\exists k \in Z, n = 2k+1$ by definition of odd.

      $m * n = n^2 +n$ by substitution from above.

      $= (2k+1)^2 + (2k+1)$ by substitution.

      $= 4k^2 + 2k$ by algebra.

      $= 2(2k^2+k)$ by distributing out the 2.

      Since $2k^2+k \in Z$ by closure of Z in multiplication and addition.

      $2(2k^2+k) \in Z^{even}$ by definition of even.

      and $m*n \in Z^{even}$ by substitution.

      Since these are the only two possibilities for the value n,

      and they both lead to the conclusion that $m*n \in Z^{even},$

      by dilema, we know that $m*n \in Z^{even}$.

      Closing the conditional world we get the implication:

      $m = n+1 \rightarrow m*n \in Z^{even}$

      And since m and n were arbitrary in Z, we get the statement:

      $\forall m,n \in Z, m=n+1 \rightarrow m*n \in Z^{even}$

   2. For any positive integer a and any rational number b, $\frac{b}{a} \in Q$.

      $\forall a \in Z^+, \forall b \in Q, \frac{b}{a} \in Q$

      PROOF:

      Let a be arbitrary in $Z^+$.

      Let b be arbitrary in Q.

      Since $b \in Q,$ it must be the case that $\exists c,d \in Z, b = \frac{c}{d} \wedge d \neq 0$

      by the definition of rational.

      $\frac{b}{a} = \frac{\frac{c}{d}}{a}$ by substitution.

      $= \frac{c}{da}$ by algebra.

      Since $c \in Z$ as defined above,

      and $da \in Z$ by closure of Z in multiplication,

      and $da \neq 0$ because $d \neq 0$ as defined above and $a \neq 0$ since it is in $Z^+$.

      $\frac{c}{da} \in Q$ by definition of rational.

      and $\frac{b}{a} \in Q$ by substitution.

      Since a and b were both arbitrary as defined above,

      $\forall a \in Z^+, \forall b \in Q, \frac{b}{a} \in Q$

      by generalizing from the generic particulars.

2. [8 pnts.] State Yes or No for each of the following (only a small justification for your answer is necessary not a complete proof). Assume a, b and c are integers and x, y and z are rationals for all of the following questions.
   1. NO $\forall x \in Z, \exists y \in Z, x+y = 0 \wedge x \neq y$ This is no becuase $0 \in Z$, but $\sim \exists y \in Z, 0+y = 0 \wedge y \neq 0$
      
      
      
      
   2. NO Every rational number has a mulitplicative inverse (you can find anohter rational number that has its numerator and denominator exchanged). This is because $\frac{0}{1} \in Q$ but $\sim (\frac{1}{0} \in Q)$
      
      
      
      
   3. NO The sum of three consecutive integers is always even. Counter example: 4+5+6 = 15 and $\sim (15 \in Z^{even})$
      
      
      
      
   4. YES The product of three consecutive integers is always even.

Web Accessibility