% Thedore Ian Martiny
% Summer 2017 Homework 1

\documentclass[addpoints]{exam}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\baselinestretch}{1.5}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{color}
\usepackage{colortbl}
\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage{multicol}
\usepackage{setspace}
\usepackage{xcolor}
 
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
\definecolor{Gray}{gray}{0.85}
 
\newcolumntype{a}{>{\columncolor{Gray}}c} 
\begin{document}
\singlespacing

\begin{center}
  {\large\textbf{CSCI 2824 - Discrete Structures}}

  {\large\textbf{Homework 1}}
\end{center}

You MUST show your work. If you only present answers you will receive minimal
credit. This homework is worth \numpoints pts with \numbonuspoints \,bonus
points.

\textbf{Due: Wednesday June 14}

%%%%Begin question

\begin{questions}
%% Question 1
  \question[4] Determine if the following are propositions or not:
  \begin{parts}
    \part $2 + 5 = 19$
    \begin{solution}
      Yes.
    \end{solution}

    \part $x+4 > 10$
    \begin{solution}
      No, this is a predicate. On its own this does not have a truth value, only
      when something is plugged in for $x$.
    \end{solution}

    \part Audrey Meadows was the original ``Alice'' in ``The Honey-Mooners''.
    \begin{solution}
      Yes.
    \end{solution}

    \part This statement is false.
    \begin{solution}
      No, this is a paradox.
    \end{solution}
  \end{parts}

  %% Question 2
  \question[9] Find the bitwise $OR$, $AND$, and $XOR$ of the following pairs
  of bit strings.
 \begin{parts}
  \part 0101 1110, 0010 0001
  \begin{solution}
    \begin{itemize}
      \item $OR$---$0111$ $1111$

      \item $AND$---$0000$ $0000$

      \item $XOR$---$0111$ $1111$
    \end{itemize}
  \end{solution}

  \part 1111 0000, 1010 1010
  \begin{solution}
    \begin{itemize}
      \item $OR$---$1111$ $1010$

      \item $AND$---$1010$ $0000$

      \item $XOR$---$0101$ $1010$
    \end{itemize}
  \end{solution}

  \part 0000 0111 0001, 10 0100 1000
  \begin{solution}
    \begin{itemize}
      \item $OR$---$0010$ $0111$ $1001$

      \item $AND$---$0000$ $0100$ $0000$

      \item $XOR$---$0010$ $0011$ $1001$
    \end{itemize}
  \end{solution}
 \end{parts} 

 %% Question 3
  \question[15] Write the truth table for each of the following propositions:
  \begin{parts}
    \part $\neg(p\wedge q) \vee (r\wedge \neg p)$
    \begin{solution}

      \begin{tabular}[h]{c|c|c|c|c|a}
        $p$ & $q$ & $r$ & $\neg(p\wedge q)$ & $r\wedge\neg p$ & $\neg(p\wedge q)
        \vee (r\wedge \neg p)$ \\
        \hline
        T & T & T & F & F & F\\
        T & T & F & F & F & F\\
        T & F & T & T & F & T\\
        T & F & F & T & F & T\\
        F & T & T & T & T & T\\
        F & T & F & T & F & T\\
        F & F & T & T & T & T\\
        F & F & F & T & F & T
      \end{tabular}
    \end{solution}
    \part $(p \vee q) \wedge \neg p$
    \begin{solution}

      \begin{tabular}[h]{c|c|c|c|a}
        $p$ & $q$ & $p\vee q$ & $\neg p$ & $(p\vee q) \wedge \neg p$ \\
        \hline
        T & T & T & F & F\\
        T & F & T & F & F\\
        F & T & T & T & T\\
        F & F & F & T & F
      \end{tabular}
    \end{solution}

    \part $\neg(p \wedge q) \vee (\neg q \vee r)$
    \begin{solution}

      \begin{tabular}[h]{c|c|c|c|c|a}
        $p$ & $q$ & $r$ & $\neg(p\wedge q)$ & $\neg q \vee r$ & $\neg(p\wedge q)
        \vee (\neg q\vee r)$ \\
        \hline
        T & T & T & F & T & T\\
        T & T & F & F & F & F\\
        T & F & T & T & T & T\\
        T & F & F & T & T & T\\
        F & T & T & T & T & T\\
        F & T & F & T & F & T\\
        F & F & T & T & T & T\\
        F & F & F & T & T & T
      \end{tabular}
    \end{solution}

  \end{parts}

  %% Question 4
  \question Given the following statements, and formulas de-construct the
  symbolic expressions into words.
  \begin{center}
    $p$: \emph{Today is Monday}

    $q$: \emph{It is raining}

    $r$: \emph{It is hot}
  \end{center}

  \begin{parts}
    \part[3] $\neg p \wedge (q \vee r)$
    \begin{solution}
      Today is not Monday and it is either raining or it is hot (or both).
    \end{solution}

    \part[7] $(p \wedge (q\vee r)) \wedge (r \vee (q \vee p))$
    \begin{solution}
      Today is Monday and it is raining or it is hot (or both) and it is also
      hot or it is raining or it is Monday.
    \end{solution}
  \end{parts}

  %% Question 5
  \question[12] There are 3 people, A, B, C. Each person either only tells the
  truth (is truthful) or only tells lies (is not truthful), independently (that
  is A being truthful does not imply B is or is not truthful, etc.). They then
  say the statements:

  \begin{center}
    A: ``Exactly one of us is telling the truth.''

    B: ``We are all lying.''

    C: ``The other two are lying.''
  \end{center}

  What can you conclude about the identities about A, B, C? Are they liars or
  truthful? You should do this problem similar to the one in class with a
  truth-table considering each possibility and determining if it is viable.
  \begin{solution}

  {\small
    \begin{tabular}[h]{c@{\,}|c@{\,}|c@{\,}|c@{\,}|c@{\,}|c@{\,}|c@{\,}}
      A truthful & B truthful & C truthful & A's statement & B's statement & C's
      statement & viable?\\
      \hline
      T & T & T & F & F & F & No\\
      T & T & F & F & F & F & No\\
      T & F & T & F & F & F & No\\
      T & F & F & T & F & F & Yes\\
      F & T & T & F & F & F & No\\
      F & T & F & T & F & F & No\\
      F & F & T & T & F & T & No\\
      F & F & F & F & T & T & No\\
    \end{tabular}
  }
  
  The first 3 are not viable since A lies, while he should be truthful. The
  fourth is viable, because everyone lives up to expectations. The 5th is not
  viable since B lies while he should be truthful. The 6th and 7th are not
  viable because A is truthful when he should lie. The 8th is not viable since B
  is truthful when he should lie.
  \end{solution}

  %% Question 6
  \bonusquestion[5] This question is trickier, and more of a riddle than a
  puzzle. Two people, A and B are on an island and they either both tell the
  truth or both lie. There are also two paths on this island, one leads to
  certain death, the other to paradise. You are allowed to ask one question to
  determine your path, which you must then stick with. What question do you ask,
  that guarantees you go to paradise? Explain why it works.
  \begin{solution}
    Logic is a peculiar case where two wrongs do make a right. The key point
    here is if A and B are truthful I can trust everything that is said, but if
    they are liars while I can't 
    trust what they say to a direct question, they will actually correct an
    indirect answer. For example: I ask the question ``If I were to ask your
    partner which path lead to paradise what would she say?''.

    For the sake of analysis suppose the \emph{left} path is the path to
    paradise. If both A and B are truthful, and supposing I asked this of A then
    he knows B would say the left path (because B is truthful) and so A would
    tell me the left path (because A is truthful). 

    If A and B are both liars then A knows that B would say the right path 
    (because B lies) and thus A would say the left path (because A lies).

    So in either case after asking my question, whether they are both liars or
    not they will always tell me the correct path.
  \end{solution}

  %% Question 7.
  \question[6] In class we talked about some of De Morgan's Laws, I proved some
  of them, you should prove the others:
  \begin{parts}
    \part Show that $\neg(p\vee q) \Leftrightarrow (\neg p) \wedge (\neg q)$,
    you should provide a truth table.
    \begin{solution}

      \begin{tabular}[h]{c | c | a | a}
        $p$ & $q$ & $\neg (p\vee q)$ & $\neg p \wedge \neg q$\\
        \hline
        T & T & F & F\\
        T & F & F & F\\
        F & T & F & F\\
        F & F & T & T
      \end{tabular}

      Thus since the two columns are the same $\neg (p\vee q)$ is logically
      equivalent to $\neg p \wedge \neg q$.
    \end{solution}

    \part Show that $\neg(\exists x \ P(x)) \Leftrightarrow \forall x \ \neg P
    (x)$, you should provide an argument for this.
    \begin{solution}
      We have four cases to show, in order to show logical equivalence. First:
      if $\neg(\exists x \ P(x))$ is true then that means that $\exists x \ P
      (x)$ is false, meaning that there is no value of $x$ which makes $P(x)$
      true. This gives that every value of $x$ makes $P(x)$ false, or every
      value of $x$ makes $\neg P(x)$ true. Thus $\forall x \ \neg P(x)$ is true.

      Conversely if $\forall x \ \neg P(x)$ is true then every value of $x$
      makes $\neg P(x)$ true, so every value of $x$ makes $P(x)$ false. This
      means that no value of $x$ makes $P(x)$ true. Which means that $\exists x
      \ P(x)$ is false, and that $\neg(\exists x \ P(x))$ is then true as well.

      By the above paragraphs the two statements are logically equivalent,
      they have the same truth values.
    \end{solution}

  \end{parts}

  %% Question 8
  \question[10] Determine whether the following propositions are logically
  equivalent or not:
  \begin{parts}
    \part $p\rightarrow q$ and $\neg q \rightarrow \neg p$
    \begin{solution}

      \begin{tabular}[h]{c | c | a | c | c | a}
        $p$ & $q$ & $p\rightarrow q$ & $\neg q$ & $\neg p$ & $\neg q \rightarrow
        \neg p$\\
        \hline
        T & T & T & F & F & T\\
        T & F & F & T & F & F\\
        F & T & T & F & T & T\\
        F & F & T & T & T & T
      \end{tabular}

      Thus since the two columns are the same $p\rightarrow q$ is logically
      equivalent to $\neg q \rightarrow \neg p$.
    \end{solution}

    \part $(p\rightarrow q) \wedge (q\rightarrow r)$ and $p\rightarrow r$
    \begin{solution}

      \begin{tabular}[h]{c | c | c | c | c | a | a}
        $p$ & $q$ & $r$ & $p\rightarrow q$ & $q\rightarrow r$ & $(p\rightarrow
        q) \wedge (q \rightarrow r)$ & $p\rightarrow r$\\
        \hline
        T & T & T & T & T & T & T\\
        T & T & F & T & F & F & F\\
        T & F & T & F & T & F & T\\
        T & F & F & F & T & F & F\\
        F & T & T & T & T & T & T\\
        F & T & F & T & f & F & T\\
        F & F & T & T & T & T & T\\
        F & F & F & T & T & T & T
      \end{tabular}

      Thus since the two columns are different, $(p\rightarrow q) \wedge 
      (q\rightarrow r)$ is not equivalent to $p\rightarrow r$. This may disagree
      with your intuition however recognize that as an argument it does work.
      That is whenever $p\rightarrow q$ and $q\rightarrow r$ are true, so is
      $p\rightarrow r$, it is just that there are some situations when the
      $\wedge$ is not true, but the implication $p\rightarrow r$ is true. 
    \end{solution}

  \end{parts}

  %% Question 9
  \question[6] Write the following propositions symbolically using quantifiers
  with the predicate $L(x,y)$ to mean $x$ loves $y$. Do you think either are
  true?
  \begin{parts}
    \part Somebody loves everybody.
    \begin{solution}
      $\exists x \ \forall y \ L(x,y)$. There are probably people who claim this
      is true for them, but they probably don't \emph{love} everybody.
    \end{solution}

    \part Somebody loves somebody.
    \begin{solution}
      $\exists x \ \exists y \ L(x,y)$. This is certainly true, someone
      somewhere loves someone else.
    \end{solution}

  \end{parts}
  
  %% Question 10 
  \question[6] Let $P(x)$ denote $x$ is a professional athlete and $Q(x)$ denote
  $x$ plays soccer. For each of the following propositions determine their truth
  values and write the proposition in words.
  \begin{parts}
    \part $\forall x \ (P(x) \rightarrow Q(x))$
    \begin{solution}
      This proposition says that for every person if they are a professional
      athlete they are a soccer player. This is false, Alexander Ovechkin is a
      professional hockey player, who does not play soccer.

      Though some arguments might be able to be made that its impossible to know
      if they have \emph{ever} played soccer, but that is not the intent of the
      question.
    \end{solution}

    \part $\exists x \ (P(x) \vee Q(x))$
    \begin{solution}
      This proposition says that there exists a person who is a professional
      athlete or a soccer player (or both). This is true, as mentioned above
      Alexander Ovechkin is a professional hockey player.
    \end{solution}
  \end{parts}

  %% Question 11
  \question[9] Determine the truth value of each statement, where $x,y$ are real
  numbers.
  \begin{parts}
    \part $\forall x \ \forall y \ (x^2 < y + 1)$
    \begin{solution}
      This is a false proposition. As a counterexample consider $x = 5$ and $y =
      0$ then we have that $25 < 1$ which is false.
    \end{solution}

    \part $\forall x \ \exists y \ (x^2 + y^2 = 9)$
    \begin{solution}
      Technically this is not true for real numbers. If $x$ is chosen to be
      greater than 3 then there is no real $y$ which will put it on the circle
      of radius 3. However this is true for complex numbers. Let $x$ be an
      arbitrary complex number. Now we can choose a $y$ (since it is the second
      quantifier) to be $\sqrt{9 - x^2}$, note that since $x$ was chosen first,
      $y$ can depend on $x$. In this case we have that:
      \begin{align*}
        x^2 + y^2 &= x^2 + \left(\sqrt{9 - x^2}\right)^2\\
        &= x^2 + 9 - x^2\\
        &= 9
      \end{align*}
    \end{solution}

    \part $\forall x \ \exists y \ ((x < y ) \rightarrow (x^2 < y^2))$
    \begin{solution}
      This is true, and probably has numerous proofs. The easiest is as follows:
      Let $x$ be an arbitrary real number, now we may choose $y$ second and have
      it depend on $x$. Let $y = x - 1$, in this case $x<y$ is false, meaning
      the proposition $(x<y) \to (x^2 < y^2)$ is vacuously true.

      Other arguments might include statements about choosing a big enough $y$
      for a given $x$, and this is valid, you need to be careful about negative
      $x$ though. 
    \end{solution}
  \end{parts}

  %% Question 12
  \question[4] Translate the following into symbolic logic using the given
  variables: ``To use the wireless network in the airport you must pay the
  daily fee unless you are a subscriber to the service.''
  \begin{itemize}
    \item $w$: ``You can use the wireless network in the airport''

    \item $d$: ``You pay the daily fee''

    \item $s$: ``You are a subscriber to the service''
  \end{itemize}

  \begin{solution}
    This can be written as:
    \[
      (d\vee s)\rightarrow w
    \]
  \end{solution}

  \question[9] In a particular isolated tribal village of 100 people, all
  of which have blond hair, everyone follows a particular set of rules. Any
  person that knows their own hair color must leave the village forever. Thus
  every morning there is a ceremony where the elder asks if anyone knows their
  hair color, and if they do they are kicked out (and everyone else in the
  village instantly knows as well). 

  Every person is completely truthful, and will follow this rule. But since no
  one wants to be kicked out of the village they go to great lengths to avoid
  seeing their reflection, and telling others what color their hair is.

  Eventually, an archaeologist stumbles upon this isolated village and walks
  among them for a time. The archaeologist mentions (when the whole village can
  hear her) ``someone village member has blond hair'' and then immediately
  leaves.

  What happens (assuming no more discussion on hair color occurs)?

  \begin{solution}
    The way to approach these problems is to simplify the question at first.

    Imagine there were only 1 person in the village. Then the villager
    immediately knows their hair color and will kick themselves out the
    following morning at the ceremony.

    If there are 2 people in the village, each villager knows that they other is
    blond. Person A expects Person B to leave the following morning and vice
    versa. When neither leave the following morning Person A immediately knows
    Person B didn't leave because Person B sees a blond person (Person A) and
    vice versa. Thus on the second morning both people will leave.

    One more simplification, if there are 3 people in our village, none will
    leave the next morning, since they all see other blond people (worth noting
    that they also expect no one to leave, since they see 2 blond people). On
    the second morning no one will leave since they all see 2 blond people 
    (however here they might each expect the other two to leave since they each
    see two blond people). After no one leaves on the second morning they all
    know they must all be blond, and on the third morning everyone will leave.

    Thus for our actual problem: it will take 100 mornings after the
    announcement for anyone to leave, and then everyone will leave all together.
  \end{solution}
\end{questions}
\end{document}
