


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 1
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{8} \textbf{Structured Reasoning}

For this proof, fill in the predicate and quantifier rules used for
each step denoted with a *, and say which statements they are based on.


\begin{tabbing}
Given: $\forall x \exists y [Q(x, y) \vee R(x, y)]$\\
Prove: $\forall x [\exists y Q(x,y) \vee \exists y R(x,y)]$\\
Proof:\\
*\=XX\=*\=XX\=*\=XXXXXXXXXXXXXXXXXXXXXXXXX\=\kill
\>1.  Let $x_0$ be  arbitrary.\\         
\>2.  $\exists y [Q(x_0, y) \vee R(x_0, y)]$
\>\>\>\>\>Universal Instantiation, from Given\\
\>3.  $Q(x_0, y_0) \vee R(x_0, y_0)$
\>\>\>\>\>Existential Instantiation, from 2.\\
\>4.  $\exists y Q(x_0, y) \vee \exists y R(x_0, y):$\\
\>\>\>4.1.  case $i$:  Assume $Q(x_0, y_0)$.\\
\>\>\>\>*4.1.1.  $\exists y Q(x_0, y)$
\>\>\underline{\hspace{2in}}\\
\>\>\>\>*4.1.2.  $\exists y Q(x_0, y) \vee \exists y R(x_0,y)$
\>\>\underline{\hspace{2in}}\\
\>\>\>4.2.  case $ii$:  Assume $R(x_0, y_0)$.\\
\>\>\>\>\>4.2.1.  $\exists y R(x_0, y)$\\
\>\>\>\>\>4.2.2.  $\exists y Q(x_0, y) \vee \exists y R(x_0,y)$\\
\>\>*4.3. QED $\exists y Q(x_0, y) \vee \exists y R(x_0, y)$
\>\>\>\>\underline{\hspace{2in}}\\
*5. QED $\forall x [\exists y Q(x,y) \vee \exists y R(x,y)]$
\>\>\>\>\>\>\underline{\hspace{2in}}
\end{tabbing}

\solution{ {\bf Solution:}
4.1.1:  Existential Generalization, from 4.1

4.1.2:  Addition, from 4.1.1

4.3:  Proof by cases, from 3, 4.1.2, and 4.2.2

5:  Universal Generalization, from 1 and 4.3
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 1
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem\pts{30} \textbf{Predicates and Quantifiers}

Use the following propositions where the universe of discourse is the
set of all natural numbers:

\begin{eqnarray*}
P(n):& n \hbox{ is a perfect square}\\
Q(n):& n \hbox{ is prime}\\
R(n,m):& n < m\\
S(n,m):& n \hbox{ divides } m\\
T(n,m):& n = m\\
\end{eqnarray*}

Express each of the following statements using quantifiers, logical
connectives, and the propositions listed above, along with variables and
integers.

\begin{problemparts}

\problempart {\bf (5 points)}  4 is a perfect square and 4 is greater than 1.

\solution{ 
\bigskip
{\bf Solution: }
$P(4) \wedge R(1,4)$ 
}
\bigskip

\smallspace

\problempart {\bf (5 points)}  There is a natural number that divides 
all natural numbers.

\solution{ 
\bigskip
{\bf Solution: }
$\exists n \forall m S(n, m)$
}

\bigskip

\smallspace

\problempart {\bf (5 points)} Two natural numbers are equal exactly
when neither is less than the other.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n \forall m T(n, m) \leftrightarrow \neg R(n, m) \wedge
\neg R(m, n)$
}

\nextproblem

\problempart {\bf (5 points)} A natural number $n$ that is greater
than 1 is prime exactly when the only positive natural number less
than $n$ that divides $n$ is 1.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n Q(n) \wedge R(1,n) 
\leftrightarrow [\forall m R(0, m) \wedge R(m, n)
\wedge S(m, n) \rightarrow T(m, 1)]$
}

\smallspace

\problempart {\bf (5 points)} A natural number $n$ is a perfect square
only if there is a positive natural number (strictly) between 1 and
$n$ that divides $n$.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n P(n) \rightarrow [\exists m R(0, m) \wedge R(1, m) 
\wedge R(m, n) \wedge S(m, n)]$
}

\smallspace

\problempart {\bf (5 points)} Given only the statements (a)-(e) above
and the standard rules of propositional and quantifier reasoning, can
you conclude that 4 is not prime?  If not, state a fact you can use
together with the statements (a)-(e) to conclude that 4 is not prime
(your fact should not mention the number 4).  If so, just list which
of the statements (a)-(e) above are necessary.


