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



\title{CSC165, Summer 2014\\
Assignment 2\\
Weight: 5\% \\
Solutions}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

The goal of this assignment is to make sure that you understand how to relate language and logic, and how to transform statements to get their negation, converse, and contrapositive.

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

You will receive 20\% of the marks for any question you either leave blank, or write ``I cannot answer this.''


\begin{enumerate}
\item For this question, consider Table~\ref{tab:gpa}. For the purposes of this question, assume that Table~\ref{tab:gpa} contains data on \textbf{all Waterloo students}. 
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|} 		
									\hline

	Student			& 	Major			&	GPA		\\		\hline
  	Al	 			& 	Math			&	2.3		\\ 		\hline
  	Betty		 		& 	Physics		&	2.7		\\ 		\hline
	Carlos				&	Math			&	3.0		\\		\hline
	Doug				&	Physics		&	2.0		\\		\hline
	Ellen				&	Math			&	4.0		\\		\hline
	Flo				&	Math			&	2.5		\\		\hline
	David				&	Art			&	4.0		\\		\hline
\end{tabular}
\caption{The complete list of students at Waterloo.\label{tab:gpa}}
\end{center}
\end{table}

\begin{enumerate}
\item (5 pts.) Define the sets and/or predicates to be used in answering questions \ref{item_second}-\ref{item_last}. For example, you might define $P$ to be the set of Physics majors; you can use any reasonable notation. \label{item_defns}
\end{enumerate}

\newpage 
\textbf{Solution:}
Set definitions:
\begin{itemize}
	\item W: the set of students at Waterloo
	\item P: the set of Physics majors at Waterloo
	\item M: the set of Math majors at Waterloo
	\item A: the set of art majors at Waterloo
\end{itemize}

Note: we defined the sets P, M, A to explicitly be Waterloo students. If we just defined M as, for example, ``Math majors," we'd have to use $M \cap W$ for ``Math majors at Waterloo."

Predicate definitions:
\begin{itemize}
	\item $S_3$: $S_3(x)$ is true iff the GPA of x is smaller than $3.0$.
	\item $G_1$: $G_1(x)$ is true iff the GPA of x is greater than $1.0$.
	\item $G_3$: $G_3(x)$ is true iff the GPA of x is greater than $3.0$.
\end{itemize}

\textit{Note: we can implicitly use the sets as predicates. For example, $P(x) \iff x \in P$.}

For questions \ref{item_second}-\ref{item_last}, express the given statement in symbolic form, using the definitions from your answer to~\ref{item_defns}. State whether the statement is true or false (assuming Table~\ref{tab:gpa} contains data on all Waterloo students) and briefly state why your conclusion is correct.   

\begin{enumerate}
\addtocounter{enumii}{1}

\item (5 pts.) All Physics majors at Waterloo have GPA that is smaller than $3.0$.   \label{item_second}

\textbf{Solution:} $\forall s \in P, S_3(s)$. This statement is \textbf{true} since Doug and Betty are the only Physics students, and both of them have GPA smaller than $3.0$.

\item (5 pts.) Some Math majors at Waterloo have GPA that is larger than $1.0$.

\textbf{Solution:} $\exists s \in M, G_1(s)$. This statement is \textbf{true} since Flo is a Math student with GPA that is larger than 1.0. (Note: one example is sufficient.)

\item (5 pts.) Not all Math majors at Waterloo have GPA that is larger than $1.0$.

\textbf{Solution:} $\lnot (\forall s \in M, G_1(s))$. This statement is \textbf{false} since all the Math majors at Waterloo (Al, Ellen, Flo) have GPA greater than $1.0$, so the negation of the statement that they all have GPA larger than $1.0$ is false. \label{mathnotall}

\item (5 pts.) Not all Forestry majors at Waterloo have GPA that is larger than $1.0$.

\textbf{Solution:} $\lnot (\forall s \in  F, G_1(s))$. This statement is \textbf{false} since all the Forestry majors at Waterloo (all zero of them!) have GPA greater than $1.0$, so the negation of the statement that they all have GPA larger than $1.0$ is false. (Compare to the answer to~\ref{mathnotall}!)

\item (5 pts.) All Forestry majors at Waterloo have GPA that is larger than $1.0$.

\textbf{Solution:} $\forall s \in  F, G_1(s)$. This statement is \textbf{true} since all the Forestry majors at Waterloo (all zero of them!) have GPA greater than $1.0$

