Transcript Document

Lecture 4: Logic (3)

Methods of proof
2006
• Definitions of theorem
• Rules of inference
• Formal proofs
310205 Mathematics for Comter I
1
4.1. Basic Definitions


A theorem is a mathematical statement that
can be shown to be true.
It is essentially a conditional statement of the
form:
H1  H2    Hn  C
where
Hi are called the hypothesis.
and
C is the conclusion.
2006
310205 Mathematics for Comter I
2
4.1. Basic Definitions

Examples:
• A set with n elements has exactly 2n subsets.
•
2006
or
If S is a set with n elements, then S has
exactly 2n subsets.
If x is a real number and x2 - 1 = 0, then x = -1
or x = 1.
310205 Mathematics for Comter I
3
4.1. Basic Definitions

A theorem can be proved using
•
•
•
other theorems
axioms (statements which are given to be true)
rules of inference.

A lemma (not a “lemon”) is a 'pre-theorem' or a
result which is needed to prove a theorem.

A corollary is a 'post-theorem' or a result which
follows directly from a theorem.

A conjecture is a statement whose truth value
is unknown.
2006
310205 Mathematics for Comter I
4
4.2. Rules of Inference

Rules of inference (or deduction):
2006
•
Logical rules which allow the deduction of conclusions
from premises.
310205 Mathematics for Comter I
5
4.2. Rules of Inference

Examples:
• Given tautology P(PQ)  Q, we have
P
PQ
Q
• This means that whenever P is true and PQ is
•
•
2006
true, we can conclude logically that Q is true.
This rule of inference is the most famous one.
It is called modus ponens or law of detachment.
310205 Mathematics for Comter I
6
4.2. Rules of Inference

Other famous rules of inference:
2006
Rule of Inference
Tautology
Name
P
PQ
P  (P  Q)
Addition
PQ
P
(P  Q)  P
Simplification
P
Q
PQ
((P)  (Q))  (P 
Q)
Conjunction
310205 Mathematics for Comter I
7
4.2. Rules of Inference

Other famous rules of inference:
2006
Rule of Inference Tautology
Name
Q
PQ
 P
[Q  (PQ)] 
P
Modus tollens
PQ
QR
PR
[(P  Q)  (Q  R)] Hypothetical
syllogism
 (P  R)
310205 Mathematics for Comter I
8
4.3. Formal Proofs

To prove an argument is valid or the
conclusion follows logically from the
hypotheses:
• Assume the hypotheses are true.
• Use the rules of inference and logical
equivalences to determine that the conclusion
is true.
2006
310205 Mathematics for Comter I
9
4.3. Formal Proofs

Example:
• Consider the following logical argument:
• If horses fly or cows eat flowers, then mosquito are
birds.
• If mosquitoes are birds, then butter tastes good on
hot dogs.
• But butter tastes terrible on hot dogs.
• Therefore, cows don't eat flowers.
2006
310205 Mathematics for Comter I
10
4.3. Formal Proofs
• Assign propositional variables to the component
propositions in the argument:
• F: Horses fly
• S: Cows eat flower
• M: Mosquitoes are birds
• P: Butter tastes good on hot dogs
• Represent the formal argument using the variables
1. (FS)  M
2. M  P
3. P
S
2006
310205 Mathematics for Comter I
11
4.3. Formal Proofs
• Use the hypotheses 1, 2, and 3 and the rules
of inference and any logical equivalences to
construct the proof.
2006
Assertion
Reasons
1. (FS)  M
Hypothesis 1.
2. M  P
Hypothesis 2.
3. (FS)  P
Step 1 and 2 and hypothetical
syllogism.
4. P
Hypothesis 3.
5. (FS)
Step 3 and 4 and modus tollens
310205 Mathematics for Comter I
12
4.3. Formal Proofs
Assertion
Reasons
6. FS
Step 5 and DeMorgan
7. SF
Step 6 and commutativity
of ‘and’
8. S
Step 7 and simplification
• Q.E.D.
• An abbreviation for the Latin phrase “Quod Erat
Demonstrandum” - “which was to be demonstrated”
• Used to signal the end of a proof.
• Equivalent notations ■
2006
or
□
310205 Mathematics for Comter I
13
4.5. Methods of Proof

We wish to establish the truth of the 'theorem‘
PQ
•
•

P may be a conjunction of other hypotheses.
PQ is a conjecture until a proof is produced.
Several methods:
2006
•
•
•
•
Trivial proof.
Direct proof.
Indirect proof.
Proof by contradiction.
310205 Mathematics for Comter I
14
4.5.1. Trivial Proof

Trivial proof:

