%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%
% Updated for Fall 2019 by Joshua Spayd
% Updated for Win 2020 by Cynthia Lee
%

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{minted}
\usepackage{wrapfig}
\usepackage{hyperref}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#2}
\author{Your Name(s) Here}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set \#2}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2020}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}
\RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}

\hypersetup{urlcolor=blue}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
% end MZ

\begin{document}

\maketitle

\section*{Checkpoint Problem One: Interpersonal Dynamics}

\begin{wrapfigure}{r}{3.75cm}
  \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on
      grid,auto,baseline={(current bounding box.north)}]
    \node[state] (A)   {$A$};
    \node[state] (C) [below=of A] {$C$};
    \node[state] (B) [left=of C] {$B$};
    \node[state] (D) [right=of C] {$D$};
    \node[state] (E) [below=of C] {$E$};
    \node[state] (F) [right=of E] {$F$};
    \path[->]
    (A) edge [bend left=30] node {} (C)
        edge [loop right] node {} ()
    (B) edge [loop above] node {} ()
    (C) edge [bend left=30] node {} (A)
        edge node {} (B)
        edge node {} (D)
        edge [bend left = 30] node {} (E)
    (D) edge [loop above] node {} ()
    (E) edge [bend left=30] node {} (C)
        edge [loop right] node {} ()
    (F) edge [loop above] node {} ();
  \end{tikzpicture}
\end{wrapfigure}

The diagram to the right represents a set of people named $A, B, C, D, E,$ and
$F$. If there's an arrow from a person $x$ to a person $y$, then person $x$
loves person $y$. We'll denote this by writing $\textit{Loves}(x, y)$. For
example, in this picture, we have $\textit{Loves}(C, D)$ and $\textit{Loves}(E,
E)$, but not $\textit{Loves}(D, A)$. \\

There are no ``implied'' arrows anywhere in this diagram. For example, even
though $A$ loves $C$ and $C$ loves $E$, the statement $\textit{Loves}(A, E)$ is
false because there's no direct arrow from $A$ to $E$. Similarly, even though
$C$ loves $D$, the statement $\textit{Loves}(D, C)$ is false because there's no
arrow from $D$ to $C$. \\

Below is a series of ten first-order logic statements. For each of those
statements, tell us the minimum number of additional arrows that must be added
to the diagram to the right to make that formula true. You’re only allowed to
add arrows; you can’t remove existing ones. If a formula is already true, the
answer will be ``zero'' because no edges need to be added. Then, tell us what
those arrows are, and briefly explain why that’s the smallest number of arrows
that need to be added.

\begin{enumerate}[label=\roman*.,ref=\roman*]
  \item $Loves(A, A) \rightarrow Loves(E, E)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, B) \rightarrow Loves(C, D)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, C) \rightarrow Loves(C, F)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, D) \rightarrow Loves(D, E)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, D) \leftrightarrow Loves(B, C)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, C) \leftrightarrow Loves(E, C)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\forall x.~\exists y.\ Loves(x, y)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\forall x.~\exists y.\ (x \ne y \land Loves(x, y))$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\exists x.~\forall y.\ Loves(x, y)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\exists x.~\forall y.\ (x \ne y \rightarrow Loves(x, y))$
    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak

\section*{Checkpoint Problem Two: First-Order Fundamentals}

Consider the following first-order logic statement:
\begin{flalign*}
  &\exists p.\ (Problem(p) \land \\
  &\qquad \forall g.~(Program(g) \rightarrow \lnot Solves(g, p)) \\
  &)
\end{flalign*}
Here, the predicate $Problem(x)$ states that $x$ is a problem, the predicate
$Program(y)$ states that $y$ is a program, and the predicate $Solves(a, b)$
states that $a$ solves $b$.

\begin{enumerate}[label=\roman*.,ref=\roman*]

  \item Translate this formula into plain English. No justification is required.
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item Write a first-order logic formula that is the negation of the above
    formula. Your formula should not include any negations, except possibly
    for direct negations of predicates.

    \begin{shaded}
      Write your answer here.
    \end{shaded}

\end{enumerate}

