%
% 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.
%
\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{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#2}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Spring 2017}
\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}}
\begin{document}
\maketitle
\section{Implies and False}
Although propositional logic has many different connectives,
it turns out that any formula in propositional
logic can be rewritten as an equivalent propositional
formula that uses only the $\neg$, $\land$, and $\top$ connectives.
(You don't need to prove this).
In this problem,
you will prove a different result:
every formula in propositional
logic can be rewritten as an equivalent logical formula purely using the
$\rightarrow$ and $\perp$ connectives.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Find a formula that's logically equivalent to $\neg p$
that uses only the variable $p$ and the $\rightarrow$ and $\perp$ connectives.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a formula that's logically equivalent to $\top$
that uses only the $\rightarrow$ and $\perp$ connectives.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a formula that's logically equivalent to $p \land q$
that uses only the variables $p$ and $q$ and the $\rightarrow$
and $\perp$ connectives.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Since you can express $\neg$, $\land$, and $\top$ using just $\rightarrow$
and $\top$,
every possible formula in propositional logic can
be expressed using purely the $\rightarrow$ and $\bot$ connectives.
Nifty!
\section{Ternary Conditionals}
Many programming languages support a
\emph{ternary conditional operator}.
For example, in C, C++, and Java,
the expression $x$ ? $y$ : $z$ means
``evaluate the boolean expression $x$.
If it's true, the entire expression evaluates to $y$.
If it's false, the entire expression evaluates to $z$.'' \\
In the context of propositional logic,
we can introduce a new ternary connective ?: such that $p$ ? $q$ : $r$
means ``if $p$ is true, the connective evaluates to the truth value of $q$,
and otherwise it evaluates to the truth value of $r$.''
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Based on this description, write a truth table for the ?: connective.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a propositional formula equivalent to $p$ ? $q$ : $r$
that does not use the ?: connective.
Justify your answer by writing a truth table for your new formula.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
It turns out that it's possible to rewrite any formula
in propositional logic using only ?:, $\top$, and $\perp$.
The rest of this question will ask you to show this.
\begin{enumerate}[resume*]
\item Find a formula equivalent to $\neg p$
that does not use any connectives besides ?:, $\top$, and $\perp$.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a formula equivalent to $p \rightarrow q$
that does not use any connectives besides ?:, $\top$, and $\perp$.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Since all remaining connectives can be written purely
in terms of $\neg$ and $\rightarrow$,
any propositional formula using the seven standard connectives
can be rewritten using only the three connectives ?:, $\top$, and $\perp$. \\
The fact that all propositional formulas can be written
purely in terms of ?:, $\top$, and $\perp$ forms the basis for
the \textit{binary decision diagram},
a data structure for compactly encoding propositional formulas.
Binary decision diagrams have applications in program optimization,
graph algorithms, and computational complexity theory.
Take CS166 or CS243 for more info!
\section{Executable Logic}
\begin{shaded}
Submit your edited $\mathsf{ExecutableLogic.cpp}$ file through GradeScope.
\end{shaded}
\section{First-Order Negations}
For each of the first-order logic formulas below,
find a first-order logic formula that is the negation of the
original statement.
Your final formula must not have any negations in it
except for direct negations of predicates.
For example,
the negation of the formula
$\forall x.\ (P(x) \rightarrow \exists y.\ (Q(x) \land R(y)))$
could be found by
pushing the negation in from the outside inward as follows:
\begin{align*}
&\neg (\forall x.\ (P(x) \rightarrow \exists y.\ (Q(x) \land R(y)))) \\
&\exists x.\ \neg(P(x) \rightarrow \exists y.\ (Q(x) \land R(y))) \\
&\exists x.\ (P(x) \land \neg\exists y.\ (Q(x) \land R(y))) \\
&\exists x.\ (P(x) \land \forall y.\ \neg(Q(x) \land R(y))) \\
&\exists x.\ (P(x) \land \forall y.\ (Q(x) \rightarrow \neg R(y)))
\end{align*}
Show every step of the process
of pushing the negation into the formula
(along the lines of what is done above), and
\textit{please preserve the indentation from the original formula} as you go.
You don't need to formally prove that your negations are correct. \\
We strongly recommend reading
over the Guide to Negations before starting this problem.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item
$\begin{aligned}[t]
&\exists p.\ (\textit{Problem}(p) \land \\
&\qquad \forall g.\ (\textit{Program}(g) \rightarrow
\neg \textit{Solves}(g, p)) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$\begin{aligned}[t]
&\forall x \in \R.\ \forall y \in \R.\ (x < y \rightarrow \\
&\qquad \exists q \in \Q.\ (x < q \land q < y) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$(\forall x.\ \forall y.\ \forall z.\ (R(x, y) \land
R(y, z) \rightarrow R(x, z))) \rightarrow
(\forall x.\ \forall y.\ \forall z.\ (R(y, x) \land R(z, y)
\rightarrow R(z, x)))$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$\begin{aligned}[t]
&\forall x.\ \exists S.\ (\textit{Set}(S) \land \\
&\qquad \forall z.\ (z \in S \leftrightarrow z = x) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$\begin{aligned}[t]
&\forall k.\ (\textit{SixClique}(k) \rightarrow \\
&\qquad \exists t.\ (\textit{Triangle}(t, k)\ \land \\
&\qquad\qquad (\forall e.\ (\textit{Edge}(e, t) \rightarrow
\textit{Red}(e)) \lor \forall e.\ (\textit{Edge}(e, t) \rightarrow
Blue(e))) \\
&\qquad) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\section{Vacuous Truths}
A statement is called \textbf{\textit{vacuously true}} if either
\begin{itemize}
\item it's an implication of the form $P \rightarrow Q$ where $P$ is false,
\item it's a universally-quantifed implication $\forall x.\ (P(x) \rightarrow Q(x))$ where $P(x)$ is never true, or
\item it's a universally-quantifed implication $\forall x \in S.\ Q(x)$ where $S$ is the empty set.
\end{itemize}
These statements are true \textit{by definition}. In the first case,
the truth table for the $\rightarrow$ connective says the
implication is true when the antecedent is false, and in the second
and third cases we just define these sorts of statements to be true. \\
You might be wondering why exactly this is the case.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Negate the propositional formula $P \rightarrow Q$ and push the negations as deep as possible. Now, look at
the resulting formula. Explain why when $P \rightarrow Q$ is vacuously true, its negation is false.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Negate the first order formula $\forall x.\ (P(x) \rightarrow Q(x))$ and push the negations as deep as possible. Now,
look at the resulting formula. Explain why if the original formula is vacuously true, then its negation is false.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Negate the first order formula $\forall x \in S.\ Q(x)$ and push the negations as deep as possible. Now, look
at the resulting formula. Explain why if the original formula is vacuously true, then its negation is false.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Your answers to parts (i), (ii), and (iii) of this problem give another justification for vacuous truths. The
three classes of statements given above have false negations in the indicated cases, and therefore to keep
everything consistent we choose to define them as true.
\begin{enumerate}[resume,label*=\roman*.,ref=\roman*]
\item Now, look back over the code you wrote for parts (ii), (iv), and (v) of the Executable Logic problem.
In the course of writing those functions, you should not have needed to add in any special
case logic to handle groups of people where the formulas were vacuously true. (If you did, see if
you can go back and remove it!) Briefly explain why it's not necessary to handle these cases explicitly
and why your code, as written, will correctly handle empty inputs without any special-case logic.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Your answer to part (iv) of this problem gives a different intuition for why statements would be vacuously
true - vacuous truth naturally follows from how we might think about checking whether a universally-quantifed
formula would be true.
\section{This, But Not That}
\begin{shaded}
Submit your five edited $\mathsf{.people}$ files through GradeScope.
\end{shaded}
\section{Translating into Logic}
In each of the following,
you will be given a list of first-order predicates and functions
along with an English sentence.
In each case,
write a statement in first-order logic that expresses
the indicated sentence.
Your statement may use any first-order construct
(equality, connectives, quantifiers, etc.),
but you \textbf{\textit{must}} only use the predicates, functions,
and constants provided.
You do not need to provide the simplest formula
possible, though we'd appreciate it if you made an effort to do so.
\smiley \\
We strongly recommend reading the Guide to First-Order Logic Translations before starting this problem.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Given the predicate
\qquad $\textit{Natural}(x)$,
which states that $x$ is an natural number
and the functions
\qquad $x + y$, which represents the sum of $x$ and $y$, and
\qquad $x \cdot y$, which represents the product of $x$ and $y$
write a statement in first-order logic that says
``for any $n \in \N$, $n$ is even if and only if
$n^2$ is even.''
Remember that numbers are not a part of first-order logic,
so you cannot use the number $2$ here.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Given the predicates
\qquad $\textit{Person}(p)$,
which states that $p$ is a person;
\qquad $\textit{Kitten}(k)$,
which states that $k$ is a kitten; and
\qquad $\textit{HasPet}(o, p)$,
which states that $o$ has $p$ as a pet,
write a statement in first-order logic that says
``someone has exactly two pet kittens and no other
pets.'' Make sure your formula requires that the person
have \textit{exactly} two pet kittens; look at the
lecture example of uniqueness as a starting point.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item The \textbf{\textit{axiom of pairing}}
is the following statement:
given any two distinct objects $x$ and $y$,
there's a set containing $x$ and $y$ and nothing else.
Given the predicates
\qquad $x \in y$, which states that $x$ is an element of $y$, and
\qquad $\textit{Set}(S)$, which states that $S$ is a set,
write a statement in first-order logic that expresses the axiom of pairing.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Given the predicates
\qquad $x \in y$, which states that $x$ is an element of $y$, and
\qquad $\textit{Set}(S)$, which states that $S$ is a set,
write a statement in first-order logic that says
``every set has a power set.''
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Given the predicates
\qquad $\textit{Lady}(x)$, which states that $x$ is a lady;
\qquad $\textit{Glitters}(x)$, which states that $x$ glitters;
\qquad $\textit{SureIsGold}(x, y)$,
which states that $x$ is sure that $y$ is gold;
\qquad $\textit{Buying}(x, y)$, which states that $x$ buys $y$; and
\qquad $\textit{StairwayToHeaven}(x)$,
which states that $x$ is a Stairway to Heaven;
write a statement in first-order logic that says
``there's a lady who's sure all that glitters is gold,
and she's buying a Stairway to Heaven.''
\footnote{Let's face it -- the lyrics to Led Zeppelin's
``Stairway to Heaven'' are impossible to decipher.
Hopefully we can gain some
insight by translating them into first-order logic!}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
The remaining problems on this problem set are here for proofwriting practice.
When writing up your final answers, you should still obey all the proofwriting
stylistic conventions we've used throughout the quarter: write in complete
sentences, don't use mathematical symbols instead of plain English, etc. In
partticular, \textit{do not use propositional logic symbols or quantifers in your proofs};
FOL is extremely useful for expressing definitions and reasoning about negations,
but is generally not used in written proofs.
\section{Hereditary Sets}
Let's begin with a fun little definition:
\begin{center}
A set $S$ is called a \textbf{\textit{hereditary set}}
if all its elements are hereditary sets.
\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 these types of 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}
\item Prove that if $S$ is a hereditary set,
then $\wp(S)$ is also a hereditary set.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\newpage
\section{Symmetric Latin Squares}
A \textbf{\textit{Latin square}} is an $n \times n$ grid filled with
the numbers $1,2,3,\dots,n$ such that every number appears
in every row and every column exactly once.
For example, the following are Latin squares:
\begin{figure}[h!]
\centering
\begin{minipage}{2cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|}{|c|c|c|}
1 & 2 & 3 \\
3 & 1 & 2 \\
2 & 3 & 1
\end{TAB}
\end{minipage}
\begin{minipage}{2.5cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|}{|c|c|c|c|}
4 & 2 & 1 & 3 \\
1 & 3 & 2 & 4 \\
3 & 1 & 4 & 2 \\
2 & 4 & 3 & 1
\end{TAB}
\end{minipage}
\begin{minipage}{3cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|c|}{|c|c|c|c|c|}
1 & 3 & 5 & 2 & 4 \\
2 & 4 & 1 & 3 & 5 \\
3 & 5 & 2 & 4 & 1 \\
4 & 1 & 3 & 5 & 2 \\
5 & 2 & 4 & 1 & 3
\end{TAB}
\end{minipage}
\end{figure}
A \textbf{\textit{symmetric Latin square}} is a Latin square that is
symmetric across the main diagonal (the one from the
upper-left corner to the lower-right corner).
That is, the elements at positions $(i, j)$ and $(j, i)$ are always the same.
For example:
\begin{figure}[h!]
\centering
\begin{minipage}{2cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|}{|c|c|c|}
1 & 2 & 3 \\
2 & 3 & 1 \\
3 & 1 & 2
\end{TAB}
\end{minipage}
\begin{minipage}{2.5cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|}{|c|c|c|c|}
4 & 2 & 3 & 1 \\
2 & 3 & 1 & 4 \\
3 & 1 & 4 & 2 \\
1 & 4 & 2 & 3
\end{TAB}
\end{minipage}
\begin{minipage}{3cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|c|}{|c|c|c|c|c|}
1 & 2 & 3 & 4 & 5 \\
2 & 4 & 5 & 3 & 1 \\
3 & 5 & 2 & 1 & 4 \\
4 & 3 & 1 & 5 & 2 \\
5 & 1 & 4 & 2 & 3
\end{TAB}
\end{minipage}
\end{figure}
Prove that in any $n \times n$ symmetric Latin square
where $n$ is odd, every number $1, 2, 3, \dots, n$ must appear
at least once on the main diagonal. \\
As a note,
this statement is \emph{not} true if $n$ is even
and this statement is \emph{not} true if the Latin square isn't symmetric.
As a good way of checking your work,
if you have an answer written up to this problem,
read over it and make sure that you specifically refer to the fact that
$n$ is odd and to the fact that the Latin square is symmetric.
If your proof doesn't rely on these facts,
it is almost certainly incorrect.
(Generally speaking,
this is a great way to check your proofs:
try changing the assumptions you're making and see if your proof still works.
If it does, chances are it contains a logical error.) \\
\emph{(Hint: split the Latin square into three regions --
the main diagonal and the two regions above and below
the main diagonal. Then think about how often each element
appears in each group.)}
\begin{shaded}
Provide a proof here.
\end{shaded}
\section{Tournament Winners}
Here's one more problem to help you practice your proofwriting.
It's a classic CS103 problem,
and we hope that you enjoy it! \\
\begin{wrapfigure}{l}{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 \textbf{\textit{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 drawing arrows between pairs of players
to indicate who won each game.
For example,
in the tournament to the left,
player $A$ beat player $E$, but
lost to players $B$, $C$, and $D$. \\
A \textbf{\textit{tournament winner}}
is a player in a tournament who, for each other player,
either won her game against that player,
or won a game against a player who in
turn won his game against that player (or both).
For example, in the graph on
the left,
players B, C, and E are tournament winners.
However, player D is \textbf{\textit{not}} a tournament winner,
because he neither beat player C,
nor beat anyone who in turn beat player C.
Although player D won against
player E, who in turn won against player B,
who then won against player C, under our definition player D
is not a tournament winner.
\emph{(Make sure you understand why!)} \\
One of the most fundamental results about tournaments is the
following:
any tournament with at least one
player has a tournament winner.
The first part of this problem asks you to prove this.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\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 winner in $T$.
This shows that every tournament with at least one
player has at least one winner.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item A \textbf{\textit{pseudotournament}} is like a tournament,
except that exactly one pair of people don't play each other.
Show that for any $n \geq 2$,
there's a pseudotournament $P$ with $n$ players
and no tournament winners.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\section*{Optional Fun Problem: Insufficient Connectives
(1 Point Extra Credit)}
On some of the earlier problems on this problem set, you
that every propositional logic formula could be
written in terms of just the $\neg$, $\land$, and $\top$. You also saw that you could use just $\rightarrow$ and $\bot$, or alternatively that you could just use ?:, $\top$, and $\bot$. \\
Interestingly, you cannot express every possible propositional logic formula using just the $\leftrightarrow$ and $\bot$ connectives. Prove why not.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{document}