\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}  (Carried over from 2/6/04.)

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\footnote{Rosen, Exercise 1.1.36} 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}


\instatements{\newpage}
\begin{problem}
For each of the logical formulas, indicate whether or not it is true when
the domain of discourse is $\naturals$ (the natural numbers), $\integers$
(the integers), $\rationals$ (the rationals), $\reals$ (the real numbers),
and $\complexes$ (the complex numbers).

\[\begin{array}{rrl}
          & \exists x & (x^2  = 2)\\
\forall x & \exists y & (x^2  = y)\\
\forall y & \exists x & (x^2  = y)\\
\forall x\neq 0 & \exists y & (xy = 1)\\
\exists x & \exists y & (x + 2y = 2) \conj (2 x + 4 y = 5)
\end{array}\]

\solution{\[
\begin{array}{llllll}
Statement & \naturals & \integers & \rationals & \reals & \complexes\\
\exists x\ (x^2=2) & f & f & f & t\ (x=\sqrt{2}) & t\\
\forall x \exists y\ (x^2 = y) & t & t & t & t\ (y=x^2)& t\\
\forall y \exists x\ (x^2=y) & f & f & f & f\ (\text{take }y<0) & t\\
\forall x\neq 0\exists y\ (xy=1) & f & f & t & t\ (y=1/x) & t\\
\exists x \exists y\ (x + 2y = 2) \conj (2 x + 4 y = 5) & f & f & f & f & f
\end{array}
\]
}
\end{problem}

\instatements{\newpage}
\begin{problem}

The goal of this problem is to translate some assertions about binary
strings into logic notation.  The domain of discourse is the set of all
finite-length binary strings: $\lambda$, 0, 1, 00, 01, 10, 11, 000, 001,
\ldots.  (Here $\lambda$ denotes the empty string.)  In your translations,
you may use all the ordinary logic symbols (including \texttt{=}),
variables, and the binary symbols \texttt{0}, \texttt{1} denoting 0, 1.

A string like $\mathtt{01}x\mathtt{0}y$ of binary symbols and variables
denotes the \emph{concatenation} of the symbols and the binary strings
represented by the variables.  For example, if the value of $x$ is
\texttt{011} and the value of $y$ is \texttt{1111}, then the value of
$\mathtt{01}x\mathtt{0}y$ is the binary string \texttt{0101101111}.

Here are some examples of formulas and their English translations.  Names
for these predicates are listed in the third column so that you can reuse
them in your solutions (as we do in the definition of the predicate
{\sc no-1s} below).

\begin{center}
\begin{tabular}{lclcl}
Meaning & \hspace{0.25in} & Formula & \hspace{0.25in} & Name \\ \hline
$x$ is a prefix of $y$ & & $\exists z\ (xz = y)$ & & \sc{prefix}($x, y$) \\
$x$ is a substring of $y$ & & $\exists u \exists v\ (uxv = y)$ & & \sc{substring}($x, y$) \\
$x$ is empty or a string of 0's & & $\neg \text{\sc{substring}}(\mathtt{1},x)$
 & & \sc{no-1s}($x$)
\end{tabular}
\end{center}

\begin{problemparts}

\problempart $x$ consists of three copies of some string.

\solution{
$\exists y\ (x = yyy)$
}
\problempart $x$ is an even-length string of 0's.

\solution{
$\text{\sc{no-1s}}(x) \conj \exists y\ (x = yy)$
}

\problempart $x$ does not contain both a 0 and a 1.

\solution{
$\neg [\text{\sc{substring}}(\mathtt{0}, x) \conj \text{\sc{substring}}(\mathtt{1}, x)]$

\iffalse
Another solution is
\[
\text{\sc{no-1s}}(x) \disj \text{\sc{no-0s}}(x).
\]
\fi
}

\problempart $x$ is the binary representation of $2^k + 1$ for some
integer $k \geq 0$.

\solution{ $(x = \mathtt{10}) \disj (\exists y\ (x = \mathtt{1}y\mathtt{1}
\conj \text{\sc{no-1s}}(y)))$ }


