\documentclass[12pt]{article}


%----------Packages----------
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
%\usepackage{amsrefs}
\usepackage{dsfont}
\usepackage{mathrsfs}
\usepackage{stmaryrd}
\usepackage[all]{xy}
\usepackage[mathcal]{eucal}
\usepackage{verbatim}  %%includes comment environment
\usepackage{fullpage}  %%smaller margins
\usepackage{hyperref}
%----------Commands----------

%%penalizes orphans
\clubpenalty=9999
\widowpenalty=9999

%% bold math capitals
\newcommand{\bA}{\mathbf{A}}
\newcommand{\bB}{\mathbf{B}}
\newcommand{\bC}{\mathbf{C}}
\newcommand{\bD}{\mathbf{D}}
\newcommand{\bE}{\mathbf{E}}
\newcommand{\bF}{\mathbf{F}}
\newcommand{\bG}{\mathbf{G}}
\newcommand{\bH}{\mathbf{H}}
\newcommand{\bI}{\mathbf{I}}
\newcommand{\bJ}{\mathbf{J}}
\newcommand{\bK}{\mathbf{K}}
\newcommand{\bL}{\mathbf{L}}
\newcommand{\bM}{\mathbf{M}}
\newcommand{\bN}{\mathbf{N}}
\newcommand{\bO}{\mathbf{O}}
\newcommand{\bP}{\mathbf{P}}
\newcommand{\bQ}{\mathbf{Q}}
\newcommand{\bR}{\mathbf{R}}
\newcommand{\bS}{\mathbf{S}}
\newcommand{\bT}{\mathbf{T}}
\newcommand{\bU}{\mathbf{U}}
\newcommand{\bV}{\mathbf{V}}
\newcommand{\bW}{\mathbf{W}}
\newcommand{\bX}{\mathbf{X}}
\newcommand{\bY}{\mathbf{Y}}
\newcommand{\bZ}{\mathbf{Z}}

%% blackboard bold math capitals
\newcommand{\bbA}{\mathbb{A}}
\newcommand{\bbB}{\mathbb{B}}
\newcommand{\bbC}{\mathbb{C}}
\newcommand{\bbD}{\mathbb{D}}
\newcommand{\bbE}{\mathbb{E}}
\newcommand{\bbF}{\mathbb{F}}
\newcommand{\bbG}{\mathbb{G}}
\newcommand{\bbH}{\mathbb{H}}
\newcommand{\bbI}{\mathbb{I}}
\newcommand{\bbJ}{\mathbb{J}}
\newcommand{\bbK}{\mathbb{K}}
\newcommand{\bbL}{\mathbb{L}}
\newcommand{\bbM}{\mathbb{M}}
\newcommand{\bbN}{\mathbb{N}}
\newcommand{\bbO}{\mathbb{O}}
\newcommand{\bbP}{\mathbb{P}}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbR}{\mathbb{R}}
\newcommand{\bbS}{\mathbb{S}}
\newcommand{\bbT}{\mathbb{T}}
\newcommand{\bbU}{\mathbb{U}}
\newcommand{\bbV}{\mathbb{V}}
\newcommand{\bbW}{\mathbb{W}}
\newcommand{\bbX}{\mathbb{X}}
\newcommand{\bbY}{\mathbb{Y}}
\newcommand{\bbZ}{\mathbb{Z}}

%% script math capitals
\newcommand{\sA}{\mathscr{A}}
\newcommand{\sB}{\mathscr{B}}
\newcommand{\sC}{\mathscr{C}}
\newcommand{\sD}{\mathscr{D}}
\newcommand{\sE}{\mathscr{E}}
\newcommand{\sF}{\mathscr{F}}
\newcommand{\sG}{\mathscr{G}}
\newcommand{\sH}{\mathscr{H}}
\newcommand{\sI}{\mathscr{I}}
\newcommand{\sJ}{\mathscr{J}}
\newcommand{\sK}{\mathscr{K}}
\newcommand{\sL}{\mathscr{L}}
\newcommand{\sM}{\mathscr{M}}
\newcommand{\sN}{\mathscr{N}}
\newcommand{\sO}{\mathscr{O}}
\newcommand{\sP}{\mathscr{P}}
\newcommand{\sQ}{\mathscr{Q}}
\newcommand{\sR}{\mathscr{R}}
\newcommand{\sS}{\mathscr{S}}
\newcommand{\sT}{\mathscr{T}}
\newcommand{\sU}{\mathscr{U}}
\newcommand{\sV}{\mathscr{V}}
\newcommand{\sW}{\mathscr{W}}
\newcommand{\sX}{\mathscr{X}}
\newcommand{\sY}{\mathscr{Y}}
\newcommand{\sZ}{\mathscr{Z}}

\renewcommand{\phi}{\varphi}
%\renewcommand{\emptyset}{\O}

