\newcommand{\ig}[1]{}

% !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)

\usepackage{url}
%%% 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 3}

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

\begin{itemize}

\item Rosen 1.3:15 \\
Show that $(\lnot q \land (p \rightarrow q)) \rightarrow \lnot p$ is a tautology \\
\begin{tabular}{lll}\\
{\bf Step} & {\bf Sentence} & {\bf Equivalence law} \\
0. & $\lnot (\lnot q \land (p \rightarrow q)) \lor \lnot p$ \\
1. & $\equiv \lnot (\lnot q \land (\lnot p \lor q)) \lor \lnot p$  & Implication law\\
2. & $\equiv (q \lor (p \land \lnot q)) \lor \lnot p$  & DeMorgan's law\\
3. & $\equiv ((q \lor p) \land (q \lor \lnot q)) \lor \lnot p$  & Distributive law\\
4. & $\equiv ((q \lor p)) \lor \lnot p$  & Identity law\\
5. & $\equiv(q \lor (p \lor \lnot p))$  & Associative law\\
6. & $\equiv q \lor T$  & Identity law\\
7. & $\equiv T$  & Identity law
\end{tabular}

\item Rosen 1.3:23\\
Show that $(p \rightarrow r) \land (q \rightarrow r) \equiv$ $(p \lor q) \rightarrow r$\\
\begin{tabular}{lll}\\
{\bf Step} & {\bf Sentence} & {\bf Equivalence law} \\
0. & $(p \rightarrow r) \land (q \rightarrow r)$ \\
1. & $\equiv (\lnot p \lor r) \land (\lnot q \lor r)$ & Implication law\\
2. & $\equiv (\lnot p \land \lnot q) \lor r$ & Distributive law\\
3. & $\equiv \lnot (\lnot p \land \lnot q) \rightarrow r$ & Implication law\\
4. & $\equiv (p \lor q) \rightarrow r$ & DeMorgan's law and double negation law
\end{tabular}

