|
Chapter 6: Deduction and Proof |
|
|
|
|
|
6.1: Introduction |
|
|
So far we have looked at logic via truth-values. This is said to be the semantic aspect of logic. Truth-trees are sometimes called Semantic Tableaux.
Another stle of logic is the Proof Theoretic, in which concepts are defined in terms of what can be proved. The type of proof theory that we will work with n this chapter is called Natural Deduction. Other types of proof theory are Axiomatics and Sequent Calculus.
|
|
|
6.2: Equivalence Deductions |
|
|
We can show that one formula is Logically Equivalent to another by deducingone from the other by logical steps. At each step replace the formula, or subformulae of it, according to Replacement Rules.
Here are 6 replacement rules:
~~p : : p (DN) Double Negation p v q : : q v p (Com) Commutation for Disjunction p & q : : q & p (Com) Commutation for Conjunction ~(p & q) : : ~p v ~q (DeM) DeMorgans Law ~(p v q) : : ~p & ~q (DeM) DeMorgans Law p É q : : ~p v q (IMP) Material Implication
Read the replacement rule A : : B as 'A can replace or be replaced by B' 1. Replacement rules apply to both formulae and well-formed subformulae 2. Replacement rules work in both directions.
Here is an example. We wish to prove the logical equivalence
((p & (q v r)) º (~~(r v q) & p))
Begin an Equivalence Deduction with the LHS and derive the RHS, thus
1. ((p & (q v r)) Premise 2. ((p & (r v q)) From 1 by Com 3. (((r v q) & p) 2, Com 4. ((~~(r v q) & p) 3, DN
The right hand column is the justification column. It and the line numbers are really just to keep track of the process of forming a deduction.
|
|
|
6.3: Deductions |
|
|
Every formula in an equivalence deduction is equivalent, and the deduction can go in either direction. This is a special case. The more general case is that one formula follows from another but not vice versa. For this we need Inference Rules.
Here are 8 inference rules
p & q (Simp) Simplification p
p (Conj) Conjunction ... q p & q
p É q (MP) Modus Ponens, or p (AA) Affirming the Antecedent q
p É q (MT) Modus Tollens, or ~q (DC) Denying the Consequent ~p
p É q (HS) Hypothetical Syllogism, or q É r (ChArg) Chain Argument p É r
p v q (DS) Disjunctive Syllogism, or ~p (DC) Denying a Disjunt q
p (Add) Addition, or p v q (DA) Disjunctive Addition
p v r (CD) Constructive Dilemma p É q r É s q v s
Here is an example of the use of these inference rules. We wish to prove that
from p, p É q, ~r É ~q we may infer r
1. p Premise 2. p É q Premise 3. ~r É ~q Premise 4. q 1, 2, MP 5. ~~q 4, DN 6. ~~r 5, 3, MT 7. r 6, DN
|
|
|
6.4: More Replacement Rules |
|
|
Here are 3 more replacement rules:
p v (q v r) : : (p v q) v r (Assoc) Association p v (q & r) : : (p v q) & (p v r) (Dist) Distribution p v p : : p (Idem) Idempotence
From these we can prove yet 3 more rules:
p & (q & r) : : (p & q) & r (Assoc) Association p & (q v r) : : (p & q) v (p & r) (Dist) Distribution p & p : : p (Idem) Idempotence
From which we can prove 2 more rules:
(p & q) É r : : p É (q É r) (Exp) Exportation p É (q É r) : : q É (p É r) (Perm) Permutation
And so on:
p º q : : (p É q) & (q É p) (Equiv) Equivalence p º q : : (p & q) v (~p & ~q) (Equiv) Equivalence p x q : : ~(p º q) (Xor) Xor, or Exclusive Or p É q : : ~q É ~p (Cont) Contraposition p : : p & (q v ~q) (TConj) Tautologous Conjunct p : : p v (q & ~q) (TConj) Contradictory Disjunct
|
|
|
6.5: Short Cut Inference Rules |
|
|
The rule Simp is really a rule of Left-Simplification. But an application of Com to the top line followed by Simp would make it a rule of right simplification. Several of the rules (Simp, Add, DS) are biassed like that and we can ignore the bias in deductions because we know the 'right bias' versions are valid. We use the same names for both biases.
The following short-cut rules can be proved using DN.
~p v q p v ~q (DS) Disjunctive Syllogism p q q p
p É ~q (MT) Modus Tollens q ~p
|
|
|
6.6: Conditional Proof |
|
|
We have seen rules which eliminate & and rules which introduce it: ditto for v and ~. We have seen a rule for eliminating É (e.g. MP) but not for introducing it. Now we'll introduce the rule of Conditional Proof which will do just that.
Suppose we have the following deduction, where Ai are formulae:
1. A1 Premise 2. A2 Assumption ç 3. A3 Some rule ç ... ç n. An Some rule ç n+1. A2 É An 2-8, CP (Conditional Proof)
Line 2 is an assumption, lines 3 to n follow from it and the other involved premisses. The conclusion is that if the assumption holds then the statement of line n follows. The first horizontal line marks the Assumption, the second line discharges the assumption, and the vertical line marks the scope of the assumption.
Conditional proofs are useful when the conclusion to be proved is a conditional. The trick is to assume the antecedent and try to derive the consequent, then the conditional follows by the rule.
Note the following: 1. The assumption is not a premise; it's only a premise if it never gets discharged. 2. Once the assumption is discharge, both it and everything in the scope must be ignored - you can't keep using those formulae for further deductions. 2. Several assumptions can be made in a proof. But scope lines must never cross.
There is a related method of proof called Reductio ad Absurdum (RAA) or Indirect Proof.
Suppose we have the following deduction, where Ai are formulae:
1. A1 Premise 2. A2 Assumption 3. A3 Some rule ... n. ~A3 Some rule
Here ~A3 and A3 are deduced from the assumption A2. If we have the following rule
p ~p (RAA) Reductio ad Absurdum ç ... ç ... ç q & ~q ç q & ~q ç ç ~p p
then the deduction can be continued as
ç n+1. A3 & ~A3 3, n, Conj (discharging the assumption on line 2) ç n+2. ~A2 3 - n+1, RAA
Now that we know what is meant by a deduction the formal definition can be introduced.
A deduction is a finite sequence of formulae each of which (a) is a premise, or (b) is an assumption which is discharged before the end of the sequence, or (c) follows by Replacement or Inference Rules from previous formulae which do not occur within the scope of a previously discharged assumption, or (d) follows from an immediately preceding discharge of an assumption by the Conditional Proof Inference Rule.
If a sequence of formulae A1, A2, ..., An, is a deduction and contains the premisses Ai, ..., Aj, then the deduction is a Proof of the Validity of the argument:
Ai ... Aj
An
|
|
|
6.7: Theorems and Contradictions |
|
|
In a deduction with no premisses we must begin with an assumption. For example
1. p & q Assumption ç 2. p 1, Simp ç 3. (p & q) É ~p 1-2, CP
Since there are no Premises, the final formula is a Theorem or a Zero Premise Conclusion. Since no Premises are required it can be inserted anywhere in any deduction.
We therefore extend the deduction definition, to get:
Now that we know what is meant by a deduction the formal definition can be introduced.
A deduction is a finite sequence of formulae each of which (a) is a premise, or (b) is an assumption which is discharged before the end of the sequence, or (c) is a theorem, or (d) follows by Replacement or Inference Rules from previous formulae which do not occur within the scope of a previously discharged assumption, or (e) follows from an immediately preceding discharge of an assumption by the Conditional Proof Inference Rule.
If a sequence of formulae A1, A2, ..., An, is a deduction and contains no premises, then the deduction is a Proof of An and An is a Theorem.
We can use deductions to show sets of formulae are inconsistent, thus: i. make all formulae in the set into premises of a deduction, and ii. deduce a prima facie contradiction.
A prima facie contradiction is a formula of the form (p & ~p).
If we can deduce a contradiction from a set of premises then the set is inconsistent.
|
|
|
6.8: Proof Strategies |
|
|
Here are some hints. Look for the following:
1. If the conclusion is a subformula of one of the premises, try to find a way to extract it from that premise.
2. If the conclusion is a conditional, try assuming the antecedent and deriving the consequent; then CP will give the conclusion.
3. If the conclusion is a conjunction, try deriving each of the conjuncts separately.
4. If the conclusion has a propositional letter that doesn't occur in any premise, then you will probably have to use Add somewhere in the proof.
5. Try using the working backwards strategy. Write down the conclusion and try to find a way to work backwards up the deduction to the premisses
6. Try using Reductio ad Absurdum by assuming the negation of the conclusion.
7. If you're completelry desperate, try randomly applying rules until you see something that gives you inspiration. (This hardly qualifies as a 'strategy'.)
|
|