\providecommand{\abs}[1]{\lvert #1 \rvert}
\providecommand{\norm}[1]{\lVert #1 \rVert}
\providecommand{\x}{\times}
\providecommand{\ar}{\rightarrow}
\providecommand{\arr}{\longrightarrow}


%----------Theorems----------

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{nondefinition}[theorem]{Non-Definition}
\newtheorem{exercise}[theorem]{Exercise}

\numberwithin{equation}{subsection}

%Redefine the first level
\renewcommand{\theenumi}{(\alph{enumi})}
\renewcommand{\labelenumi}{\theenumi}


%----------Title-------------
\title{Homework 3}
\author{Donald Knuth} 
\date{\today}

\begin{document}

\pagestyle{plain}

\maketitle


%%---  sheet number for theorem counter
%\setcounter{section}{1}   

% 1
\bigskip
\noindent
\textbf{1. (Practice in Posing Questions)} What is an interesting open-ended question you could ask, which is related to the material that we covered in class? What is a concrete mathematical question that could be used to approach an answer to the question? (If you also want to provide a proof of this concrete mathematical question, that's great and we'll look at it, but what you're being graded on are the questions themselves.)


% 2
\bigskip
\noindent
\textbf{2. (Practice with logic symbols and truth tables)} Use truth tables to create them  to decide which of the following implications are tautologies (i.e. always true):
\begin{enumerate}
  \item{If $P \Leftrightarrow Q$, then $(P \wedge R) \Leftrightarrow (Q \wedge R)$.}
  \begin{proof}
  The statement ``not A" is given in symbols at $\neg A$.
  
  You can make truth tables by using the \textbf{tabular} environment:
 \[
\begin{tabular}{ l | c | c | r }
  A & B & C & D \\
  \hline			
  T & T & T & F \\
  F & T & F & T \\
  F & F & F & F \\
\end{tabular}
\]
  \end{proof}

  
  \item{If $P \Leftrightarrow Q$, then $(P \wedge R) \Leftrightarrow (Q \wedge R)$.}
  
  \item{If $(P \vee R) \Leftrightarrow (Q \vee R)$, then $P \Leftrightarrow Q$.}
  
  \item{If $(P \wedge R) \Leftrightarrow (Q \wedge R)$, then $P \Leftrightarrow Q$.}	
\end{enumerate}



% 3
\bigskip
\noindent
\textbf{3. (Logical Equivalence in Life)} Consider the following pairs of statements. Which pairs of statements are equivalent? (Write the logical form of P and Q, for example, rewrite a statement ``$P$" in the form ``$A \Rightarrow B$" where A and B are statements.)
\begin{enumerate}
  \item{P: I won't be accepted to medical school if I don't do well on the MCAT.
  
  \noindent
  Q: If I do well on the MCAT, I will be accepted to medical school.}	
  \item{P: In order for it to rain, there must be clouds.
  
  \noindent
  Q: If it does not rain, then there are no clouds.}
  
  \item{P: If it is sunny tomorrow, then I'll go hiking.
  
  \noindent
  Q: I'll go hiking only if it is sunny tomorrow.}
  
  \item{P: Only completely justified answers will get full credit.
  
  \noindent
  Q: If complete justification is not given, the answer will not receive full credit.}
\end{enumerate}

% 4
\bigskip
\noindent
\textbf{4. (Aphorisms)} State the contrapositive and the converse of each of the following statements:
\begin{enumerate}
  \item{In order for it to rain, there must be clouds.}
  \begin{proof}[Solution]
  	
  \end{proof}

  \item{In order for it to rain, it is sufficient that there are clouds.}
  \item{What is good for the goose is good for the gander.}
  \item{If wishes were horses, then beggars would ride.}	
\end{enumerate}



% 5
\bigskip
\noindent
\textbf{5. (A Consistency Check)} Formalize these statements and determine (with truth tables or otherwise), whether they are consistent (i.e. if there are some assumptions on the atomic propositions that would make it true): ``The system is in a multiuser state if and only if it is operating normally. If the system is operating normally, the kernel is functioning. Either the kernel is functioning or the system is in interrupt mode. If the system is not in multiuser state, then it is in interrupt mode. The system is not in interrupt mode."


% % % % % % 
% % % % % %
% COPY OVER THE FOLLOWING TEXT TO groupwork_template.tex if you'd like
% % % % % %
% % % % % % 


\bigskip
\noindent
\textbf{6. (Groupwork) [The Legend of the Three Chests]} You are exploring a secret cave and you stumble upon three treasure chests. According to legend, one contains gold, while the other two are empty. Each chest is inscribed with a clue:

Chest 1: ``I am empty"

Chest 2: ``I am empty."

Chest 3: ``The gold is in the second chest."

According to the trustworthy old sage that told you about the cave, only one message is true, the other two are false. Which chest contains the gold?

Formalize the puzzle using propositional logic, and justify the solution using a truth table.

\bigskip
\noindent
\textbf{7. (Groupwork) [Who wants to live on this planet?]} Every inhabitant of far-flung planet has one of three possible occupations: educator, lawyer, or politician. The educators always tell the truth, the politicians always lie, and lawyers sometimes tell the truth and sometimes lie, depending on how they feel. This planet's society has a strict hierarchical order: educators are considered to be the upper class, lawyers are members of the middle class, and politicians belong to the lower class. 
\begin{enumerate}
  \item{You overhear two citizens (who you creatively call A and B) of this planet say the following to each other:
  \begin{quote}
  A: ``You [pointing to B] are in a higher class than me."
  
  B: ``That's not true."
  \end{quote}
  Can we determine the occupations of A and B?
  }	
  
  \item{One day, you meet three inhabitants of this planet (who you call X, Y, and Z because you cannot pronounce their names). According to your trusted intelligence briefing, all three have different occupations. They tell you the following:
  \begin{quote}
  X: ``I am a lawyer."
  
  Y: ``That's true."
  
  Z: ``I am not a lawyer."	
  \end{quote}
  Can we determine the occupations of X, Y, and Z?
  }
\end{enumerate}

\end{document}