\documentclass{article}
\usepackage{ccfonts}
\usepackage{amsmath,amsfonts,graphics}
\renewcommand{\bfseries}{\scshape}
\usepackage{fullpage}
\title{CSC165, Summer 2005,
  Assignment 2\\
  {\large Due: Thursday June 23rd, 10 am}}
\author{Danny Heap}
\renewcommand{\today}{~}

\begin{document}
\maketitle

\section*{Instructions}
\label{instructions}

Please work on all questions.  Turn in the outline and structure of a
solution, even if you cannot provide every step, and we will
try to assign some part marks.  However, if there is any question you
cannot see how to even begin, leave it blank you will receive 20\%
of the marks for that question.

Be sure to give full credit to any sources you consult (other than
course notes, TAs, and the instructor) in preparing this problem set.
If you try to pass off somebody else's work as your own for credit,
you are committing an academic offense, and that can entail serious
consequences.  Any ideas that you do not attribute to someone else are
assumed to be the ideas of the author(s) listed below, and will be
evaluated for grading.

Write your name(s) and student number(s) (maximum of two names and two
student numbers) in the space below.\vspace{2\baselineskip}

\noindent Name\hfill
\rule{0.8\textwidth}{1pt}\\[2\baselineskip]
\noindent Student \#\hfill
\rule{0.8\textwidth}{1pt}\\[2\baselineskip]
\noindent Name\hfill
\rule{0.8\textwidth}{1pt}\\[2\baselineskip]
\noindent Student \#\hfill
\rule{0.8\textwidth}{1pt}
\newpage

\begin{enumerate}
\item For $x,y,z$ $\in$ $\mathbb{R}$ define:
  \begin{itemize}
  \item $d(x,y,z)$ means $x/y=z$.
  \item $s(x,y,z)$ means $x+y=z$.
  \item $eq(x,y)$ means $x=y$.
  \item $g(x,y)$ means $x>y$.
  \item $\mathbb{N}(x)$ means $x\in\mathbb{N}$, where $\mathbb{N}$ $=$
    $\{0,1, 2, \ldots\}$ (the natural numbers).
  \end{itemize}
  Express each of the following symbolic sentences in English.  If the
  sentence is false, provide a counterexample.  If it's true, explain
  why.
  \begin{enumerate}
  \item $\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, \exists
    z\in\mathbb{R}, s(x,y,z)$.
  \item $\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, \forall
    z\in\mathbb{R}, \mathbb{N}(x) \wedge \mathbb{N}(y) \wedge s(x,y,z)
    \Rightarrow \mathbb{N}(z)$.
  \item $\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, \exists
    z\in\mathbb{R}, d(x,y,z)$.
  \item $\exists y\in\mathbb{R}, \forall x\in\mathbb{R}, s(x,y,x)$.
  \item $\forall y\in\mathbb{R}, \forall x\in\mathbb{R},
    s(x,y,x)\Rightarrow eq(y,0)$.
  \item $\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, d(x,y,x)
    \Rightarrow eq(y,1)$.
  \item $\forall x\in\mathbb{R}, \exists y\in\mathbb{R}, s(x,y,0)$. 
  \item $\exists y\in\mathbb{R}, \forall x\in\mathbb{R}, s(x,y,0)$. 
  \item $\forall x\in\mathbb{R},\forall y\in\mathbb{R}, \forall
    z\in\mathbb{R}, g(x,y)\wedge d(z,x,y)\Rightarrow g(z,y)$.
  \end{enumerate}

\item Using the predicates defined in the previous question, and
  $\mathbb{N}$ $=$ $\{0,1,2,\ldots,\}$:
  \begin{enumerate}
  \item Translate the following into English:
    \begin{displaymath}
      \forall x\in\mathbb{N}, \forall y\in\mathbb{N}, \forall z
      \in\mathbb{N}, d(x,3,y) \wedge
      d(z,x,x) \Rightarrow \exists w\in\mathbb{N}, d(z,3,w) 
    \end{displaymath}
  \item If the sentence you translated above is false, provide a
  counterexample.  Otherwise, write a direct proof of the
  implication.
  \end{enumerate}
\item Consider the following java method (if you have \textbf{any}
  questions about java, please feel free to ask your TA or
  instructor):
  {\footnotesize
\begin{verbatim}
  public static boolean longPredicate(boolean p, boolean q) {
   return ( 
           ((!p || q) && (p || !q) && !q) ||
           (!(p && !q) && !(!p && q) && p)
             );
  }
\end{verbatim}
  }
  \begin{enumerate}
  \item Make a literal translation of the conditional expression being
    returned into precise symbolic notation, using $p$, $q$, $\wedge$,
    $\vee$, and $\neg$, but without using $\Rightarrow$ or
    $\Leftrightarrow$. $p$ and $q$ should occur as many times in your
    expression as they do in the java conditional expression.
  \item Simplify your expression from the previous part, allowing
    yourself to use $\Rightarrow$ or $\Leftrightarrow$
    where appropriate.  Use $p$ and $q$ no more than twice each.
    Explain the steps you took in simplifying the expression.
  \item Write the negation of the previous part in precise symbolic
    notation, and explain its meaning in English.
  \end{enumerate}
\pagebreak
\item Define $P(x)$ as ``$x$ is pedantic,'' $Q(x)$ as ``$x$ is a
  quibbler,'' $R(x)$ as ``$x$ is redundant,'' and $S$ is the
  domain of scholars. For each sentence below:
  \begin{itemize}
  \item Write the negation of the sentence in precise symbolic
    notation, moving the negation symbol $\neg$ as close as possible to
    the predicates $P$, $Q$ or $R$ as possible.
  \item Draw a Venn diagram showing $P$, $Q$, $R$ and $S$ for which the
    original sentence is false.
  \end{itemize}
  Here are the sentences:
  \begin{enumerate}
  \item Any redundant scholar is a quibbler only if he/she is
  pedantic.
  \item Some scholar is not redundant if he/she is neither a quibbler
    nor non-pedantic.
  \item All redundant and pedantic scholars must be quibblers.
  \item Some scholar is either not both pedantic and a quibbler, or
    is redundant.
  \item Whenever any scholar is a quibbler, there is a scholar who
    is redundant and pedantic.
  \end{enumerate}

\item In the previous question, is (a) equivalent to the negation of
  (b)?  Either provide a counter-example or show they are equivalent.
\end{enumerate}
\end{document}