In
logic and
mathematics, a proof is a series of
statements forming an
argument with the final statement designated a
conclusion or
theorem.
To construct a proof
To prove a statement to be true, one starts with axioms (premises, postulates), which are statements that are assumed to be true (usually they will or have been proved elsewhere, or are too obvious to need proving, or are fundamental mathematical structures). From these axioms, one derives further statements by using rules of inference, which are tautologies (logical statements that are always true regardless of the truth values of their individual elements). For example, ((p->q)^(q->r))->(p->r) is a tautology, and a rule of inference known as "Hypothetical Syllogism". One continues to derive statements in this manner until he has derived the theorem he set out to prove. One then puts a "therefore" symbol (3 dots in a triangle) in front of it, writes "QED" (Quod Erat Demonstrandum), and calls it a day.
To show a proof to be incorrect
There are two ways a proof can be incorrect: either an axiom was untrue, or a rule of inference was misused (or, depending on how you look at it, a rule of inference was used that is not a tautology). Certain sorts of misuses are very common and are documented logical fallacies (note: that node, while very useful, contains many fallacies of informal logic as well as formal logic). For example, this fallacy is very common: ((p->q)^q)->p. This is known as "Affirming the consequent" and arises from assuming that an implication (p->q) is equivalent to its converse (q->p), which it is not. (Aside: (p->q)<-->(~q->~p), its contrapositive).
Related terms
A lemma is a simple theorem used in the proof of other theorems.
A corollary is a proposition that can be established directly from a theorem which has just been proved.
A conjecture is a statement whose truth value is unknown. When a conjecture has been proven, it becomes a theorem.