225d224
< \section{Proof Techniques}
227,413c226,228
< \subsection{Vocabulary}
< 
< \noindent
< function
< 
< \noindent
< predicate
< 
< \noindent
< tautology
< 
< \noindent
< contradiction
< 
< \noindent
< satisfiable
< 
< \vskip 2in
< 
< \subsection{Boolean as an ordered type}
< 
< \noindent
< $0 $ false
< 
< \noindent
< $1 $ true
< 
< \noindent
< $0 < 1$
< 
< \noindent
< $\le$ implies
< 
< \noindent
< $\ge$ if
< 
< \noindent
< ``if $x\ge 2$ then $x^2\ge 4$'' can be rewritten as
< ``$\parend{x\ge 2}\le\parend{x^2\ge 4}$''
< 
< \subsection{Quantifiers}
< 
< 
< \noindent
< $\exists$
< 
< \noindent
< $\forall$
< 
< \noindent
< $\max$
< 
< \noindent
< $\min$
< 
< \noindent
< $\max$ is a generalization of $\exists$, and
< $\min$ is a generalization of $\forall$.
< 
< \eject
< 
< \section{Proving statements involving quantifiers}
< 
< \noindent
< $P$ is a predicate on a set $X$, and $F:X\to\reals$.
< 
< \noindent
< To prove $\exists(x\in X)P(x)$, must find some $a\in X$ for which
< $P(a)$
< 
< \noindent
< To prove $\forall(x\in X)P(x)$, must show that $P(a)$ for all $a\in X$.
< 
< \noindent
< To prove $\max_{x\in X}F(x)=K$, must show
< \begin{eqnarray*}
< \forall(x\in X)\braced{F(x)\le K}\\
< \exists(x\in X)\braced{F(x)\ge K}
< \end{eqnarray*}
< 
< \noindent
< To prove $\min_{x\in X}F(x)=K$, must show
< 
< \vskip 1in
< 
< \noindent
< To prove $\max_{x\in X}F(x)\le K$, must show
< \begin{eqnarray*}
< \forall(x\in X)\braced{F(x)\le K}\\
< \end{eqnarray*}
< 
< \vskip 1in
< 
< \noindent
< To prove $\max_{x\in X}F(x)\ge K$, must show
< \begin{eqnarray*}
< \exists(x\in X)\braced{F(x)\ge K}\\
< \end{eqnarray*}
< \noindent
< Example: prove that
< $\forall(x\ge 0)\braced{\max\braced{x^2-1,0}\ge x-1}$
< 
< \noindent
< Break into cases.
< 
< \vskip 2in
< \noindent
< 
< \eject
< \section{Adversarial Proofs of Statements involving Quantifiers}
< 
< Suppose $F,G,H:X\to\reals$.  Prove that
< \begin{eqnarray*}
< \max_{x\in X}\braced{F(x)-H(x)}\le
< \max_{x\in X}\braced{F(x)-G(x)}
< +\max_{x\in X}\braced{G(x)-H(x)}
< \end{eqnarray*}
< 
< Step 1 of proof: allow expansion of scopes by using unique variable names.
< 
< \vskip 1in
< 
< Step 2 of proof: Allow the adversary to make an arbitrary choice of the
< ``adversarial'' variables.
< 
< \vskip 1in
< 
< Step 3 of proof: We choose ``our'' variables, using the adversarial
< variables as needed.
< 
< \vskip 1in
< 
< Steps 2 and 3 can be repeated any number of times.  (But not in this simple
< example.)
< 
< \vskip 0.2in
< 
< Step 4.  Verify.
< 
< \vskip 1in
< 
< \eject
< \section{Nested Quantifiers}
< 
< \noindent
< ``Some people can't understand any statement with two quantifiers in it.''
< 
< \noindent
< ``What?''
< 
< \noindent
< ``See what I mean?''
< 
< \noindent
< Prove that
< \begin{eqnarray*}
< \max_{x\in X}\min_{y\in Y} F(x,y) \le
< \min_{y\in Y} \max_{x\in X} F(x,y)
< \end{eqnarray*}
< \eject
< \section{Dynamic Programming}
< 
< 
< %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
< \begin{figure}[htb]
< \centerline{\epsfig{file=dungeon.eps,width=8in}}
< \caption{The Layered Dungeon Problem}
< \label{fig: dungeon}
< \end{figure}
< %%%%%%%%%%%%%%%%%%%%%%
< 
< 
< The greedy strategy yields a treasure of 6, while the optimal path
< yields a treasure of 9.
< 
< \vskip 2in
< 
< \section{An Online Problem}
< 
< %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
< \begin{figure}[htb]
< \centerline{\epsfig{file=dydungeon.eps,height=3in}}
< \caption{The Online Layered Dungeon Problem}
< \label{fig: dydungeon}
< \end{figure}
< %%%%%%%%%%%%%%%%%%%%%%
< 
---
> This document should be completed by Friday, September 3.  It will be a
> ``retroactive'' handout this time, \ie, it will consist of material
> to support the lecture I give today (September 2).
