\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}

%\makeslides

\renewcommand{\bar}[1]{\overline{#1}}

\begin{document}

\onlystudents
 
\lecture{notes1}{Proofs}{September 7, 2000}

\renewcommand{\thepage}{\arabic{page}}

\noindent
Topics for today:
\begin{itemize}
\item
Course overview
\item
What is a proof?
\item
Propositions
\item
Logical systems
\item
Proof examples 
\end{itemize}

\noindent
\reading{Velleman Chapter 1, Sections 3.1, 3.2. \\
Rosen 1.1, 1.2, 1.4, 1.6, 3.1}
\section{Course Overview}

\subsection{Introductions}

\forlecture{
6.042, Mathematics for Computer Science\.
Prerequisites: First year calculus\.
Introductions\.
Faculty, TAs, secy
}

\subsection{Course Goals and Content}

This course will cover:
\begin{description}
\item[Basic discrete math concepts.]
Basic data types and structures used in programming and in reasoning
about computer systems: \\
Numbers, Booleans, strings; sets, functions, relations; digraph, graphs,
trees; state machines\.
Their properties\.

\item[Proofs.]
How to do them, how to read them, how to recognize correct/incorrect ones\.
Reasoning about propositions, about predicates (with quantifiers)\.
Common proof strategies:  Direct proof, proof by contradiction, by cases...\.
Induction (very important in this course and elsewhere in CS)\.

\item[Mathematical foundations for programming.]
Basic concepts and methods underlying formal specification and verification
of software systems\.
Developing models for programs and their required behavior\.
Proving that a program model satisfies its correctness requirements.

\item[Analytic Tools.] 
The quantitative part of discrete math\.
Methods for handling series, sums, recurrences, asymptotic analysis, counting\.
The kind of math that tends to arise in computer science problems, e.g.,
analysis of algorithms.

\item[Discrete probability.]  
How to analyze random events\.
Probability provides good ways of modeling the unpredictability of the
  real world\.
Critical in the study of real computer systems.
\end{description}

Overall, we want you to learn how to use mathematics to help you think
about concepts in computer science:
\begin{itemize}
\item Define abstract models for computer science objects like programs,
computers, networks...
\item Think about these models carefully, correctly.
\item Use the conclusions to help understand the real-world objects.
\end{itemize}

\subsection{Administrivia}

\forlecture{
{\large \bf SIGN UP} {\tt http://bigred.lcs.mit.edu/6.042/}

\noindent
See Handout 1\.
Lectures, tutorials\.
Handouts\.
Books\.
Old lecture notes, Spring00, Fall97 \.
Exams\.
Problem sets\.
Collaboration policy\.
Grading
}

\section{What is a proof (and why should we care)?}

Rough definition:  A way of convincing people that a statement is true\.
But there are many ways to convince someone that a statement is true,
for example:
\begin{itemize}
\item
Experimental evidence, e.g., physics experiments to validate 
theories of General Relativity; medical experiments to
validate that rats that eat chemicals get cancer.
\item
Statistical sampling, e.g., Gallup polls to convince people that Bush will
be elected President.
\item
Citing a reputable authority, e.g., ``The professor said the answer
to the problem was...''.
\item
Acting confident, talking loudly, e.g., ``I'm sure my program works now.''
\item
Shifting the burden of proof to someone who disagrees with you,
e.g., ``I don't see why not.''
\end{itemize}
These are not proofs, at least, not in the mathematical sense\.
All of these methods can go wrong, for example:
\begin{itemize}
\item
Experiments can be contaminated or otherwise messed up.
\item
Statistics can be misleading, e.g., polled population could be
non-representative, or people could lie to the pollsters.
\item
Authorities can make mistakes, e.g., Intel said the original
Pentium chip worked fine.
\end{itemize}

Mathematics uses a particularly convincing way to argue that something is
true:
\begin{definition}
A {\em proof\/} is a formal verification of a {\em proposition\/} by a chain of
{\em logical deductions\/} starting from a base set of {\em axioms\/}.
\end{definition}
The important pieces of this definition are:
\begin{description}
\item[Formal language:] 
Need a precisely defined language for expressing everything.
\item[Proposition:] 
Statement in the language, e.g., what you want to prove. 
\item[Axioms:] 
Statements that you are assuming in your proof. 
\item[Logical deductions:] 
Getting a new truth from old ones, according to agreed-upon,
formal rules of deduction. 
\end{description}
In the rest of this lecture, I'll explain what these things are,
present basic proof methods, and give examples.

The main idea is to specify everything so precisely that everyone is
convinced\.  
Advantages: 
If people agree about assumptions and deduction rules, they must also
agree about conclusions\.
Also, even if we can't understand the entire argument at once, if we
believe each deductive step, we can be comfortable accepting the conclusions.

We will try to teach you how to read and write proofs\.
For CS students, the main purpose is so that you can use them to reason 
carefully about ideas that arise in your (and other people's) 
computer system designs/implementations.

\section{Basic data types}

%\reading{Velleman chapter 1, Rosen 1.1-1.6}
First, we need to agree on some basic language of discourse
so we can say things to each other.  
We'll be using the standard basic data types used in programming:
numbers, Booleans (true/false)\.
(Also later strings, but skip for now.)
We'll also use other basic data types from mathematics, such as sets and 
functions\. 
These are used in reasoning about programs\.  
This is review for most of you, so I won't lecture about it\.  
I'll just list the basic notions:  definitions, operations, some properties\.
You will be expected to read this material carefully on your own, making sure 
you can do all the study exercises.

\subsection{Booleans}

%\reading{Velleman 1.1--1.2, Rosen 1.1}
Values: 1 (true), 0 (false)\.
Operations: and ($\wedge$), or ($\vee$), not ($\neg$), exclusive-or
($\oplus$)\. 
\\
These operations can be explained with tables:
\\
\begin{tabular}{cc}
$x$ & $\neg x$ \\
\hline 
1   & 0 \\
0   & 1 \\
\end{tabular}
\\
\\
\begin{tabular}{ccccc}
  $x$ & $y$ & $x \wedge y$ & $x \vee y$ & $x \oplus y$ \\
\hline 
  1   & 1   & 1            & 1          & 0\\ 
  1   & 0   & 0            & 1          & 1\\
  0   & 1   & 0            & 1          & 1\\
  0   & 0   & 0            & 0          & 0\\
\end{tabular}

\subsection{Numbers}

%\reading{Rosen, Section 1.4}
These are just the standard number classes.
\begin{description}
\item[Natural numbers] $N = \{ 0, 1, 2, \ldots \}$ 

  Most math books actually let $N$ start at 1 rather than 0, but computer
  scientists like to start counting with 0\.  We'll stay consistent
  with the course texts and start with 0\.  
  We'll write $N^+$ for the positive naturals.

  Operations: $+$, $-$ (a partial function), times, integer division (round
  down), remainder (mod), exponentiation

  Prime number:  Natural number $\geq 2$ that has no divisors except for
  itself and $1$\.
  Example:  7 is prime, 14 is not.

\item[Integers,] denoted by $Z$: $N$ and its negatives 
\item[Rationals,] denoted by $Q$ 

  These are all numbers that are expressible as a ratio of two integers ${a
    \over b}$, where $b \neq 0$\.  A basic theorem (we might prove it
  later) says that we can write any rational number in lowest terms.
\item[Reals,] denoted by $R$
\end{description}

%\subsection{Strings}
%
%Strings are sequences of symbols drawn from some fixed alphabet\.  
%For example, if the alphabet consists of $a, b, c$, some examples of 
%strings are $abc$, $aaa$, $b$, and the empty string ($\lambda$, a shorthand 
%for no symbols)\.
%The main interesting operation is concatenation\. 
%Concatenating the two strings $abc$ and $bba$ gives the string $abcbba$.

\subsection{Sets}

%\reading{Velleman 1.3--1.4, Rosen  1.4--1.5}
Values: $\emptyset$, universal set $U$, singleton sets $\{ a \}$\.
Relationships:  Subset ($\subseteq$), proper subset ($\subset$)\.
Operations are:  Union ($\cup$), intersection ($\cap$), complement
(overbar)\.  

Venn diagrams are useful for reasoning about sets\.
There are many laws about how the operations behave---see Rosen p. 49\.
E.g.: $A \cup A = A$\.
%We'll come back to this later.

\subsection{Functions}

%\reading{Rosen, Section 1.6}
A function is a rule that assigns an element of one set (known as the range) 
to each element of another set (the domain)\.
Operations include function inverse and composition ($f \circ g(x) =
f(g(x))$)\.
We'll come back to this later.

\section{Propositions}

Now we consider the kinds of statements that we might want to convince people 
about\.

\subsection{What are propositions?}

\begin{definition}
A {\em proposition\/} is a statement that has a truth value,
$\ms{true}$ or $\ms{false}$. 
\end{definition}

Examples:
\begin{enumerate}
\item
$5$ is a prime number. 

This is a proposition, and it's true. 

\item
$8$ is a prime number. 

This is a false proposition.

\item
$x$ is a prime number. 

This is not a proposition\.
It has no truth value, because we don't know what $x$ is\.
It's said to be an {\em unbound variable}. 

\item 
There is an least one prime number.

  This is a true proposition\.  In math notation, it can be written as
  $\exists x (x \mbox{ is a prime})$\. The quantifier $\exists$
  ``binds'' $x$.

\item
All natural numbers $\geq 2$ are primes. 

This is a false proposition\.  It can be written as $\forall x \in N,
x \geq 2 (x \mbox{ is a prime})$\. The quantifier $\forall$ also binds $x$. 

We will revisit the quantifiers soon (they have their own reasoning
methods)\.  For now, we are just using them as shorthand notation for
the English phrases. 

\item
All $x$ of the form $n^2 + n + 41$, where $n \in N$, are prime. 

This is a proposition\.
Is it true or false?
That's not immediately obvious\. 
Certainly this proposition is true for many natural numbers $n$:

\[
\begin{array}{cc}
n = 0 \rightarrow 41 & (prime) \\
n = 1 \rightarrow 43 & (prime) \\
n = 2 \rightarrow 47 & (prime) \\
n = 3 \rightarrow 53 & (prime) \\
\ldots & (more\ primes) \\
n = 20 \rightarrow 461 & (prime) \\
\ldots & (still\ more\ primes) \\
n = 39 \rightarrow 1601 & (prime)
\end{array}
\]

However, if $n = 40$, then $n^2 + n + 41 = 40^2 + 40 + 41 = 41 \cdot 41$,
which is not prime\.  
Since it is not the case that the expression is prime {\em for all} $n$, 
the proposition is false!

\item 
``true'' and ``false'' are regarded as propositions, 
with the obvious truth values.

\item
$\forall A, B (\bar{A} \cup \bar{B} = \overline{A \cup B})$. 

Propositions can be about other things besides numbers, for instance, sets\.
This proposition happens to be false. 

\item
$\forall A, B (\bar{A} \cup \bar{B} = \bar{A \cap B})$. \\
$\forall A, B (\bar{A} \cap \bar{B} = \bar{A \cup B})$. 

These are called De Morgan's laws and are true.

\item
The original Pentium chip always divided correctly\.

Intel's ``proofs'' by authority and by sampling turned out to be
invalid\.  The proposition is false.

\item White can always win at chess.

A proposition whose truth value nobody knows.

\item Every even integer greater than 2 is the sum of two prime
  numbers.

  No one knows whether this proposition is true or false\.  This is
  the Goldbach Conjecture, which dates back to 1742\.  It was described
  in {\em The Boston Globe} as ``one of the great unsolved
  mysteries.'' 
  Unfortunately, the ``example'' they gave was $20=9+11$!

\item There is no $x, y, z \in N^+, n \geq 3$ such that $x^n + y^n =
  z^n$.

  This is Fermat's last theorem, which he stated in the 1640s\.  
  Although he claimed it, he never proved it\. 
  Only recently have we learned for sure that it's true\.  
  Andrew Wiles, in 1994, gave a 130-page proof\.  
  After months of work, other mathematicians found bugs\. 
  Wiles needed hundreds of more pages to fix them\.  
  But even while we didn't know if it was true or false, it
  was still a proposition.

\item $a^4+b^4+c^4=d^4$ has no positive integer solutions.

  This statement was conjectured by Euler (1769)\.  The first
  counterexample was found by Elkies, 218 years later\.  The smallest
  one: $95800^4+217519^4+414560^4=422481^4$.

\item Every map can be colored with four colors, in such a way that no two
  adjacent regions have the same color (Four-Color Theorem).

  This proposition was first ``proved'' in 1879\.  
  The ``proof'' stood for 10 years before a flaw was found\.  
  Recently, the theorem was proved with computer aid\.
  People still debate whether this is a valid proof\.  
  After all, nobody has proved that the computer is working correctly!
\end{enumerate}

Not all sentences are propositions:
     \begin{itemize}
     \item $x = y$.  (Truth depends on knowing what $x$ and $y$ are.)
     \item What time is it?
     \item This sentence is false.
     \end{itemize}

\subsection{Compound propositions and truth tables}

Logical connectives are used to combine simple propositions into compound
propositions\.
And ($\wedge$), or ($\vee$), exclusive-or ($\oplus$), and not ($\neg$),
which we already mentioned for Booleans, are also used for propositions\.  
Other connectives used for propositions include implication 
(if-then, $\implies$) and double implication 
(equivalence, $\Leftrightarrow$)\.  
These are very important in logical reasoning\.
The truth values of compound propositions are obtained from the truth
values of the simpler propositions according to the {\em truth tables\/}:

\begin{tabular}{cc}
$P$  & $\neg P$ \\
 \hline T  &   F \\
F  &   T \\
\end{tabular}

\noindent If a proposition $P$ is true, then its negation is false, and
vice versa.

\begin{tabular}{ccccc}
$P$  & $Q$ &    $P \wedge Q$ &  $P \vee Q$ & $P \oplus Q$ \\
\hline
T  &  T     &  T &             T   &        F\\
T  &  F    &   F  &            T  &         T\\
F  &  T   &    F   &           T &          T\\
F  &  F  &     F    &          F&           F\\
\end{tabular}

Important: $\vee$ means {\bf inclusive} or\.  
It is true if either \emph{or both} of the two statements are true\.  
Sometimes in English or is used to mean exclusive or: 
``Lynch or Dolev will teach today'' is saying one but not both.

\vspace{2ex}

\begin{tabular}{cccc}
$P$ & $Q$ &   $P \Rightarrow Q$ &  $P \Leftrightarrow Q$ \\
\hline
T&    T   &       T  &               T \\
T &   F  &        F   &              F \\
F  &  T &         T    &             F \\
F   & F&          T     &            T \\
\end{tabular}

The nice thing about these truth tables is that it doesn't matter what
the specific propositions are; we know how to get compound truth value
from basic truth values.

The only slightly mysterious column here is the implication column\.
We say that $P \Rightarrow Q$ is false only if the hypothesis $P$ is
true and the conclusion $Q$ is false\.  Some thought shows this aligns
with our intuition\.  Consider the statement ``if you do your
homework, then I will give you an A''\.  Under what circumstances
would you accuse me of lying\?  Well, I am clearly lying if you do
your homework but then you don't get an A\.  
But if you skip your
homework and I give you an A \emph{anyway,} you won't say I'm lying\.
Also, if you skip your homework the statement promises
nothing, so it is true regardless of what I do.

One way to determine truth values for compound propositions is by
adding new columns to the basic truth table(s).  Consider for example 
\[
R = (P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) 
\]
To decide the truth value of this messy proposition, we can evaluate
its sub-propositions in a truth table and then combine their evaluations to
evaluate the whole\.  This yields a column containing all T values\.  
That is, the expression is always true, regardless
of the truth values of $P$ and $Q$.

\begin{tabular}{ccccccc}
$P$  &$Q$  &  $P \Rightarrow Q$  & $\neg Q$&  $\neg P$ &  $\neg Q\Rightarrow\neg P$ & $R$ \\
\hline
T&    T   &       T &              F   &      F&        T &T\\
T &   F  &        F  &             T  &       F &       F &T\\
F  &  T &         T   &            F &        T  &      T &T\\
F   & F&          T    &           T&         T   &     T &T\\
\end{tabular}

An expression (like this one) whose column contains all T is called a
{\em tautology}.


\section{Logical Systems}

Now we can say what proofs are\.  
A proof takes {\bf axioms} and {\bf definitions} and
uses {\bf deduction rules}, step by step, to get a desired conclusion.

\subsection{Axioms}

\begin{defin*}
An {\em axiom} is a proposition that is assumed to be true.
\end{defin*}

Axioms aren't proved---just accepted as reasonable assumptions\.
``Axiom'' is Greek for ``to think worthy,'' not ``to be true''\.
Here are some examples:

\begin{axiom}[Arithmetic]
If $a = b$ and $b = c$, then $a = c$.
\end{axiom}

This seems very reasonable!\\
But sometimes the right choice of axiom is not clear. 

\begin{axiom}[Euclidean geometry]
Given a line $l$ and a point $p$ not on $l$, there is exactly one line
through $p$ parallel to $l$.
\end{axiom}

\begin{axiom}[Spherical geometry]
Given a line $l$ and a point $p$ not on $l$, there is {\em no} line
through $p$ parallel to $l$.
\end{axiom}

\begin{axiom}[Hyperbolic geometry]
Given a line $l$ and a point $p$ not on $l$, there are {\em infinitely
many} lines through $p$ parallel to $l$.
\end{axiom}
None of the three preceding axioms is better than the others; all
yield equally good proofs\.  Of course, a different choice of axioms
makes different propositions true\.  In fact, the axioms above are
mutually contradictory---they can't all be true\.  

Mathematicians still argue about which axioms are ``right,'' e.g.,
there is a lot of debate about the Axiom of Choice (whose assertion
and denial are equally consistent with other commonly agreed upon
axioms).

Axioms provide us with a place to start in building proofs\.
Every argument has assumptions\.  
To be rigorous, it is important to state those assumptions explicitly as 
axioms. 

%In the real world axioms capture our beliefs about what we are
%studying (e.g. Newton's mechanics)\. Definitions capture what we think
%is important (e.g. force, velocity)\.  If we prove something with those
%axioms, we tend to believe it about the real world\.  If the real
%world turns out different, we need to change our axioms (Einstein made
%us discard Newton's axioms).

\subsection{Definitions}

Definitions are used to agree on what something means.
\begin{itemize}
\item A natural number $\geq 2$ is prime if it has no divisors other than 
itself and 1.
\item A divisor of an integer $z$ is a nonzero integer $d$
for which there exists some integer $k$ such that $n = k d$.
\item A triangle is a polygon with 3 sides.
\end{itemize}
Definitions are axiomatic: we can define terms to mean whatever we want, 
so long as we do so unambiguously\. 
Definitions can be built from prior definitions.

\subsection{Deduction Rules}

These are also called inference rules\.  They are rules for combining
axioms and true propositions to construct more true propositions\.
The most fundamental inference rule is called {\em modus ponens}\.  
\begin{enumerate}
\item Modus ponens: \\
Given that $P$ and $P \Rightarrow Q$ are both true \\
Conclude:  $Q$ 

\item Modus tolens (proof by contradiction): \\
Given:  $P \Rightarrow Q$, $\neg Q$ \\
Conclude: $\neg P$ 

\item Syllogism: \\
Given:  $P \Rightarrow Q$, $Q \Rightarrow R$ \\
Conclude:  $P \Rightarrow R$ 

\item Given:  $\neg P \Rightarrow \ms{false}$ \\
Conclude:  $P$ 

\item Given: $P$, $\neg P$: \\
Conclude: $\ms{false}$ 

\item (Cases): \\
Given: $Q \Rightarrow P$, $\neg Q \Rightarrow P$ \\
Conclude: $P$
\end{enumerate}

These deduction rules rely only on the truth values of the statements 
$P,Q,R$, and \emph{not} on what the particular statements are\.  So we can 
apply them in many situations.

Truth tables provide a source of deduction rules, all of which are
accepted in mathematics\.
Namely, if $R \Rightarrow S$ is a tautology, then \\
Given: $R$ \\
Conclude: $S$ \\
is an allowable inference rule\.

\noindent
Examples: 
\begin{enumerate}
\item
$[P \wedge (P \Rightarrow Q)] \Rightarrow Q$ 
is a tautology (check in truth table), which leads to (Modus Ponens): \\
Given: $P \wedge (P \Rightarrow Q)$ \\
Conclude: $Q$ 

\item
$(P \wedge \neg P) \Rightarrow \ms{false}$ is a tautology, which leads to: \\
Given: $P$, $\neg P$: \\
Conclude: $\ms{false}$ 

\item
$[(P \vee Q) \wedge \neg P] \implies Q$
is a tautology, which leads to (Disjunctive Syllogism): \\
Given: $P \vee Q$, $\neg P$ \\ 
Conclude: $Q$ 
\end{enumerate}

Another way of getting acceptable deduction rules from a truth table,
exemplified using Modus Ponens again: \\
In the truth table, look at the rows where $P$ and $P \Rightarrow Q$ 
are both true\.
$P$ is true in rows 1, 2 \.
$Q$ is true in rows 1, 3, 4 \.
So, both are true exactly in row 1\.
But in that row, $Q$ is also true. 

\subsection{Formal proofs}

In a complete, formal proof of a theorem, each step follows from
previous steps using formal deduction rules\.  
Such a process is ideally so systematic that it could be checked mechanically 
by a program\.
Theorem proving programs can do this.

What about using a computer to {\em produce\/} proofs of true theorems
automatically? \\
Hilbert posed (as one is his 23 famous problems) the problem of finding 
a method that could generate all proofs of true theorems\.
One of the great accomplishments of 20th century math is the proof that no 
such method exists (G\"odel)\.  
So we will always rely on human intuition to find the proofs, although
computers can be used to check that they are right. 

Mathematicians don't actually write proofs that formally and completely:
they leave a lot of gaps that they expect a ``knowledgeable reader''
can fill in. 

\section{Proof examples}

%\reading{Velleman Chapter 3, Rosen, Section 3.1}
This section contains some examples of proofs using the deduction rules
described above\.
They are presented at about the level of detail commonly used by 
mathematicians\.
The examples illustrate basic methods: 
direct proof, proof by contradiction, and proof by cases\.  

These proofs are written in a stylized way, using statements and
reasons (as in high school geometry proofs)\.  
In math books, proofs are usually presented in prose, with the 
logical structure left implicit\.
Caution: 
The proof writer is expecting the reader to figure out the logical
structure\.
To understand the proofs, you really have to do this. 
%It should always be possible to rewrite any of these proofs in
%structured form (given enough time)\.

\subsection{Direct proof}

To prove that a proposition of the form $P \Rightarrow Q$ is true, it
is enough to assume $P$ and show $Q$\.  Written in a structured style,
the pattern of such a proof is:
\begin{structproof}
Prove:  $P \Rightarrow Q$ \\
1. Assume $P$. \\
2. $Q$ \\
3. QED 
\> \> \> \> \> Implication \\
\end{structproof}
QED stands for Quod Erat Demonstrandum, Latin for ``which was to be
proved''\.  Here, it's a shorthand for writing the goal out again as
the final step\.

\begin{example} 
  Let's prove that the sum of the first 100 numbers, $1 + ... + 100$,
  is 5050\.
  We'll rewrite this as an implication and use the direct proof rule
  above.

\begin{proofoverhead}
Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
1. Assume  $S = 1 + ... + 100$. \\
2. $S = 5050$ 
\> \> \> \> \> ??? \\
3. QED  (That is, $S = 1 + ... + 100 \Rightarrow S = 5050$.) 
\> \> \> \> \> Implication 
\end{proofoverhead}

Of course, the interesting part is to fill in the ???\.  This needs
some calculations:

\begin{proofoverhead}
Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
1. Assume  $S = 1 + ... + 100$. \\
2. $S = 5050$ \\
\> 1. $S = 100 + 99 +...+ 1$  
   \> \> \> \> Commutativity of addition \\
\> 2. $2S = 101 + 101 + ... + 101$  (100 terms) 
   \> \> \> \> Add term-by-term \\
\> 3. $2S = 10,100$           
   \> \> \> \> Add the terms up \\
\> 4. QED  (That is, $S = 5050$.) 
   \> \> \> \> Divide by 2 \\
3. QED ($S = 1 + ... + 100 \Rightarrow S = 5050$.) 
\> \> \> \> \> Implication 
\end{proofoverhead}
\end{example}

\begin{example}
The following argument shows a property of basic set theory\.
It says that, if an element $x$ is in the complements of sets $A$ and
$B$, then it is in the complement of their union\.
Like the previous proof, this one involves a direct, step-by-step
calculation.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A \cup  B}$ \\
1. Assume $x \in \bar{A} \cap \bar{B}$ \\
2. $x \in \bar{A}$, $x \in \bar{B}$ 
\> \> \> \> \> Definition of intersection \\
3. $x \notin A$, $x \notin B$ 
\> \> \> \> \> Definition of complement \\
4. $x \notin A \cup B$ 
\> \> \> \>  \> Definition of union \\
5. $x \in \overline{A \cup  B}$  
\> \> \> \> \> Definition of complement \\
6. QED ($x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A \cup  B}$) 
\> \> \> \> \> Implication 
\end{tabbing}
\end{example}

\subsection{Proof by contradiction}

To prove that a proposition $P$ is true, it is enough to prove that 
$\neg P \Rightarrow \ms{false}$\. The pattern is: 
\begin{structproof}
Prove:  $P$ \\
1. $\neg P \Rightarrow \ms{false}$ \\
2. QED   
\> \> \> \> \> Contradiction
\end{structproof}

\noindent
Some variants of this:

\begin{structproof}
Prove: $P$ \\
1. $\neg P \Rightarrow (Q \wedge \neg Q)$ \\
2. QED 
\> \> \> \> \> Contradiction \\
\\
\\
Prove: $P$ \\
1. $\neg P \Rightarrow Q$ \\
2. $\neg Q$ \\
3. QED       
\> \> \> \> \> Contradiction \\
\end{structproof}

\begin{example}
\mbox{}
\begin{structproof}
Assume: If Richard gets at least four hours of sleep then he passes his 
6042 final. \\
Richard fails his 6042 final. \\
Prove: Richard gets less than four hours of sleep.
\end{structproof}

\noindent
Here, let $P= \mbox{``Richard gets less than four hours sleep.''}$\.
$Q= \mbox{``Richard passes.''}$. So the proof steps for proving $P$ are:

\begin{structproof}
Prove: Richard gets less than four hours of sleep. \\
1. If Richard gets at least four hours of sleep then he passes. 
   ($\neg P \Rightarrow Q$). \\
\> \> \> \> \> Assumed \\
2. Richard fails ($\neg Q$). 
\> \> \> \> \> Assumed \\
3. QED (Richard gets less than four hours of sleep.) 
\> \> \> \> \> Contradiction 
\end{structproof}
\end{example}

\begin{example}
A more interesting proof by contradiction\.
\begin{structproof}
Prove: $\sqrt{2}$ is irrational.\\
1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
2. QED 
\> \> \> \> \> Contradiction. 
\end{structproof}
Assume it's rational, play with the definitions, and try to get a
contradiction. 

\begin{proofoverhead}
Prove: $\sqrt{2}$ is irrational. \\
1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
\> 1. Assume $\sqrt{2}$ rational. \\
\> 2. $\ms{false}$ \\
\> \> 1. Choose $a, b \in N^{+}$, $\sqrt{2} = \frac{a}{b}$, lowest terms.
      \> \> \> Basic property of rationals. \\
\> \> 2. $2 b^2 = a^2$       
      \> \> \> Algebra \\
\> \> 3. $a^2$ is even.
      \> \> \> Definition of ``even'' \\
\> \> 4. $a$ is even. \\   
\> \> 5. Choose $c \in N$, $a = 2c$. \\
\> \> 6. $4 c^2 = a^2 = 2b^2$ 
      \> \> \> Algebra \\
\> \> 7. $2 c^2 = b^2$       
      \> \> \> Algebra \\
\> \> 8. $b^2$ is even.
      \> \> \> Definition of ``even'' \\
\> \> 9. $b$ is even. \\
\> \> 10. $a$ and $b$ aren't in lowest terms. 
      \> \> \> 1.2.4, 1.2.9 \\
\> \> 11. QED ($\ms{false}$) 
      \> \> \> 1.2.1, 1.2.10, propositional logic \\
\> 3.  QED ($\sqrt{2}$ rational $\Rightarrow \ms{false}$) 
   \> \> \> \> Implication \\
2. QED  ($\sqrt{2}$ is irrational) 
\> \> \> \> \> Contradiction
\end{proofoverhead}

Some steps aren't justified here: 
\begin{itemize}
\item
Showing that $a$ and $b$ are even, because we know their squares
are even.
\item
Some other points involving quantifier logic.
\end{itemize}
We may revisit this next week to fill in the gaps.
\end{example}

\subsection{Proof by cases}

To prove that a proposition $P$ is true, it is enough to prove that
$Q$ and $\neg Q$ both imply $P$, where $Q$ is any other proposition\.
This shows $P$ is true in either case, so it's always true.

\begin{structproof}
Prove: $P$ \\
1. $Q \Rightarrow P$ \\
2. $\neg Q \Rightarrow P$ \\
3. QED                     
\> \> \> \> \> Cases 
\end{structproof}

\noindent This generalizes to any number of
predicates, provided that together they cover all possibilities\.  If
$Q_1 \vee Q_2 \vee \ldots \vee Q_k$ is always true, and you can show
each $Q_i$ implies $P$, then you can infer $P$.
\begin{example}
\mbox{}
\begin{structproof}
Assume: $d =$ Susan's birth date (day of month, 1-31). \\
Prove: $d^2 + d$ is even. \\
1. $d = 1 \Rightarrow d^2 + d = 2 \mbox{ is even}$. \\
2. $d = 2 \Rightarrow d^2 + d = 6 \mbox{ is even}$. \\
3. $\ldots$ \\
31. $d = 31 \Rightarrow d^2 + d=992 \mbox{ is even}$. \\
32. QED ($d^2 + d$ is even.)
\> \> \> \> \> Cases 
\end{structproof}
More clever proofs than this one might consider fewer cases\.
For example, can we just consider whether $d$ is even or odd?
\end{example}

\begin{example}
This example combines an argument by contradiction and an
argument by cases\.
\begin{structproof}
Prove:  There are infinitely many prime numbers. \\
1. Assume there are only finitely many prime numbers. \\
2. $\ms{false}$ \\
\> 1. Choose $P$ to be the finite set of all prime numbers, and define 
$m$ to be $1 + \Pi_{p \in P} p$. \\
\> 2. $m$ isn't in $P$. 
   \> \> \> \> It's larger than all the elements of $P$. \\
\> 3. $m$ isn't divisible by anything in $P$. 
   \> \> \> \> Remainder is $1$ for any such division. \\
\> 4. There is some prime that isn't in $P$. \\
\> \> 1. If $m$ is prime then there is some prime that isn't in $P$. \\
\> \> \> \> \> $m$ is an example. \\
\> \> 2. If $m$ is not prime then there is some prime that isn't in $P$. \\
\> \> \> 1. Assume $m$ is not prime. \\
\> \> \> 2. $m$ has a prime divisor. 
         \> \> Number theory fact \\
\> \> \> 3. Choose $q$ to be a prime divisor of $m$. \\
\> \> \> 4. $q$ isn't in $P$ 
         \> \> $m$ is divisible by $q$, but not by any $p \in P$. \\
\> \> \> 5. There is some prime that isn't in $P$. \\
\> \> \> 6. QED 
         \> \> Implication \\
\> \> 3. QED (There is some prime that isn't in $P$.) \\
\> \> \> \> \> Cases \\
\> 3. QED ($\ms{false}$) \\
3. QED (Infinitely many primes)
\> \> \> \> \> Contradiction
\end{structproof}
We may prove the missing number theory fact later in the course\.
Again, some arguments about quantifiers are made informally, so we may
want to return to these after we study quantifier logic.
\end{example}

\section{Good proofs}

Some features of good proofs:
\begin{itemize}
\item
They must be {\em correct\/}.
\item
They should be clear and understandable.
\item
They should have nice structure: 
They should be broken up into pieces that
prove key intermediate properties (lemmas)\.
(This makes them easier to understand, and possibly reusable.) 
\item
They should be written fairly generally and abstractly, so they apply to
many cases. 
\item
Don't leave gaps, saying something is obvious when it isn't.
\item
Elegant, economical,...
\end{itemize}
Notice that many of these are also features that we look for in 
good programs.
\end{document}

Names to use:
Sonia, BB, Stacy, Ramona,
Joel, Gretchen, Dirk, Greg,
Jenna, Gervase, Colleen, Sean,
Susan, Rudy, Kelly, Richard


Proof handouts?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Coverage:

Tell them what proofs are (propositions, axioms, deduction rules...).
Point them to the basic data types (Booleans, numbers, sets, functions)
Propositional logic, truth tables.
Examples:  Direct, contradiction, cases.

Classification:

Basic discrete math concepts:
  Booleans, numbers, strings, sets, functions, 
Proofs:
  Know what they are
  Propositions, truth tables.
  Propositional logic proofs:  direct, contradiction, cases.
Math foundations for programming
Analytic tools
Discrete probability

