\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{bbm}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{pdflscape}
\usepackage{tikz-cd}
\usepackage{hyperref}

\usepackage{bussproofs}
\newcommand{\TagC}[1]{\RightLabel{\scriptsize #1}}

\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\newcommand{\points}[1]{\hfill {\bf \color{darkgray} [#1 points]}}

\DeclareMathOperator{\circhat}{\widehat{\circ}}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
15-151 Homework 4
}

Please submit in class at 8:00am on Tuesday 18th July
\end{center}

\subsection*{Exercises}

\begin{enumerate}[1.]
\item 
\begin{enumerate}[(a)]
\item Prove that $(p \vee q) \Rightarrow r$ is logically equivalent to $(p \Rightarrow r) \wedge (q \Rightarrow r)$. \points{3}
\item Draw a truth table demonstrating that $p \vee (\neg p)$ is true, no matter whether $p$ is true or false. \points{1}
\item Suppose you know that $p \Rightarrow r$ and $(\neg p) \Rightarrow r$ are true. Explain how parts (a) and (b) imply that $r$ is true. \points{1}
\end{enumerate}

\item Define a new logical operator $\uparrow$ by letting $p \uparrow q$ be true if $p$ and $q$ are not both true, and false otherwise.
\begin{enumerate}[(a)]
\item Draw the truth table for $p \uparrow q$. \points{1}
\item Prove that $\neg p \equiv p \uparrow p$. \points{1}
\item Prove that $p \wedge q \equiv (p \uparrow q) \uparrow (p \uparrow q)$. \points{2}
\item Express $p \vee q$ in terms of the variables $p$ and $q$ and the logical operator $\uparrow$, and prove that your expression is valid. \points{3}
\item Express $p \Rightarrow q$ in terms of the variables $p$ and $q$ and the logical operator $\uparrow$, and prove that your expression is valid. \points{3}
\end{enumerate}

\item The \textit{unique existential quantifier} `$\exists!$' is defined by saying $\exists!x \in X,\, p(x)$ is true if there is exactly one value of $x \in X$ such that $p(x)$ is true. More precisely, it can be defined in terms of $\exists$ and $\forall$ by saying
$$\exists! x \in X,\, p(x) \quad \equiv \quad \exists x \in X,\ (p(x) \wedge \forall y \in X,\, (p(y) \Rightarrow y=x))$$
Using this definition, write out $\neg \exists! x \in X,\, p(x)$ as a maximally negated logical formula containing only the quantifiers $\forall$ and $\exists$.

\points{5}

\item Write out the following sets in set-builder notation, without using English words; for example, the set of all even integers is $\{ n \in \mathbb{Z} \mid \exists k \in \mathbb{Z},\, n=2k \}$.
\begin{enumerate}[(a)]
\item The set of all odd integers; \points{3}
\item The set of all irrational numbers; \points{3}
\item The set of all natural numbers which can be expressed as $3u+7v$ for some natural numbers $u$ and $v$. \points{4}
\end{enumerate}
\end{enumerate}

\textit{Please also complete the task on the next page}

\subsection*{Other tasks}

\begin{enumerate}[1.]
\setcounter{enumi}{4}
\item Fill out the two-week questionnaire located at the following URL (which will be activated after the \LaTeX{} project submission deadline): \url{https://goo.gl/forms/o7zFaI2qYaTaeKQE3}

\points{5}
\end{enumerate}

\subsection*{Optional but recommended tasks {\normalfont (not for credit)}}

\begin{enumerate}[1.]
\setcounter{enumi}{5}
\item There are sixteen possible truth tables for propositional formulae containing two propositional variables. Prove that all propositional formulae containing two propositional variables is equivalent to one containing only the logical operator $\uparrow$ defined in Question 2. Deduce that all propositional formulae, no matter how many propositional variables they contain, can be expressed using only the logical operator $\uparrow$.
\item Another way of defining the unique existential quantifier is by letting
$$\exists ! x \in X,\, p(x) \quad \equiv \quad [\exists x \in X,\, p(x)] \wedge [\forall y,z \in X,\, (p(x) \wedge p(y)) \Rightarrow x=y]$$
Explain how this definition, and the definition given in Question 3, inform us of two ways in which we can prove statements of the form $\exists ! x \in X,\, p(x)$.
\item Let $p$ and $q$ be propositional variables, and let $C(p,q)$ be some logical formula involving only the variables $p$ and $q$. Suppose that $C(p,q)$ satisfies the following conditions:
\begin{enumerate}[(i)]
\item $C(p,q) \Rightarrow p$ and $C(p,q) \Rightarrow q$;
\item If $X$ is any propositional formula such that $X \Rightarrow p$ and $X \Rightarrow q$, then $X \Rightarrow C(p,q)$.
\end{enumerate}
Prove that $C(p,q) \equiv p \wedge q$.
\end{enumerate}

\end{document}