\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\title{Assignment 2}
\date{Tuesday May 29, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
This is Assignment 2. The problems are arranged in the natural order which we learn the material. You should do as much as you can everyday, but if you don't recognize something that means we probably have learned that material yet.
{\bf Remember to show all work, and argue any claim, unless otherwise stated. Getting a correct answer does not suffice}
This assignment is due Tuesday May 29.
\section{Non-Constructive Proofs}
It is intended for you to complete this section on Thursday May 24.
In class, we talked about the {\bf law of the excluded middle}. To remind you, this law says, any statement is either true or false. It amounts to being able to add any statement of the form $\phi \oor \neg \phi$ to your present context, which you can use any way you wish (usually to do cases).
In everyday math one rarely explicitly mentions this law. Instead, we implicitly use it frequently; for instance, we make use of it when we do cases on whether some statement is true or false. It's natural to use this law as we used it during lecture.
\begin{prob}
In class when talking about the algebra of statements we made some observations which we gave intuitive reasons for. We were not able to prove these statements with the constructive proof methods we had. Now, we can prove them!
\begin{enumerate}
\item Prove a statement is logically equivalent to its double negation. That is: \[ P \bimp (\neg\neg P) \]
\item Prove an implication is logically equivalent to its contrapositive. That is: \[(P\to Q) \bimp (\neg Q \to \neg P)\]
\item Prove the following instance of DeMorgan's Law \[ (P\oand Q) \bimp \neg ( \neg P \oor \neg Q )\]
\end{enumerate}
{\bf Bonus:} In each of the above, it is possible to prove exactly one direction of the bi-implication with just our constructive methods (ie. not using the law of the excluded middle). Do this for an extra point! If you do the bonus, make a note of it so we know to look for it while grading.
\end{prob}
\section{Final Project for Propositional Logic}
You will have the material to complete this section on Thursday May 24th. It is a comprehensive part of the homework that will truly test your understanding of logical connectives.
Recall we have defined the following connectives:
\[
\top, \bot, A\oand B, A\oor B, \neg A, A\to B, A\bimp B
\]
We wish to make a few new connectives using these.
\begin{prob}
By the ``above connectives'' we mean $\top$, $\bot$, $\oand$, $\oor$, $\neg$, $\to$, and $\bimp$
\begin{enumerate}
\item Make a connective using the above which we will call xor and denote $\oplus$ where $A\oplus B$ is true whenever $A$ is true or whenever $B$ is true, but not both.
\item Make a connective using the above which we will call nand and denote $\uparrow$ where $A\nand B$ is true whenever both $A$ and $B$ are not true.
\end{enumerate}
Verify these are correct with a truth table. No other work is necessary but the definition of the connectives and the truth tables.
\end{prob}
\begin{prob}
Suppose that we have defined the $\nand$ operator above.
\begin{enumerate}
\item Write a definition for $\neg$ using only the $\nand$ operator. That is, write a function $P(A)$ using just the symbol $\nand$ and $A$ such that $P(A)$ is true exactly whenever $\neg A$ is true. Verify your definition with a truth table.
\item Write a definition for $\to$ using only the $\nand$ operator. That is, write a function $P(A,B)$ using just the symbol $\nand$, $A$, and $B$ such that $P(A,B)$ is truth exactly whenever $A\to B$ is true. Verify your definition with a truth table.
\item Note that DeMorgan's laws, Double Negation elimination, and Implication Rephrasing allow us to write any statement in terms of $\neg$ and $\to$. In light of this, what is a consequence of the previous two results?
\end{enumerate}
\end{prob}
\section{Quantifiers}
It is intended for you to complete this section on Friday May 25.
\begin{prob}
Identify which variables are free and which are bound in the following formulas:
\begin{enumerate}
\item $\A x \st x^2 > 4 \to y \cdot x > 2$
\item $\A z\st ( \A x \st T(x') \oand T(x) ) \to \E x \st G(x,z)$
\item $( \A x_1 \st R(x_1,x_2) ) \to R(x_1,x_2)$
\end{enumerate}
\end{prob}
\begin{prob}
Negate the following. When something is given in words, your answer should be words. When something is given in symbols, your answer should be in symbols.
\begin{enumerate}
\item For every boy, there is a dog that he loves.
\item $\A x \st P(x) \to ( \E y\st Q(x,y) \oand R(x,y) )$
\item In every shop, if there is a camera then it is hard to steal.
\item $\A x \st \A \epsilon > 0 \st \E \delta > 0 \st \A y \stt |x - y| < \delta \to |f(x) - f(y)| < \epsilon $
\end{enumerate}
\end{prob}
\begin{prob}
Rewrite the following English statement in terms of logical symbols.
\begin{enumerate}
\item For every real number $x$, if there is a natural number such that $n^2=x$ then $x$ is a natural number.
\item For every real number $x$, if for every integer $z$ where $z\neq 0$ we have $z\cdot x$ is not a natural number then $x$ is not a rational.
\item Every even natural number larger than 6 can be written as the sum of two primes.
\end{enumerate}
\end{prob}
\begin{prob}
Let $f$ be a function on the real numbers. Consider the statement:
\[
A = \A x \st \A \epsilon > 0 \st \E \delta > 0 \st \A y \stt |x - y| < \delta \to |f(x) - f(y)| < \epsilon
\]
and
\[
B = \A \epsilon > 0 \st \E \delta > 0 \st \A x \st \A y \stt |x - y| < \delta \to |f(x) - f(y) < \epsilon
\]
Prove $B\to A$.
\textit{Note: You do not need to use any properties of real numbers in this problem. It is purely logical}
\end{prob}
\begin{prob}
Let the domain of discourse be the natural numbers, and let $P(x)$ be a property depending on $x$, and $Q(x,y,z)$ be a property depending on both $x$ and $y$. Prove
\[
(\E x \st P(x) \to \A y \st \E z \stt Q(x,y,z)) \bimp (\E x \st \A y \st \E z \stt P(x) \to Q(x,y,z))
\]
\end{prob}
\section{Let's Do Some Proof}
This section is intended to be completed over the weekend of May 26th-May 28th.
\begin{prob}
Prove or disprove the following statements:
\begin{enumerate}
\item $\A x \in \R \st x^4 \geq x^3$
\item $\A x \in \N \st \E y \in \R \stt y^2 - 1 = 6x$
\item $\A n\in \N \st n^2 \mbox{ even } \bimp n \mbox{ even }$
\textit{Hint: for the $\to$ direction of the implication, consider the contrapositive}
\end{enumerate}
\end{prob}
\begin{prob}
Consider the following statements. Describe what the statements say in everyday language. Then state whether they are true or false and give an informal explanation why.
\begin{enumerate}
\item $\A p\in \N \st \E q\in \N \st \E n\in \N \stt (q\neq 1) \oand (n \neq 1) \oand (n\cdot q = p)$
\item $\A x \in \R \st \E y \in \R \stt y^2 = x$
\item $\A q\in \Q \st \E m \in \Z \stt (m\neq 0) \oand (m\cdot q \mbox{ is a natural number})$
\end{enumerate}
\end{prob}
\end{document}