Example:
• If we know Q is true then PQ is true.
• If it's raining today then 3 is an odd number.
• The assertion is trivially true independent of the
truth of P.
2006
310205 Mathematics for Comter I
15
4.5.2. Direct Proof

Direct proof:
• Assumes the hypotheses are true.
• Uses the rules of inference, axioms and any
logical equivalences to establish the truth of
the conclusion.

Example 1:
• The Cows don’t eat flowers proof in Section
4.3.
2006
310205 Mathematics for Comter I
16
4.5.2. Direct Proof

Example 2:
• Theorem: If 6x + 9y = 101, then x or y is not
•
an integer.
Proof:
• Assume 6x + 9y = 101 is true.
• Then from the rules of algebra 2x + 3y = 101/3.
• But 101/3 is not an integer so it must be the case
that one of 2x or 3y is not an integer (maybe both).
• Therefore, one of x or y must not be an integer.
• Q.E.D.
2006
310205 Mathematics for Comter I
17
4.5.3. Indirect Proof

Indirect proof:
• Makes use of the law of contrapositive:
•
PQ  QP
A direct proof of the contrapositive:
• assumes the conclusion of PQ is false (Q is true)
• uses the rules of inference, axioms and any logical
equivalences to establish the premise P is false (P
is true).
• Note:
• To show that a conjunction of hypotheses is false it
suffices to show just one of the hypotheses is false.
2006
310205 Mathematics for Comter I
18
4.5.3. Indirect Proof

Example:
•
•
Theorem: If x + y  100, then x  50 or y  50.
Proof:
• Suppose that x and y are some fixed real numbers.
Then it suffices to show that PQ, where:
P: x + y  100,
Q: x  50 or y  50
• Assume that Q is true and show that P is true, where:
Q: x  50 and y  50,
P: x + y  100
• Suppose that x  50 and y  50. Then
x + y  50 + 50 = 100
• Hence P is proved, that is, QP.
• It follows from the law of the contrapositive that PQ.
• Q. E. D.
2006
310205 Mathematics for Comter I
19
4.5.4. Proof by Contradiction

Proof by contradiction:
• Assumes the conclusion Q is false (Q is true)
• Derives a contradiction R (R is false).
• Since (PQ) R is true, but R is false, we
•
•
2006
can conclude that the premise (PQ) is false.
But then its negation (PQ) is true.
This is logically equivalent to the desired
statement PQ.
310205 Mathematics for Comter I
20
4.5.4. Proof by Contradiction

Example:
•
Theorem: There is no largest prime number.
•
Proof:
• Note: There are no formal hypotheses here.
• We assume the conclusion 'there is no largest prime
number' is false, i.e.
•
There is a largest prime number. Call it p.
• Hence, the set of all primes lie between 1 and p.
• Form the product of these primes:
•
•
•
2006
r = 2  3  5  7  11    p.
But r + 1 is a prime larger than p. (Why?).
This contradicts the assumption that there is a largest
prime.
Q.E.D.
310205 Mathematics for Comter I
21
4.5.4. Proof by Contradiction
•
The formal structure of the above proof is as follows:
• Let:
•
•
Q be the assertion that there is no largest prime.
R be the assertion that p is the largest prime.
• Assume Q is true.
• Then (for some p) R is true so QR is true.
• We then construct a prime greater than p so RR.
• Applying hypothetical syllogism we get QR.
• From two applications of modus ponens, we conclude that R
•
2006
is true and R is true. So by conjunction RR or a
contradiction is true.
Hence the assumption must be false, and the theorem is true.
310205 Mathematics for Comter I
22
4.4. Fallacies


Fallacies are incorrect inferences.
Some common fallacies:
• The Fallacy of Affirming the Consequent
• This argument has the form
PQ
Q
P
• which is not a tautology and hence not a rule of inference!
• Example:
• If the butler did it he has blood on his hands.
• The butler had blood on his hands.
• Therefore, the butler did it.
2006
310205 Mathematics for Comter I
23
4.4. Fallacies

Some common fallacies (continued):
• Begging the question or circular reasoning
• This occurs when we use the truth of statement
being proved (or something equivalent) in the proof
itself.
• Example:
• Conjecture: if x 2 is even then x is even.
• Proof: If x 2 is even then x 2 = 2k for some k. Then
assume x = 2m for some integer m, we have …
Hence, x must be even.
2006
310205 Mathematics for Comter I
24
4.6. Further Readings

Methods of proof

Other resources on Logic:
• Rules of inference: Section 3.1.
• Formal proofs: Section 3.1.
• http://people.hofstra.edu/faculty/Stefan_Wane
r/RealWorld/logic/logicintro.html
2006
310205 Mathematics for Comter I
25