\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}

\title{Week 4 Recitation}
\author{Robert Woodward}

\begin{document}
\maketitle

\begin{itemize}
\item (3 min max) Go over quiz from last week
\item (3 min max) Go over homework from last week.
\item Questions about lecture / homework so far?

\item Guidance for making proofs using equivalence rules:
\begin{enumerate}
\item
Write the equivalence to prove.
\item Start from either the LHS (left hand-side) or the RHS, whichever
  you are more comfortable with or whichever seems more complex (so
  you can simplify it).

\item
Put a number on each step starting from zero.

\item Make sure to put the equivalence sign between a step and the
  next to clarify the meaning of the transition.

\item Justify each transition with the name of the equivalence law
  that you have applied.

\item Further, most of the time, you want to proceed through the
  following sequence of operations, some of them may be ommitted:
  Remove biconditionals, remove implications, push negation inwards
  (applying DeMorgan laws or double negation), apply distribution
  laws.  Then, you may have to use commutativity or associativity
  before reconfiguring what you have so far in the format of the
  `goal' expression.  The best method is {\em practice}.

\end{enumerate}

\item Rosen 1.2:19  \\
Show that $\lnot p \leftrightarrow q$ $\equiv$ $p \leftrightarrow \lnot q$ \\
\begin{tabular}{lll}\\
{\bf Step} & {\bf Sentence} & {\bf Equivalence law} \\
0 & $\lnot p \leftrightarrow q$ & \\
1 & $ \equiv (\lnot p \rightarrow q) \land (q \rightarrow \lnot p)$ & Biconditional law\\
2 & $\equiv (p \lor q) \land (\lnot q \lor \lnot p)$ & Implication law\\
3 & $\equiv (q \lor p) \land (\lnot p \lor \lnot q)$ & Commutative law\\
4 & $\equiv (\lnot q \rightarrow p) \land (p \rightarrow \lnot q)$ & Implication \\
5 & $\equiv p \leftrightarrow \lnot q$ & Biconditional law.
\end{tabular}
\newpage

Notice that, above, we used the implication rule.  Using the
contrapositive is also an option:\\
\begin{tabular}{lll}\\
{\bf Step} & {\bf Sentence} & {\bf Equivalence law} \\
0 & $\lnot p \leftrightarrow q$ & \\
1 & $ \equiv (\lnot p \rightarrow q) \land (q \rightarrow \lnot p)$ & Biconditional law\\
2 & $ \equiv (\lnot q \rightarrow \lnot\lnot p) \land (\lnot\lnot p \rightarrow \lnot q)$ & Contrapositive on both conjuncts.\\
3 & $ \equiv (\lnot q \rightarrow p) \land (p \rightarrow \lnot q)$ & Double negation, applied twice.\\
4 & $\equiv p \leftrightarrow \lnot q$ & Biconditional law.
\end{tabular}

The proofs are quite similar because $(p \rightarrow q) \equiv (\lnot q \rightarrow \lnot p) \equiv (\lnot p \lor q).$

\item 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 Predicates and their meaning: 
\begin{itemize}
\item
$Fools(x,y,t)$: $x$ fools $y$ at time $t$
\item
$P(x)$: $x$ is a politician
\end{itemize}
\item 
Universe of discourse: $x,y$ all human beings, $t$ all time instants
\item 
$\forall x [P(x) \rightarrow [(\exists y \forall t Fools(x,y,t)) \land
(\exists t \forall y Fools(x,y,t)) \land \neg (\forall y \forall t
Fools(x,y,t))]]$
\end{enumerate}

The expression $\neg (\forall y \forall t Fools(x,y,t))$ can be
difficult to spell out in English.  We recommand that you use the
expression ``{\em 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 a 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 $x$ fools every
  $y$ at every time $t$.
\item
$\forall x [P(x) \rightarrow (\forall y \forall t \neg Fools(x,y,t))]$:
Politicians do not ever fool anyone.
\end{itemize}
\end{itemize}

\item 
Every student enrolled in CSE235 knows \LaTeX\ but only some students
use \LaTeX\ in their homework. 
\begin{enumerate}
	\item Predicates and their meaning:
\begin{itemize}
\item
$Enrolled(x,y)$: $x$ is enrolled in class $y$.
\item
$WritesHomework(x,y,z)$: $x$ writes homework for $y$ in $z$.
\item
$Knows(x,y)$: $x$ knows language $y$,
\end{itemize}  

\item 
Universe of discourse: all students, classes, languages

\item 

$(\forall x Enrolled(x,CSE235) \rightarrow (Knows(x,$\LaTeX$))) \land $\\
$(\exists x Enrolled(x,CSE235) \land WritesHomework(x,CSE235,$\LaTeX$))$
\end{enumerate}
\item 
Every student enrolled in CSE235 knows \LaTeX\ but only some students
use \LaTeX\ in their homework. However, every student in CSE310 uses
\LaTeX\ in his/her homework.
\begin{enumerate}
\item
Predicates and their meaning: Use the same as above

\item
Universe of discourse: Same as above

\item
$(\forall x Enrolled(x, CSE235) \rightarrow (Knows(x,$\LaTeX$))) \land $\\
$(\exists x Enrolled(x,CSE235) \land WritesHomework(x,CSE235,$\LaTeX$)) \land$\\
$(\forall x Enrolled(x,CSE310) \rightarrow (WritesHomework(x,CSE310,$\LaTeX$))$
\end{enumerate}
\item 
Every student enrolled in CSE235 knows some language because they took a course about it
\begin{enumerate}
	\item Predicates and their meaning:

\begin{itemize}
\item
$Enrolled(x,y)$: $x$ is enrolled in class $y$
\item
$Knows(x,y)$: $x$ knows language $y$,
\item
 $TC(x,y)$: $x$ took course about language $y$
\end{itemize} 
	\item 
Universe of discourse: $x$ all students, $y$ all languages
	\item
$\forall x \exists y Enrolled(x, CSE235) \rightarrow (Knows(x, y) \land TC(x,y))$
\end{enumerate}

\item Rosen 1.2:21 \\
Show that $\lnot (p \leftrightarrow q)$ $\equiv$ $\lnot p \leftrightarrow q$ \\
\begin{tabular}{lll}\\
{\bf Step} & {\bf Sentence} & {\bf Equivalence law} \\
0. & $\lnot (p \leftrightarrow q)$ \\
1. & $ \equiv \lnot ((p \rightarrow q) \land (q \rightarrow p))$ & Biconditional law \\
2. & $ \equiv \lnot ((\lnot p \lor q) \land (\lnot q \lor p))$ & Implication law\\
3. & $ \equiv \lnot ((\lnot p \land \lnot q) \lor (\lnot p \land p) \lor (q \land \lnot q) \lor (q \land p))$ & Distributive law \\
4. & $ \equiv \lnot ((\lnot p \land \lnot q) \lor (q \land p))$ & Identity law\\
5. & $ \equiv (p \lor q) \land (\lnot q \lor \lnot p)$ & DeMorgan's law\\
6. & $ \equiv (\lnot p \rightarrow q) \land (q \rightarrow \lnot p)$ & Implication law\\
7. & $ \equiv \lnot p \leftrightarrow q$ & Biconditonal law \\
\end{tabular}

\item Rosen 1.2: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 Rosen 1.2: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 (Last 10 minutes) Give quiz

\end{itemize}

\end{document}
