\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{2, Mon.}                    % !! start the paper


\begin{problem}
Generalize the proof from lecture (reproduced below) that $\sqrt{2}$ is
irrational, for example, how about $\sqrt[3]{2}$?  Remember that an irrational
number is a number that cannot be expressed as a ratio of two integers.

\begin{quote}

\begin{theorem*}
$\sqrt{2}$ is an irrational number.
\end{theorem*}

\begin{proof}
The proof is by contradiction.  Assume for purpose of contradiction that
$\sqrt{2}$ is rational.

Then we can write $\sqrt{2} = m/n$ where $m$ and $n$ are integers and the
fraction is in lowest terms.  Squaring both sides gives $2 = m^2 / n^2$,
so $2 n^2 = m^2$.  This implies that $m^2$ is even, and hence that $m$ is
even; that is, $m$ is a multiple of $2$.  But that means $m^2$ is actually
a multiple of 4, say $m^2 = 4k$.

Now we have $2 n^2 = m^2 = 4k$, so $n^2 = 2k$.  So $n^2$ is even, and
hence $n$ is even. But since $m$ and $n$ are both even, the fraction $m/n$
is not in lowest terms, a contradiction.
\end{proof}

\end{quote}

\solution{We prove that for any $n>1$, $\sqrt[n]{2}$ is irrational by
contradiction.

Assume that $\sqrt[n]{2}$ is rational.  Under this assumption, there
exist integers $a$ and $b$ with $\sqrt[n]{2} = a/b$, where $a$
and $b$ have no common factors (so that the fraction $a/b$ is in lowest
terms).  Now we prove that $a$ and $b$ are both even, which contradicts
the existence of $a,b$.
\begin{eqnarray*}
\sqrt[n]{2} & = & \frac{a}{b}\\
2 & = & \frac{a^{n}}{b^{n}}\\
2b^{n} & = & a^{n}.
\end{eqnarray*}
The lefthand side of the last equation is even, so $a^{n}$ is even.  This
implies that $a$ is even as well (see below for justification).

In particular, $a = 2c$ for some integer $c$.  Thus, 
\begin{eqnarray*}
2b^{n} & = & (2c)^n = 2^{n}c^{n},\\
b^{n} & = & 2^{n-1}c^{n}.
\end{eqnarray*}
Since $n-1>0$, the righthand side of the last equation is an even number,
so $b^{n}$ is even.  But this implies that $b$ must be even as well,
contradicting the fact that $m/n$ is in lowest terms.

\medskip
Now we justify the claim that if $a^n$ is even, so is $a$.

There is a simple proof by contradiction: suppose $a$ was not even, \ie
$a$ is odd.  It's a familiar (and easily verified) fact that the product
of \emph{any} number of odd numbers is odd, so $a^n$ would also be odd,
contradicting the fact that $a^n$ is even.

But more generally for \emph{any} integers $m,k >0$, if $m^k$ is divisible
by a prime number, $p$, then $m$ must be divisible by $p$.  This follows
from the factorization of an integer into primes (which we'll discuss
further in a coming lecture): the primes in the factorization of $m^k$ are
precisely the primes in the factorization of $m$ repeated $k$ times, so if
there is a $p$ in the factorization of $m^k$ it must be one of $k$ copies
of a $p$ in the factorization of $m$.

\begin{optional}
%From S99 Tutorial 1 Notes:

Here's a somewhat broader generalization of the proof that $\sqrt{2}$ is
irrational.

\begin{lemma*}
Let the coefficients of the polynomial
$a_0+a_1x+a_2x^2+\cdots + a_{n-1}x^{n-1} + x^n$ be
integers.  Then any real root of the polynomial is either integral or
irrational.
\end{lemma*}

Notice that this Lemma directly implies that $\sqrt{2}$ is irrational:
$x^2 - 2$ has no integer root because 2 is not a perfect square, so the
real roots, namely, $\pm\sqrt{2}$, must be irrational.  Similarly, if $m
\in \naturals$ is not the $k$th power of an integer, then $x^k - m$ has no
integer roots, so $\sqrt[k]{m}$ will be irrational.

\begin{proof}

Let $r\in \reals$ be a root of the polynomial, that is,
\[
a_0+a_1r+a_2r^2+\cdots+  a_{n-1}r^{n-1}+ r^n = 0.
\]
There are three cases for $r$: it is either integral, irrational, or the
ratio of two integers with no common divisors where the denominator is
greater than one.  We want to eliminate the last case.

So assume to the contrary that $r = s/t$ for integers $s$ and $t$ which
have no common divisors and such that $t >1$.  Now $t$ must have a prime
divisor, $p$.

Substituting $s/t$ for $r$ and multiplying both sides of the above
equation by $t^n$ yields:
\begin{eqnarray}
a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\cdots+a_{n-1}s^{n-1}t+s^n & = & 0,\\
a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+s^{n-1}t & = & -s^n.\label{e2}
\end{eqnarray}
Then $p$ divides each term of the lefthand side of equation~\eqref{e2},
and therefore also divides the righthand side, viz., $p \divides -s^n$.
But this means that $p$ must also divide $s$.  So $p$ is a common divisor
of $s$ and $t$, contradicting our choice of $s$ and $t$.

\end{proof}

\end{optional}
}

