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.

Google Online Preview   Download