Lecture 2



Lecture 7 Logic (Cont.)

Goals and Objectives:

• Understand rules of inference on quantifiers

• Understand how to use rules of inference to draw conclusions on quantifiers

• Understand how to use different methods to prove theorems

• Understand what are mistakes in proof

Read section 1.5, p.56-73

Methods of Proof (Cont.)

Rules of Inference for Quantified Statement

1. Universal instantiation

If [pic]x P(x), then for a particular x value t, that P(t) is true.

Example.

Let M(x): x is a man, where x refers an object on earth

T(x): x is mortal

Then “all men are mortal” can be represented by

[pic]x (M(x)->T(x))

Hence, M(socrates) -> T(Socrates)

2. universal generalization

If P(t) is true for arbitrarily chosen t, then [pic]x P(x).

3. existential instantiation

If [pic]x P(x), then for some t that P(t) is true.

4. existential generalization

If for some t that P(t) is true, then [pic]x P(x).

Example.

What rules of inference are used in the following:

“All men are mortal. Socrates is a man. Therefore, Socrates is mortal.”

Answer:

Let M(x): x is a man, where x refers an object on earth

T(x): x is mortal

Then “all men are mortal” can be represented by

[pic]x (M(x)->T(x))

5. Hence, by Universal instantiation that

M(socrates) -> T(Socrates)

Given M(Socrates) is true, by Modus ponents that T(Sócrates). That is, Sócrates is mortal.

Questions: p. 73, Exercise #8

II. Fallacies:

(1) fallacy of affirming the conclusion

p -> q

q

__

p

Example.

p: You do all problems in this book.

q: You will get an A in the class.

Error:

If you do all problems in this book, then you will get an A in the

class. And since you will get an A in the class, you do all problems in

this book.

(2) fallacy of denying the hypothesis

p -> q

[pic]p

__

[pic]q

Example.

p: You do all problems in this book.

q: You will get an A in the class.

Error:

If you do all problems in this book, then you will get an A in the

class. And since you didn't do all problems in this book, you will not

get an A in the class.

(3) fallacy of begging the question: circular reasoning

Example.

Prove that if n2 is even, then n is even

Proof:

Given n2 is even, or n2=2m, where m is an integer

Let n=2k, where k is an integer

Therefore, n is even

The proof above is using circular reasoning.

Questions: p. 73, Exercise #13

III. Methods of Proving Theorem

There are basically 2 methods:

• Direct proof:

o Prove conclusion is true by given hypothesis is true and hypothesis-> conclusion

o Prove conclusion is false by finding a counter example

• In-direct proof:

o Prove the contra-positive of the statement

o Prove by contradiction: Assume hypothesis is true and conclusion is false, we find any contradiction

(1) Direct proof: (Assume hypothesis is true)(Given hypothesis p is true, we prove q is true and then we have p -> q is true)

Example. Give a direct proof of the theorem:

If n is odd, then n2 is odd.

Proof:

Since n is odd, n=2k+1,

n2 = 4k2+4k+1=2(2k2+2k)+1 is odd.

(2) Indirect proof: (Assume conclusion is false) since p->q ( [pic]q->[pic]p

If we assume that [pic]q is true and we can prove that [pic]p is true. Then we have p->q is true.

Example. Give an indirect proof of the theorem:

If n is odd, then n2 is odd.

Proof:

Assume n2 is even, or n2 = 2k. That is n2 has 2 in its factor,

then n must also have 2 as its factor since n is an integer

That is, n = 2m, or n is even

(3) Vacuous proof: To show p->q is true, given p is false

p is False

____

p -> q

Example.

Given

P(n): If n>1, then n2 > n

Prove P(0) is true.

Proof:

P(0): If 0>1. then 02 > 0

Since

0>1 is false, therefore P(0) is true.

(4) Trivial proof: To show p->q is true, given q is true

q

____

p -> q

Example.

P(n): If a > = b, a,b are positive integers, then a^n > = b^n

Prove P(0) is true.

Proof:

P(0): If a > = b, a,b are positive integers, then a0 > = b0

Since a0 > = b0, P(0) is true.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download