\documentstyle[11pt]{article}

\setlength{\textheight}{9in}
\setlength{\textwidth}{6in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0.3in}
\newtheorem{theorem}{Theorem}[section]
\newenvironment{proof}{\par\noindent{\bf Proof:}}{$\Box$}
\newcommand{\ms}[1]{%
        \relax\ifmmode
                \mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}%
        \else
                {\it #1}%
        \fi
}
\newcommand{\implies}{\longrightarrow}

\begin{document}

\begin{titlepage}

\title{\bf Lecture 1: Basic Proof Methods}
\author{Nancy Lynch, David Karger}
\date{February 1, 2000}
\maketitle

\end{titlepage}
\renewcommand{\thepage}{\arabic{page}}

\section{Course Overview}

6.042, Mathematics for Computer Science \\
\\
Prerequisites: First year calculus. \\
\\
Introductions. \\
Faculty, TAs, secys

\subsection{Course Goals and Content}

What we want you to learn this term:
\begin{enumerate}
\item
Basic discrete math concepts.

Basic data types and structures used in programming and in reasoning
about programs (numbers, Booleans, strings; sets, functions;
relations, trees, graphs,...). \\
Their properties.

\item
Proofs.

\noindent
How to do them, how to read them, how to recognize correct/incorrect ones.

\noindent
Reasoning about propositions. \\
Basic proof strategies: Direct proof, contradiction, cases...\\
Reasoning with quantifiers. \\
Induction (very important in this course and other places in CS).

\item
Math foundations for software engineering (6170).

\noindent
Working with Profs. Chapin, Guttag to select material for this course...\\
Models for programs and their required behavior.\\
Showing a program satisfies its requirements.

\item
Analysis methods for algorithms (6046)

\noindent
Summations of series. \\
Asymptotic analysis, recurrences. \\
Counting methods and theorems; basic combinatorics. \\
Which leads into:

\item
Discrete probability (6046, 6033?)
\end{enumerate}

\noindent
Course also supports 6045 (theory of computation). \\

\noindent
Overall: \\
We want you to learn how to use mathematics to help you think about
concepts in computer science. 

\noindent
(E.g., define abstract models for real-world objects like programs,
computers, communication channels.
Reason about these models carefully, correctly.
Use the conclusions to help understand the real-world objects.)


{\Large
\begin{itemize}
\item Introduction to basic notions of proofs, using
simple, familiar structures like sets and natural numbers. 
\item Methods for analysis and counting.
\item Probability.
\end{itemize}

Proofs appear throughout the term.

This course moves rapidly from topic to topic.
\begin{itemize}
\item Disadvantage:  none last long enough for thorough coverage.
\item Advantage: boredom/confusion is temporary.
\end{itemize}
}

\subsection{Administrivia}

\noindent
See Handout 1. \\
\\
Lectures, tutorials \\
\\
Handouts \\
\\
Books \\
Old lecture notes, see Fall99 Web site (?) \\
\\
Exams \\
\\
Problem sets \\
\\
Collaboration policy \\
\\
Grading

%\newpage
\section{Basic data types}

\noindent
Reading: \\
Rosen Sections 1.4, 1.5, 1.6 \\
\\
The standard basic data types used in programming:  numbers, Booleans
(true/false), and strings. \\
\\
And other basic data types used in mathematics: sets, functions. \\
Used in reasoning about programs. \\
\\
This is review for most of you. \\
So I won't lecture about it. \\
Just list the basic notions: definitions, operations, some properties. \\
You will be expected to read these three sections carefully on your
own, making sure you can do all the study exercises. 

\subsection{Booleans}

\noindent
Rosen, Section 1.1 \\
\\
Values: 1 (true), 0 (false) \\
\\
Operations: and ($\wedge$), or ($\vee$), not ($\neg$), exclusive-or
($\oplus$). \\
\\
Easiest to explain how they work with tables: \\
\\
$x$  $\neg x$ \\
1       0 \\
0       1 \\
\\
$x$   $y$   $x \wedge y$  $x \vee y$   $x \oplus y$ \\
1     1     1             1            1\\ 
1     0     1             0            0\\
0     1     1             0            0\\
0     0     0             0            1\\


\subsection{Numbers}

Rosen, Section 1.4 


\subsubsection{Natural numbers}

\noindent
$N = \{ 0, 1, 2, \ldots \}$ \\
\\
Most math books actually let N start at 1, not 0, but computer
scientists like to start counting with 0. \\
We'll stay consistent with Rosen. \\
I'll write $N^+$ for the positive naturals. \\
\\
Operations: +, - (partial), times, integer div (round down), remainder
(mod), exp \\
\\
Prime number = Any natural number greater than or equal to $2$ that
has no divisors (except itself and $1$). \\
\\
Even, odd ($2x$ vs. $2x + 1$).


\subsubsection{Integers}

\noindent
$Z$: $N$ and negatives 

\subsubsection{Rationals}

$Q$ \\
\\
Defined to be expressible as a ratio of two integers ${a \over b}$,
where $b \neq 0$. \\
\\
Basic property says can write in lowest terms.


\subsection{Strings}

Over alphabet $A$ of symbols \\
\\
Example: 
$A$ consists of $a, b, c$. \\
Strings: $abc$, $aaa$, $b$, empty string ($\lambda$, no symbols) \\
\\
Operations: concat(string, symbol), concat(string, string)


\subsection{Sets}

