Proof Techniques

Before we begin, Let’s define some terms,

1. Proposition. A statement that is either true or false.
2. Predicate. A proposition whose truth depends on the value of variable(s).
3. Axiom. A proposition that is assumed to be true.
4. Implication. An implication p⇒q is true if p is false or q is true. Read as p implies q, also can be read as p results q. (an important tool to validate stuff, including proof technique.)

Proof Techniques

• Direct Proof. You start with axioms, or some theorems you knew before, you proved along the way, and make logical deduction until you get to where you want to go, the theorem.
• Indirect Proof. Proof by contradiction, you assume the opposite of what you are trying to proof. Then you just take steps for logical deductions forward, until you arrive at a contradiction, something where you proof false equals true.
• Induction Proof. Probably the most powerful and commonly used proof technique in computer science.

Proof the Proof Techniques

How do you know the above proof techniques work? The ultimate tool to validate — implication.

Let P be the proposition that you are trying to proof correct or wrong.

• Indirect Proof — !P ⇒ false. By assuming P is false, in order to derive/result a true implication, LHS can be either false/true.
• Induction Proof — P(n) ⇒ P(n+1). By assuming P is true, in order to derive/result a true implication, P(n+1) must be true.

Spot the pattern?

It turns out, there is a pattern in proof techniques,

(ASSUME⇒ RESULT) = TRUE

Explanations:

• ASSUME. First, you make an assumption of a proposition, pick a side: true or false. I.e: if true, probably you are using induction proof; false, proof by contradiction.
• RESULT. Then, from the assumption, form axiom(s) if necessary, work through the chain of logic deductions, and obtain result that resulted a TRUE implication.
• TRUE. A TRUE implication means the truth of proposition is now determined.