\item (5 pts.) There is a Physics major at Waterloo whose GPA is between $1.0$ and $3.0$ and whose name is Al.

\textbf{Solution:} $\exists s \in  P, G_1(s) \land L_3(s)$. This statement is \textbf{false}, since there is no such student.

\item (5 pts.) If all Math majors at Waterloo have GPA larger than $1.0$, then there is a Physics major at Waterloo whose GPA is larger than $3.0$.

\textbf{Solution:} $[\forall s \in  M, G_1(s)] \implies [\exists s \in P, G_3(s)]$. This statement is \textbf{false}, since $[\forall s \in  M, G_1(s)]$ is true but $ [\exists s \in P, G_3(s)]$ is false, so the implication statement as a whole is false. \label{impl}

\item (5 pts.) It is not the case that if all Math majors at Waterloo have GPA larger than $1.0$, then there is a Physics major at Waterloo whose GPA larger than $3.0$.

\textbf{Solution:} $\lnot[[\forall s \in  M, G_1(s)] \implies [\exists s \in P, G_3(s)]]$. This statement is \textbf{true}, since its negation is false (see the answer to~\ref{impl}).


\item (5 pts.) David majors in Art.

\textbf{Solution:} $David \in A$. This statement is true, since David does in fact major in Art.

\item (5 pts.) David majors in Art if and only if Al's GPA is larger than $1.0$.  \label{item_last}.

\textbf{Solution:} $A(David) \iff G_1(Al)$. This statement is true, since both the left-hand side is true and the right-hand side is true, so the bi-implication is true as a whole.


\end{enumerate}



\item   Let $C$ be the set of cats. $G(c)$ means the cat $c$ is grinning, and $H(c)$ means the cat $c$ is happy. 
\begin{enumerate}
\item (5 pts.) Express the statement ``All happy cats are grinning" as an implication (i.e., as $A \implies B$, where $A$ and $B$ are logical expressions) using the predicates and sets defined above. \label{cats_grin}.

\textbf{Solution:} $\forall c \in C, H(c) \implies G(c)$.

	
\item (5 pts.) State  (as a symbolic expression) the contrapositive of the statement in your answer to question~\ref{cats_grin}.

\textbf{Solution:} $\forall c \in C, \lnot G(c) \implies \lnot H(c)$.
	
\item (5 pts.) Express the statement ``Some cats may be grinning, but only if they are not happy"  as an implication (i.e., as $A \implies B$, where $A$ and $B$ are logical expressions), using the predicates defined above. \label{cats_but}.
	
\textbf{Solution:} $\forall c \in C, G(c) \implies \lnot H(c)$. (Note: the only way for the statement to be false is for a happy to grin.)
	
\item (5 pts.) State  (as a symbolic expression) the contrapositive of the statement in your answer to question~\ref{cats_but}.

\textbf{Solution:} . $\forall c \in C, H(c) \implies \lnot G(c)$ (Note: the only way for the statement to be false is for a happy to grin.)

(Note: it would be fine to flip around the answers to the last two questions.)

\end{enumerate}


\item   Let $C$ be the set of cats. $G(c)$ means the cat $c$ is grinning, and $H(c)$ means the cat $c$ is happy. 
For questions \ref{item3_first}-\ref{item3_last}, give a \textbf{natural} English sentence that captures the meaning of the symbolic sentence.

\begin{enumerate}
\item (5 pts.) $\forall c \in C, H(c) \implies G(c)$ \label{item3_first}

\textbf{Solution:} All happy cats are grinning.

\item (5 pts.) $\forall c \in C, G(c) \implies H(c)$

\textbf{Solution:}  All the grinning cats are happy.

\item (5 pts.) $\forall c \in C, \lnot G(c) \implies H(c)$

\textbf{Solution:}  All the cats that aren't grinning are happy.

\item (5 pts.) $\forall c \in C, \lnot G(c) \implies \lnot H(c)$

\textbf{Solution:} All the cats that aren't grinning are unhappy.

\item (5 pts.) $\exists c \in C, H(c) \implies G(c)$

\textbf{Solution:} Either there is a cat that's unhappy, or there is a cat that is both happy and grinning, or both.

\item (5 pts.) $\not \exists c \in C, G(c) \lor  H(c)$ 

\textbf{Solution:} There are no cats that are grinning, there are no cats that are happy, and there are no cats that are both grinning and happy. (Alternatively: no cat is grinning and all the cats are unhappy.)

\label{item3_last}

\end{enumerate}









\end{enumerate}





\end{document}


