% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.

\documentclass[11pt]{article} % use larger type; default would be 10pt

\usepackage[utf8]{inputenc} % set input encoding (not needed with XeLaTeX)

%%% Examples of Article customizations
% These packages are optional, depending whether you want the features they provide.
% See the LaTeX Companion or other references for full information.

%%% PAGE DIMENSIONS
\usepackage{geometry} % to change the page dimensions
\geometry{a4paper} % or letterpaper (US) or a5paper or....
% \geometry{margins=2in} % for example, change the margins to 2 inches all round
% \geometry{landscape} % set up the page for landscape
%   read geometry.pdf for detailed page layout information

\usepackage{graphicx} % support the \includegraphics command and options

% \usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent

%%% PACKAGES
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
% These packages are all incorporated in the memoir class to one degree or another...

%%% HEADERS & FOOTERS
\usepackage{fancyhdr} % This should be set AFTER setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{\thepage}\rfoot{}

%%% SECTION TITLE APPEARANCE
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (See the fntguide.pdf for font help)
% (This matches ConTeXt defaults)

%%% ToC (table of contents) APPEARANCE
\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!

%%% END Article customizations

%%% The "real" document content comes below...

\title{Recitation 2}
\author{Created by Taylor Spangler, Adapted by Beau Christ}
\date{\today} % Activate to display a given date or no date (if empty),
         % otherwise the current date is printed 

\begin{document}
\maketitle

\begin{itemize}

\item Questions about Piazza, \LaTeX \hspace{1 mm}or lecture?

\item Questions on the homework?

\item Consider Section 1.1, problem 15 on page 14 of your Rosen textbook

\begin{enumerate}

\item First, we define the following \textit{propositions}:

\begin{itemize}
\item \textit{p}: Grizzly bears have been seen in the area.
\item \textit{q}: Hiking is safe on the trail.
\item \textit{r}: Berries are ripe along the trail.
\end{itemize}
\item Now, we convert the following English sentences into PL sentences using logical connectives:
\begin{itemize}
\item[a] : ``Berries are ripe along the trail, but grizzly bears have not been seen in the area:'' $r \wedge \neg p$
\item[b] : ``Grizzly bears have not been seen in the area and hiking on the trail is safe, but berries are ripe along the trail:'' $\neg p \wedge q \wedge r$
\item[c] : ``If berries are ripe along the trail, hiking is safe if and only if grizzly bears have not been seen in the area:'' $r \rightarrow (q \leftrightarrow \neg p)$
\item[d] : ``It is not safe to hike on the trail, but grizzly bears have not been seen in the area and berries along the trail are ripe:'' $\neg q \wedge \neg p \wedge r$
\item[e] : ``For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail and for grizzly bears not to have been seen in the area:'' $ (q \rightarrow (\neg r  \wedge \neg p)) \wedge \neg((\neg r \wedge \neg p) \rightarrow q)$
\item[f] : ``Hiking is not safe on the trail whenever grizzly bears have been seen in the area and berries are ripe along the trail:'' $(p \wedge r) \rightarrow \neg q$
\end{itemize}

\end{enumerate}

\pagebreak

\item Consider Section 1.1, problem 35, part C. Construct the truth table for the following sentence:
\[(p\rightarrow q) \vee (\neg p \rightarrow q)\]
\begin{enumerate}
\item We proceed step by step following three stages:
\begin{enumerate}
\item $p\rightarrow q$
\item $\neg p \rightarrow q$
\item $(p\rightarrow q) \vee (\neg p \rightarrow q)$
\end{enumerate}

\item Now we construct a table filling in the $p$ an $q$ values:\\
\begin{center}
\begin{tabular} {|cc||c|c|c|}\hline
$p$ & $q$ & $p \rightarrow q$ & $\neg p \rightarrow q$ & $(p\rightarrow q) \vee (\neg p \rightarrow q)$\\\hline\hline
0 & 0 & - & - & -\\
0 & 1 & - & - & -\\
1 & 0 & - & - & -\\
1 & 1 & - & - & -\\\hline
\end{tabular}
\end{center}

\item Now fill in the rest of the table:\\
\begin{center}
\begin{tabular} {|cc||c|c|c|}\hline
$p$ & $q$ & $p \rightarrow q$ & $\neg p \rightarrow q$ & $(p\rightarrow q) \vee (\neg p \rightarrow q)$\\\hline\hline
0 & 0 & 1 & 0 & 1\\
0 & 1 & 1 & 1 & 1\\
1 & 0 & 0 & 1 & 1\\
1 & 1 & 1 & 1 & 1\\\hline
\end{tabular}
\end{center}
\end{enumerate}

\item Consider now a harder problem, from Section 1.2, problem 35. 
\begin{enumerate}
\item First, we select \textit{atomic propositions}:
\begin{itemize}
\item Let $b$ be the butler
\item Let $c$ be the cook
\item Let $g$ be the gardener
\item Let $h$ be the handyman
\end{itemize}
We use 0 to indicate that the person is lying, and 1 to indicate that the person is telling the truth.

