\documentclass{article}

\usepackage{fullpage}
\usepackage{textcomp}
\usepackage{amsmath}
\usepackage{wasysym}

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\cfoot{\sc Page \thepage\ of \pageref{end}}

\begin{document}

{\large \noindent{}University of Toronto at Scarborough\\
\textbf{CSC A67/MAT A67 - Discrete Mathematics, Fall 2016}}

\section*{\huge Exercise \#3: Logic and Proofs}

{\large Due: September 28, 2016 at 11:59 p.m.\\
This exercise is worth 3\% of your final grade.}\\[1em]
\textbf{Warning:} Your electronic submission on MarkUs affirms that this exercise is your own work and no
one else's, and is in accordance with the University of Toronto Code of Behaviour on Academic Matters,
the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSC A67/MAT A67.\\[1ex]
This exercise is due by 11:59 p.m. September 28. Late exercises will not be accepted.\\[1ex]
\renewcommand{\labelenumi}{\arabic{enumi}.}
\renewcommand{\labelenumii}{(\alph{enumii})}
\begin{enumerate}
\item Si\marginpar{[5]}mplify the following expression:
\[\neg \forall x \in D, \forall y \in D, \exists z \in D, p(x, y, z) \rightarrow q(x) \lor r(y, z)\]
Distribute negative
\[\exists x \in D, \exists y \in D, \forall z \in D, \neg ( p(x, y, z) \rightarrow q(x) \lor r(y, z) )\]
Apply Conditional Law
\[\forall z \in D, \exists x \in D, \exists y \in D, \neg ( \neg p(x, y, z) \lor (q(x) \lor r(y, z) ))\]
Apply DeMorgan's Law
\[\forall z \in D, \exists x \in D, \exists y \in D, p(x, y, z) \land \neg ( (q(x) \lor r(y, z) )\]
Apply DeMorgan's Law
\[\forall z \in D, \exists x \in D, \exists y \in D, p(x, y, z) \land \neg q(x) \land \neg r(y, z)\]

\item\begin{enumerate}\marginpar{[5]}
\item  Give an example of a pair of predicates $P(x)$ and $Q(x)$ in some domain to show that the $\exists$ quantifier \textbf{does not} distribute over the $\land$ connective.  In other words, your example should show that
\[\exists x\in D, (P(x) \land Q(x)) \;\;\;\textrm{ and } \;\;\;(\exists x \in D, P(x)) \land ( \exists x \in D, Q(x))\]

are not logically equivalent.
\item Does $\exists$ distribute over $\lor$? In other words, is

\[\exists x\in D, (P(x) \lor Q(x)) \iff (\exists  x\in D, P(x)) \lor (\exists x\in D, Q(x))\]

true? If $\exists$ distributes over $\lor$, verify that your example from (a) satisfies this equivalence.  If it does not, give an example of a pair of predicates $P(x)$ and $Q(x)$ and domain $D$ that do not satisfy this equivalence. \\

Note: What does \emph{satisfy} mean? \emph{Satisfy} or \emph{satisfies} means the example makes the statement true.
\end{enumerate}
 \item  Determine \marginpar{[5]} whether $\exists$ can be factored from an implication.  In other words, is

\[ \exists x \in X, (p(x)\rightarrow q(x))\;\; \iff \;\; (\exists x \in X, p(x)) \rightarrow (\exists x \in X, q(x))\]

true? Explain your reasoning. Marks will only be given for your \emph{explanation}. Hint: Think about giving meaning to each of $X, p(x)$ and $q(x)$.

\item Give\marginpar{[5]}  a direct proof of the claim:

\begin{quote} Let $a, b$ and $c$ be integers. If $a | b$ and $b | c$, then $a | c$.\end{quote}

\begin{quote}Let a, b, and c \in \mathbb{Z}.\end{quote}
\begin{quote}Let p, q, and r \in \mathbb{Z}.\end{quote}
\begin{quote}Suppose $a|b$ and $b|c$.\end{quote}
\[a(p) = b\]
\[a = b/p\]
\[b(q) = c\]
\[b = c/q\]

\[a = (c/q) / p\]
\[a = c/(qp)\]
\[(a)(qp) = c\]
\begin{quote} Since q and p are both integers, and the set of integers is closed under  multiplication, the number qp is also an integer. \end{quote}
\[qp = r\]
\[(a)(r) = c\]
\[a|c\]
\begin{quote} Therefore, the following statement is true: when a, b, and c are integers, if $a|b$ and $b|c$, then $a|c$. \end{quote}




\item We define \marginpar{[5]} the symbol $\smiley$ as follows.  Let $x$ and $y$ be integers.  We write $(x\; \smiley\; y)$ if $3x + 5y = 7k$ for some integer $k$.  \\

\noindent Prove for integers $a, b, c, d$ that:

\begin{quote} $(a\; \smiley\; b)$ and $(c\; \smiley\; d)$ is sufficient for $(a + c)\; \smiley\; (b + d)$.\end{quote}

\begin{quote} Let a, b, c, d, $k_1$, $k_2$, $k_3$ \in \mathbb{Z}.
\begin{quote} Suppose $a \smiley b = 3a + 5b = 7k_1$ and $c \smiley d = 3c + 5d = 7k_2$.
\begin{quote} Let $3a + 5b = 7k_1$ be equation 1 and $3c + 5d = 7k_2$ be equation 2.
\begin{quote} Add equations 1 and 2.
(3a + 5b) + (3c + 5d) = (7k_1)(7k_2)
3a + 5b + 3c + 5d = 7(k_1 + k_2)
3(a+c) + 5(b+d) = 7(k_1 + k_2)
\begin{quote}Since $k_1$ and $k_2$ are both integers, and the set of integers is closed under addition, $k_1 + k_2$ can be represented by some other integer $k_3$.
3(a+c) + 5(b+d) = 7k_3
(a + c) \smiley (b + d)

Conclusion: $a \smiley b$ and $c \smiley d$ is sufficient for $(a + c) \smiley (b + d)$.


\item Prove\marginpar{[5]}  that:
\begin{quote} For all integers $n$, if $n^2$ is odd, then $n$ is odd. \end{quote}
Hint: You may find it easier to rephrase the claim in another way.  Recall that $A \rightarrow B$ can be rewritten in different ways.
\end{enumerate}

\hrulefill\\

\noindent[Total: 30 marks]\label{end}
\end{document}