\input{config}
\input{preambles/preamble}
\input{preambles/definitions}
\input{preambles/environments}

\title{Problem Set 2}
\author[Daniel Gonzalez Cedre]{Discrete Mathematics}
\publisher{University of Notre Dame}
\date{Due on the \red{4\textsuperscript{th} of February, 2024}}

\begin{document}

\maketitle

% \section*{In this problem set, the variables $p$, $q$, and $r$ refer to propositions.}
% \section*{You may rely on the theorems listed in the margin.}
\marginnote{%
  You may rely on the following theorems throughout this problem set in addition to the axioms of classical logic.
  \begin{itemize}
    \item
      \emph{Uniqueness of Negations}
    \item
      $\neg \top \equiv \bot$ and $\neg \bot \equiv \top$
    \item
      \emph{Double Negation}
    \item
      \emph{Idempotency}
    \item
      \emph{Domination}
    \item
      \emph{De Morgan's Laws}
  \end{itemize}
}

We say that a propositional formula is a \defn{tautology} if it is logically equivalent to $\top$ under any assignment of truth values to its variables.

\begin{enumerate}
  \item[(5 pts) \quad 1.]
    Consider the following \emph{``proof''} of $p \lif (q \lif r) \equiv (p \lif q) \lif r$.
    \begin{mdframed}
      \vspace{2ex}
      \begin{proof}
        Observe the following chain of reasoning.
        \begin{align*}
          p \lif (q \lif r)
            &\equiv p \lor \neg(q \lif r)
              &\quad
              &\text{by \emph{conditional disintegration}} \\
            &\equiv p \lor \neg(q \lor \neg r)
              &\quad
              &\text{by \emph{conditional disintegration}} \\
            &\equiv p \lor \neg q \lor \neg r
              &\quad
              &\text{by \emph{associativity}} \\
            &\equiv (p \lor \neg q) \lor \neg r
              &\quad
              &\text{by \emph{associativity}} \\
            &\equiv (p \lif q) \lor \neg r
              &\quad
              &\text{by \emph{conditional disintegration}} \\
            &\equiv (p \lif q) \lif r
              &\quad
              &\text{by \emph{conditional disintegration}}
        \end{align*}
        Therefore, $p \lif (q \lif r) \equiv (p \lif q) \lif r$.
      \end{proof}
    \end{mdframed}
    Find all of the mistakes, if any, and \emph{explain why} they are mistakes.
  \item[(40 pts) \quad 2.]
    Prove the claims below \emph{without truth tables} for all propositions $p, q, r$.
    \begin{enumerate}
      \item
        Show $p \lif q \equiv \neg q \lif \neg p$.
      % \item
        % $(p \lif q) \land (\neg p \lif q) \equiv q$.
      % \item
        % $(p \lif r) \lor (q \lif r) \equiv (p \land q) \lif r$.
      % \item
        % $(p \lif q) \land (p \lif r) \equiv p \lif (q \land r)$.
      \item
        Show $(p \land (p \lif q)) \lif q$ is a tautology.
      \item
        Show $(\neg q \land (p \lif q)) \lif \neg p$ is a tautology.
      \item
        Show $(p \lif q) \lif ((p \lif \neg q) \lif \neg p)$ is a tautology.
    \end{enumerate}
  \item[(40 pts) \quad 3.]
    In this problem, we will progressively establish that the alternative axioms Hilbert proposed are all tautologies \emph{without truth tables.}.
    Here, the variables $p$, $q$, and $r$ all represent arbitrary propositions.
    \begin{enumerate}
      \item
        Show $p \lif p$ is a tautology.
      \item
        Show $(p \lif q) \lif (\neg q \lif \neg p)$ is a tautology.
      \item
        Show $p \lif (q \lif p)$ is a tautology.
      \item
        Show $(p \lif (q \lif r)) \lif ((p \lif q) \lif (p \lif r))$ is a tautology.
    \end{enumerate}
  % \item[(10 pts) \quad 4.]
  % \item[(20 pts)~~~~3.]
    % The variables $p$, $q$, $r$ refer to propositions
    % in the following problems.%
    % \marginnote{Make sure to read section 1.4 of the lecture notes on
                % logical nonequivalence.}
    % \begin{enumerate}
      % \item
        % Show that
        % $(p \lif q) \lif r$
        % is \emph{not} equivalent to
        % $p \lif (q \lif r)$.
      % \item
        % Show that
        % $\neg (p \lif q)$
        % is \emph{not} equivalent to
        % $\neg p \lif \neg q$.
    % \end{enumerate}
  % \item[(10 pts)~~~~3.]
    % Given%
    % \marginnote{Make sure to look at the \eorange{recursive} definition
                % of a proposition in the lecture notes.
                % Your proof should involve going through
                % the cases in that definition.}
    % an arbitrary proposition $p$,
    % show that there exists a proposition $q$
    % consisting only of $\neg$ and $\land$
    % such that $p \equiv q$.
  \item[(10 pts)~~~~4.]
    Show that $\neg$ and $\land$ are sufficient to express \emph{any} proposition.
  \item[(5 pts)~~~~5.]
    Is there a \emph{single connective} capable of expressing \emph{any} proposition?%
    \sidenote{%
      This does not necessarily have to be one of $\neg$, $\land$, $\lor$, $\lif$, nor $\liff$.
      You can define new logical connectives using truth tables.
    }
    Justify your answer with a proof.
\end{enumerate}

\end{document}