Rosen, Section 1.4, 1.5 \\
\\
$\emptyset$, universal set, subset, proper subset \\
power set (define) \\
Cartesian product \\
\\
Operations: union ($\cup$), intersection ($\cap$), complement (overbar) \\
Venn diagrams (show for 2 sets). \\
\\
Some laws about how the ops behave---see Rosen p. 49 \\
E.g.: $A \cup A = A$.


\subsection{Functions}

Rosen, Section 1.6 \\
\\
A rule that assigns an element of one set (range, codomain) to each element of
another set (domain). \\
\\
Properties of functions: \\
One-to-one (no two domain elements get the same range element) \\
Onto (every element of the range gets used) \\
\\
Function inverse, composition ($f \circ g(x) = f(g(x))$)
\\
Pointwise ops (e.g., add, for functions whose range is integers,
$f+g(x) = f(x) + g(x)$) 

\section{What are proofs?}

Today's main topic is proofs. \\
A proof is a way of establishing truth of a statement (proposition). \\
\\
Logical deduction, as opposed to: \\
Accepting it on authority (Bible, horoscope, your professor says so). \\
Observing it by experiments. \\
\\
Involves a chain of logical reasoning, starting from some 
already-accepted statements, to conclude a new statement.\\
\\
This general description also applies to the kinds of reasoning used
in philosophy, law,... \\
\\
But in mathematics, it's more formal, stylized: \\
Statements are {\em propositions\/} with precise meanings. \\
Start from explicitly-assumed propositions called {\em axioms}. \\
Apply standardized {\em rules of deduction}. \\
\\
In the rest of this lecture, I'll explain what these things are, \\
present the most basic proof methods, and give examples.

{\Large
\subsection{Proofs -- What and Why}

{\bf What is a proof?}

Layman's definition of proof: ``A method of ascertaining the truth.''

There are many ways to decide what's true in society and even in science:
\begin{itemize}
\item Law: judge and jury.
\item Religion: inner conviction.
\item Education: reputable authority (e.g., the professor).
\item Science: evidence of experiment/observation (e.g., General
  Relativity, The Big Bang).
\item Statistics: sampling (testing examples).
\end{itemize}
But these methods can go wrong:
\begin{itemize}
\item Conviction: There aren't any bugs in {\em my} programs$\ldots$.
\item Authority: Intel says the Pentium is fine.   Stalin said evolution
  was wrong.
\item Religion: whose?
\end{itemize}
General problem: these methods don't convince everyone.

So mathematics focuses on a particularly convincing kind of
argument: a {\em proof.}

Idea: specify everything so precisely that everyone is convinced.
}

\section{Propositions}

A {\em proposition\/} is a statement that has a truth value,
$\ms{true}$ or $\ms{false}$. \\
\\
Examples:
\begin{enumerate}
\item
$5$ is a prime number. 

It's a proposition, and it's true. 

\item
$8$ is a prime number. 

A false proposition.

\item
$x$ is a prime number. 

Not a proposition. \\
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. 

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

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

A false proposition. \\
This can be written as $\forall x \in N, x \geq 2 (\ldots)$. \\
The quantifier $\forall$ also binds $x$. \\
\\
We will revisit the quantifiers soon (they have their own reasoning
methods). \\
For now, just using them as shorthand notation. \\

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

A proposition, but not so immediate to determine if true or false. \\
Can test:  For $n = 0, 1, 2 \ldots$, $x$ is prime. \\
But if $n = 41$, get $41^1 + 41 + 41$ = $41(43)$, not prime. \\
So, false. \\

\item
$\exists x, y, z \in N^+, n \geq 3 (x^n + y^n = z^n)$. 

Fermat's last theorem, 1640s, says this is false, but he never proved it. \\
Only recently have we learned for sure that it's false (Andrew Wiles, 1994,
130-page proof). \\
But even while we didn't know if it's true or false, it was still a
proposition.

\item
T, F 

Regarded as special cases of propositions, with the obvious truth
values. 

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

Propositions can be about other things besides numbers, e.g., sets. \\
This one is 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})$. \\

De Morgan's laws, true.

\item
The original Pentium chip always divided correctly. 

A false proposition. 

