\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, Wed.}                    % !! start the paper

\section{Problems}

\begin{problem}
Translate the following statements into logic notation, where
\begin{itemize}

\item the domain of discourse is $\set{ \mbox{linux}, \mbox{OS10},
\mbox{Win2K}, \mbox{WinXP}, \mbox{solaris} }$,

\item the predicate $D(x)$ means ``$x$ is \textbf{d}oomed to
obsolescence,''

\item $L(x, y)$ means ``$x$ will continue to be developed for at
\textbf{l}east as \textbf{l}ong as $y$.''

\item $F(x, y)$ means ``$x$ runs \textbf{f}aster than $y$ on the
benchmark.''

\end{itemize}

\begin{problemparts}

\iffalse
\problempart If neither solaris nor OS10 is doomed to obsolescence, then
solaris and linux will continue to be developed for the same amount of
time.

\solution{
\[
(\neg D(\mbox{solaris}) \conj \neg D(\mbox{OS10})) \implies
(L(\mbox{linux}, \mbox{solaris}) \conj L(\mbox{solaris}, \mbox{linux}))
\]
}
\fi

\problempart All the systems except for Win2K will last as long as OS10,
but none except OS10 will last as long as linux.

\solution{
Here is a fairly literal translation of the given sentence:
\begin{eqnarray*}
\forall x\ ( x  =   \mbox{Win2K}   			\iff \neg L(x, \mbox{OS10})) \conj 
\forall x\ ((x =   \mbox{OS10} \lor x = \mbox{linux})   \iff L(x, \mbox{linux})) 
\end{eqnarray*}

A student pointed out that this statement is false, so logically 
speaking it could be
stated equivalently by the propositional constant \emph{false}.  But this
would not exactly be a \emph{translation} of the English into a logical
formula.

The reason the statement is false is that OS10 and linux both last as long
as each other (as implied by the first and second halves of the sentence).
That is, they must last the same amount of time.  But we know that solaris
will last as long as OS10 by the first half of the sentence, but solaris
will not last as long as linux by the second half of the sentence, a
contradiction.
}

\problempart There is a system that runs faster on the benchmark than
another one, but even so, it will not last as long.

\solution{
\[
\exists x \exists y (F(x, y) \conj \neg L(x, y))
\]

Note that it would be correct to have written ``$\exists y \neq x$''
instead of just ``$\exists y$'' as above.  But this isn't necessary,
because $F(x,y)$ is only true when $x \neq y$ anyway.}

\problempart The system that runs fastest on the benchmark is not doomed
to obsolescence.

\solution{
\[
\exists x \forall y \neq x\ (F(x, y) \conj \neg D(x)).
\]
Equivalently,
\[
\forall x [(\forall y \neq x\ F(x, y)) \implies \neg D(x)].
\]
}

\problempart How could you express ``All the systems except for Win2K will
last as long as OS10,'' \emph{without} using any quantifiers ($\forall,
\exists$), that is, using only the propositional connectives and
constants?

Can you generalize to explain how \emph{any} logical formula over this
domain of discourse can be expressed without quantifiers?  How big would
the formula in the previous part be if it was expressed this way?

\solution{
\[
L(\mbox{linux},\mbox{OS10}) \land
L(\mbox{WinXP},\mbox{OS10}) \land L(\mbox{solaris},\mbox{OS10})
\land L(\mbox{OS10},\mbox{OS10}) \land \neg L(\mbox{Win2K},\mbox{OS10})
\]

In general, quantifiers can be eliminated by treating $\forall x\ P(x)$ as an
abbreviation for
\[
P(\mbox{linux}) \land P(\mbox{OS10}) \land P(\mbox{Win2K}) \land P(\mbox{WinXP}) \land
P(\mbox{solaris}),
\]
and $\exists x\ P(x)$ as an abbreviation for
\[
P(\mbox{linux}) \lor P(\mbox{OS10}) \lor P(\mbox{Win2K}) \lor
P(\mbox{WinXP}) \lor P(\mbox{solaris}).
\]

Expanded this way, the two-quantifier formula of the previous part would
expand by a factor of $ 5 \times 5 = 25$.  Similarly, a formula starting
with $n$ quantifiers would expand by a factor of $5^n$.  So using
quantifiers can pay off even when they are not strictly necessary.}

\end{problemparts}
\end{problem}


\instatements{\newpage}
\begin{problem}
\bparts

\ppart Prove that
\begin{equation}\label{v}
\exists z\ [Q(z) \land P(z)] \implies [\exists x\ Q(x) \land \exists y\ P(y)]
\end{equation}
is valid.  (The similar proof from lecture appears on the next page.)

\solution{
\begin{proof}
Assume
\begin{equation}\label{hyp}
\exists z\ [Q(z) \land P(z)].
\end{equation}
That is, $Q(z) \land P(z)$ holds for some element, $z$, of the domain.
Let $c$ be this element; that is, we have $Q(c) \land P(c)$.

In particular, $Q(c)$ holds by itself.  So we conclude (by Existential
Generalization) $\exists x\ Q(x)$.  We conclude $\exists y\ P(y)$
similarly.  Hence,
\begin{equation}\label{conc}
\exists x\ Q(x) \land \exists y\ P(y)
\end{equation}
holds.  

This shows that~(\ref{conc}) holds in any interpretation in
which~(\ref{hyp}) holds.  Therefore,~(\ref{hyp}) implies~(\ref{conc}) in
all interpretations, that is,~(\ref{v}) is valid.
\end{proof}}


