Transcript cmsc203-sep9

CMSC 203
Fall 2004
September 9, 2004
Prof. Marie desJardins
(for Prof. Matt Gaston)
September1999
1
PROOF METHODS
September1999
2
CONCEPTS / VOCABULARY
 Theorems
 Axioms / postulates / premises
 Hypothesis / conclusion
 Lemma, corollary, conjecture
 Rules of inference





Modus ponens (P and P→Q imply Q)
Modus tollens (P→Q and ¬Q imply ¬P)
Hypothetical syllogism (P→Q and Q→R imply that P→R)
Disjunctive syllogism (PQ and ¬P imply Q)
Universal instantiation, universal generalization, existential
instantiation (skolemization or Everybody Loves Raymond),
existential generalization
September1999
October 1999
3
CONCEPTS / VOCABULARY II
 Fallacies
 Affirming the conclusion [abductive reasoning]
 P→Q and Q do not imply P
 Denying the hypothesis
 P→Q and ¬P do not imply ¬Q
 Begging the question (circular reasoning)
 Proof methods






Direct proof (show that P→Q by a series of logical steps from P to Q)
Indirect proof (show that P→Q by proving that ¬Q→¬P)
Proof by contradiction (show P by showing that ¬P implies FALSE)
Trivial proof (show that P→Q by showing that Q is always true)
Proof by cases
Existence proofs (constructive, nonconstructive)
September1999
October 1999
4
Let’s make a proof
 Prove that the premises P1, P2, and P3 imply the
conclusion Q:




P1: Students who work hard will do well on the test.
P2: Students who do well on the test and study will get an A.
P3: Bill is a student who gets a B.
Q: Bill either didn’t work hard or didn’t study.
 General problem-solving approach to proof construction:
1. Restate the problem, writing the premise and conclusion in
mathematical language.
2. Decide what type of proof to use.
3. Apply any relevant definitions, axioms, laws, or theorems to
simplify the premise, make it look more like the conclusion, or
connect (relate) multiple premises.
4. Carefully write down and justify each step of the proof, in a
sequence of connected steps.
5. Write a conclusion statement.
6. Write “Q.E.D.” or □.
September1999
October 1999
5
Restate the problem
 Prove that the premises P1, P2, and P3 imply the
conclusion Q.
 P1: Students who work hard will do well on the test.
 P2: Students who do well on the test and study will get a good
grade.
 P3: Bill is a student who doesn’t get a good grade.
 Q: Bill either didn’t work hard or didn’t study.




P1: x student(x)  work-hard(x) → do-well(x)
P2: x student(x)  do-well(x)  study(x) → good-grade(x)
P3: student(Bill)  ¬good-grade(Bill)
Q: ¬work-hard(Bill)  ¬study(Bill)
September1999
October 1999
6
Restate the problem
 We wish to prove that if
x student(x)  work-hard(x) → do-well(x)
(P1)
and
x student(x)  do-well(x)  study(x) → good-grade(x)
(P2)
and
student(Bill)  ¬good-grade(x),
(P3)
then
¬work-hard(Bill)  ¬study(Bill).
(Q)
September1999
October 1999
7
Select a proof type
 Proof by contradiction
 Negate the proposition to be proved and derive FALSE
 The negation of P1  P2  P3 → Q is P1  P2  P3  ¬Q
 Mini-quiz: why?
 The negated conclusion ¬Q is
¬Q  ¬ (¬work-hard(Bill)  ¬study(Bill))
 ¬¬work-hard(Bill)  ¬¬study(Bill)
De Morgan’s law
 work-hard(Bill)  study(Bill)
Double negation
 (see Table 5, p. 24)
 So if we can prove FALSE from P1  P2  P3  ¬Q, then we can
conclude that P1  P2  P3 → Q.
September1999
October 1999
8
Apply relevant knowledge / Justify
 P1: x student(x)  work-hard(x) → do-well(x)
 (1) student(Bill)  work-hard(Bill) → do-well(Bill)