\ppart An elegant, slightly trickier way to define $\text{\sc{no-1s}}(x)$
is:
\begin{equation}\tag{*}
\text{\sc{prefix}}(x, \mathtt{0}x).
\end{equation}
Explain why~(*) is true only when $x$ is a string of 0's.

\iffalse
Explain why can't we define ``$x$ is an even-length string of 0's,'' by
\begin{equation}\tag{**}
\text{\sc{prefix}}(x, \mathtt{00}x).
\end{equation}
\fi

\solution{Prefixing $x$ with 0 rightshifts all the bits.  So the $n$th
symbol of $x$ shifts into the $(n+1)$st symbol of $0x$.  Now for $x$ to be
a prefix of $0x$, the $n+1$st symbol of $0x$ must match the $(n+1)$st
symbol of $x$.  So if $x$ satisfies~(*), the $n$th and $(n+1)$st symbols
of $x$ must match.  This holds for all $n>0$ up to the length of $x$, that
is, \emph{all} the symbols of $x$ must be the same.  In addition, if
$x\neq \lambda$, it must start with 0.  Therefore, if $x$ satisfies~(*),
all its symbols must be 0's.

Note that it's easy to see, conversely, that if $x = \lambda$ or $x$ is
all 0's, then of course it satisfies~(*).  }

\end{problemparts}

\end{problem}


\iffalse

\instatements{\newpage}
\begin{problem}
Express each of the following propositions and predicates in formal logic
notation.  The domain of discourse is the nonnegative integers,
$\naturals$.

In addition to the propositional operators, variables and quantifiers, you
may define predicates using addition, multiplication, \emph{positive}
integers, and equality and inequality symbols.  For example, the
proposition ``n is an odd number'' could be written
\[
\exists m\ (2 m + 1 = n).
\]

\begin{problemparts}
\problempart 
$n$ is the sum of three perfect squares.

\solution{
\[
\exists x \exists y \exists z\ (x \cdot x + y \cdot y + z \cdot z = n)
\]
}
\end{problemparts}

Since 0 is not an allowed constant, the predicate ``$x \neq 0$'' can't be
written directly, but note that it could be expressed in a simple way:
\[
\neg (x + x = x).
\]
Then the predicate $x > y$ could be expressed
\[
\exists w\ (y + w = x) \land (w \neq 0).
\]
Note that we've used ``$w \neq 0$'' in this formula, even though it's
technically not allowed.  But since we've shown how to express it by the
genuine formula, ``$\neg(w + w = w)$,'' we can use ``$w \neq 0$'' with the
understanding that it abbreviates the real thing.  And now that we've
shown how to express ``$x>y$'', it's ok to use it too.

\begin{problemparts}
\problempart 
$n$ is a prime number.

\solution{
\[
\text{\sc{is-prime}}(n) \eqdef (n > 1) \conj \neg (\exists x \exists y\ (x > 1) \conj (y > 1) \conj (x \cdot y = n))
\]
}

\problempart 
$n$ is a product of two distinct primes.

\solution{
\[
\exists x \exists y\ \neg (x = y) \land (n = x \cdot y) \land
\text{\sc{is-prime}}(x)
\land \text{\sc{is-prime}}(y).
\]
}

\problempart There is no largest prime number.

\solution{Of course this is a true statement, so it could be expressed by
the logically equivalent formula ``$1=1$,'' but even if we didn't know
this, we could transcribe the statement directly as:
\[
\neg \left(\exists p (Prime(p) \conj (\forall q (Prime(q) \implies p \geq q)))
\right)
\]
}

\problempart (Goldbach Conjecture) Every even natural number $n > 2$ can
be expressed as the sum of two primes.

\solution{
\[
\forall n \left( (n > 2 \conj \exists k\ n = 2k) \implies \exists p
\exists q (Prime(p) \conj Prime(q) \conj (n = p + q)) \right)
\]
}

\problempart (Bertrand's Postulate) If $n > 1$, then there is always
at least one prime $p$ such that $n < p < 2n$.

\solution{
\[
\forall n
\left( (n > 1) \implies (\exists p ( Prime(p)  \conj (n < p) \conj (p < 2n))) 
\right)
\]
}

\end{problemparts}
\end{problem}
\fi

\end{document}