\ppart Prove that the converse of~(\ref{v}) is not valid.  (The similar
proof from lecture appears on the next page.)

\solution{
\begin{proof}
We describe a counter model in which,~(\ref{conc}) is true and~(\ref{hyp})
is false.

The same counter model used in lecture for~(\ref{**}) will work here as
well.  Namely, $\exists x Q(x)$ is true (let $x$ be $e$) and likewise
$\exists y P(y)$ is true (let $y$ be $\pi$), so~(\ref{conc}) holds.

On the other hand, $Q(\pi)$ is not true, so $Q(\pi) \land P(\pi)$ is not
true.  Likewise $Q(e) \land P(e)$ is not true.  Since these are the only
elements of $D$, it is not true that there is an element, $z$, of $D$,
such that $Q(z) \land P(z)$,  That is,~(\ref{hyp}) is not true.
\end{proof}}
\eparts

\end{problem}

\instatements{\newpage}

\section{Example from Lecture on Proving and Disproving Validity}

\begin{proposition}
The assertion
\begin{equation}\label{*}
[\forall z\ Q(z) \land P(z)] \implies [\forall x\ Q(x) \land \forall y\
P(y)]
\end{equation}
is valid.
\end{proposition}

\begin{proof}
Assume
\begin{equation}\label{hyp2}
\forall z\ Q(z) \land P(z).
\end{equation}
That is, $Q(z) \land P(z)$ holds for every element, $z$, of the
domain.  Now, let $c$ be any domain element; so in particular,
$Q(c)\land P(c)$ holds.  Therefore, $Q(c)$ by itself certainly holds.

But $c$ could have been any element of the domain.  So (by
\emph{Universal Generalization}), we conclude $\forall x\ Q(x)$.
In the same way, we also conclude $\forall y\ P(y)$.
Therefore their conjunction holds, that is,
\begin{equation}\label{conc2}
\forall x\ Q(x) \land \forall y\ P(y).
\end{equation}

This shows that~(\ref{conc2}) holds in any interpretation in
which~(\ref{hyp2}) holds.  Therefore, the implication~(\ref{*}) holds
in all interpretations, that is,~(\ref{*}) is valid.

\end{proof}

\begin{proposition}
The assertion
\begin{equation}\label{**}
[\forall z\ Q(z) \lor P(z)]  \implies [\forall x\ Q(x) \lor \forall y\ Q(y)] 
\end{equation}
is \emph{not} valid.
\end{proposition}

\begin{proof}
We describe a \emph{counter model} to~(\ref{**}), that is, a model where
\begin{enumerate}

\item\label{az} $\forall z\ [Q(z) \lor P(z)]$ is true, but
\item\label{ax} $\forall x\ Q(x) \lor \forall y\ P(y)$ is not true.

\end{enumerate}

Namely, let the domain consist of just the two numbers $\pi$ and $e$:
\[
D \eqdef \set{e,\pi},
\]
and define
\begin{eqnarray*}
P(z) &\eqdef& [z = \pi],\\
Q(z) &\eqdef& [z = e].
\end{eqnarray*}

Since $(z = e) \lor (z = \pi)$ is true if $z$ is $\pi$ and also if $z$ is
$e$, we conclude that $(z = e) \lor (z = \pi)$ holds for all $z \in D$.
This proves~\ref{az}.

On the other hand, $Q(z)$ is not true for $z=\pi$, and therefore, $\forall
z\ Q(z)$ is not true.  Similarly, $\forall z\ P(z)$ is not true, so their
disjunction (or) is not true, proving~\ref{ax}.
\end{proof}


\instatements{\newpage}
\section{Defining a Limit}
\begin{problem}
A \emph{limit point} of a set, $A$, of real numbers, is a number $p \in
\reals$ such that elements of $A$ can be found that are different from
$p$, but as close to $p$ as desired.  Write a simple formula with
quantifiers that defines the predicate ``$A$ has a limit point.''

\solution{
\[
\exists p\forall \epsilon > 0 \exists a \in A [(a \neq p) \land \abs{p - a} < \epsilon]
\]

A way to understand this is as a 2-player game with players alternating
moves:
\begin{enumerate}

\item Player 1 picks a number, $p$.

\item Player 2 says how close he desires to be to $p$ by choosing a
number, $\epsilon > 0$.

\item Player 1 picks a number $a \in A-\set{p}$, and \emph{wins} when
$a$ is as close to $p$ as Player 2 desired, that is, when $\abs{p - a}
< \epsilon$.

\end{enumerate}
Saying that $A$ has a limit point is the same as saying that Player 1 has
a \emph{winning strategy}: a way of playing this game that guarantees he
wins no matter what Player 2 does.}

\end{problem}



\end{document}
