% !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 4}
\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 Go over quiz from last week (max of 3 mins).

\item Go over last week's homework (max of 3 mins).

\item Let's start by looking at section 1.3, problem 63 on page 36 of your Rosen textbook: "Show how the solution of a given 4X4 Sudoku puzzle can be solved by solving a satisfiability problem (SAT).

\begin{enumerate}
\item First, let's construct the predicate $P(x,y,n)$, which means row $x$, column $y$ contains integer $n$.
\item Since we are talking about 4x4 Sudoku puzzles, we have 4x4x4 = 64 total propositions. 
\item Our goal is to find a truth assignment to each of these 64 propositions that solves the Sudoku. To do this, we need to make a few assertions:
\begin{itemize}
\item For each cell with a given value, we assert $P(x,y,n)$ when the cell in row $x$ and column $y$ has value $n$.
\item We assert that every row contains every number: $\bigwedge_{x = 1}^{4}\bigwedge_{n = 1}^{4}\bigvee_{y = 1}^{4} P(x,y,n)$.
\item We assert that every row contains every number: $\bigwedge_{y = 1}^{4}\bigwedge_{n = 1}^{4}\bigvee_{x = 1}^{4} P(x,y,n)$.
\item We assert that each of the 2x2 blocks contains every number:\\ $\bigwedge_{r = 0}^{2}\bigwedge_{s = 0}^{2}\bigwedge_{n = 1}^{4}\bigvee_{x = 1}^{2}\bigvee_{y = 1}^{2} P(2r+x,2s+y,n)$
\item We assert that no cell contains more than one number. To do this, we take the conjunction of all values of $x$,$y$,$n$, and $n\prime$ for 1 to 4, where $n \neq n\prime$, of $P(x,y,n) \rightarrow \neg P(x,y,n\prime)$.
\end{itemize}
\item Now to construct the assertion that row $x$ contains every number $n$: $\bigvee_{y = 1}^{4} P(x,y,n)$.
\item To construct the assertion that all rows contain every number $n$: $\bigwedge_{n = 1}^{4}\bigvee_{y = 1}^{4} P(x,y,n)$.
\item Building on that to include every column: $\bigwedge_{x = 1}^{4}\bigwedge_{n = 1}^{4}\bigvee_{y = 1}^{4} P(x,y,n)$
\end{enumerate}
\begin{itemize}
\item What is an example of a term from this SAT instance? \textbf{$P(1,3,2)$}
\item What is an example of a literal from this SAT instance? \textbf{$P(1,3,2) or \neg P(1,3,2)$}
\item What is an example of a clause? \textbf{($P(1,1,1) \vee P(1,2,1) \vee(P(1,3,1) \vee P(1,4,1)$)} 
\begin{itemize}
\item Notice that this clause says that at least one column contains the number 1.
\end{itemize}
\end{itemize}

\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$ fool $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)) \wedge (\exists t \forall y Fools(x,y,t)) \wedge \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 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 $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 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.
\begin{enumerate}
\item First, do we think they are equivalent? \textbf{No}.
\item Let $P(x)$ be a proposition that is sometimes true and sometimes false. Then let $Q(x)$ be some proposition that is always false. For example let $P(x)$ be $x$ is greater than 5,000, and $Q(x)$ be $x$ is less than zero. And let our universe of discourse be all integers greater than or equal to zero.
\item $\forall x (P(x) \rightarrow Q(x))$ is false and $\forall x P(x) \rightarrow \forall x Q(x)$ is false.
\begin{itemize}
\item Notice this is because $\forall x (P(x)$ can be false, and $\forall Q(x))$ is always false. So $\forall x (P(x) \rightarrow Q(x))$ is not going to be true, because for some $x$, $P(x)$ is true, so $P(x) \rightarrow Q(x)$ is sometimes false. Therefore the entire statement is false.
\item Whereas  $\forall x P(x) \rightarrow \forall x Q(x)$ is true because both $\forall x P(x)$ and $\forall x Q(x)$ are false.
\end{itemize}
\end{enumerate}
\item Now let's look at Rosen 1.4:41 part a. Express the following using predicates, quantifiers and logical connectives:
\begin{itemize}
\item\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.}
\end{itemize}
\begin{enumerate}
\item First let $D(x,y)$ be the statement \textit{Disk $x$ has more than $y$ kilobits free}. Let $S(x)$ be the statement \textit{The message $x$ can be saved.}

\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.
\begin{itemize}
\item $\forall x \exists y (P(x,y) \rightarrow Q(x,y))$
\begin{enumerate}
\item First negate: $\neg \forall x \exists y (P(x,y) \rightarrow Q(x,y))$
\item Move the negation inside quantifiers: $\exists x \forall y \neg(P(x,y) \rightarrow Q(x,y))$
\item Next get rid of the implication: $\exists x \forall y \neg(\neg P(x,y) \vee Q(x,y))$
\item Now distribute the negation through the parentheses:
\begin{displaymath}
\exists x \forall y (P(x,y) \wedge \neg Q(x,y))
\end{displaymath}
\end{enumerate}
\item Done!
\end{itemize}
\pagebreak

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

\end{itemize}

\end{document}
