Proofs

A proof is a valid argument that establishes the truth of a statement.

In Math and CS, we mostly use informal proofs.

Why proofs in CS?

• To prove your program to be correct
• Dijkstra “Testing shows the presence of bugs, not its absence”
• To establish your OS is secure
• To prove your algorithm gives you the correct answer
• To show your system specifications are consistent

Tools in our “Proof” Toolbox

• The Rules of Inference allow us to preserve truth.
• We must begin with the truth
• We must start with premises that are true.
• To prove a mathematical statement, we will need the following tools
  • Definitions
  • Theorem - A statement that can be shown to be true
  • axioms - Statements we assume to be true
  • lemma - A helping theorem or result which is needed to prove a theorem
  • proof - A valid argument that establishes the truth of a theorem
  • corollary - A theorem that can be established directly from a theorem
  • conjecture - A statement that is proposed to be true, usually on the basis of some partial evidence or intuition of an expert. When proof is found, the conjecture becomes a theorem.

Types of Proofs

• Exhaustive Proof
• Direct Proof
• Direct Proof by Contraposition
• Proof by Contradiction
• Uniqueness Proof
• Vacuous Proof
• Proof by Cases
• Trivial Proof
• Existence Proof