Methods of proof
[Pages:12]Methods of proof
Section 1.6 & 1.7
MSU/CSE 260 Fall 2009
1
Proof Methods
Direct
Direct
Contrapositive Contradiction
p c pc ?pc ?c?p p?c
TT T
T
T
F
TF F
F
F
T
FT T
T
T
F
FF T
T
T
F
MSU/CSE 260 Fall 2009
2
How are these questions related?
1. Does p logically imply c ? 2. Is the proposition (p c) a tautology? 3. Is the proposition (? p c) is a tautology? 4. Is the proposition (? c ? p) is a tautology? 5. Is the proposition (p ? c) is a contradiction?
Proof Methods h1 h2 ... hn c ?
Let p = h1 h2 ... hn . The following propositions are equivalent:
1. p c
2. (p c) is a tautology.
Direct
3. (? p c) is a tautology.
Direct
4. (? c ? p) is a tautology.
Contrapositive
5. (p ? c) is a contradiction.
Contradiction
MSU/CSE 260 Fall 2009
3
MSU/CSE 260 Fall 2009
4
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Formal Proofs
A proof is equivalent to establishing a logical implication chain
Given premises (hypotheses) h1 , h2 , ... , hn and conclusion c, to give a formal proof that the hypotheses imply the conclusion, entails establishing
h1 h2 ... hn c
MSU/CSE 260 Fall 2009
5
Formal Proof
To prove:
h1 h2 ... hn c
Produce a series of wffs,
p1 , p2 , ... pn, c such that each wff pr is:
one of the premises or
a tautology, or
an axiom/law of the domain (e.g., 1+3=4 or x > x+1 )
justified by definition, or
logically equivalent to or implied by
one or more propositions pk
where 1 k < r.
MSU/CSE 260 Fall 2009
p1 p2
.
.
pr
. . .
pn _____ c
Premise Tautology
k, k', Inf. Rule
6
Example
Prove the theorem:
"If integer n is odd, then n2 is odd."
Informal proof:
It is given that n is an odd integer. Thus n = 2k + 1, for some integer k. Thus n2 = (2k + 1)2 = 4k2 + 4k + 1
= 2(2k2 + 2k) + 1 Therefore, n2 is odd.
MSU/CSE 260 Fall 2009
7
Example
h
c
Prove the theorem:
"If integer n is odd, then n2 is odd."
Formal Proof:
1. n is odd
Premise (h)
2. k (n = 2k + 1)
Definition of "odd" (Universe is Integers)
3. n = 2c + 1, for some integer c Step 2, specialization
4. (n = 2c + 1) (n2 = (2c + 1)2) Laws of arithmetic
5. n2 = (2c + 1)2
Steps 3 & 4, modus ponens
= 4c2 + 4c + 1
Laws of arithmetic
= 2(2c2 + 2c) + 1
Laws of arithmetic
6. k (n2 = 2k + 1)
Step 5, generalization
7. n2 is odd
Definition of "odd"
MSU/CSE 260 Fall 2009
8
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Formal Proofs.....
Example:
Given: p q, q r, p.
Prove: r We want to establish the logical implication:
(p q) (q r) p r.
We can use either of the following approaches
Truth Table A chain of logical implications
Note that if A B and B C then A C
MSU/CSE 260 Fall 2009
9
Does (p q) (q r) p r ?
Truth Table Method
p q r pq qr p r
TT T
T
T TT
TT F
T
F TF
TF T
F
T TT
TF F
F
T TF
FT T
T
T FT
FT F
T
F FF
FF T
T
T FT
FF F
T
T FF
MSU/CSE 260 Fall 2009
10
Does (p q) (q r) p r ?
Chain Method
h1 = p q, h2 = q r, h3 = p, c = r We want to prove that h1 h2 h3 c
1. p
Premise
2. p q
Premise
3. q
Steps 1 & 2, modus ponens*
4. q r
Premise
5. r
Steps 3&4, modus ponens
*See Table 1, page 66
MSU/CSE 260 Fall 2009
11
Example
Prove: If 2 is even and if 3 is even and if the sum of any two even integers is even, then all integers greater than 1 and less than 6 are even.
1. 2 is even
Premise
2. 3 is even
Premise
3. n m ((n is even) (n is even) (n+m is even)) Premise
4. (2 is even) (2 is even) (4 is even) Specialization (twice), step 3, math
5. (3 is even) (2 is even) (5 is even) Specialization (twice), step 3, math
6. 4 is even
Conj. & modus ponens, steps 1&4
7. 5 is even
Conj. & modus ponens, steps 1,2,&5
8. (2 is even) (3 is even) (4 is even) (5 is even)
Conj.(many times), steps 1,2,6&7
So this is a bona fide theorem ? the statement is true!
MSU/CSE 260 Fall 2009
12
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Proving conclusions of the form p q
Direct: Assume p, in addition to the given hypotheses, and conclude q.
Contrapositive: Assume ? q, in addition to the given hypotheses, and conclude ? p.
Contradiction: Assume both p and ? q, in addition to the given hypotheses, and conclude False.
Vacuous: Assume the given hypotheses, and conclude ? p.
Trivial: Assume the given hypotheses, and conclude q.
MSU/CSE 260 Fall 2009
13
Example: Direct proof
Prove hypothetical syllogism. Prove: (p q) (q s) (p s)
1. p 2. p q 3. q 4. q s 5. s 6. p s
Assumption Premise 1, 2, modus ponens Premise 3, 4, modus ponens 1, 5, direct method of proof
MSU/CSE 260 Fall 2009
14
Example: Contrapositive proof
Prove hypothetical syllogism. Prove: (p q) (q s) (p s)
1. ? s 2. q s 3. ? q 4. p q 5. ? p 6. p s
Assumption Premise 1, 2, modus tollens Premise 3, 4, modus tollens 1, 5, contrapositive method
MSU/CSE 260 Fall 2009
15
Example: Contradiction proof
Prove hypothetical syllogism. Prove: (p q) (q s) (p s)
1. p 2. ? s 3. q s 4. ? q 5. p q 6. ? p 7. p ? p 8. False 9. p s
Assumption
Assumption
Premise
2, 3, modus tollens
Premise
4, 5, modus tollens
1, 6, conjunction
7, logical equivalence
1, 2, 8, contradiction method
MSU/CSE 260 Fall 2009
16
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Example: Vacuous proof
Prove: If p r and q ? r, then p q s
Equivalently, prove: (p r ) (q ? r ) (p q s)
1. p r 2. ? p r 3. q ? r 4. ? q ? r 5. ? p ? q 6. ? (p q ) 7. p q s
Premise 1, Implication Premise 3, Implication 2, 4, Resolution 5, DeMorgan 6, Vacuously
MSU/CSE 260 Fall 2009
17
Example: Trivial proof
Prove: If p r and ? r, then q ? p
Equivalently, prove: (p r ) ( ? r ) ( q ? p)
1. p r 2. ? r 3. ? p 4. q ? p
Premise Premise 1, 2, modus tollens 3, Trivially
MSU/CSE 260 Fall 2009
18
Non-examples: Vacuous, trivial proofs
Recall hypothetical syllogism. Prove: (p q) (q s) (p s)
Why didn't we give example vacuous or trivial proofs of hypothetical syllogism?
Example
Let h1 = q d h2 = (q d ) ? p h3 = ? p (a ? b) h4 = (a ? b) (r s) c= r s
we want to establish h1 h2 h3 h4 c.
MSU/CSE 260 Fall 2009
19
MSU/CSE 260 Fall 2009
20
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Solution 1
Let
h1 = q d h3 = ? p (a ? b) c= r s
h2 = (q d ) ? p h4 = (a ? b) (r s)
we want to establish h1 h2 h3 h4 c.
1. (q d ) ? p 2. ? p (a ? b) 3. (q d ) (a ? b) 4. (a ? b) (r s) 5. (q d ) (r s) 6. q d 7. r s
Premise Premise 1&2, Hypothetical Syllogism Premise 3&4, HS Premise 5&6, Modus Ponens
MSU/CSE 260 Fall 2009
21
Solution 2
Let
h1 = q d h3 = ? p (a ? b) c = r s,
h2 = (q d ) ? p h4 = (a ? b) (r s)
we want to establish h1 h2 h3 h4 c.
1. q d 2. (q d ) ? p 3. ? p 4. ? p (a ? b) 5. (a ? b) 6. (a ? b) (r s) 7. r s
Premise Premise 1&2, and modus ponens Premise 3&4, modus ponens Premise 5&6, modus ponens
MSU/CSE 260 Fall 2009
22
Example
Question: Is [(? (p q)) (? p q)] (? p q) ?
Different ways to answer the above question
1. By means of the Truth Table. 2. By means of derivation. 3. By formulating it as logical equivalence, that is, as a
"proof".
MSU/CSE 260 Fall 2009
23
Is [(? (p q)) (? p q)] (? p q) ? Truth Table Method
p
q
? (p q) (? p q) LHS RHS Answer
T
T
F
T
T T YES
T
F
T
F
F F YES
F
T
T
T
T T YES
F
F
T
T
T T YES
MSU/CSE 260 Fall 2009
24
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Is [(? (p q)) (? p q)] (? p q) ? Derivation Method
(? (p q)) (? p q)
? (? (p q)) (? p q) (p q) (? p q) ((p q) ? p) q ) (? p (p q)) q ((? p p) (? p q)) q ((T) (? p q)) q (? p q) q (? p) (q q ) (? p) (q) (? p q)
MSU/CSE 260 Fall 2009
25
Is [ (? (p q)) (? p q)] (? p q) ? Logical Equivalence Method
To show S R: show that S R and R S
--------------------------------------------------
In this case, we have
S = [? (p q)) (? p q)]
and
R = (? p q)
MSU/CSE 260 Fall 2009
26
Prove [(? (p q)) (? p q)] (? p q)
1. (? (p q)) (? p q) Premise
2. (p q) (? p q)
1, Implication & double neg.
3. (p (? p q)) (q (? p q)) 2, Distribution
4. (T q) (q ? p)
3, Comm., Assoc, Taut. & Idem.
5. T (q ? p)
4, Domination
6. ? p q
5, Identity, Commutative
Prove (? p q) [(? (p q)) (? p q)]
1. ? p q
Premise
2. (? (p q)) (? p q) Trivially, from 1
MSU/CSE 260 Fall 2009
27
Example
Is the following reasoning logical?
If you are poor then you have no money. If you have money then you are not poor. Therefore, being poor is the same as having no money!
Define the following propositions:
p = "you are poor" q = "you have no money"
Can we conclude that p q given that p q and ?q ?p.
In other words, can we prove that: [(p q) (? q ? p) ] (p q) .
MSU/CSE 260 Fall 2009
28
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
Solution:
Does [(p q) (? q ? p) ] (p q) ?
p q p q ? q ? p ? q ? p LSH p q
TT
T
FF
T
T
T
TF
F
TF
F
F
F
FT
T
FT
T
T
F
FF
T
TT
T
T
T
There is a possibility of not being poor while having no money!
MSU/CSE 260 Fall 2009
29
More Example
Let
h1 = p (q s)
h2 = ? r p h3 = q
c=r s we want to establish h1 h2 h3 c
MSU/CSE 260 Fall 2009
30
Does ( p (q s) ) (? r p) q (r s) ?
1. ? r p 2. r 3. ? (? r ) 4. p
5. p (q s) 6. q s
7. q 8. s
9. r s
Premise Assumption Double negation, 2 Disj. syllogism, 1&3 Premise
Modus ponens, 4&5 Premise Modus ponens, 6&7 Direct proof, 2&8
MSU/CSE 260 Fall 2009
31
General Proof by Contradiction
Proof by contradiction is a general proof method (conclusion can be of any form)
Method:
To prove that h1 h2 ... hn c: Assume ? c, in addition to the hypotheses, and conclude False.
When c has the form p q, we get the "specialized" version presented earlier.
MSU/CSE 260 Fall 2009
32
? 2006 by A-H. Esfahanian. All Rights Reserved.
1-
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- table of logical equivalences
- r e ca p t h e au th o rity o f s c r ip tu r e r e q u i r e s o f u s
- w w ` o w t n t n w a n b w t t d c e b b a n q m r f g c h n g w ` i
- basicargumentforms colorado state university
- ejercicios de derivación lógica nivel medio avanzado
- math 213 logical equivalences rules of inference and examples
- n o o k p q p r s t u i d v w b x d m u p q w k s v q p
- sec 3 6 analyzing arguments with truth tables eiu
- truthtables tautologies andlogicalequivalences
- propositional logic truth tables and predicate logic rosen sections
Related searches
- burden of proof philosophy
- burden of proof science
- burden of proof in argument
- burden of proof examples
- burden of proof logical fallacy
- misplaced burden of proof fallacy
- examples of proof of payment
- burden of proof examples law
- the burden of proof fallacy
- legal burdens of proof chart
- burden of proof in law
- burden of proof vs preponderance of evidence