\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{listings}




\title{CSC165, Summer 2014\\
Assignment 3\\
Weight: 8\% \\
Due Jun 20th, 2:00 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

The goal of this assignment is for you to start writing proofs. Our goal this semester is for you to learn to write proofs by the end of the course, and the only way to learn to write proofs is through practice. \textbf{In your proofs, justify each step, and remember }. If you are asked to prove or disprove a claim, first determine whether the claim is true, and then prove that it is true or prove that it is false, depending on which is correct.

You may work in groups of no more than two students, and \textbf{you should submit a TEX file named \texttt{a3.tex} and a PDF file named \texttt{a3.pdf} that was produced by compiling your  \texttt{a3.tex}} and that contains the answers to the questions below. These files should be submitted using
\href{https://markus.cdf.toronto.edu/csc165-2014-05/main?locale=en}{MarkUs}. \textbf{Please make sure that your files are named \texttt{a3.tex} and \texttt{a3.pdf}. You will lose marks for not submitting correctly-named files.}

For this assignment, you will \textbf{not} receive 20\% of the marks for leaving questions blank or writing ``I cannot answer this.''


\begin{enumerate}

\item 
\begin{enumerate} 
\item (4 pts.) Prove or disprove that, for any universal set $U$ and predicates $P$ and $Q$,
$$	
	 [\exists x \in U, P(x) \land Q(x)] 	 \Rightarrow [\exists x \in U, P(x)) \land (\exists x \in U, Q(x))]
$$


\item (4 pts.) Prove or disprove that, for any universal set $U$ and predicates $P$ and $Q$,
$$	
	[\exists x \in U, P(x)) \land (\exists x \in U, Q(x))] \Rightarrow [\exists x \in U, P(x) \land Q(x)]
$$

\item (4 pts.) Prove or disprove that, for any universal set U and predicate $P$
$$
	[\exists x \in U, P(x)]  \Rightarrow [\forall x \in U, P(x)]
$$

\item (4 pts.) Prove or disprove that,  for any universal set U and predicate $P$
$$
	[\forall x \in U, P(x)]  \Rightarrow [\exists x \in U, P(x)]
$$



\end{enumerate}


\item For this question, you will prove that the roots of $x^2+6x+8.5$ are irrational. In other words, that 
$$
	\forall x \in \mathbb{R}, x^2+6x+8.5=0 \Rightarrow x \not \in \mathbb{Q}.
$$
You may use, without proof, the quadratic formula. In other words, you may use the fact that for all real $a$, $b$, and $c$, 
$$
	\forall x \in \mathbb{R},  (ax^2+bx+c = 0)\land(b^2-4ac \geq 0) \Rightarrow (x = \frac{-b-\sqrt{b^2-4ac}}{2a}) \lor (x = \frac{-b+\sqrt{b^2-4ac}}{2a})
$$
Please write complete proofs in each subquestion, without referring back to earlier subquestions.
\begin{enumerate}
	\item (4 pts.) Prove that $\forall x \in \mathbb{R}, x \in \mathbb{Q} \Rightarrow (x+1) \in \mathbb{Q}$. \textit{Hint: go back to the definition of $\mathbb{Q}$, and show that if $x$ satisfies that definition, then so does $(x+1)$.} \label{qq}
	\item (4 pts.) Prove that $\forall x \in \mathbb{R}, x \not \in \mathbb{Q} \Rightarrow (x+1) \not \in \mathbb{Q}$. \textit{Hint: can you prove the contrapositive of this statement?} \label{nqnq}
	\item (16 pts.) Prove that $\forall x \in \mathbb{R}, x^2+6x+8.5=0 \Rightarrow x \not \in \mathbb{Q}$. \textit{Hint: you may want to use results that are similar to \ref{qq} and \ref{nqnq}}.
\end{enumerate}

\item     An ``interpretation'' for a logical statement consists of   a domain $D$ (any non-empty set of elements)    and a meaning for each predicate symbol.    For example, $D = \{1,2\}$ and $P(x)$: ``$x > 0$''    is an interpretation for the statement $\forall x \in D, P(x)$    (in this case, one that happens to make the statement true).    For each statement below,    provide one interpretation under which the statement is true and    another interpretation under which the statement is false\,---\,    if either case is not possible, explain why clearly and concisely. You may reuse examples if you wish.
    \begin{enumerate}
	\item (4 pts.) $\exists x \in D, \forall y \in D, P(x, y) \implies P(y, x)$
	\item (4 pts.) $[\forall x \in D, \forall y \in D, P(x, y) \implies P(y, x)] \land [\forall x \in D, \forall y \in D, \lnot P(x, y)]$
	%\item $[\exists x \in D, \lnot P(x)] \land [\forall x \in D, Q(x)] \land [\forall x \in D, Q(x) \implies P(x)]$  %%NOTE: commented out -- not in the assignment
	%\item $[P \implies Q] \land [\lnot P \implies Q]$  %%NOTE: commented out -- not in the assignment
	\item (4 pts.) $[\exists x \in D, Q(x)] \implies [\forall x \in D, P(x)]$
    \end{enumerate}


\item     For each equivalence below,
    either provide a derivation
    from one side of the equivalence to the other
    (justify each step of your derivation with a brief explanation\,---\,
    for example, by naming one of the equivalences (See Tutorial 4),
    or show that the equivalence does not hold
    (warning: you cannot use a derivation to show non-equivalence\,---\,
    instead, think carefully about what an equivalence means,
    and how you can disprove it).
\begin{enumerate}
	\item (4 pts.) $\lnot Q \lor (P \land \lnot Q) \iff (\lnot P \lor Q) \land \lnot Q$
	\item (4 pts.) $((P \lor Q) \implies R) \iff (P \implies (Q \lor R))$
\end{enumerate}

\item (4 pts.) Use a truth table to prove that $(P \iff Q) \iff ((P \land Q) \lor (\lnot P \land \lnot Q))$.






\end{enumerate}





\end{document}