\item Next, we transcribe the English statements into statements in PL:
\begin{itemize}
\item ``If the butler is telling the truth then so is the cook.'' $b \rightarrow c$
\item ``The cook and the gardener cannot both be telling the truth.'' $\neg (c \wedge g) \equiv \neg c \vee \neg g$
\item ``The gardener and the handyman are not both lying.'' $\neg (\neg g \wedge \neg h) \equiv g \vee h$
\item ``If the handyman is telling the truth, then the cook is lying.'' $h \rightarrow \neg c$
\end{itemize}

\pagebreak

\item Now, we want to find a \textit{model} for our
  \textit{sentence}. Remember that a model is a truth assignment to
  each \textit{term} in our sentence so that the conjunction of all
  clauses is satisfied (i.e., each clause must evaluate to true).
  Because we are looking for a \textit{model}, we can stop looking at
  an assignment once we detect a clause that evaluates to false:
  indeed, the conjuction of clauses cannot be satisfied. A ``-'' is
  used in Tabl\ref{tab:tt} to denote that we interrupted the process
  before evaluating that \textit{clause}.
  \begin{table}[ht]
    \caption{Turth table}
\label{tab:tt}
\begin{center}
\begin{tabular} {|cccc|cccc|}\hline
$b$ & $c$ & $g$ & $h$ & $b \rightarrow c$ & $\neg c \vee \neg g$ & $g \vee h$ & $h \rightarrow \neg c$\\\hline
0 & 0 & 0 & 0 & 1 & 1 & 0 & - \\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
0 & 1 & 0 & 0 & 1 & 1 & 0 & - \\
0 & 1 & 0 & 1 & 1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & - & - \\
0 & 1 & 1 & 1 & 1 & 0 & - & - \\\hline
1 & 0 & 0 & 0 & 0 & - & - & - \\
1 & 0 & 0 & 1 & 0 & - & - & - \\
1 & 0 & 1 & 0 & 0 & - & - & - \\
1 & 0 & 1 & 1 & 0 & - & - & - \\\hline
1 & 1 & 0 & 0 & 1 & 1 & 0 & - \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & - & - \\
1 & 1 & 1 & 1 & 1 & 0 & - & - \\\hline
\end{tabular}
\end{center}
  \end{table}
   
\item From Table~\ref{tab:tt}, we see that the sentence has three
  models (see line 2, 3, and 4).  Examining those model, we conclude
  that the butler and the cook are both lying, and that either the
  gardener, the handyman, or both are telling the truth.

\end{enumerate}

\item Consider Section 1.1 problem number 27 (b) on page 15 of the
  textbook:
\begin{itemize}
\item ``I come to class whenever there is going to be a quiz.'' Notice that this can be rephrased ``If there is going to be a quiz, I come to class.'' $p \rightarrow q$
\item What is the inverse of this sentence, $\neg p \rightarrow \neg q$? ``If there is not going to be a quiz, then I do not come to class.''
\item What is the converse of this sentence, $q \rightarrow p$? ``If I come to class, then there is a quiz.''
\item What is the contrapositive of this sentence, $\neg q \rightarrow \neg p$? ``If I do not come to class, then there will not be a quiz.''
\item Below, examine the truth table with the inverse, converse, and  contrapositive of the implication $p\rightarrow q$.
\begin{center}
\begin{tabular}{|cc||c|c|c|c|}\hline
\multicolumn{2}{|c||}{Propositions} & \multicolumn{1}{c|}{Implication} & Inverse & Converse & Contrapositive\\
$p$ & $q$ & $p \rightarrow q$ & $\neg p \rightarrow \neg q$ & $q \rightarrow p$ & $\neg q \rightarrow \neg p$\\\hline\hline
0 & 0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 1 & 0\\
1 & 1 & 1 & 1 & 1 & 1\\\hline
\end{tabular}
\end{center}
\end{itemize}

\item Now, consider a different kind of problem, Section 1.1 problem 17 (c) on page 14.
\begin{itemize}
\item Let $p$ stand for $1+1 = 3$
\item Let $q$ stand for ``Dogs can fly.''
\item What is $p \rightarrow q$? $0 \rightarrow 0$, which is true.
\end{itemize}

\item Finally, Section 1.1 number 39, pg 15: Construct the truth table for the following sentence in PL:
\[(p \leftrightarrow q) \leftrightarrow (r \leftrightarrow s)\]
\begin{itemize}
\item First, can you tell immediately how many rows our truth table will have? With $n$ terms, we must have $2^{n}$ rows.
\end{itemize}
\begin{center}
\begin{tabular} {|cccc||c|c|c|}\hline
$a$ & $b$ & $c$ & $d$ & $(p \leftrightarrow q)$ & $(r \leftrightarrow s)$ & $(p \leftrightarrow q) \leftrightarrow (r \leftrightarrow s)$\\\hline
0 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 \\\hline
0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 \\
0 & 1 & 1 & 1 & 0 & 1 & 0 \\\hline
1 & 0 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\\hline
1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
\end{tabular}
\end{center}
\end{itemize}

\end{document}
