| proof |
Definition. A PROOF is a sequence of lines containing sentences.
Each sentence is either an assumption or the result
of applying a rule of proof to earlier sentences in the sequence. The
primitive rules of proof are stated below. |
|
|
Comment.
The purpose of presenting proofs is to
demonstrate unequivocally that a given set of premises entails a
particular conclusion. Thus, when presenting a proof we associate three
things with each sentence in the proof sequence: |
|
|
|
| annotation |
On the right of the sentence we provide an ANNOTATION specifying
which rule of proof was applied to which
earlier sentences to yield the given sentence.
|
|
|
|
| assumption set |
On the far left we associate with each
sentence an ASSUMPTION SET containing the assumptions on
which the given sentence depends.
|
|
|
|
| line number |
Also on the left, we write the current LINE NUMBER of the proof.
|
|
|
|
| line of proof |
Definition. A sentence of a proof, together
with its annotation, its assumption set and the line number, is called a
LINE OF THE PROOF.
|
| Example. |
|  |
|
|
| proof for a given argument |
Definition. A PROOF FOR A GIVEN ARGUMENT
is a proof whose last sentence is the argument's conclusion depending on
nothing other than the argument's premises.
|
|
|
|
| primitive rules |
Definition. The ten PRIMITIVE RULES OF
PROOF are the rules assumption, ampersand-introduction,
ampersand-elimination, wedge-introduction, wedge-elimination,
arrow-introduction, arrow-elimination, reductio ad absurdum,
double-arrow-introduction, and double-arrow-elimination, as described
below.
|
|
|
|
| assumption |
Assume any sentence.
|
|
| Annotation: A |
| Assumption set: The current line number. |
| Comment:Anything may be assumed at any time.
However, some assumptions are useful and some are not! |
|
| Example. |
| 1 (1) P v Q A |
|
|
|
| ampersand-intro |
Given a sentence (at line m) and a sentence (at line n),
conclude a conjunction of them.
|
|
| Annotation: m, n &I |
| Assumption set: The union of the assumption sets at lines
m and n. |
| Comment: The order of lines m and n in the proof
is irrelevant. |
| Also known as:Conjunction (CONJ). |
|
| Example. |
| 1 (1) P A |
| 2 (2) Q A |
| 1,2 (3) P & Q 1,2 &I |
| 1,2 (3) Q & P 1,2 &I |
|
|
|
| ampersand-elim |
Given a sentence that is a conjunction (at line m),
conclude either conjunct.
|
| Annotation: m &E |
| Assumption set: The same as at line m. |
| Also known as: Simplification (S). |
|
| Examples. |
| (a) |
| 1 (1) P & Q A |
| 1 (2) Q 1 &E |
| 1 (3) P 1 &E |
|
|
| (b) |
| 1 (1) P & (Q->R) A |
| 1 (2) Q->R 1 &E |
|
|
|
| wedge-intro |
Given a sentence (at line m), conclude any
disjunction having it as a disjunct.
|
| Annotation: m vI |
| Assumption set: The same as at line m. |
| Also known as: Addition (ADD). |
|
| Examples. |
| (a) |
| 1 (1) P A |
| 1 (2) P v Q 1 vI |
| 1 (3) (R <-> ~T) v P 1 vI |
|
| (b) |
| 1 (1) Q->R A |
| 1 (2) (Q->R) v (P & ~S) 1 vI |
|
|
|
| wedge-elim |
Given a sentence (at line m) that is a
disjunction and another sentence (at line n) that is a denial of one
of its disjuncts, conclude the other disjunct.
|
| Annotation: m, n vE |
| Assumption set: The union of the assumption sets at lines
m and n. |
| Comment: The order of m and n in the proof is
irrelevant. |
| Also known as: Modus Tollendo Ponens (MTP), Disjunctive
Syllogism (DS). |
|
| Examples. |
| (a) |
| 1 (1) P v Q A |
| 2 (2) ~P A |
| 1,2 (3) Q 1,2 vE |
|
|
| (b) |
| 1 (1) P v (Q->R) A |
| 2 (2) ~(Q->R) A |
| 1,2 (3) P 1,2 vE |
|
|
| (c) |
| 1 (1) P v ~R A |
| 2 (2) R A |
| 1,2 (3) P 1,2 vE |
|
|
|
| arrow-intro |
Given a sentence (at line n), conclude a
conditional having it as the consequent and whose antecedent appears in the
proof as an assumption (at line m).
|
| Annotation: n ->I (m) |
| Assumption set: Everything in the assumption set at line n
except m, the line number where the antecedent was assumed. |
| Comment: The antecedent must be present in the proof as an
assumption. We speak of DISCHARGING this assumption when applying
this rule. Placing the number m in parentheses indicates it is the
discharged assumption. |
| Also known as: Conditional Proof (CP). |
|
| Examples. |
| (a) |
| 1 (1) ~P v Q A |
| 2 (2) P A |
| 1,2 (3) Q 1,2 vE |
| 1 (4) P->Q 3 ->I (2) |
|
|
| (b) |
| 1 (1) P A |
| 2 (2) R A |
| 2 (3) P->R 2 ->I (1) |
|
|
|
| arrow-elim |
Given a conditional sentence (at line m) and
another sentence that is its antecedent (at line n), conclude the
consequent of the conditional.
|
| Annotation: m, n ->E |
| Assumption set: The union of the assumption sets at lines m and
n. |
| Comment: The order of m and n in the proof is irrelevant. |
| Also known as: Modus Ponendo Ponens (MPP), Modus Ponens (MP),
Detachment, Affirming the Antecedent. |
|
| Example. |
| 1 (1) P->Q A |
| 2 (2) P A |
| 1,2 (3) Q 1,2 ->E |
|
|
|
reductio ad
absurdum |
Given both a sentence and its denial (at lines m and n),
conclude the denial of any assumption appearing in the proof (at line k).
|
| Annotation: m, n RAA (k) |
| Assumption set: The union of the assumption sets at m and n,
excluding k (the denied assumption). |
| Comment: The sentence at line k is the assumption discharged
(a.k.a. the REDUCTIO ASSUMPTION) and the conclusion is a denial of
the discharged assumption. The sentences at lines m and n
are denials of each other. |
| Also known as: Indirect Proof (IP), ~Intro/~Elim. |
|
|
| Examples. |
| (a) |
| 1 (1) P->Q A |
| 2 (2) ~Q A |
| 3 (3) P A |
| 1,3 (4) Q 1,3 ->E |
| 1,2 (5) ~P 2,4 RAA (3) |
|
|
| (b) |
| 1 (1) P v Q A |
| 2 (2) ~P A |
| 3 (3) ~P->~ A |
| 2,3 (4) ~Q 2,3 ->E |
| 1,2,3(5) P 1,4 vE |
| 1,3 (6) P 2,5 RAA (2) |
|
|
| (c) |
| 1 (1) P A |
| 2 (2) Q A |
| 3 (3) ~Q A |
| 2,3 (4) ~P 2,3 RAA (1) |
|
|
|
double-arrow-
intro | Given two conditional sentences having the
forms PHI -> PSI and PSI -> PHI (at lines m and
n), conclude a biconditional with PHI on one side and PSI on the other. |
| Annotation: m, n <->I |
| Assumption set:The union of the assumption sets at lines m and n. |
| Comment: The order of m and n in the proof is irrelevant. |
|
|
| Examples. |
| 1 (1) P->Q A |
| 2 (2) Q->P A |
| 1,2 (3) P <-> Q 1,2 <->I |
|
| or | 1,2 (3) Q <-> P 1,2 <->I |
|
|
|
double-arrow-
elim |
Given a biconditional sentence PHI <->
PSI (at line m), conclude either PHI -> PSI or PSI -> PHI.
|
| Annotation: m <->E |
| Assumption set: the same as at m. |
| Also known as: Sometimes the rules <->I and <->E are
subsumed as Definition of Biconditional (df.<->). |
|
|
| Examples. |
| 1 (1) P <-> Q A |
| 1 (2) P->Q 1 <->E |
|
| or | 1 (2) Q->P 1 <->E |
| Comment. These ten rules of proof are truth-preserving. Given
true premises, they will always yield true conclusions. This entails that
if a proof can be constructed for a given argument, then the argument is
valid. |
|
|
|
| Exercise 1.4 | Fill in the blanks in the following proofs. |
|
|
| i | 1 (1) P |
| (2) ~Q A |
| (3) P&Q |
|
|
|
| ii* | (1) P v Q A |
| 2 (2) ~Q v R |
| (3) A |
| (4) Q 1,3 vE |
| (5) 2,4 |
|
|
|
| iii* | (1) P->Q A |
| (2) P v Q A |
| 3 (3) ~Q |
| (4) P |
| (5) |
| (6) Q 3,5 RAA |
|
|
|
| iv | (1) ~P <-> Q A |
| (2) ~P A |
| 3 (3) ~Q v R |
| (4) ~P->Q |
| (5) 2,4 |
| (6) R |
| (7) ~P->R |
|
|
|
| v | 1 (1) P->Q A |
| 2 (2) A |
| 3 (3) P A |
| (4) 1,3 ->E |
| (5) R 2,4 vE |
| (6) 5 ->I (3) |
| 1 (7) (R v ~Q)->(P->R) 6 |