\end{problem}

\instatements{\newpage}

\begin{problem}\label{sys}\footnote{From Rosen, 5th
edition, Exercise 1.1.36} A set of propositions is \emph{consistent} if
there is a possible situation in which they are all true.  This problem
examines whether the following specifications are consistent.

\begin{enumerate}

\item If the file system is not locked, then

   \begin{enumerate}

   \item new messages will be queued.

   \item new messages will be sent to the messages buffer.

   \item the system is functioning normally, and conversely, if the system
         is functioning normally, then the file system is not locked.

   \end{enumerate}



\item  If new messages are not queued, then they will be sent to
the messages buffer.

\item  New messages will not be sent to the message buffer.

\end{enumerate}

\bparts

\ppart Begin by translating the parts of the specification into
propositional formulas using four propositional variables:
\begin{eqnarray*}
L   & \eqdef &   \text{file system locked}, \\
Q   & \eqdef &   \text{new messages are queued}, \\
B   & \eqdef &   \text{new messages are sent to the message buffer}, \\
N   & \eqdef &   \text{system functioning normally}.
\end{eqnarray*}

\solution{
The translations of the specifications are:
\begin{align}
\neg L  \implies & Q & \tag{Spec.\ 1.(a)}\\
\neg L  \implies & B & \tag{Spec.\ 1.(b)}\\
\neg L  \bicond  & N & \tag{Spec.\ 1.(c)}\\
\neg Q  \implies & B & \tag{Spec.\ 2.}\\
\neg B           &   & \tag{Spec.\ 3.}
\end{align}}

\ppart To be precise, the specification is consistent if there is a single
choice of truth values for the variables $L,Q,B,N$, so that every one the
propositional formulas from the previous part are true.  Explain how to
use a \emph{truth table} to determine whether the specification is
consistent.

\solution{ We can construct a truth table with sixteen lines---one for
each way of assigning truth values to the four variables $L$, $N$, $Q$,
and $B$.  For each line, we could record the truth values of these five
statements above.

If all five statements are true for some assignment of truth values to the
variables, then the system is consistent.  If for every one of the
sixteen possible truth assignments, at least one of the five statements
is false, then the system is inconsistent.  Carrying out the calculation
shows that there is a unique assignment of True/False values to $L$, $N$,
$Q$, and $B$ (see below) that satisfies all the specifications.}

\ppart Use \emph{simple reasoning by cases} to find a truth assignment
that confirms that this system specification is consistent.  Explain why
there is only one such assignment.

\solution{
We can avoid the full truthtable calculation if we reason by
cases.

\textbf{Case 1} ($B$ is True):  Then the last formula, (Spec.\ 3.), is false,
and the whole specification is false.

\textbf{Case 2} ($B$ is False): Now (Spec.\ 2.) and (Spec.\ 1.(b)) can be
true only if $Q$ and $L$ are true.  Since $L$ is true, (Spec.\ 1.(c)) can
be true only if $N$ is false.  Thus, we have deduced that in order to be
consistent, we must have
\begin{eqnarray*}
L       & = &   \text{True} \\
N       & = &   \text{False} \\
Q       & = &   \text{True} \\
B       & = &   \text{False}.
\end{eqnarray*}

From the way this assignment was constructed, we know it ensures that
formulas from (Spec.\ 1.(b)) on are true.  So all that remains is to check
formula (Spec.\ 1.(a)), and indeed it is also true under this assignment.

So the system is consistent, and this is the only assignment that will
satisfy it.}