by P1 and univ. instantiation
[Table 2, p. 62]
P2: x student(x)  do-well(x)  study(x) → good-grade(x)
(2) student(Bill)  do-well(Bill)  study(Bill) → good-grade(Bill)
by P2 and univ. instantiation
P3: student(Bill)  ¬good-grade(Bill)
(3) student(Bill)
by P3 and simplification
[Table 1, p. 58]
(4) ¬good-grade(Bill)
by P3 and simplification
¬Q: work-hard(Bill)  study(Bill)
(5) work-hard(Bill)
by ¬Q and simplification
(6) study(Bill)
by ¬Q and simplification
(7) student(Bill)  work-hard(Bill)
by (3), (5) and conjunction
(8) do-well(Bill)
by (1), (7) and modus ponens
(9) student(Bill)  do-well(Bill) study(Bill)
by (3), (8), (6) and conjunction
(10) good-grade(Bill)
by (2), (9) and modus ponens
(11) good-grade(Bill)  ¬good-grade(Bill)
by (4), (10) and conjunction
FALSE
by (11) and the negation law
[Table 2, p. 24]
September1999
October 1999
9
Write a conclusion statement
 Therefore, P1  P2  P3 → Q.
October 1999
September1999
10
Write “Q.E.D.”
 Q.E.D.
or
□
October 1999
September1999
11
The Proof
 Theorem. If students who work hard will do well on
the test (P1), students who do well on the test and
study will get an A (P2), and Bill is a student who
gets a B (P3), then Bill either didn’t work hard or
didn’t study (Q).
 Proof. By contradiction. Suppose that the
premises hold and the conclusion Q is false (i.e.,
Bill did work hard and did study). Then
 [insert the sequence of steps on slide 13]
Therefore, P1  P2  P3 → Q. □
October 1999
September1999
12
Perfect numbers
 A perfect number is an integer that is equal to the
sum of its proper divisors.
 6 is a perfect number, since 1 + 2 + 3 = 6
 28 is a perfect number, since 1 + 2 + 4 + 7 + 14 = 28
 Show that x=2p-1(2p-1) is a perfect number when
2p-1 is prime.
October 1999
September1999
13
Restate the problem
 Show that x=2p-1(2p-1) is a perfect number when
2p-1 is prime.
 Use the definition of a perfect number to restate
more precisely/mathematically/explicitly.
 Show that the sum of the proper divisors of x=2p1(2p-1) is equal to x when 2p-1 is prime.
October 1999
September1999
14
Select a proof type
 It seems like we should be able to work forward, so
we’ll try a direct proof.
 Common error: Proof by cases, applied to a few
cases. Not valid, because the cases must be
exhaustive, i.e., cover all possible situations:
 odd numbers and even numbers
 negative numbers, positive numbers, and zero
 integers that are 0, 1, or 2 mod 3
October 1999
September1999
15
Apply relevant knowledge
 Often it’s useful to verify the proposition for some
specific instances.
 x=2p-1(2p-1) is a perfect number when 2p-1 is
prime.
 Let p=2. Then 2p-1=3, which is prime, and x=6,
which we already showed to be a perfect number.
 Let p=3. Then 2p-1=7, which is prime, and x=28,
which is also a perfect number.
 Let p=5. Then 2p-1=31, which is prime, and
x=16*31=406. Is that a perfect number? How will
we list its divisors?
October 1999
September1999
16
Apply relevant knowledge, cont.
 Premises:
 x=2p-1(2p-1)
 2p-1 is prime
 What we know about divisors:
 The divisors of x are 2p-1, 2p-1, their divisors, and the products of
their divisors.
 The divisors of 2p-1 are 1, 2, 22, …, 2p-1.
 Since 2p-1 is prime, its only divisors are 1 and 2p-1.
 The proper divisors of x are the unique combinations of these
divisors (except x itself)
 One more step: figure out all the divisors and their sum
October 1999
September1999
17
The Proof
 Theorem. x=2p-1(2p-1) is a perfect number when 2p-1 is
prime.
 Proof. For x to be a perfect number, it must be equal to the
sum of its proper divisors. The divisors of 2p-1 are 1, 2, 22,
..., 2p-1. Since 2p-1 is prime, its only divisors are 1 and
itself. Therefore, the proper divisors of x are 1, 2, 22, ..., 2p1, 2(2p-1), 22(2p-1 ), …, 2p-2(2p-1).
The sum of these divisors is
i=0p-1 2i + (2p-1) i=0p-2 2i
= 2p-1 + (2p-1) (2p-1 – 1)
= (2p-1) (1 + 2p-1 – 1)
= 2p-1 (2p-1)
 Therefore, x=2p-1 (2p-1) is a perfect number.
 Q.E.D.
October 1999
September1999
18