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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- marketing management pdf lecture notes
- strategic management lecture notes pdf
- strategic management lecture notes
- philosophy 101 lecture notes
- philosophy lecture notes
- philosophy of education lecture notes
- financial management lecture notes
- financial management lecture notes pdf
- business management lecture notes
- introduction to philosophy lecture notes
- business management lecture notes pdf
- introduction to management lecture notes