\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}
\begin{document}
\psol{1}{February 12, 1999}

\begin{problems}

\problem (\S 1.1, Exercise 28) To make sense of this confusing
paragraph, let's introduce four boolean variables.

\begin{eqnarray*}
L	& = &	\text{file system locked} \\
N	& = &	\text{system operating normally} \\
Q	& = &	\text{messages are queued} \\
B	& = &	\text{messages are sent to the message buffer} \\
\end{eqnarray*}

Now we can translate the paragraph into logic notation as follows.

\begin{eqnarray*}
\neg L & \rightarrow & Q \\
\neg L & \leftrightarrow & N \\
\neg Q & \rightarrow & B \\
\neg L & \rightarrow & B \\
\neg B
\end{eqnarray*}

The specification is consistent if there is an assignment of truth
values to the variables that makes every expression true.

There are several ways to approach this problem.  One is to construct
a truth table with one line for each way of assigning truth values to
the variables that we defined, $L$, $N$, $Q$, and $B$.  For each
assignment, we could record the truth values of the five statements
above obtained from the system description.  If all five statements
are true for some assignment of truth values to the variables, then
the system is consistent; otherwise, the system is inconsistent.

We will use a more ad hoc approach here.  The final statement is true
only if $B$ is false.  This fact, together with the third and fourth
statements, imply that $Q$ is true and $L$ is true.  Since $L$ is
true, the second statement implies that $N$ is false.  Thus, we have
deduced the following:

\begin{eqnarray*}
L	& = &	\text{true} \\
N	& = &	\text{false} \\
Q	& = &	\text{true} \\
B	& = &	\text{false}
\end{eqnarray*}

With this assignment of truth values to variables, all of the five
statements are true, and so the system is consistent.

\problem (\S 1.2, Exercise 36) We give two proofs.  The first is from
first principles, but is rather intricate.  The second is simpler, but
assumes the result of problem 28 on page 20 of Rosen.

FIRST PROOF: We must show that for every compound proposition there is
an equivalent compound proposition containing only the NAND operator.

We can construct such a proposition as follows.  The new proposition
is the NAND of a set of subexpressions.  There is one such
subexpression for each assignment to the variables in the original
proposition that makes that proposition true.

A subexpression is formed from an assignment to the variables as
follows.  The subexpression is the NAND of many tiny expressions.  If
a variable $x$ is assigned the value TRUE, then the subexpression
contains the tiny expression $x$.  If variable $x$ is assigned the
value FALSE, then the subexpression contains the tiny expression $x
\text{ NAND } x$, which is logically equivalent to $\neg x$.

All that remains is to check that this new proposition is logically
equivalent to the original.  By the definition of NAND, the new
proposition is true if and only if one of the subexpressions is false.
Again by the definition of NAND, a subexpression is false if and only
if the variables are assigned a specific set of values that make the
original proposition true.  Since there is one such subexpression for
each assignment that makes the original expression true, the new
proposition is logically equivalent to the original.

\bigskip

SECOND PROOF: We must show that for every compound proposition there
is an equivalent compound proposition containing only the NAND
operator.  The result of problem 28 on page 20 of Rosen is that every
compound proposition is logically equivalent to a proposition
involving only $\neg$ and $\wedge$.  Consequently, it suffices to show
that every compound proposition involving only these two operators is
in turn logically equivalent to a proposition involving only the NAND
operator.

Given a compound proposition involving $\neg$ and $\wedge$, we
construct an equivalent proposition involving NAND by substitution as
follows.

\bigskip
\centerline{
\begin{tabular}{ccc}
replace this	& \hspace{1cm} & by this \\ \hline
$\neg p$	& & $p \text{ NAND } p$ \\
$p \wedge q$	& & $(p \text{ NAND } q) \text{ NAND } (p \text{ NAND } q)$
\end{tabular}
}
\bigskip

Truth tables establish that logical equivalence is preserved by these
substitutions.

\problem (\S 1.3, Exercise 10)

\begin{problemparts}
\problempart $\forall x \ F(x, \text{Fred})$
\problempart $\forall x \ F(\text{Evelyn}, x)$
\problempart $\forall x \ \exists y \ F(x, y)$
\problempart $\neg \exists x \ \forall y \ F(x, y)$
\problempart $\forall x \ \exists y \ F(y, x)$
\problempart $\neg \exists x \ (F(x, \text{Fred}) \wedge F(x, \text{Jerry}))$
\problempart $(\exists x \ \exists y \ (F(\text{Nancy}, x) \wedge F(\text{Nancy}, y) \wedge x \neq y)) \wedge \neg (\exists x \ \exists y \ \exists z \ (F(\text{Nancy}, x) \wedge F(\text{Nancy}, y) \wedge F(\text{Nancy}, z) \wedge x \neq y \wedge y \neq z \wedge x \neq z))$
\problempart $(\exists x \ \forall y \ F(y, x)) \wedge \neg (\exists x \ \exists y \ \forall z \ (F(z, x) \wedge F(z, y) \wedge x \neq y))$
\problempart $\neg \exists x \ F(x, x)$
\problempart $\exists x \ ((\exists y \ (F(x, y) \wedge x \neq y)) \wedge \neg (\exists y \ \exists z \ (F(x, y) \wedge F(x, z) \wedge y \neq z \wedge y \neq x \wedge z \neq x)))$
\end{problemparts}

