
\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{description}
\item[Experimental evidence], e.g., physics experiments to validate 
  theories of General Relativity; medical experiments to
  validate that rats that eat sugar get cancer.
\item[Statistical sampling] e.g., Gallup polls to convince people that
  Bush will be elected President.
\item[Citing a reputable authority.]  ``The professor/boss said
  the answer to the problem was...''.
\item[Religion,] the most reputable authority of all.
\item[Acting confident, talking loudly.] ``I'm sure my program
  works now.'' 
\item[I don't see why not.] Shifting the burden of proof to someone
  who disagrees with you. 
\item[Legal system.] Uses ``proof beyond a reasonable
  doubt''---convince a judge and jury
\end{description}

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. Consider Florida election!
\item Authorities can make mistakes, e.g., Intel said the original
  Pentium chip worked fine.
\item Juries can be fooled.
\end{itemize}
General problem: methods don't convince everyone.

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\.  If people accept the assumptions and deduction rules,
they must also accept the 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\.  This is a
philosophical position, and thus debatable, but most of modern
civilization accepts it.

We will try to teach you how to read and write proofs\.  By learning
to read and do proofs, you will be able to
\begin{itemize}
\item Convince others
\item Find flaws in others' attempts to convince you
\item Find flaws in your own proofs, so can figure out what else you
  need to find out or assume
\end{itemize}

Proofs are like programs, so you also develop the ability to reason
carefully about, attack, and defend ideas that arise in your (and
other people's) computer system designs and implementations.