\annotate{We \emph{strongly} recommend reading over the Guide to Negations
  before attempting the above problem.}

\begin{enumerate}[resume*]

  \item Using only the predicates given above, write a statement in first-order
    logic that says ``there is a program that solves every problem.'' (Alas,
    this isn’t true, but wouldn’t it be nice?)

    \begin{shaded}
      Write your answer here.
    \end{shaded}

\end{enumerate}

\annotate{We \emph{strongly} recommend reading over the Guide to Logic
  Translations before attempting the above problem.}

\pagebreak

\section{Propositional Completeness}
\begin{shaded}
  Submit your edited $\mathsf{PropositionalCompleteness.proplogic}$ file through
  Gradescope under ``Programming Assignment 2''.
\end{shaded}

\section{Set Theory and Propositional Logic}

(Parts (i) -- (v) of this question are autograded; please edit the file
$\mathsf{SetTheory.proplogic}$ in the Problem Set Two starter files with your
answers. Part (vi) should be submitted as part of your written answers.)

Imagine we have two sets $A$ and $B$ and some object x. Let’s introduce two
propositional variables:
\begin{itemize}
  \item $a$, which states that $x \in A$, and
  \item $b$, which states that $x \in B$.
\end{itemize}

By combining $a$ and $b$ together in different ways using propositional logic,
we can express different claims about how $x$ relates to $A$ and $B$.
\begin{shaded}
  For parts (i) -- (v), submit your edited $\mathsf{SetTheory.proplogic}$ file
  through Gradescope under ``Programming Assignment 2''.
\end{shaded}

Now, suppose we have some third set $C$. Let’s introduce a third propositional
variable $c$ that means $x \in C$.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \setcounter{enumi}{5}
  \item Using your answer to part (v) as a starting point, simplify the
    expression $(A \Delta B) \Delta B$ as much as possible. Briefly justify your
    answer. No formal proof is necessary. \textit{(Please write up your solution
    to this problem in your written assignment submission, since we want to see
    your justification in ad- dition to your answer.)}
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

Generally speaking, if you ever find yourself in possession of a strange
set-theoretic expression involving the set combination operations $\cap$,
$\cup$, $-$, or $\Delta$, you can use the above technique to get a slightly
better handle at what you're looking in fact. In fact, many rules about how
these set-theoretic operators work follow directly from propositional logic! \\

That result in part (vi) is an interesting one. You may want to keep it in mind
for later in the quarter. \smiley{}

\pagebreak

\section{Executable Logic}
\begin{shaded}
  Submit your edited $\mathsf{ExecutableLogic.cpp}$ file through Gradescope.
\end{shaded}

\section{First-Order Negations}
\begin{shaded}
  Submit your edited $\mathsf{FirstOrderNegations.fol}$ file through Gradescope.
\end{shaded}

\section{This, But Not That}
\begin{shaded}
  Submit your five edited $\mathsf{.people}$ files through Gradescope.
\end{shaded}

\section{Translating into Logic}
\begin{shaded}
  Submit your edited $\mathsf{TranslatingIntoLogic.fol}$ file through
  Gradescope.
\end{shaded}

\pagebreak

\section{Hereditary Sets}

Let's begin with a fun little definition:

\begin{center}
  A set $S$ is called a \emph{hereditary set} if every $x \in S$ is also a
  hereditary set.
\end{center}

This definition might seem strange because it's self-referential -- it defines
the hereditary sets in terms of other hereditary sets!  However, it turns out
that this is a perfectly reasonable definition to work with, and in this problem
you'll explore some properties of hereditary sets.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

  \item Given the self-referential nature of the definition of hereditary sets,
    it's not even clear that hereditary sets even exist at all!  As a starting
    point, prove that there is at least one hereditary set.

  \begin{shaded}
    Provide a proof here.
  \end{shaded}

\end{enumerate}

\annotate{When confronted with a new definition, it never hurts to try out some
  examples. So pick a set, any set, and then apply the above definition to see
  whether it's hereditary. If so, great! You're done. If not, make sure you can
  explain why not. Then, based on what you found, pick another set and repeat
  this process. After a few iterations, you will likely converge on an answer.}
  \\