\solution{
\bigskip
{\bf Solution: }
We can conclude that 4 is not prime, using parts (a), (c), (d), and (e).

Though a structured proof was not required, we provide one.  The
statement from part (c) was necessary so that we can use that if $m_0
> 1$ then $\neg m_0 = 1$.  Parts (d), and (e) are clearly required, and
part (a) is required so that we know 4 is a perfect square and that 4 > 1,
which are required to use the implications from (d) and (e).  Here is the
structured proof:


\begin{tabbing}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\=XXXXXX\=\kill
1.  $P(4) \rightarrow [\exists m R(0, m) \wedge R(1, m) \wedge R(m, 4)
\wedge S(m, 4)]$\>UI, from part (e).\\
2.  $P(4)$\>Simplification, from part (a).\\
3.  $\exists x R(0, x) \wedge R(1, x) \wedge R(x, 4) \wedge S(x, 4)$
\>Modus Ponens, from 1 and 2.\\
4.  $R(0, m_0) \wedge R(1, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$
\>EI, from 3.\\
5.  $R(1, m_0)$ \>Simplification, from 4.\\
6.  $T(1, m_0) \leftrightarrow \neg R(1, m_0) \wedge \neg R(m_0, 1)$
    \>UI, from part (c).\\
7.  $\neg R(1, m_0) \wedge \neg R(m_0, 1) \leftarrow T(1, m_0)$
    \>Simplification, from 6.\\
8.  $\neg [R(1, m_0) \vee R(m_0, 1)] \leftarrow T(1, m_0)$
    \>DeMorgan's law, from 7.\\
9.  $R(1, m_0) \vee R(m_0, 1)$  \>Addition, from 5.\\
10.  $\neg T(1, m_0)$  \>Modus Tollens, from 8 and 9.\\
11.  $R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$ \>Simplification,
     from 4.\\
12.  $(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \wedge \neg T(1,
     m_0)$ \>Conjunction, from 10 and 11.\\
13.  $\neg[\neg (R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \vee
     T(1, m_0)]$ \>DeMorgan's Law, from 12.\\
14.  $\neg[(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \rightarrow
     T(1, m_0)]$ \>Logical equivalence, from 13.\\
15.  $\exists m \neg [(R(0, m) \wedge R(m, 4) \wedge S(m, 4))
     \rightarrow T(1, m)]$ \>EG, from 13.\\
16.  $\neg \forall m [(R(0, m) \wedge R(m, 4) \wedge S(m, 4)) \rightarrow
     T(1, m)]$ \>Negation rule for quantifiers\\
17.  $Q(4) \wedge R(1,4) \leftrightarrow [\forall m R(0, m) \wedge
     R(m, 4) \wedge S(m, 4) \rightarrow T(m, 1)]$ \>\>UI, from part (d).\\
18.  $\neg (Q(4) \wedge R(1,4))$  \>Modus Tollens, from 15 and 16.\\
19.  $\neg Q(4) \vee \neg R(1,4)$  \>DeMorgan's Law, from 18.\\
20.  $R(1,4)$ \>Simplification, from part (a).\\
21.  QED $\neg Q(4)$  \>Disjunctive Syllogism, from 19 and 20.  
\end{tabbing}}
\nextproblem

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} Define the matrix

\begin{eqnarray*}
M & = & \left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right].
\end{eqnarray*}

Let $M^n$ denote the product of $n$ copies of the matrix $M$.  Use
ordinary induction to prove that for all $n \geq 1$, the upper right
entry of $M^n$ is $F_n$, the $n$-th Fibonacci number.  State your
inductive hypothesis clearly.

For reference, the standard formula for the product of $2 \times 2$
matrices is given below.

\begin{eqnarray*}
\left[
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right]
\cdot
\left[
\begin{array}{cc}
e & f \\
g & h
\end{array}
\right]
& = &
\left[
\begin{array}{cc}
ae + bg & af + bh \\
ce + dg & cf + dh
\end{array}
\right]
\end{eqnarray*}

Recall that $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, \ldots.

\solution{
\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that

\begin{eqnarray*}
M^n & = & \left[
\begin{array}{cc}
F_{n-1} & F_n \\
F_n & F_{n+1}
\end{array}
\right].
\end{eqnarray*}

In the base case, $P(1)$ is true because

\begin{eqnarray*}
M^1 & = & 
\left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right] \\
& = &
\left[
\begin{array}{cc}
F_0 & F_1 \\
F_1 & F_2
\end{array}
\right].
\end{eqnarray*}
\end{proof}

In the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The following equalities hold.

\begin{eqnarray*}
M^{n+1} & = &   M^n \cdot M \\
    & = &   \left[
        \begin{array}{cc}
        F_{n-1} & F_n \\
        F_n & F_{n+1}
        \end{array}
        \right] \cdot
        \left[
        \begin{array}{cc}
        0 & 1 \\
        1 & 1
        \end{array}
        \right] \\
    & = &   \left[
        \begin{array}{cc}
        F_n & F_{n-1} + F_n \\
        F_{n+1} & F_n + F_{n+1}
        \end{array}
        \right] \\
    & = &   \left[
        \begin{array}{cc}
        F_n & F_{n+1} \\
        F_{n+1} & F_{n+2}
        \end{array}
        \right]
\end{eqnarray*}

The first step uses the definition of $M^n$.  The second step uses the
induction hypothesis and the definition of the matrix $M$.  We carry
out a matrix multiplication in the third step and use the Fibonacci
recurrence in the last step.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  {\bf (6 points)} Consider the following proposition.

\[
\forall x \forall y \ (x < y \rightarrow \exists z \ (x < z \wedge z < y))
\]

\begin{problemparts}

\problempart {\bf (2 points)}  Prove or disprove this proposition,
assuming that the universe is the set of integers.

\examonly{\vspace{2 in}}

\solution{ The proposition is false.  In the case where $x = 0$ and $y
= 1$, there does not exist an integer $z$ such that $x < z$ and $z <
y$.  }

\problempart {\bf (4 points)}  Write the negation of this proposition.
Your solution may {\em not} use the $\neg$ symbol, but may use any of
the relations $=$, $<$, $>$, $\leq$, or $\geq$.

\examonly{\vspace{1.0 in}}

\solution{
\[
\exists x \exists y \ (x < y \wedge \forall z \ (x \geq z \vee z \geq y))
\]
}

\end{problemparts}