\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{fancyhdr}
\usepackage{lastpage}
\newcommand{\studentname}{}
\pagestyle{fancy}
\lhead{MATH 311-02}
\chead{Problem Set \#2}
\rhead{\studentname}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
%\cfoot{Page \thepage}
\rfoot{\bf due February 4}
\begin{document}
\begin{enumerate}
\item \textbf{(10 points)} \emph{Consider the statements $P:
x^2-3x+2=0$ and $Q: x\geq 0$.}
\begin{enumerate}
\item \textbf{(6 points)} \emph{Explain in words why $P\Rightarrow
Q$ is true.}
If we were to presume that $x$ satisfies the equation
$x^2-3x+2=0$, then it follows from basic algebraic methods (the
quadratic formula, factorization, or any other quadratic-solution
method) that $x$ is equal to either $1$ or $2$. In both of these
cases, $x\geq 0$, so we have verified that whenever $P$ is true,
$Q$ is true---which is exactly equivalent to asserting that
$P\Rightarrow Q$ is true.
\item \textbf{(4 points)} {\em There are four pairs of truth values for
$P$ and $Q$. For each of the four pairs, either find a value of
$x$ corresponding to those truth values, or explain why such an
$x$ cannot exist.}
A simple example where $P$ is true and $Q$ is true, as explored in
the previous part of this problem, is $x=1$ ($x=2$ would also
work). When $x=1$, both $x^2-3x+2=0$ and $x\geq 0$ are true
statements.
We can likewise find a simple example where $P$ is false and $Q$
is true by choosing any non-negative number other than 1 or 2. For
instance, if we select $x=3$, we can verify that $x^2-3x+2\neq 0$
(specifically, $x^2-3x+2=2$), so $P$ is false, but $x\geq 0$, so
$Q$ is true.
Letting $x$ be any negative number will result in false $P$ and
false $Q$. For instance, when $x=-1$, we see that $x^2-3x+2\neq 0$
(specifically, $x^2-3x+2=6$), so $P$ is false, and in addition,
$x\ngeq 0$, so $Q$ is also false.
The one remaining case, where $P$ is true and $Q$ is false, is the
truly interesting one. We \emph{can't} find an example of a value
of $x$ such that $x^2-3x+2=0$ but $x\ngeq 0$, and this could be
explained either algebraically, or, more relevantly, in terms of
the assertion of the previous section. We saw that $P\Rightarrow
Q$ was true, or in other words, whenever $P$ is true, $Q$ must be
true. Thus, the pair of a true $P$ and a false $Q$ is not actually
an achievable combination.
\end{enumerate}
\item \textbf{(9 points)} \emph{The statements $(\neg P)\vee(\neg Q)$
and $\neg(P\wedge Q)$ are equivalent. You will demonstrate this
two ways.}
\begin{enumerate}
\item \textbf{(4 points)} \emph{Fill in the following truth table,
and note that the two columns corresponding to $(\neg
P)\vee(\neg Q)$ and $\neg(P\wedge Q)$ have identical entries.}
\begin{center}
\begin{tabular}{|c|c||c|c|c||c|c|}
\hline
$P$&$Q$&$\neg P$&$\neg Q$&$(\neg P)\vee(\neg Q)$&$P\wedge Q$&$\neg(P\wedge Q)$\\
\hline\hline
T&T&F&F&F&T&F\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
T&F&F&T&T&F&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
F&T&T&F&T&F&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
F&F&T&T&T&F&T\\
\hline % This is the bottom edge of the table, so you should
% probably leave this \hline in.
\end{tabular}
\end{center}
We can observe visually that the fifth and seventh columns have
identical truth values for all combinations of $P$ and $Q$; thus,
the expressions they describe are identical.
\item \textbf{(5 points)} \emph{Write out the statements $(\neg
P)\vee(\neg Q)$ and $\neg(P\wedge Q)$ in words instead of
symbols, and explain why these two different statements describe
the same situation.}
$(\neg P)\vee(\neg Q)$ could be unrolled into ``at least one of
``not $P$'' or ``not $Q$'' is true''. Since ``not $P$'' is true
only when $P$ is false, and likewise for $Q$, we could rephrase
this as ``at least one of $P$ or $Q$ is false''.
Similarly, we can unroll $\neg(P\wedge Q)$ into ``it is not the
case that $P$ and $Q$ are both true''. Showing these two
expressions are equivalent is, after a fashion, common sense: $P$
and $Q$ will not both be true exactly when at least one of them is
not true.
\end{enumerate}
\item \textbf{(6 points)} \emph{Letting $P$ and $Q$ be statements,
identify each of the following statements as either tautological,
contradictory, or neither. Justify your results, either with
explanation or exhaustive computation.}
\begin{itemize}
\item \emph{$(P\wedge(P\Rightarrow Q))\Rightarrow Q$.}
This statement could be read as ``if both $P$ and $P\Rightarrow Q$
are true, then $Q$ is true''. This will actually be a tautology,
because $P\Rightarrow Q$ expands to mean ``when $P$ is true, $Q$
is also true'', so the full statement is ``if $P$ is true and in
addition, when $P$ is true, $Q$ is true, it follows that $Q$ is
true'', something which is self-evident.
Alternatively, one could compute the truth table for this
statement and note that it is true regardless of $P$ and $Q$.
\begin{center}
\begin{tabular}{|c|c||c|c|c|}
\hline
$P$&$Q$&$P\rightarrow Q$&$P\wedge(P\Rightarrow Q)$&$(P\wedge(P\Rightarrow Q))\Rightarrow Q$\\
\hline\hline
T&T&T&T&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
T&F&F&F&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
F&T&T&F&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
F&F&T&F&T\\
\hline % This is the bottom edge of the table, so you should
% probably leave this \hline in.
\end{tabular}
\end{center}
As a point of useful information, this statement, which is called
\emph {modus ponens} (Latin: the method of affirmation), is one of
the building blocks of proof methodology. Most important results
are presented in the form ``if $P$ than $Q$''. Often, we want to
use such a theorem, together with the knowledge that $P$ is true,
to assert $Q$. We shall see the use of this method later in the
course.
\item \emph{$(P\vee Q)\Leftrightarrow(P\wedge Q)$.}
This is neither a tautology nor a contradiction. It claims that
``$P$ or $Q$'' has the same truth value as ``$P$ and $Q$'', which
is sometimes true (for instance, when $P$ and $Q$ are both true),
and sometimes false (for instance, when $P$ is true and $Q$ is
false).
\item \emph{$(P\wedge Q)\Rightarrow\neg Q$.}
This is neither a tautology nor a contradiction. It seems
moderately contradictory when written out, as it claims that if
both $P$ and $Q$ are true, then $Q$ is false, which seems like a
statement that would always be false, but in fact, it is only
given the lie when $P$ and $Q$ are both true, in which case the
implication's premise is met and its consequence fails, so the
implication is false. For \emph{all} other values of $P$ and $Q$,
no contradiction arises since the premise isn't even true, so the
implication is true regardless of the truth value of the
consequence.
\begin{center}
\begin{tabular}{|c|c||c|c|c|c|}
\hline
$P$&$Q$&$P\rightarrow Q$&$P\wedge(P\Rightarrow Q)$&$\neg Q$&$(P\wedge(P\Rightarrow Q))\Rightarrow Q$\\
\hline\hline
T&T&T&T&F&F\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
T&F&F&F&T&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
F&T&T&F&F&T\\
\hline % You may not like having a horizontal line here. Try
% commenting it out.
F&F&T&F&T&T\\
\hline % This is the bottom edge of the table, so you should
% probably leave this \hline in.
\end{tabular}
\end{center}
\end{itemize}
\item \textbf{(5 points)} \emph{Let $P$ be the proposition ``$n$ is a
prime number between 4 and 10''. For each of the propositions
given below, indicate whether that proposition is a necessary
condition for $P$, a sufficient condition for $P$, both, or
neither; briefly justify your claim.}
% We use `` and '' as smartquotes.
\begin{itemize}
\item \emph{$Q_1$: $n$ is equal to 5.}
If $Q_1$ is satisfied, then $n=5$, and thus $P$ is satisfied,
since 5 is indeed a prime number between 4 and 10. Thus
$Q_1\Rightarrow P$, so $Q_1$ is a sufficient condition for $P$.
However, it is not the case that if $P$ is satisfied, then $Q_1$
must be satisfied: for instance, $n=7$ satisfies $Q_1$ but not
$P$. Thus it is not true that $P\Rightarrow Q_1$, so $Q_1$ is not
a necessary condition for $P$.
\item \emph{$Q_2$: $n$ is a positive, odd integer.}
Even if $Q_2$ is satisfied, $P$ might not be satisfied; for
instance, $n=9$ satisfies $Q_2$ but not $P$. Thus it is not the
case that $Q_2\Rightarrow P$, so $Q_2$ is not a sufficient condition
for $P$.
However, if $P$ is satisfied, then $Q_2$ must be: we know every
prime number is positive, and every prime number except 2 is odd,
so any number satisfying the conditions of $P$ will be a positive
odd integer, satisfying $Q_2$. Thus $P\Rightarrow Q_2$, so $Q_2$
is a necessary condition for $P$.
\item \emph{$Q_3$: $n$ is a prime number less than 6.}
Even if $Q_3$ is satisfied, $P$ might not be satisfied; for
instance, $n=2$ satisfies $Q_3$ but not $P$. Thus it is not the
case that $Q_3\Rightarrow P$, so $Q_3$ is not a sufficient condition
for $P$.
Likewise, even if $P$ is satisfied, $Q_3$ might be unsatisfied, as by
for instance $n=7$, which makes $P$ true but not $Q_3$. Thus it is
not the case that $P\Rightarrow Q_3$, so $Q_3$ is not a necessary
condition for $P$ either.
\end{itemize}
\item \textbf{(5 points)} \emph{Below, we shall discuss the true
statement ``For every rational number $r$, $\frac{1}{r}$ is
rational.''}
\begin{enumerate}
\item \textbf{(2 points)} \emph{Write this statement entirely in
symbols. Note that we can assert that some $x$ is rational with the
statement $x\in\mathbb Q$.}
``For every rational number $r$'' is a universal quantification,
so it would be written as $\forall r\in\mathbb Q$. The
statement ``$\frac1r$ is rational'' can be written symbolically as
$\frac1r\in\mathbb Q$, so putting these two parts together, the
above statement is:
$$\forall r\in\mathbb Q, \frac1r\in\mathbb Q$$
\item \textbf{(3 points)} \emph{Write the negation of this statement
in words, in as easy-to-comprehend a way as possible. Do not
simply wrap the entire expression in the phrase ``it is not the
case that...''. Note that the statement you produce will in fact
be false.}
The negation of a universally quantified statement is an
existentially quantified statement: that is, ``for all $x$, $P$ is
true'' has negation ``for some $x$, $P$ is false''. In this
particular case, the negation of the statement given is ``For some
rational number $r$, $\frac1r$ is not rational''. Note that this
statement is false: there in fact is no rational number whose
reciprocal is not rational.
\end{enumerate}
\item \textbf{(5 points)} \emph{Below, we shall discuss the false
statement ``There is a rational number $r$ such that $r^2=2$.''}
\begin{enumerate}
\item \textbf{(2 points)} \emph{Write this statement entirely in
symbols.}
``There is a rational number $r$'' is an existential
quantification, so it would be written as $\exists r\in\mathbb
Q$. The statement ``$r^2=2$'' is already symbolic, so putting these two
parts together, the above statement is:
$$\exists r\in\mathbb Q: r^2=2$$
\item \textbf{(3 points)} \emph{Write the negation of this statement
in words, in as easy-to-comprehend a way as possible. Do not
simply wrap the entire expression in the phrase ``it is not the
case that...''. Note that the statement you produce should be
true.}
The negation of an existentially quantified statement is a
universally quantified statement: that is, ``for some $x$, $P$ is
true'' has negation ``for all $x$, $P$ is false''. In this
particular case, the negation of the statement given is ``For all
rational numbers $r$, $r^2\neq 2$''. This is a true statement,
which you probably already know because $\pm \sqrt 2$ are
well-known to be irrational; however, we will actually prove it
later in the course.
\end{enumerate}
% You only need to do the following if you want to -- which is why
% it's commented out in the basic template, so that it doesn't show
% up unless you uncomment it and work on it.
\item \textbf{(4 point bonus)} \emph{Logic is important in designing
computers, since the ``true'' and ``false'' properties of a
statement correspond to the circuit states of having a high signal
(usually 5 volts) and a low signal (0 volts). Due to technical
restrictions, early computers had only one basic operation,
generally called NAND (standing for ``not-and'') and written with
the symbol $\uparrow$. $P\uparrow Q$ was logically equivalent to
$\neg(P\wedge Q)$, as shown in the following truth table.}
\begin{center}
\begin{tabular}{|c|c||c|}
\hline
$P$&$Q$&$P\uparrow Q$\\\hline\hline
T&T&F\\\hline
T&F&T\\\hline
F&T&T\\\hline
F&F&T\\\hline
\end{tabular}
\end{center}
\emph{While this was the only primitive operation which was
feasible, early computer scientists of course wanted to use the
more familiar and useful operations. Show that one can express the
statements $\neg P$, $P\wedge Q$, and $P\vee Q$ entirely in terms
of repeated application of the ``nand'' operation to $P$ and $Q$
in various combinations.}
It's actually fairly easy to construct $\neg P$: since $P\wedge
P=P$, we know that
$$\neg P=\neg(P\wedge P)=P\uparrow P$$
And now that we have negation, it's not too hard to bootstrap
$P\wedge Q$ by expanding it into a collection of nands and
negations:
$$P\wedge Q=\neg\neg(P\wedge Q)=\neg(P\uparrow Q)=(P\uparrow Q)\uparrow(P\uparrow Q)$$
The trickiest statement to construct is $P\vee Q$. We can appeal to
DeMorgan's Law: $P\vee Q=\neg[(\neg P)\wedge(\neg Q)]$, and since
we already have both the negation and conjunction operations
expressable in terms of the nand operation, we can simply unroll
this piece by piece:
$$P\vee Q=\neg[(\neg P)\wedge(\neg Q)]=(\neg P)\uparrow(\neg Q)=(P\uparrow P)\uparrow(Q\uparrow Q)$$
\end{enumerate}
% This is a cute bit of code to fill down to the bottom of the page
% with whitespace (so the box appears at the very end of the last
% page), and then put in a boxed quotation.
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
``I know what you're thinking about,'' said Tweedledum: ``but it
isn't so, nohow.''
``Contrariwise,'' continued Tweedledee, ``if it was so, it might
be; and if it were so, it would be; but as it isn't, it
ain't. That's logic.''
\hfill ---Lewis~Carroll, \emph{Through~the~Looking-Glass}
\end{minipage}
}
\end{center}
\end{document}