\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\title{CSC165, Winter 2015\\
Assignment 1\\
Due January 30th, 11:59 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

\noindent The aim of this assignment is for you to practice using quantifiers,
implications, logical connectives and expressions.  

\begin{itemize}
	\item You may work in groups of no more than \textbf{two} students, and you should 
	produce a single solution in a PDF file named \texttt{a1.pdf}, submitted to
	\href{https://markus.cdf.toronto.edu/csc165-2015-01}{MarkUs}. Submissions must be \textbf{typed}. 
	\item Note that you \textbf{won't} be able to login to MarkUs and submit 
	the assignment \textbf{before Jan 24}.
	\item \textbf{Late submission policy}: Each \textbf{group} can benefit from 
	\textbf{one} time 24-hour	grace period with no penalty.
	
	If you use your grace period for one assignment, then change your group for the 
	next one, and your new group-mate has not use his/her grace period, the new 
	group \textbf{can} submit late by 24 hours. 
	However, if both students in the group have used their grace period, the new group 
	\textbf{cannot} submit late. 
\end{itemize}
\vspace{2\baselineskip}

\begin{enumerate}

\item Let $B(x)$ denotes ``$x$ plays this 2-person board game" and $P(x,y)$ denotes 
``$x$ has played this 2-person board game with $y$", 
where the domain for variables $x$ and $y$ consists of all students in your class. 

\textbf{Questions}:
\begin{itemize}
	\item Express each of the following sentences in logical notation.  
	
	Define all set and predicate symbols that you use in the logical expressions.
	\item Write the negation of each of the sentences in English and in logical form.
	
	Simplifying the logical sentences so that only predicates are negated. 
\end{itemize}
  \begin{enumerate}
  \item If Carol and Dan play this 2-person board game, then they have played it with each other.
  
  (\textbf{Hint}: note that $P(x,y)$ only expresses that $x$ has played with $y$; 
  this does \textbf{not} necessarily mean that  $y$ has played with $x$).
  \item No one in the class has played this 2-person board game with Bob.
  \item Someone in your class does not play this 2-person board game.
  \item Everyone in your class who plays this 2-person board game has 
  played the game with at least one other student in your class.
  \item A student in your class has played this 2-person board game with everyone in your class.
  \end{enumerate}  
 

  

  \item Let $S$ denotes the set of all students in your class, $C$ denotes the set of all countries, and 
  $T(x,y)$ denotes that $x$ travels to country $y$. 
  
  Express each of the following statements by a simple English sentence. 
  
  Avoid symbols (e.g. $x$) and predicates (e.g. T(x,y)) in English sentences.
    
  \begin{enumerate}
  \item $\neg T(Bob, y)$. 
  \item ($\exists x\in S, T(x, Denmark)) \wedge (\forall x\in S, T(x, France)$).
  \item $\exists y\in C,T(Mona, y)\lor T(Pete, y)$.
  \item $\forall x\in S, \forall z\in S,\exists y\in C, (x\neq z) \Rightarrow \neg(T(x,y) \wedge T(z,y))$.
  \item $\exists x\in S, \exists z\in S, \forall y\in C, (x\neq z)\wedge (T(x,y) \Leftrightarrow T(z,y))$.
  \item $\forall x\in S, \forall z\in S, \exists y\in C,(T(x,y) \Leftrightarrow T(z,y))$.
  \end{enumerate}
    
 
  \item Give the contrapositive and converse of the following statements in English.  

  (Hint: it might be helpful if you first write these sentences in logical form)
  	\begin{enumerate}
 			\item If Socrates is a man and all men are mortal, then Socrates is mortal.
 			
 			\item If it does not rain or it is not foggy, then the sailing race will 
 			be held and the lifesaving demonstration will go on.
 		 			
  		\item For me, playing hockey is sufficient for being sore the next day.
  		
  	
  	\end{enumerate}
  
  
  \item Suppose $T$ is a set of natural numbers, and we have the following statement about $T$.
  
  \begin{description}
		\item{${\bf S_1}$:} 2 is the only prime number that divides elements of $T$. 
	\end{description}
	Which of the following statements imply ${\bf S_1}$? Which are implied by ${\bf S_1}$? 
  For each case, give a brief justification.
  	\begin{enumerate}
			\item ${\bf S_2}$: $T$ is the set of all natural numbers that satisfy the quadratic equation $x^2+x+1=0$.
								
			\item ${\bf S_3}$: $T=\{16,8,528\}$.
			
			\item ${\bf S_4}$: All elements of $T$ are equal to $2^n$, where $n$ is a natural number. 
			\item ${\bf S_5}$: If $i, j \in T$, and $i < j$, then $i$ divides $j$.
        
     \end{enumerate}
  
  
  
  \item Prove that the following equivalences are tautology. Show your work in detail. 
  
  You \textbf{may not} use truth tables or Venn diagrams in your proof, but you are allowed 
  to use manipulation rules (presented in Section 2.17 of the course notes). 
  
  For each step, you \textbf{must} clearly state which rule you apply.
  
 
\begin{enumerate}
	\item $((P\Rightarrow Q_1) \wedge (P\Rightarrow Q_2)) \Leftrightarrow (P \Rightarrow (Q_1 \wedge Q_2))$
  \item $(( \exists x\in D, P(x) \vee Q(x)) \Rightarrow R(y) ) \Leftrightarrow 
	       ((( \exists x\in D, P(x)) \Rightarrow R(y)) \wedge (( \exists x\in D, Q(x)) \Rightarrow R(y)))$
\end{enumerate}

\end{enumerate}

\end{document}