\eparts
\end{problem}

\begin{problem}
If we raise an irrational number to an irrational power, can the result be
rational?  Show that it can by considering $\sqrt{2}^{\sqrt{2}}$ and
arguing by cases.

\solution{
We want to find irrational numbers $a,b$ such that $a^b$ is rational.
We argue by cases.

Case 1: [$\sqrt{2}^{\sqrt{2}}$ is rational].  Let $a = b = \sqrt{2}$.  $a$
and $b$ are irrational since $\sqrt{2}$ is irrational as we know.  Also,
$a^b$ is rational by case hypothesis.  So we have found the required $a$
and $b$ in this case.

Case 2: [$\sqrt{2}^{\sqrt{2}}$ is irrational].  Let $a =\sqrt{2}^{\sqrt{2}}$
and $b = \sqrt{2}$.  Then $a$ is irrational by case hypothesis, we know
$b$ is irrational, and
\[
a^b = \paren{\sqrt{2}^{\sqrt{2}}}^{\sqrt{2}} =
      \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2,
\]
which is rational.  So we have found the required $a$
and $b$ in this case also.

So in any case, there will be irrational $a,b$ such that $a^b$ is rational.
}

\end{problem}

\iffalse
\instatements{\newpage}
\begin{problem}
Why the propositional operators $\land, \lor, \neg$?  Because for any
finite set of propositional variables, every propositional function of
these variables is definable by an expression using only these variables
and operators.

To illustrate how this works, consider the truth assignment
$(\true,\true,\false,\true)$ for the propositional variables
$(P_1,P_2,P_3,P_4)$.  Then the formula,
\begin{equation}\label{pe}
(P_1 \equiv \true) \land (P_2 \equiv \true) \land (P_3 \equiv \false)
\land (P_4 \equiv \true)
\end{equation}
is true for this assignment and no other.  But since $P \equiv \true$ is
equivalent simply to $P$, and $P \equiv \false$ is equivalent to
$\bar{P}$, we can simplify~\eqref{pe} to the equivalent formula
\begin{equation}\label{c4}
P_1 \land P_2 \land \bar{P_3} \land P_4.
\end{equation}
That is,~\eqref{c4} is true when $P_1,P_2,P_3,P_4$ are assigned the values
\true,\true,\false,\true, but not for any other assignment of values.

Now explain how, given any set of truth assignments for $P_1,\dots,P_n$,
you could write a propositional formula, $F$, using only these variables
and the operators $\land, \lor, \neg$ such that $F$ is true for exactly
the given set of truth assignments.

\solution{
Let $P^{(\false)}$ be another notation for $\bar{P}$, and $P^{(\true)}$ simply
be another notation for $P$.  So
\[
F_{(a_1,\dots,a_n)} \eqdef P^{(a_1)} \land \dots P^{(a_n)}
\]
is a formula that is true exactly for the truth assignment
$(a_1,\dots,a_n)$.  So if $\set{\mathbf{s}_1, \dots \mathbf{s}_k}$ is a
set of truth assignments, then
\[
F_{\mathbf{s}_1} \lor  \dots \lor F_{\mathbf{s}_k}
\]
is the desired formula.  Formulas of this form are said to be in \emph{complete
disjunctive form}.
}

\end{problem}


\instatements{\newpage}

\begin{problem}
``NAND'' is a Boolean operation denoted~$\nand$ which takes two argument.
$A \nand B$ means $\neg (A \conj B)$.  Show that all the basic boolean
operations can be defined solely in terms of the NAND operation (and
parentheses), \eg $\neg A$ can be defined as $A \nand A$.

\begin{problemparts}

\problempart $A \disj B$
\solution{
       $(A \nand A) \nand (B \nand B)$
}

\problempart $A \conj B$
\solution{
  $(A \nand B) \nand (A \nand B)$ 
}

\problempart $A \implies B$
\solution{
  $A \nand (B \nand B)$
}
\end{problemparts}

\end{problem}
\fi

\end{document}