\annotate{This strategy, by the way, is a \emph{great} way to get a handle on
  any new definition.}

\begin{enumerate}[resume*]

  \item Prove that if $H$ is a hereditary set, then $\wp(H)$ is also a
    hereditary set.

  \begin{shaded}
    Provide a proof here.
  \end{shaded}

\end{enumerate}

\annotate{The hardest part of this problem is determining how to set this proof
  up in a way that's precise and rigorous. Here are some things to think about:
  \begin{itemize}
    \item What is the general procedure for proving an implication? What's the
      antecedent here? What's the consequent?
    \item Consider the statement ``every $x \in S$ is also a hereditary set.''
      Is that an existentially-quantified statement, a universally-quantified
      statement, both, or neither? Based on what you know about how to prove
      existentially-quantified and universally-quantified statements, what
      should you do to prove this statement?
  \end{itemize}
  After you've written up a draft of your proofs, take a minute to read over
  them and apply the criteria from the Proofwriting Checklist. Here are a few
  specific things to watch out for:
  \begin{itemize}
    \item Although we've just introduced first-order logic as a tool for
      formalizing definitions and reasoning about mathematical structures, the
      convention is to \emph{not} use first-order logic notation (connectives,
      quantifiers, etc.) in written proofs. In a sense, you can think of
      first-order logic as the stage crew in the theater piece that is a proof –
      it works behind the scenes to make everything come together, but it's not
      supposed to be in front of the audience. Make sure that you're still
      writing in complete sentences, that you’re not using symbols like
      $\forall$ or $\rightarrow$ in place of words like ``for any'' or
      ``therefore,'' etc.
    \item A common mistake we see people make when they're just getting started
      is to restate definitions in the abstract in the middle of a proof. For
      example, we commonly see people say something like ``since $A \subseteq
      B$, we know that every element of $A$ is an element of $B$.'' When you're
      writing a proof, you can assume that whoever is reading your proof is
      familiar with the definitions of relevant terms, so statements like the
      one here that just restate a definition aren't necessary. Instead of
      restating definitions, try to apply those definitions. A better sentence
      would be something to the effect of ``Since $x \in A$ and $A \subseteq B$,
      we see $that x \in B$,'' which uses the definition to conclude something
      about a specific variable rather than just restating the definition. See
      the Guide to Proofs on Set Theory for more details.
  \end{itemize}}


Hereditary sets are used in \emph{foundational mathematics}, the study of how to
assemble all mathematical structures from simple structures. If you'd like to
learn more about them, take Math 161!


\pagebreak


\section{Tournament Champions}
\begin{wrapfigure}{r}{3.75cm}
  \begin{tikzpicture}[x=1.5cm, y=1.5cm]
    \node[draw, circle] (C) at (1, 0) {$C$};
    \node[draw, circle] (B) at
    (0.30901699437494745, 0.9510565162951535) {$B$};
    \node[draw, circle] (A) at
    (-0.8090169943749473, 0.5877852522924732) {$A$};
    \node[draw, circle] (E) at
    (-0.8090169943749475, -0.587785252292473) {$E$};
    \node[draw, circle] (D) at
    (0.30901699437494723, -0.9510565162951536) {$D$};
    \path[->] (B) edge (A);
    \path[->] (C) edge (A);
    \path[->] (D) edge (A);
    \path[->] (A) edge (E);
    \path[->] (B) edge (C);
    \path[->] (B) edge (D);
    \path[->] (E) edge (B);
    \path[->] (C) edge (D);
    \path[->] (C) edge (E);
    \path[->] (D) edge (E);
  \end{tikzpicture}
