A proof is a series of statements intended to demonstrate some conclusion. Each step in a proof must follow logically from previous steps in accordance with recognized rules of logic and mathematical reasoning.
In discrete mathematics, proofs are used to establish the truth or falsity of important claims. When an important claim is proven, it becomes known as a theorem.
When an important mathematical claim is suspected to be true, but has not yet been proven, it is known as a conjecture.
Mathematical exploration and discovery are driven by the formulation and investigation of conjectures.
A variety of logical and mathematical techniques are employed in proofs. A single proof may contain multiple of such techniques. Some of these techniques are described in the term pages below.
- Conditional Proof
- Proving a conditional statement by assuming the antecedent and showing that the consequent follows.
- Proof by Cases
- Proving a statement by showing that it holds in each of a set of mutually exhaustive cases.
- Proof by Contradiction
- Proving a statement by assuming that it is false and showing a contradiction follows on that assumption.
- Proof by Induction
- Proves a universal generalization using the hypothesis that the previous element in a series has some property.
- Proof by Strong Induction
- Proves a universal generalization using the hypothesis that all previous elements in a series have the same property.