{\Large
\item Every even integer greater than 2 is the sum of two prime
  numbers (Goldbach's conjecture, 1742).
\begin{itemize}
\item Raised in {\em The Boston Globe} as ``one of great unsolved mysteries.''
\item Globe gave example: $20=9+11$ (oops).
\end{itemize}
\item Every map can be colored with four colors, so that no two
  adjacent regions have the same color (Four Color Theorem).
\begin{itemize}
\item First ``proved'' in 1879.
\item The ``proof'' stood for 10 years before a flaw was found.
\item Recently proved with computer aid.
\item Still debated whether this is a valid proof
 (need to prove the computer is working correctly).
\end{itemize}
\item $a^4+b^4+c^4=d^4$ has no positive integer solutions.
\begin{itemize}
\item Conjectured by Euler (1769).
\item Counterexample by Elkies, 218 years later.
\item Smallest counterexample: $95800^4+217519^4+414560^4=422481^4$.
\end{itemize}
\item my algorithm works correctly
}


\end{enumerate}

\section{Propositional Reasoning}

Logical connectives are used to combine simple propositions: \\
And ($\wedge$), or ($\vee$), exclusive-or ($\oplus$), not ($\neg$) \\
As I already mentioned for Booleans. \\
\\
Also implication (if-then, $\Rightarrow$), double implication (equivalence,
$\Leftrightarrow$). \\
Very important in logical reasoning. \\
\\
Truth values of compound propositions are obtained from the 
truth values of the simpler propositions according to {\em truth
tables\/}: 

{\Large example with running statement e.g. ``I like chocolate''}

$P$   $\neg P$ \\
T     F \\
F     T \\

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


$P$  $Q$     $P \wedge Q$   $P \vee Q$  $P \oplus Q$ \\
T    T       T              T           F\\
T    F       F              T           T\\
F    T       F              T           T\\
F    F       F              F           F\\


$P$  $Q$    $P \Rightarrow Q$   $P \Leftrightarrow Q$ \\
T    T          T                 T \\
T    F          F                 F \\
F    T          T                 F \\
F    F          T                 T \\

\noindent
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. \\
\\
Example: \\
If Ricky gets at least five hours of sleep then he passes his 6042
final. \\
($P \Rightarrow Q$) \\
\\
Under what circumstances is this a true statement? \\
Well, it's clearly false if Ricky gets at least 5 hours of sleep and
doesn't pass ($P$ true, $Q$ false). \\
But it's a perfectly OK statement if he sleeps a lot and passes ($P$
and $Q$ both true), \\
or if he does not sleep (my statement did not promise anything about this case). \\
\\
One way to determine truth values for compound propositions is by 
adding new columns to the basic truth table(s): \\
\\
Example: $R = (P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$ \\
\\
Trace through the columns, using the expression structure. \\
Determine that the column contains all T. 


$P$  $Q$    $P \Rightarrow Q$   $\neg Q$  $\neg P$ $\neg Q\Rightarrow\neg P$  $R$ \\
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\\

\noindent
An expression (like this one) whose column contains all T is called a
{\em tautology}. \\
\\
By looking at truth tables like these, we can determine lots of rules \\
that are acceptable for use in proofs about proposition. \\
\\
Examples: 
\begin{enumerate}
\item
Given (assumptions, axioms): $P$, $P \Rightarrow Q$ \\
We can conclude:  $Q$ \\  
\\
Check in the truth table: \\
Situations where $P$ is true are covered by rows 1 and 2. \\
Situations where $P \Rightarrow Q$ is true are covered by rows 1, 3, and 4. \\
So, situations where both statements are true are covered by row 1 (only). \\
But in that row, $Q$ is also true. \\
\\
Modus ponens. 

\item Given:  $P \Rightarrow Q$, $\neg Q$ \\
We can conclude: $\neg P$ 

\item Given:  $P \Rightarrow Q$, $Q \Rightarrow R$ \\
We can conclude:  $P \Rightarrow R$ \\

\item Given: $P$, $\neg P$ \\
We can conclude: $\ms{false}$ \\
\\
No tt rows satisfy the combination of conditions (they're contradictory). \\
So from this utter nonsense, anything can be concluded (including ``false''). \\
(A convention) \\

\item Given:  $\neg P \Rightarrow \ms{false}$ \\
We can conclude:  $P$ 
\end{enumerate}
Etc.  We'll use such truth table rules in proofs wherever we need them.

{\Large

\subsubsection{Predicates}

Predicates are similar to propositions but they depend on variables.
$P(x,y,z)$
denotes a predicate on variables $x,y,z$.  For example, define:
\begin{itemize}
\item $R(x)$: $x$ is an odd number.
\item $Q(x)$: $x > 2$.
\item $P(x)$: $x$ is a prime number.
\end{itemize}
These predicates are {\em not} propositions, because they can be true
or false depending on $x$.  They are like functions from variables to
propositions. 
\begin{itemize} 
\item $P(2)$ is true.
\item $R(2)$ is false.
\item $P(4) \vee R(3)$ is true.
\item $Q(3) \wedge R(4)$ is false.
\item $Q(1) \implies R(2)$ is true.
\end{itemize}

\subsection{Quantifiers}

Many propositions assert that something is true for all or some elements
of a given domain (e.g., all numbers).  The following quantifiers presume
a particular {\em universe of discourse} has been agreed upon in advance.

\begin{itemize}
\item ``$\forall$'' means ``for all.'' $\forall x P(x)$ is a statement
that is true iff $P(x)$ is true for {\em every} $x$ in the universe of
discourse. 
\item ``$\exists$'' means ``there exists.'' $\exists x P(x)$ is true
iff $P(x)$ is true for {\em at least one} $x$ in the universe of
discourse.
\item ``$\not\exists''$ mean ``there does not exist'' (``there is no'').
\item ``$\exists !$'' means ``there exists {\em exactly} one.''
\item ``$\forall x \in S$'' means ``for every $x$ in the set $S$.''
$(\forall x \in S) P(x)$ is equivalent to $(\forall x) (x \in S
\implies P(x)).$
\end{itemize}

Quantifiers can turn predicates into propositions, e.g.
\[
\forall x, P(x) \wedge Q(x) \implies R(x).
\]
Note that each appearance of $x$ is associated with the $\forall$
quantifier.  A variable associated with a quantifier in this way
is said to be {\em bound}.  Since every variable in the above expression
is bound, it is a proposition.  If $P$, $Q$, and $R$ are the predicates
defined above, this proposition is true.

{\bf Note:} $\forall x \exists y$ is {\em different} from $\exists y \forall
x$:
\begin{itemize}
\item $S(x,y):$ student $x$ will fall asleep in class $y$.
\item $\forall y \exists x P(x,y):$ ``In every class, some student will fall asleep.''
\item $\exists x \forall y P(x,y):$ ``There exists a student who will
fall asleep in every class.''
\end{itemize}

What is the universe of discourse above?


\subsection{Axioms}

Axioms are propositions that are {\em assumed} to be true.
One does not prove axioms.  They are simply accepted as
reasonable assumptions. (``Axiom'' comes from Greek:  ``to think
worthy,'' not ``to be true'').  It is not wrong to make assumptions
(in fact, it is unavoidable), but to be rigorous you have to state
your assumptions explicitly.

The rule is {\bf not} ``don't make assumptions'', but rather
{\bf ``state them.''}

Some typical examples of axioms from various parts of mathematics:
\begin{itemize}
\item
If $a=b$ and $b=c$ then $a=c$.
\item
Euclidean geometry has an axiom: Given a line $l$ and a point $p$ not
on $l$, there is exactly one line through $p$ parallel to
$l$. (parallel postulate)
\item
Sometimes an axiom from one domain contradicts an axiom from another.
Spherical geometry has an axiom contradicting Euclid's: Given a line
$l$ and a point $p$ not on $l$, there is {\em no} line through $p$
parallel to $l$.
\item
So does hyperbolic geometry: Given a line $l$ and a point $p$ not on
$l$, there are {\em infinitely many} lines through $p$ parallel to
$l$.

None of these three axioms is ``better'' than any other:  all yield
equally consistent logical proof systems.
\item
Modern mathematicians still argue about which axioms are ``right,''
e.g., the Axiom of Choice (whose assertion and denial are equally
consistent with other commonly agreed upon axioms).
\end{itemize}

Of course, different axioms lead to very different theorems.  But
anyone who agrees with your axioms and inference rules has to accept
your theorems.

What axioms to accept will generally be no problem in this class:
\begin{itemize}
\item  You can
assume that everything you've learned so far (e.g., in high school) is true. 
\item  This may change when we cover
 probability because faulty assumptions are easy to make.
Testing on O.J.'s blood was an example of how probabilistic reasoning can be
``assumption dependent.''
\end{itemize}

\subsection{Inference Rules for Propositions}

Once you have axioms and some propositions that are believed to be
true, all you need is a system of rules for combining true proposition to form new
true propositions. Such rules are called {\em inference rules}. The most
famous rule is modus ponens:
\begin{itemize}
\item 
Let $p$ and $q$ be propositions.
\item
If $p$ is true and $p \implies q$ is true then q is true.
\end{itemize}

This rule and some others are written below in a format where the truth
of all expressions above the line permits the expression below the line to be
inferred to be true.


\newcommand{\alaw}[1]{\parbox[t]{1in}{
\begin{tabular}{l}
#1
\end{tabular}}}

Modus Ponens: \alaw{$p$\\
$p\implies q$\\
\hline
$q$}

Syllogism: \alaw{
$p\implies q$\\
$q\implies r$\\
\hline
$p\implies r$}

Modus Tolens (proof by contradiction): 
\alaw{$p\implies q$\\
$\neg q$\\
\hline
$\neg p$}

Proof by cases: \alaw{$a \vee b$\\ $a \implies q $ \\ $b \implies q$
  \\ \hline $q$} 

You don't have to remember the names of these rules:  just use them
correctly.

Boolean Algebra is a useful aid in reasoning and inferring.  
Mathematics accepts as inference rules all propositional tautologies.
That is, if $A\rightarrow B$ is a tautology, then
\alaw{
A\\
\hline
B}
is a valid inference rule.
For
example, 
\[
[(p \vee q) \wedge \neg p] \implies q
\] so we can derive an
inference rule:

Disjunctive Syllogism: \alaw{$p \vee q$\\ $\neg p$ \\ \hline $q$}\\


In fact, you can get the same power with just three inference rules,
but it makes life harder.

}

\section{Logical Proof Systems}

Recall: a logical proof system consists of:
\begin{itemize}
\item A {\bf language} for stating propositions (propositional/predicate calculus)
\item {\bf Axioms:} Propositions accepted as true
\item {\bf Rules of inference:} Acceptable ways of combining
  propositions 

(all propositional tautologies)
for example:
\[
\neg(\forall x)\neg S(x) \equiv (\exists x)S(x)
\]
(This particular one is rejected by constructivists, since it lets you prove 
something exists
without actually saying what it is).
\item {\bf Theorems:} Propositions that can be derived by applying the
inference rules to the axioms.
\end{itemize}

Note: we must always have some axioms: there are no ``self evident''
propositions.  

\subsection{Example: equality}

Axioms:
\begin{itemize}
\item (E1) $(\forall x) (x=x)$
\item (E2) For any formula $F$ with free variable x,
\[
(\forall xyz\ldots)(x=y \Rightarrow (F \rightarrow F[x/y])
\]
where $F[x/y]$ denotes substituting $y$ for some or all occurrences of
$x$.  
\end{itemize}
Actually (E2) is an {\bf axiom scheme} describing an infinite number of
axioms.

Inference Rules: propositional logic (e.g. modus ponens)

How can we prove $(\forall ab)(a=b \Rightarrow b=a)$?

\begin{itemize}
\item fix $a,b$
\item Let $F$ be $(x=z)$ in E2: $(\forall xyz)(x=y \Rightarrow
  ((x=z)\Rightarrow(y=z))$
\item Thus in particular, $(a=b)\Rightarrow (a=a \Rightarrow b=a)$
\item By hypothesis, $a=b$
\item Modus ponens: $(a=a) \Rightarrow (b=a)$
\item E1: $a=a$
\item MP: $b=a$
\item we proved for fixed $a,b$, so by universal generalization, holds
  for all.
\end{itemize}

This is incredibly torturous.  Why do we care?
\begin{itemize}
\item Each step is justified by reference to previous steps.
\item Justification is mechanical
\item A {\bf machine} can check the work
\end{itemize}

A true proof can be verified by purely mechanical (algorithmic)
means.  No creativity, common sense, or outside knowledge needed.

The mathematician Hilbert suggested that in any proof we must be able to
substitute the words  ``points, lines, planes'' with  ``tables, chairs, 
beer mugs'' and arrive at the same conclusions (i.e. our method of proof should
not depend on a particular representation of our mathematical objects).



\subsection{Completeness/Consistency}


If proofs are mechanical, where is the creativity  in {\bf
  finding} the proof?   Well, you might have noticed that proving something is
much harder than verifying it. Actually some statements are impossible to 
prove!

Hilbert posed (as one of his 23 famous problems) the problem of
finding a rote method for proving any true theorem.  One of the great
accomplishments of 20th century math is the proof that no such method
exists.  There are actually several different kinds of obstacles.

A logical proof system is 
\begin{itemize}
\item {\bf consistent} if no statement and its complement can both be
derived.
\item {\bf complete} if it can be used to prove or disprove every proposition.
\end{itemize}

Russell and Whitehead, in {\em Principia Mathematica}, tried to completely
axiomatize mathematics but failed.

G\"odel's Theorems:
\begin{itemize}
\item no axiomatization of arithmetic is complete and consistent.
\item ``arithmetic is consistent'' is a proposition that cannot be
proved in arithmetic.
\item Gensen: ``arithmetic is consistent'' can be proved by adding
some reasonable-sounding axioms, but these axioms can't be proved
consistent.
\end{itemize}

There are true facts in math that cannot be proven! (Goldbach?)

We'll try to keep these off the homework.

Even if we limit ourselves to things that can be proven, computers
won't be much help.  Finding a proof---even, say, just a proof that a
given propositional logic statement is a tautology---is {\bf
  NP-complete}, meaning that it is untractable in a certain formal
sense you will learn about in 6.045 or 6.046.

So we will always rely on human intuition to find the proofs, although
we will be using computers more and more to check if they are right.

\section{Some Basic Proof Methods}

Rosen, Section 3.1 \\
\\
Some common types of proofs are direct proof, proof by contradiction,
and proof by cases. \\
Here, I'll say what these are and give some tiny examples. \\
\\
Proof style: \\
\\
Today, I'm presenting these proofs in a pretty stylized, structured
format, \\
listing statements and reasons, as in high school geometry proofs. \\
Uses of proof rules explicit. \\
Look like programs (but I don't have a formally-defined language). \\
\\
In math books (incl. Rosen), on-line lecture notes, proofs don't look 
like this. \\
Written in paragraphs, with the logical structure implicit in the prose. \\
Caution: To really understand them, and write them yourself, you have to
understand the logical structure. \\
That's why I'm starting out by laying it out carefully. \\
\\
Later in the course, as we become surer that you understand the 
logical structure, we will present many proofs in less structured styles. \\
Paragraphs, semi-structured (laying out only the major steps). \\
But ideally, it should be possible to rewrite any of these proofs in
structured form (given enough time). \\
\\
For your own proofs: \\
You can write them in structured form, paragraphs, or somewhere in
between. \\
Just make sure you get the proof logic right. 

\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{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove:  $P \Rightarrow Q$ \\
1. Assume $P$. \\
2. $Q$ \\
3. QED 
\> \> \> \> \> Implication \\
\end{tabbing}

QED = Quod Erat Demonstrandum = ``which was to be proved''. \\
Here, it's a shorthand for writing the goal out again as the final
step. \\
\\
%[[[I thought about trying to ``derive'' these rules also from the truth
%table, but, e.g., ``assume'' is confusing---you have to consider all
%the rows where the assumption is false...]]]
\\
Example: \\
\\
Prove: The sum of the first 100 numbers, $1 + ... + 100$, is 5050. \\
Rewrite as an implication: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
1. Assume  $S = 1 + ... + 100$. \\
2. $S = 5050$ 
\> \> \> \> \> ??? \\
3. QED        
\> \> \> \> \> Implication \\
\end{tabbing}
Of course, the interesting part is showing step 2, where I've put the ???. \\
Fill in steps (calculations): 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill\\
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  
   \> \> \> \> Divide by 2 \\
3. QED                       
\> \> \> \> \> Implication 
\end{tabbing}

\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{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove:  $P$ \\
1. $\neg P \Rightarrow \ms{false}$ \\
2. QED   
\> \> \> \> \> Contradiction
\end{tabbing}

\noindent
Some variants of this:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $P$ \\
1. $\neg P \Rightarrow (Q \wedge \neg Q)$ \\
3. QED 
\> \> \> \> \> Contradiction \\
\\
\\
Prove: $P$ \\
1. $\neg P \Rightarrow Q$ \\
2. $\neg Q$ \\
3. QED       
\> \> \> \> \> Contradiction \\
\end{tabbing}

\noindent
Example:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Assume: If Ricky gets at least six hours of sleep then he passes his 6042 final. \\
Ricky fails his 6042 final. \\
Prove: Ricky gets less than six hours of sleep.
\end{tabbing}

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

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
1. If Ricky gets at least five hours of sleep then he passes. 
   ($\neg P \Rightarrow Q$). \\
\> \> \> \> \> Assumed \\
2. Ricky fails ($\neg Q$). 
\> \> \> \> \> Assumed \\
3. QED       
\> \> \> \> \> Contradiction 
\end{tabbing}

\subsection{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. \\
Says $P$ is true in either case.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $P$ \\
1. $Q \Rightarrow P$ \\
2. $\neg Q \Rightarrow P$ \\
3. QED                     
\> \> \> \> \> Cases 
\end{tabbing}

\noindent
Of course, generalize this to any number of predicates, provided that
together they cover all possibilities: \\
$Q_1 \vee Q_2 \vee \ldots \vee Q_k$ is true. \\
\\
Example: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Assume: $d =$ Britney's birth date (day of month, 1-31). \\
Prove: $d^2 + d$ is even. \\
1. $d = 1 \Rightarrow d^2 + d \mbox{ is even}$. \\
2. $d = 2 \Rightarrow d^2 + d \mbox{ is even}$. \\
3. $\ldots$ \\
31. $d = 31 \Rightarrow d^2 + d \mbox{ is even}$. \\
32. QED   
\> \> \> \> \> Cases 
\end{tabbing}
Of course we might imagine more clever proofs than this one, e.g., by 
breaking up the proof into only two cases based on whether $d$ is even/odd.

\section{Predicate Reasoning}

Reading: \\
Proofs book \\
Rosen, Section 3.1 \\
\\
Manipulates sentences containing $\forall$ and $\exists$ quantifiers.
%(Variables all bound, though.) \\
\\
This section gives some examples.

\subsection{Britney's birthdate}

Illustrates: Quantifier reasoning (UG, EI, EG).  Cases.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N (n^2 + n \mbox{ is even})$. \\
1. Fix $n \in N$. \\
2. $n^2 + n$ is even. 
\> \> \> \> \> ??? \\
3. QED  
\> \> \> \> \> Universal Generalization (UG) 
\end{tabbing}
UG is the official fancy name for the rule that says, 
to show something is true for all elements of a set ($\forall$), 
you pick (``fix'') any arbitrary generic element and show it for that. \\
The name is hard to remember, don't worry too much about it. \\
\\
Pattern: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall x \in X (P(x))$. \\
1. Fix $x \in X$. \\
2. $P(x)$ \\
3. QED  
\> \> \> \> \> Universal Generalization (UG) 
\end{tabbing}

Four main rules for manipulating quantifiers: \\
Rosen, p. 173 \\
Universal Generalization  UG \\
Universal Instantiation UI \\
Existential Generalization EG \\
Existential Instantiation EI \\
\\
We'll introduce these as we use them. \\
\\
\\
Back to the proof: \\
To show step 2, can use cases: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N (n^2 + n \mbox{ is even})$. \\
1. Fix $n \in N$. \\
2. $n^2 + n$ is even. \\
\> 1. If $n$ is odd then $n^2 + n$ is even.    
   \> \> \> \> ??? \\
\> 2. If $n$ is even then $n^2 + n$ is even.   
   \> \> \> \> ??? \\
\> 3. QED                                      
   \> \> \> \> Cases \\
3. QED 
\end{tabbing}
Now fill in steps for the odd case: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 1. If $n$ is odd then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is odd. \\
\> \> 2. $n^2 + n$ is even. \\
\> \> \> 1. $\exists x \in N (n = 2x + 1)$ 
         \> \> Definition of ``odd'' \\
\> \> \> 2. Choose $x \in N$, $n = 2x + 1$ 
         \> \> Existential Instantiation (EI) \\
\> \> \> \> \> (If there {\em exists\/} one, you can {\em choose\/} one.) \\
\> \> \> 3. $n^2 + n = 4x^2 + 4x + 1 + 2x + 1 = 2(2x^2 + 3x + 1)$ \\
\> \> \> \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$ 
         \> \> Existential Generalization (EG) \\
\> \> \> \> \> (If you {\em have\/} one, then one {\em exists}.) \\
\> \> \> 5. QED                 
         \> \> Definition of ``even'' \\
\> \> 3. QED                    
      \> \> \> Implication 
\end{tabbing}
Analogously for the ``even'' case: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 2. If $n$ is even then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is even. \\
\> \> 2. $n^2 + n$ is even. \\
\> \> \> 1. $\exists x \in N (n = 2x)$ 
         \> \> Definition of ``even'' \\
\> \> \> 2. Choose $x \in N$, $n = 2x$ 
         \> \> EI \\
\> \> \> 3. $n^2 + n = 4x^2 + 2x = 2(2x^2 + x)$ 
         \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$ 
         \> \> EG \\
\> \> \> 5. QED                 
         \> \> Definition of ``even''. \\
\> \> 3. QED                    
      \> \> \> Implication 
\end{tabbing}
Or, condensing a little: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 2. If $n$ is even then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is even. \\
\> \> 2. Choose $x \in N$, $n = 2x$
      \> \> \> Definition of ``even'', EI \\
\> \> 3. $n^2 + n = 4x^2 + 2x = 2(2x^2 + x)$ 
      \> \> \> Algebra \\
\> \> 4. $n^2 + n$ is even. 
      \> \> \> EG, definition of ``even'' \\
\> \> 5. QED        
      \> \> \> Implication 
\end{tabbing}

\subsection{Proofs by contradiction}

Illustrates: Contradiction, more quantifiers. \\

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\sqrt{2}$ is irrational.\\
1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
2. QED 
\> \> \> \> \> Contradiction. 
\end{tabbing}
Assume it's rational, play with the definitions, and try to get a
contradiction. 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
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} = {a \over b}$, lowest terms.
      \> \> \> Definition and basic properties of rationals, EI \\
\> \> 2. $2 b^2 = a^2$       
      \> \> \> Algebra \\
\> \> 3. $a^2$ is even.
      \> \> \> EG, Definition of ``even'' \\
\> \> 4. $a$ is even.      
      \> \> \> ??? \\
\> \> 5. Choose $c \in N$, $a = 2c$. 
      \> \> \> Definition of ``even'', EI \\
\> \> 6. $4 c^2 = a^2 = 2b^2$ 
      \> \> \> Algebra \\
\> \> 7. $2 c^2 = b^2$       
      \> \> \> Algebra \\
\> \> 8. $b^2$ is even.
      \> \> \> EG, Definition of ``even'' \\
\> \> 9. $b$ is even.
      \> \> \> ??? \\
\> \> 10. $a$ and $b$ aren't in lowest terms. 
      \> \> \> 1.2.4, 1.2.9 \\
\> \> 11. QED
      \> \> \> 1.2.1, 1.2.10, propositional logic \\
\> 3.  QED                 
   \> \> \> \> Implication. \\
2. QED  
\> \> \> \> \> Contradiction. \\
\end{tabbing}

\noindent
Little missing piece: Showing that $a$ and $b$ are even, because we know
their squares are even. \\
Reason is a general fact, which could itself be proved by
contradiction: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Assume: $x \in N$, $x^2$ is even. \\
Prove: $x$ is even. \\
1. $x \mbox{ is odd} \Rightarrow \ms{false}$ \\
\> 1. Assume $x$ is odd. \\
\> 2. $x^2$ is odd. 
   \> \> \> \> Do a proof like the one in the birthdate example. \\
\> 3. $\ms{false}$           
   \> \> \> \> Assumption, 1.2.4, Prop. logic \\
2. QED
\> \> \> \> \> Contradiction
\end{tabbing}


{\Large

Note: this process is based on the assumption that math is consistent,
since otherwise it would be possible to prove something false.

We freely used lots of basic facts about divisibility, lowest terms
for fractions, definitions of square, all without reference or proof.

Pythagoras and his followers knew this proof, but suppressed it because
they axiomatically denied the existence of irrational numbers (so
their system was not consistent, because they also had an axiom that
every line had a numeric length).
}


\subsection{De Morgan's Law}

Illustrates:  Set theory proof. 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall A, B (\bar{A} \cap \bar{B} = \bar{A \cup B})$ \\
1. Fix $A$, $B$. \\
2. $\bar{A} \cap \bar{B} = \bar{A \cup B}$   
\> \> \> \> \> ??? \\
3. QED
\> \> \> \> \> UG 
\end{tabbing}

\noindent
To show two sets are equal, we show that they contain the same elements. \\
See Rosen, Def. 2, p. 40. 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall A, B (\bar{A} \cap \bar{B} = \bar{A \cup B})$. \\
1. Fix $A$, $B$. \\
2. $\bar{A} \cap \bar{B} = \bar{A \cup B}$ \\
\> 1. $\forall x (x\in \bar{A} \cap \bar{B}  \Leftrightarrow x\in\bar{A \cup B})$ \\
\> \> 1. Fix $x$. \\
\> \> 2. $x \in \bar{A} \cap \bar{B}  \Leftrightarrow x \in \bar{A \cup B}$ 
      \> \> \> ??? \\
\> \> 3. QED    
      \> \> \> UG \\
\> 2. QED           
   \> \> \> \>  Definition of set equality. \\
3. QED 
\> \> \> \> \> UG 
\end{tabbing}

\noindent
Equivalence can be shown by showing two implications, one in each
direction: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $x \in \bar{A} \cap \bar{B}  \Leftrightarrow x \in \bar{A \cup B}$ \\
\> \> \> 1. $x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A\cup B}$ 
         \> \> ??? \\
\> \> \> 2. $x \in \bar{A \cup  B} \Rightarrow x \in \bar{A} \cap\bar{B}$ 
         \> \> ??? \\
\> \> \> 3. QED   
         \> \> Propositional logic 
\end{tabbing}
One direction:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 1. $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 \bar{A \cup  B}$  
            \> Definition of complement. \\
\> \> \> \> 6. QED 
            \> Implication 
\end{tabbing}
Actually, the union step could be expanded to a little proof by
contradiction:  \\
if it is in the union, it's in one of the sets, etc. \\
The other direction essentially reverses the steps: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 2. $x \in \bar{A \cup  B} \Rightarrow x \in \bar{A} \cap\bar{B}$ \\
\> \> \> \> 1. Assume $x \in \bar{A \cup B}$. \\
\> \> \> \> 2. $x \notin A \cup B$
            \> Complement \\
\> \> \> \> 3. $x \notin A$, $x \notin B$
            \> Union \\
\> \> \> \> 4. $x \in \bar{A}$, $x \in \bar{B}$
            \> Complement \\
\> \> \> \> 5. $x \in \bar{A} \cap \bar{B}$
            \> Intersection \\
\> \> \> \> 6. QED 
            \> Implication 
\end{tabbing}


\subsection{Proof by counterexample}

Prove: All natural numbers $\geq 2$ are prime. \\
\\
This turns out to be false. \\
We can show this using a ``counterexample'', $10$. \\
That's all that's needed. \\
Really, we're proving the negation, which says $\exists$ a non-prime
$\geq 2$. \\
And this follows just by exhibiting one.
%(Existential Generalization).

\section{Good proofs}

Correct. \\
\\
Clear, understandable. \\
\\
Nice structure:  \\
Broken up into separate pieces to prove key intermediate properties.\\
Makes it easier to understand. \\
Reusable pieces.\\
\\
Pieces general, abstract. \\
Written to apply to many cases. \\
Avoid clutter of unnecessary assumptions. \\
\\
Doesn't leave ``gaps''---saying it's obvious when it isn't. \\
\\
Elegant, short, clever...\\
\\
A lot like criteria for good programs. \\
\\
A difference: \\
In math, proofs are sometimes valued for being deep, hard. \\
Not much of a consideration in programming:  here, the premium is more
on how well it works and how easy it is to understand. 

{\Large

\subsection{A Nonconstructive Existence Proof}

\begin{theorem}
For any number $n$, there is a prime number greater than $n$.
\end{theorem}
\begin{proof}
Fix $n$, and consider $n!+1=(1\cdot2\cdot3\cdots(n-1)\cdot n)+1$.  If
$n!+1$ is prime, we are done.  Otherwise, $n!+1$ has a prime factor
$x$ (relies on the prime number theorem).  By definition, $n!+1$ is
divisible by $x$ (without leaving a remainder).  But if $n!+1$ is
divided by a number less than $n$, the remainder is 1.  Therefore,
$x>n$.
\end{proof}

(Note: $n!+1$ need not be prime.  $5!+1 = 11^2$.)

We don't know what $x$ is, only that it exists.

Constructivists would deny this is a proof.

\subsection{Proof by Cases}

Proof by cases: 
    \begin{itemize}
    \item show $p\implies (a \vee b)$
    \item show $a \implies q$ and $b \implies q$
    \item deduce $p \implies q$
    \end{itemize}

\begin{theorem} for some irrational number $\alpha$ and $\beta$,
  $\alpha^{\beta}$ is rational.
\end{theorem}

\begin{proof}

Consider the number ${\sqrt{2}}^{\sqrt{2}}$.  If it is rational, we are done!

If not, then it is irrational.  We also know that $\sqrt{2}$ is
irrational (previous proof).  But then we have,

${\sqrt{2}}^{{\sqrt{2}}^{\sqrt{2}}} = {\sqrt{2}}^{2} = 2$, which is rational!

\end{proof}

This is a wierd proof!  
We proved that it exists, but we didn't construct it!
It's easy to follows, but hard to imagine.  How
did we know?

{\bf Practice}.  Seeing proofs develops a feeling for finding proofs.

\subsection{Other Proof Methods}

\begin{itemize}
\item Indirect proof: from $\neg q \implies \neg p$, deduce $p
\implies q$ (similar to proof by contradiction).
\item Vacuous proof: if $p$ is false, then $p\implies q$ is true.
\begin{itemize}
\item if $x$ is an even prime greater than 2, then $x$ is a perfect
square.
\end{itemize}
Boring, but often arises as one case of a proof by cases.
\end{itemize}

\subsection{Fallacies}

There are several ways to generate an incorrect proof.

\begin{eqnarray*}
\sqrt{-1} &= &\sqrt{-1}\\
\sqrt{\frac{1}{-1}} &= &\sqrt{\frac{-1}{1}}\\
\frac{\sqrt{1}}{\sqrt{-1}} &= &\frac{\sqrt{-1}}{\sqrt{1}}\\
\sqrt{1}\cdot\sqrt{1} &= &\sqrt{-1}\cdot\sqrt{-1}\\
1 &= &-1\\
\end{eqnarray*}

Where's the bug?

There are several common fallacies:
\begin{description}
\item[Affirming the conclusion:]\mbox{ }
\begin{itemize}
\item If you are tired, you will fall asleep
\item You fall asleep
\item therefore, you are tired
\end{itemize}
The fact that the conclusion is true does not make the hypothesis
true.  Maybe you are just bored.

\item[Denying the hypothesis:]\mbox{ }
\begin{itemize}
\item If you work hard, you will pass the course
\item You don't work hard
\item therefore, you will fail the course.
\end{itemize}
Even if the hypothesis is false, the conclusion can be true.  Maybe
you are smart enough to pass without working.

\item[Circular reasoning:] proposition: If $n^2$ is not divisible by 3,
then $n$ is not divisible by 3.
\begin{itemize}
\item If $n^2$ is not divisible by 3, then $n^2$ is not
equal to $3k$ for any integer  $k$.
\item therefore, $n$ does not equal $3l$ for any integer $l$.
\item therefore, $n$ is not divisible by $3$.
\end{itemize}

\end{description}

If you assume (or prove) something FALSE, you can prove anything!
}

\end{document}

% Names (from teeny-bopper rock music):  Ricky, Enrique, Britney, Christina.
% Jessica, Kid, Lou
%
% Monica, Erica, Rita, Tina, Sandra, Mary, Jessica.

Slides: 

- What we want you to learn this term (5 bullets)

- List of 5 basic data types; under each, list the operations,...??

- Truth tables for Booleans

- List of proposition examples

- Truth tables for propositional logic

- Propositional logic sample proof rules


- Direct proof pattern

- Direct proof example, short version

- Direct proof example, full version

- Contradiction pattern 1

- Contra pattern 2, pattern 2

- Contra example, full version, but without the comments.

- Cases pattern

- Cases example


- Birthdate example, short proof; cases; odd; even

- De Morgan short proof; ... all the separate versions/pieces

- Contradiction proofs...













\\
