\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


%cp2w F02
\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 0, 1, 2,
\dots), $\integers$ (the integers), $\rationals$ (the rationals), $\reals$
(the real numbers), and $\complexes$ (the complex numbers).

\[\begin{array}{rrrcl}
          & \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) \wedge (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) \wedge (2 x + 4 y = 5) & f & f & f & f & f
\end{array}
\]
}
\end{problem}


\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}


\instatements{\newpage}
%cp2w F02
\begin{problem}
A media tycoon has an idea for an all-news television network called
LNN: The Logic News Network.  Each segment will begin with a
definition of the domain of discourse and a few predicates.  The day's
happenings can then be communicated concisely in logic notation.  For
example, a broadcast might begin as follows:

\begin{quotation}\noindent
``THIS IS LNN.  The domain of discourse is $\{
\mbox{Bill}, \mbox{Monica}, \mbox{Ken}, \mbox{Linda}, \mbox{Betty}
\}$.  Let $D(x)$ be a predicate that is true if $x$ is deceitful.  Let
$L(x, y)$ be a predicate that is true if $x$ likes $y$.  Let $G(x, y)$
be a predicate that is true if $x$ gave gifts to $y$.''
\end{quotation}

Complete the broadcast by translating the following statements into
logic notation.

\begin{problemparts}

\problempart If neither Monica nor Linda is deceitful, then Bill and
Monica like each other.

\solution{
\[
(\neg (D(\mbox{Monica}) \vee D(\mbox{Linda}))) \implies
(L(\mbox{Bill}, \mbox{Monica}) \wedge L(\mbox{Monica}, \mbox{Bill}))
\]
}

\problempart Everyone except for Ken likes Betty, and no one except Linda
likes Ken.

\solution{
\begin{eqnarray*}
\forall x\ (x  =   \mbox{Ken} \wedge \neg L(x, \mbox{Betty})) \vee
           (x \neq \mbox{Ken} \wedge      L(x, \mbox{Betty})) \wedge \\
\quad \quad
\forall x\ (x  =   \mbox{Linda} \wedge      L(x, \mbox{Ken})) \vee
           (x \neq \mbox{Linda} \wedge \neg L(x, \mbox{Ken}))
\end{eqnarray*}
}

\problempart If Ken is not deceitful, then Bill gave gifts to
Monica, and Monica gave gifts to someone.

\solution{
\[
\neg D(\mbox{Ken}) \implies
        (G(\mbox{Bill}, \mbox{Monica}) \wedge
        \exists\ x G(\mbox{Monica}, x))
\]
}

\problempart Everyone likes someone and dislikes someone else.

\solution{
\[
\forall x \exists y \exists z\ (y \neq z) \wedge L(x, y) \wedge \neg L(x, z)
\]
}

\problempart How could you express ``Everyone except for Ken likes
Betty'' using just propositional connectives \emph{without} using any
quantifiers ($\forall, \exists$)?  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{Bill},\mbox{Betty}) \land L(\mbox{Monica},\mbox{Betty}) \land
L(\mbox{Linda},\mbox{Betty}) \land L(\mbox{Betty},\mbox{Betty}) \land
\neg L(\mbox{Ken},\mbox{Betty})
\]

In general, quantifiers can be eliminated by treating $\forall x\ P(x)$ as an
abbreviation for
\[
P(\mbox{Bill}) \land P(\mbox{Monica}) \land P(\mbox{Ken}) \land P(\mbox{Linda}) \land
P(\mbox{Betty}),
\]
and $\exists x\ P(x)$ as an abbreviation for
\[
P(\mbox{Bill}) \lor P(\mbox{Monica}) \lor P(\mbox{Ken}) \lor
P(\mbox{Linda}) \lor P(\mbox{Betty}).
\]

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

\end{problemparts}

\end{problem}


\begin{problem}
\bparts

\ppart  Describe a counter-model demonstrating that
\[
(\forall x \exists y.\; P(x,y)) \implies \forall z.\; P(z,z)
\]
is not valid.

