\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,amsmath}
\usepackage{hyperref}
\title{CSC165 Fall 2014, Assignment \#1\\
{\large Due October 3rd, 10:00 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.  You may work in
groups of no more than three 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-2014-09}{MarkUs}.

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

\begin{enumerate}
\item Suppose $A$ is the set of acronyms, $B(a)$ means $a$ is
  bifurcated, $C(a)$ means $a$ is catherized, and $D(a)$ means $a$ is
  diagonal (you do not need to worry about the meaning of acronym,
  bifurcated, catheterized, or diagonal for the rest of this question).
  Write the negation of each of the following statements in English, and
  then in symbolic form.
  \begin{enumerate}
  \item All acronyms are catheterized unless they are bifurcated.
  \item There are no acronyms that are both bifurcated and diagonal.
  \item All non-diagonal acronyms are catheterized.
  \item There are diagonal acronyms that are bifurcated.
  \item For an acronym to be catherized, it is necessary and
    sufficient that it be diagonal.
  \end{enumerate}
\item Consider the sentence:
  \begin{quotation}
    \noindent
    $S$: Every employee who is honest and persistent is successful or bored.
  \end{quotation}
  Each of the statements below is equivalent to either the converse,
  the contrapositive, or the negation of $S$.  You must decide which label
  fits each statement, and explain your thinking.
  \begin{enumerate}
  \item All employees who are successful or bored must be honest and
    persistent.
  \item Every employee who is neither successful nor bored is
    either dishonest or not persistent.
  \item Some honest and persistent employee is neither successful nor bored.
  \item All employees who are dishonest or not persistent must be
    unsuccessful and not bored.
  \end{enumerate}
\item $X$ is a set that contains both students and
  courses. \textbf{Zorn} is a student, and \textbf{Zukes} is a course.
  Predicate $S(x)$ means $x$ is a student, and $C(x)$ means $x$ is a course,
  $E(x,y)$ means $x$ is enrolled in $y$, $EQ(x,y)$ means $x$ equals
  $y$, and $P(x,y)$ means $x$ is more popular than $y$.  Use set $X$,
  \textbf{Zorn}, \textbf{Zukes}, the predicates above, and the logical
  connectives you have learned in our course to translate each
  sentence below, either from symbolic form to English, or from
  English to symbolic.  In English, try to avoid symbols (e.g. $x$)
  and predicates (e.g. $C(x)$).
  \begin{enumerate}
  \item One, and only one, student in $X$ is more popular than
    \textbf{Zorn}.
  \item $\forall x \in X, \left(S(x) \wedge E(x,
      \text{\textbf{Zukes}})\right)
    \Rightarrow \neg P(x, \text{\textbf{Zorn}})$
  \item $\exists x \in X, C(x) \wedge E(\text{\text{Zorn}}, x),
    \forall y \in X, \left(C(y) \wedge \neg EQ(y,x)\right) 
     \Rightarrow P(y, x)$
  \item The only course in $X$ that \textbf{Zorn} is not enrolled in
    is \textbf{Zukes}
  \end{enumerate}
\item For each pair of statements below, given an example of sets $D,
  P$, and $Q$ that make one statement true and the other false.
  Explain the difference in words, and show it with a Venn diagram.
  \begin{enumerate}
  \item The pair $\forall d \in D, P(d) \Rightarrow Q(d)$ and $\forall
    d\in D, P(d) \wedge Q(d)$.
  \item The pair $\exists d\in D, P(d) \wedge Q(d)$ and $\exists d
    \in D, P(d) \Rightarrow Q(d)$.
  \end{enumerate}
\item Suppose $T$ is a set of natural numbers, and we have the
  following statement about $T$:
  \begin{quote}\noindent
    S2: Every element of $T$ is 2 raised to some natural number power.
  \end{quote}
  Which of the following statements imply $S2$?  Which of the
  following statements are implied by $S2$?  Explain.
  \begin{enumerate}
  \item $T=\{64, 32, 128\}$.
  \item If $i, j \in T$, and $i < j$, then $i$ divides $j$.
  \item $T$ has no more than 1 odd member.
  \item No odd prime number divides any element of $T$.
  \item $T$ is the empty set.
  \end{enumerate}
\end{enumerate}

\end{document}

% LocalWords:  brachial
