Proofs
Introduction
No amount of testing can prove that software or hardware will always behave correctly, but proofs can. A proof is a method of establishing truth.
A proposition is a statement that is either true or false.
You can't check a claim about an infinite set by checking a finite sample of its elements, no matter how large it is. Special notation for propositions for all numbers:
$$ \forall \, n \in \mathbb{N}. \; p(n) \, \text{is prime.} $$
The symbol \(\forall\) is read "for all". \(\mathbb{N}\) stands for the set of nonnegative integers: 0, 1, 2, ... The symbol \(\in\) is read as "is a member of", "belongs to", or "in". The period after the \(\mathbb{N}\) is a separator between phrases.
A predicate is a proposition whose truth depends on the value of one or more variables. A function-like notation is used to denote a predicate supplied with specific variable values. This function returns only values true or false. For example:
$$ P(n)::= \text{"\(n\) is a perfect square"} $$
where the symbol \(::=\) means "equal by definition".
An axiom is a proposition that is simply accepted as true. A theorem is an important true proposition. A lemma is a preliminary proposition useful for proving later propositions. A corollary is a proposition that follows in just a few logical steps from a theorem.
A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question. Inference rules are logical deductions that are used to prove new propositions using previously proved ones.
A fundamental inference rule is modus ponens.
A set of claims is consistent if it's logically possible for all of them to be true at the same time. Logically possible means the set of claims does not entail a contradiction (A and not-A). If there is a contradiction, then it's logically impossible, and the set is inconsistent.
DeMorgan's Rules:
not-(not-A) = A
not-(A and B) = (not-A) or (not-B)
not-(A or B) = (not-A) and (not-B)
not-(if A then B) = (A) and (not-B) = (A) but (not-B) \(\ne\) if A then (not-B)
The conditional truth table:
| A | -> | B |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | T | F |
The contradictory of the conditional
| A | ? | B |
|---|---|---|
| T | F | T |
| T | T | F |
| F | F | T |
| F | F | F |
| A | and | not-B |
|---|---|---|
| T | F | T |
| T | T | F |
| F | F | T |
| F | F | F |
Identify properly the antecedent: it is followed by "if" whether at the beginning or at the end.
B if A = If A then B
Q if P = If P then Q
A only if B = If A then B
The biconditional:
A if and only if B = A iff B = (if A then B) and (if B then A)
B unless A = If not-A then B
Read "unless" = "if not-"
The contrapositive:
If A then B = If not-B then not-A
If A then B = (not-A) or B
A is sufficient for B = If A then B
Necessary and sufficient
A is necessary for B = If B then A
A is necessary for B = If not-A then not-B
Oxigen is necessary for combustion.
= If there's combustion then there's oxygen.
= If there's no oxygen then there's no combustion.
If I have a driver's license then I passed a driver's test.
= Passing a driver's test is necessary for having a driver's license.
= Having a driver's license is sufficient for passing a driver's test.
A is necessary and sufficient for B = A iff B