\solution{
Let $P(x,y)$ mean $x \neq y$.  Then the conclusion $\forall z.\; z \neq z$
is always false, but in any domain with two or more elements, the
hypothesis is true.
}


\ppart
Explain why
\begin{equation}\label{v}
(\forall z.\; P(z,z)) \implies \forall x \exists y.\; P(x,y)
\end{equation}
is valid.

\solution{
\begin{proof}
Assume
\begin{equation}\label{hyp}
\forall z.\; P(z,z)
\end{equation}
is true for some domain and interpretation of the predicate $P$.
We want to show that
\begin{equation}\label{csq}
\forall x \exists y.\; P(x,y)
\end{equation}
also holds.

So let $c$ be an element of the domain.  Then $P(c,c)$ holds by
assumption~\eqref{hyp}.  So there is a $y$, namely $y=c$ such that $P(c,y)$
holds.  That is, $\exists y.\; P(c,y)$ is true.  But $c$ could have been
any element in the domain, so (by \emph{Universal Generalization}), we
conclude that~\eqref{csq} holds.
\end{proof}}



\eparts

\end{problem}


\newpage
\section*{Proof of a Validity about Quantifiers}
\begin{lemma*}

The formula
\[
\forall x\; [P(x) \land Q(x)] \implies [(\forall y.\; P(y)) \land \forall z.\; Q(z)]
\]
is valid.

\end{lemma*}

\begin{proof}
Assume
\begin{equation}\label{QP}
\forall x\; [Q(x) \land P(x)]
\end{equation}
holds (for some domain and interpretation of $P$ and $Q$).  We want to prove
that
\begin{equation}\label{csqp}
(\forall y.\; Q(y)) \land \forall z.\; P(z)
\end{equation}
holds.

To do this, let $c$ be an element of the domain.  Then $Q(c) \land P(c)$
holds by hypothesis~\eqref{QP}.  In particular, $Q(c)$ holds.  But since,
$c$ could have been any element of the domain, we conclude (by Universal
Generalization) that
\begin{equation}\label{AQ}
\forall y.\; Q(y)
\end{equation}
holds.  We conclude similarly that
\begin{equation}\label{AP}
\forall z.\; P(z)
\end{equation}
holds.  Now~\eqref{AQ} and~\eqref{AP} immediately yield~\eqref{csqp}, as required.
\end{proof}


\iffalse

\begin{problem}
Prove that
\begin{equation}\label{v}
\forall x.\; [P(x) \lor A] \implies (\forall x,\; P(x)) \lor A
\end{equation}
is valid, providing $x$ does not appear in $A$.  \hint Consider two cases:
$A$ is true or $A$ is false.

\solution{
\begin{proof}
Assume
\begin{equation}\label{hyp}
\forall x.\; [P(x) \lor A],
\end{equation}
holds in some domain and interpretation of $P$ and $A$.  We want to prove
that
\begin{equation}{csq}
(\forall x,\; P(x)) \lor A
\end{equation}
holds under this interpreatation.

\textbf{Case 1:} $A$ is true.  Then $Q \lor A$ is true for any $Q$, so in
particular,~\eqref{csq} is true.

\textbf{Case 2:} $A$ is false.  So $Q \lor A$ is equivalent to $Q$ for any
$Q$.  In particular, (letting $Q$ be $P(x)$) we conclude that $[P(x) \lor
A]$ is equivalent to $P(x)$.  So replacing $[P(x) \lor A]$ by $P(x)$
in~\eqref{hyp}, we conclude that~\eqref{hyp} is equivalent to $\forall x.\;
P(x)$.  Now letting $Q$ be $\forall x.\; P(x)$, we conclude in turn that
$\forall x.\; P(x)$ is equivalent to~\eqref{csq}.  So assuming~\eqref{hyp}
is true, we conclude that~\eqref{csq} is true.

So from~\eqref{hyp} we can conclude~\eqref{csq} in any case, which
completes the proof.
\end{proof}}

\end{problem}
\fi



\end{document} 
