% !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 Week 3}
\author{Taylor Spangler}
%\date{} % 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 (\textbf{Skipped in Recitation}) Let's start by looking at section 1.1, problem 15 on page 14 of your Rosen textbook

\begin{enumerate}

\item First, lets figure out what our \textit{terms} are:

\begin{itemize}
\item[-] \textit{p} : Grizzly bears have been 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 why don't we try converting the following sentences into logical connectives, our \textit{clauses}:
\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 Now let's look at section 1.1, problem 35, part C. Construct the truth table for the following $(p\rightarrow q) \vee (\neg p \rightarrow q)$
\begin{enumerate}
\item First we break the problem into 3 parts
\begin{itemize}
\item[-] $p\rightarrow q$
\item[-] $\neg p \rightarrow q$
\item[-] $(p\rightarrow q) \vee (\neg p \rightarrow q)$
\end{itemize}

\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
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
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 Now a harder problem, from section 1.2, problem 35. 
\begin{enumerate}

\item First decide what the \textit{terms} are:
\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 will use 0 to represent that the person is lying, and a 1 to represent that the person is telling the truth.

\item Next we parse the question to get our \textit{clauses}:
\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 a \textit{model} is a truth assignment of our \textit{terms} which satisfies all of our \textit{clauses}. Since we are looking for a \textit{model}, we can stop looking at an assignment once we see that a \textit{clause} evaluates to false. A "-" is used in the following table to denote that we stopped before evaluating that \textit{clause}.

\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}

\item From this table we can 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 Now let's look at Section 1.1 problem number 27 (b) on page 15 of the text:

\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[-] Let's compare the truth tables for the inverse, contrapositive, and converse with implication.
\begin{center}
\begin{tabular}{|cc|cccc|}\hline
$p$ & $q$ & $p \rightarrow q$ & $\neg p \rightarrow \neg q$ & $q \rightarrow p$ & $\neg q \rightarrow \neg p$\\\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 let's look at 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$? $1 \rightarrow 0$ which is false.
\end{itemize}

\item 1.1 number 39, pg 15: Construct the truth table for $(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 get $2^{n}$ rows.
\end{itemize}
\begin{center}
\begin{tabular} {|cccc|ccc|}\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}

\item Now let's try looking at a problem using logical equivalences. From section 1.3, number 29 on page 35:\\
Show that $(p \rightarrow q) \wedge (q \rightarrow r) \rightarrow (p\rightarrow r)$ is a tautology
\begin{itemize}
\item First we will do so by using a truth table, then we will do so using the logical equivalences.
\item Recall that $\wedge$ has higher precedence than $\rightarrow$. We begin by constructing the truth table:
\newpage
\begin{center}
\begin{tabular}{|ccc|cccc|}\hline
$p$ & $q$ & $r$ & $p\rightarrow q$ & $q \rightarrow r$ & $p\rightarrow r$ & $(p \rightarrow q) \wedge (q \rightarrow r) \rightarrow (p\rightarrow r)$\\\hline
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
\end{tabular}
\end{center}
\item We can see that every truth assignment here evaluates to true, therefore we have that this is a tautology.
\item Now let's try proving it using logical equivalences:
\begin{enumerate}
\item $(p \rightarrow q) \wedge (q \rightarrow r) \rightarrow (p\rightarrow r)$ \hfill Given
\item $\neg ((p \rightarrow q) \wedge (q \rightarrow r)) \vee (p\rightarrow r)$ \hfill Implication
\item $\neg ((\neg p \vee q) \wedge (\neg q \vee r)) \vee (\neg p\vee r)$ \hfill Implication $\times$ 3
\item $\neg(\neg p \vee q) \vee \neg(\neg q \vee r) \vee (\neg p\vee r)$ \hfill DeMorgan's Law
\item $ (p \wedge \neg q) \vee ( q \wedge \neg r) \vee (\neg p\vee r)$ \hfill DeMorgan's Law $\times 2$ 
\begin{flushright}and Double Negation \end{flushright}
\item $(p \wedge \neg q) \vee ( q \wedge \neg r) \vee \neg p\vee r$ \hfill Associative Law
\item $(p \wedge \neg q) \vee \neg p\vee ( q \wedge \neg r) \vee r$ \hfill Commutative Law
\item $((p\vee \neg p) \wedge (\neg p \vee \neg q)) \vee ( q \wedge \neg r) \vee r$ \hfill Distributive Law
\item $(1 \wedge (\neg p \vee \neg q)) \vee ( q \wedge \neg r) \vee r$ \hfill $p \vee \neg p = 1$
\item $ (\neg p \vee \neg q) \vee ( q \wedge \neg r) \vee r$ \hfill Identity
\item $ (\neg p \vee \neg q) \vee ( (q\vee r) \wedge (\neg r\vee r))$ \hfill Distributive Law
\item $ (\neg p \vee \neg q) \vee ( (q\vee r) \wedge 1) $\hfill $r \vee \neg r = 1$
\item $ (\neg p \vee \neg q) \vee (q\vee r)$ \hfill Identity
\item $ \neg p \vee \neg q \vee q\vee r$ \hfill Associative Law
\item $ \neg p \vee 1 \vee r$ \hfill $q \vee \neg q = 1$
\item 1 \hfill Identity
\end{enumerate}
\item Thus we have a tautology.

\end{itemize}
\item Now how do we show that 2 things are not logically equivalent, here we see 1.3 problem 31:\\
Show that $(p\rightarrow q) \rightarrow r$ is not logically equivalent to $p\rightarrow(q\rightarrow r)$.
\begin{itemize}
\item Here we can use a counterexample. Suppose $p = 0$, $q = 1$, and $r = 0$. We can see that $(p\rightarrow q) \rightarrow r$ is false, however $p\rightarrow(q\rightarrow r)$ is true.
\end{itemize}

\newpage

\item Another useful procedure is to be able to show that two compound propositions are equal. Well to do that we can simply use the logical equivalences. For example, problem number 27 in section 1.3 on page 35:
\begin{itemize}
\item Show that $p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q$
\end{itemize}
\begin{enumerate}
\item $p \leftrightarrow q$ \hfill Given
\item $p \rightarrow q \wedge q \rightarrow p$ \hfill Equivalence Rule
\item $\neg p \vee q \wedge \neg q \vee p$ \hfill Implication $\times 2$
\item $q \vee \neg p \wedge p \vee \neg q$ \hfill Commutative Law
\item $\neg \neg q \vee \neg p \wedge \neg \neg p \vee \neg q$ \hfill Double Negation
\item $\neg q \rightarrow \neg p \wedge \neg p \rightarrow \neg q$ \hfill Implication $\times 2$
\item $ \neg p \rightarrow \neg q\wedge \neg q \rightarrow \neg p $ \hfill Commutativity
\item$\neg p \leftrightarrow \neg q$ \hfill Equivalence Rule
\end{enumerate}
\begin{itemize}
\item Thus we have shown that the two are equivalent.
\end{itemize}

\item (Last 10 minutes) Quiz.
\end{itemize}

\end{document}