\item
Example from a url that no longer exists:\footnote{\url{http://marauder.millersville.edu/~bikenaga/mathproof/rules-of-inference/rules-of-inference.html}}

Given:
\begin{enumerate}
\item
$p \land q$
\item
$p \rightarrow \lnot(q \land r)$
\item
$s \rightarrow r$
\end{enumerate}
Prove $\lnot s$ using the rules of inference.

\begin{tabular}{rll}
    & {\bf Step} & {\bf Reason} \\
1. & $p \land q$ & Premise \\
2. & $p \rightarrow \lnot(q \land r)$ & Premise \\
3. & $s \rightarrow r$ & Premise \\
4. & $p$ & Simplification of (1) \\
5. & $q$ & Simplification of (1) \\
6. & $\lnot(q \land r)$ & Modus Ponens (2) and (4) \\
7. & $\lnot q \lor \lnot r$ & DeMorgan's Law (6) \\
8. & $\lnot r$ & Disjunctive syllogism (5) and (7) \\
9. & $\lnot s$ & Modus Tollens (3) and (8)
\end{tabular}


\item Transcribe in FOL the following English statement: ``Politicians
  can fool some of the people all of the time, all of the people some
  of the time, but they cannot fool all of the people all of the time.''
\begin{enumerate}
\item First we define the predicates:\\
  \begin{tabular}{ll}
$Fools(x,y,t)$: & $x$ fool $y$ at time $t$.\\
$P(x)$: & $x$ is a politician.
  \end{tabular}
\item Universe of discourse: $x,y$ all human beings, $t$ all time instants.
\item The answer is:
  \begin{eqnarray}
  \forall x[P(x) \rightarrow &[ & (\exists y \forall t Fools(x,y,t)) \nonumber\\
&&  \wedge (\exists t \forall y Fools(x,y,t)) \nonumber\\
&& \wedge \neg (\forall y \forall t Fools(x,y,t))]]   \nonumber 
  \end{eqnarray}
\end{enumerate}
The expression $\neg (\forall y \forall t Fools(x,y,t))$ can be
difficult to spell out in English. We recommend that you use the
expression ``\textit{it is not the case that}'' whenever an expression
starts with a negation. Thus, the above reads: ``It is not the case
that every $x$ fools every $y$ at every time $t$.''

\item Beware of errors:
\begin{itemize}
\item Let's compare the meaning of the two expressions:
\begin{itemize}
\item $\exists t \forall y Fools(x,y,t)$: There is at least one time (or one incident) where everyone was fooled by $x$.
\item $\forall y \exists t Fools(x,y,t)$: Everyone is fooled at some point in time by $x$, but the time is not necessarily the same for all human beings.
\end{itemize}
Naturally, we intend the first meaning.

\item Also, compare the meaning of the following two expressions:
\begin{itemize}
\item $\forall x [P(x) \rightarrow \neg (\forall y \forall t Fools(x,y,t))] \equiv \forall x [P(x) \rightarrow (\exists y \exists t \neg Fools(x,y,t))]:$ It is not the case that every politician fools everyone all the time.
\item $\forall x[P(x) \rightarrow (\forall y \forall t \neg Fools(x,y,t))]$: Politicians do not ever fool anyone or politicians never fool anyone.
\end{itemize}
\end{itemize}
\item Now let's look at Rosen 1.4:43\\ Determine whether $\forall x (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \forall x Q(x)$ are logically equivalent. Justify your answer.

Do we think they are equivalent? \textit{No, they are not}.

Let $P(x)$ be a proposition that is sometimes true and sometimes false, and let $Q(x)$ be some proposition that is always false. For example:

  \begin{tabular}{ll} 
  $P(x)$: & $x$ is even \\
$Q(x)$: & $x$ is irrational\\
UoD: & $x \in Z$
\end{tabular}

Where an even number is always divisible by 2 and a rational number is
a number that can be written as the ratio of two integers, $\forall x
(Q(x) \rightarrow \exists a,b \in Z$ such that $x =\frac{a}{b})$.


In this situation, $\forall x (P(x) \rightarrow Q(x))$ is false whereas  
 $\forall x P(x) \rightarrow \forall x Q(x)$ is true.  Indeed:
\begin{itemize}

\item The statement $\forall x (P(x) \rightarrow Q(x))$ states that
  every odd integer is irrational, which obviously does not
  hold. (Actually, it states, for every integer, if it is odd then it
  is irrational.)


\item The statement $(\forall x P(x)) \rightarrow (\forall x Q(x))$ is
  true because $(\forall x P(x))$ is always false (remember, $P(x)$
  sometimes holds and sometimes does, so it cannot hold for every
  $x\in Z$) because it is says that every integer is even, which is
  not true.  On the other hand, we know that every integer is rational
  so it cannot be an irrational, so $(\forall x Q(x))$ is always
  false.  So, $(\forall x P(x)) \rightarrow (\forall x Q(x))$ is true
  becase 0$\rightarrow$0 holds.
\end{itemize}

\item Now let's look at Rosen 1.4:41 part a.\\
 Express the following English statement using predicates, quantifiers and logical connectives:
\textit{At least one mail message, among a nonempty set of messages, can be saved if there is a disk with more than ten kilobits of free space.}
\begin{enumerate}
\item We define our predicates:

  \begin{tabular}{ll}
  $D(x,y)$: &  \textit{Disk $x$ has more than $y$ kilobits free}. \\
$S(z)$: & \textit{The message $z$ can be saved}.
  \end{tabular}
\item Universe of discourse: $x$ is a disk, $y$ is an integer, $z$ is a message.

\item We can express the specification in the following way: $\exists x D(x,10) \rightarrow \exists z S(z)$.
\end{enumerate}
\item Next, Rosen 1.5:31 part d.\\
Express the negation of the following statement so that negation immediately precedes a predicate.
\[\forall x \exists y (P(x,y) \rightarrow Q(x,y))\]
\begin{tabular}{llr}
0. &  $\neg \forall x \exists y (P(x,y) \rightarrow Q(x,y))$ & Given\\
1. & $\equiv \exists x \forall y \neg(P(x,y) \rightarrow Q(x,y))$ & Move negation onward\\  
2. & $\equiv \exists x \forall y \neg(\neg P(x,y) \vee Q(x,y))$ & Implication rule\\
3. & $\equiv \exists x \forall y (P(x,y) \wedge \neg Q(x,y))$ & De Morgan's law
\end{tabular}\\
\mbox{}\hfill{Q.E.D.}

\item (Last 10 minutes) Give quiz

\end{itemize}

\end{document}