\problem (\S 1.3, Exercise 26) Let the universe be the set of natural
numbers, $0, 1, 2, \ldots$.  Let $P(x)$ be the proposition that $x$ is
even, and let $Q(x)$ be the proposition that $x$ is odd.

In this case, the proposition $(\forall x \ P(x)) \vee (\forall x \
Q(x))$ is false; it is neither the case that every number is even nor
that every number is odd.  On the other hand, the proposition $\forall
x \ (P(x) \vee Q(x))$ is true; that is, every number is either even or
odd.

Since the first proposition can be false while the second proposition
is true, the two propositions are not equivalent.

\problem (\S 1.4, Exercise 12) We will prove that if the power sets of
$A$ and $B$ are equal, then sets $A$ and $B$ are equal.  In
particular, we will prove $A = B$ by showing that each set is
contained in the other.

First, we show that $A \subseteq B$.  Let $x$ be an element of $A$.
Then $\{ x \}$ is an element of $P(A)$, the power set of $A$.  By the
assumption that $P(A)= P(B)$, we know that $\{ x \}$ is an element of
$P(B)$.  This implies that $x \in B$.  Therefore $A \subseteq B$.  The
argument that $B \subseteq A$ is symmetric.  Therefore, $A = B$ as
claimed.

\problem Note that $|A| + |B|$ counts each element that is in $A$ but
not in $B$ or in $B$ but not in $A$ exactly once, and each element
that is in both $A$ and $B$ exactly twice.  Thus, $|A| + |B| - 2 |A
\cap B|$ counts only elements that are in $A$ but not in $B$ or in $B$
but not in $A$.  This is precisely the set $A \oplus B$, so we have

\begin{eqnarray*}
|A \oplus B| & = & |A| + |B| - 2 |A \cap B|.
\end{eqnarray*}

\problem (\S 1.5, Exercise 26)  We prove that

\begin{eqnarray*}
A \oplus B & = & (A - B) \cup (B - A)
\end{eqnarray*}

by showing that each set contains the other.  Let $S$ be the set on
the left side of the equation, and let $T$ be the set on the right
side.  Our goal is then to prove that $S = T$.

First, we prove that $S \subseteq T$.  If $x \in S$, then either $x
\in A$ and $x \not\in B$ or else $x \not\in A$ and $x \in B$.  In the
former case, $x \in A - B$, and so $x \in T$.  In the latter case, $x
\in B - A$, and so $x \in T$ again.  Thus, $S \subseteq T$.

Now, we prove that $T \subseteq S$.  If $x \in T$, then there are two
cases: either $x$ is only an element of $A - B$ or only an element of
$B - A$.  (Note that $x$ can not be an element of both sets; they are
disjoint.)  In the first case, $x$ is an element of $A$, but not $B$,
so $x \in S$.  In the second case, $x$ is an element of $B$, but not
$A$, so $x \in S$ again.  Thus, $T \subseteq S$.

Since each set contains the other, $S = T$ as claimed.

\problem (\S 2.3, Exercise 34) We are given that $a \equiv b
\pmod{m}$.  This is equivalent to the assertion that $m \mid (a - b)$.
Consequently, $mc \mid (a-b)c$.  By the distributive law, $mc \mid (ac
- bc)$, which is equivalent to $ac \equiv bc \pmod{mc}$.

\problem (\S 3.1, Exercise 18) As a preliminary, note that a natural
number $n$ is a perfect square if an only if every prime appears an
even number of times in the prime factorization of $n$.  To prove one
direction, note that if $n$ is a perfect square, then there exists an
$m$ such that $n = m^2$.  Each prime appears twice in the prime
factorization of $n$ for each appearance of the prime in the
factorization $m$; thus, each prime appears an even number of times in
the factorization of $m$.  To prove the other direction, suppose that
every prime appears an even number of times in the factorization of
$n$.  Then let $m$ be the product of primes in which each prime
appears half as many times as in the factorization of $n$.  Then $m^2
= n$, and so $n$ is a perfect square.

Now we prove the main claim.  Let $n$ be a natural number that is not
a perfect square.  Assume for the purpose of contradiction that
$\sqrt{n}$ is rational.  Then we can write $\sqrt{n} = a / b$, where
$a$ and $b$ are integers and $b$ is positive.  Squaring and
multiplying both sizes of this equation by $b^2$ gives $nb^2 = a^2$.
Since $n$ is not a perfect square, there is a prime $p$ such that the
highest power of $p$ dividing $n$ is odd.  Since $b^2$ is a perfect
square, the highest power of $p$ dividing $b^2$ is even.  Thus, the
highest power of $p$ dividing $n b^2$ is odd.  On the other hand, the
highest power of $p$ dividing $a^2$ is even, since $a^2$ is a perfect
square.  These conclusions contradict the fact that $n b^2 = a^2$.
Thus, the assumption that $\sqrt{n}$ is rational must be false.
\end{problems}

\end{document}