\end{wrapfigure}
A \emph{tournament} is a contest among $n$ players. Each player plays a game against each other player, and either wins
or loses the game (let's assume that there are no draws). We can visually represent a tournament by drawing a circle for
each player and adding arrows between pairs of players to indicate who won each game. For example, in the tournament to
the right, player $A$ beat player $E$, but lost to players $B$, $C$, and $D$. \\

A \emph{tournament champion} is a player $c$ where, for each other player $p$ in the tournament, either
\begin{itemize}
  \item $c$ won her game against $p$, or
  \item there's a player $q$ where $c$ won her game against $q$ and $q$ won his game against $p$.
\end{itemize}
In the tournament shown here, player $B$ is a champion: she won against $A$, $C$, and $D$, and although she lost to $E$,
she won against $D$, who in turn won against $E$. Player $C$ is also a champion: she won against $A$, $D$, and $E$, and
the one player she lost to ($B$) is covered because $C$ won against $E$, who in turn won against $B$. Player $A$,
however, is not a tournament champion. To see this, $A$ didn't win against $C$, nor is there any player who $A$ won
against who in turn won against $C$.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \item Is player $D$ a tournament champion? How about player $E$? No justification required.
\end{enumerate}
\annotate{This is all about applying the definition. You might have an intuition for what a tournament champion is, but
  to determine the answers to these questions, you'll have to look back at the definition.}
\begin{shaded}
  Write your answer here.
\end{shaded}

Here's an amazing fact about tournaments.
\begin{enumerate}[resume*]
  \item Let $T$ be an arbitrary tournament and $p$ be any player in that tournament. Prove the following statement: if
        $p$ won more games than anyone else in $T$ or is tied for winning the greatest number of games, then $p$ is a
        tournament champion in $T$.
\end{enumerate}
\annotate{Remember that proofwriting heavily involves leveraging definitions. Intuitively it makes sense that someone
  who won the most games did the best in a tournament, but that's not what's being asked here. Instead, you're asked to
  show that if someone won the most games (or tied for winning the most games), then they specifically meet the criteria
  described above that characterize what a tournament champion is.}
\annotate{A great question to ponder -- what has to happen for someone to not be a tournament champion? Don't guess
  based on your intuition; negate the definition of a tournament champion and see what happens. You might want to draw a
  picture of what happens in this case.}
\begin{shaded}
  Provide a proof here.
\end{shaded}
A corollary of the result you proved from (ii) is that every tournament with at least one player has at least one
tournament champion -- pick someone who won the most games or is tied for winning the most games. \\

\begin{enumerate}[resume*]
  \item Prove or disprove: if $T$ is a tournament and $c$ is a champion in $T$, then either $c$ won the most games or is
        tied for winning the most games.
\end{enumerate}
\annotate{This is the converse of the result from part (ii). Remember -- the converse of an implication is not
  necessarily equivalent to the original implication.}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\annotate{The result you proved in part (ii) of this problem is an example of a style of proof called a proof by extreme case. In a proof of that sort, you pick some "extreme" object, usually the biggest or smallest object of some type, then prove that it has some property. Here, you proved that the "winningest" player must be a tournament champion. Keep this idea in mind for the future,}



Next we introduce the notion of a \emph{loop} in a tournament. A loop
in a tournament $T$ is a series of $n \ge 3$ different players $p_1, p_2, \dots,
p_n$  such that player $p_1$ won against player $p_2$, player $p_2$ won against
player $p_3, \dots$, and, finally, player $p_n$  won against player $p_1$. The
\emph{length} of a loop is the number of players in the loop.

\begin{enumerate}[resume*]

  \item Give an example of a loop of length five in the tournament shown above.
    No justification is necessary.

\end{enumerate}

\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]

  \item Prove that if a tournament has any loops at all, then it must have a
    loop of length three.

\end{enumerate}

\begin{shaded}
  Provide a proof here.
\end{shaded}

\annotate{This would be a great spot to draw pictures and try out examples. Try
  drawing tournaments with different numbers of players and loops of different
  sizes and see if you notice anything. As a hint, use a \emph{proof by extreme case}. Focus on the smallest loop in the tournament -- what can you
  say about it?}

\pagebreak

\section*{Optional Fun Problem: Insufficient Connectives
(Extra Credit)}

Every propositional logic formula could be written in terms of just
$\rightarrow$ and $\perp$. However, you \textit{cannot} express every possible
propositional logic formula using just the $\leftrightarrow$ and $\perp$
connectives. Prove why not.

\begin{shaded}
Provide a proof here.
\end{shaded}

\end{document}