Transcript CMSC 203 / 0202 Fall 2002

CMSC 203 / 0201
Fall 2002
Exam #1 Review – 27 September 2002
Prof. Marie desJardins
September1999
Survey says…
1(a)
1(b)
1( c)
Moving too fast
3(a)
3(b)
3( c)
3(d)
Don't understand lecture
4
-2 (m. worse) -- 2 (much better)
Worried about grade
Considering dropping
TRUE FALSE
13
12 F
23
3T
1
24 F
6
25
6
1
Lecture OK but not HW
Not enough time on HW
No trouble
AVG:
20
1
19
24
-0.57692
T
T
F
T
T
F
F
F
T
T
F
-1
0
September1999
October 1999
Proposal
 Better balance of straightforward and challenging problems
on homework
 Grading (somewhat) less weighted towards challenging
problems
 More time in class on developing and writing well structured
proofs
 More time in class for students to try to solve problems that
we then work through as a class
 In return: Students agree to review chapter readings
before class so we can spend less time on the basics
without losing everybody.
September1999
October 1999
Let’s make a proof
 HW #2, Problem #1, exercise 1.6.20

If f and fg are one-to-one, does it follow that g is one-to-one?
Justify your answer.
 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.”
September1999
October 1999
Restate the problem
 If f and fg are one-to-one, does it follow that g is one-toone?
 PREMISE 1: “f is one-to-one” iff f(x) = f(y)  x = y for all x,y
in the domain of f.
 Used: Definition of one-to-one
 PREMISE 2: “fg is one-to-one” iff f(g(a)) = f(g(b))  a = b
for all x, y in the domain of g.
 Used: Definition of one-to-one and composition 
 CONCLUSION: “g is one-to-one” iff g(w) = g(z)  w = z for
all w,z in the domain of g.
 Used: Definition of one-to-one
September1999
October 1999
Restate the problem
 If f and fg are one-to-one, does it follow that g is
one-to-one?
 Show that if
xy ( f(x) = f(y)  x = y )
(P1)
and
ab ( f(g(a)) = f(g(b))  a = b ),
(P2)
then
wz ( g(w) = g(z)  w = z ).
(C)
September1999
October 1999
Select a proof type
 Direct proof
 Work from premises to conclusions
 Indirect proof
 Negate the conclusion and derive a contradiction
 In this case, the negated conclusion is
wz ( g(w) = g(z)  w = z )
or
wz ( g(w) = g(z)  w = z )
or
wz ( g(w) = g(z)  (w=z) )
(C´)
September1999
October 1999
Apply relevant knowledge
 Premise 1:
xy ( f(x) = f(y)  x = y )
 Premise 2:
ab ( f(g(a)) = f(g(b))  a = b )
 Negated conclusion:
wz ( g(w) = g(z)  (w=z) )
 Suppose (3) holds. Then  w and z s.t.:
(P1)
(P2)
(C´)
 g(w) = g(z)
(1)
 w <> z
(2)
 Since g(w) = g(z), it must be the cas that f(g(w)) = f(g(z)),
therefore w=z by (P2), which contradicts (2).
September1999
October 1999
Construct a sequence of steps
 Suppose that g is not one-to-one.
 Then (by the definition of “one-to-one”) there must
exist some values w and z in the domain of g such
that g(w) = g(z) and w < > z.
 But since g(w) = g(z), it must be the case that
f(g(w)) = f(g(z)).
 Since fg is one-to-one, it must be the case that
w=z, which contradicts our earlier supposition.
September1999
October 1999
Write a conclusion statement
 Therefore, g must be one-to-one.
September1999
October 1999
Write “Q.E.D.”
 Q.E.D.
September1999
October 1999
The Proof
 Theorem. If f and fg are one-to-one, then g is one-to-one.
 Proof. Suppose that g is not one-to-one. Then (by the
definition of “one-to-one”) there must exist some values w
and z in the domain of g such that g(w) = g(z) and w < > z.
But since g(w) = g(z), it must be the case that f(g(w)) =
f(g(z)). Since fg is one-to-one, it must be the case that
w=z, which contradicts our earlier supposition.
Therefore, g must be one-to-one.
Q.E.D.
September1999
October 1999
Another proof problem
 HW2, P2, exercise 1.6.56
 Suppose that f is an invertible function from Y to Z and g is an
invertible function from X to Y. Show that the inverse of the
composition fg is given by (fg)-1 = g-1f-1.
 f is invertible: there exists a function f-1 such that
yY, f-1(f(y)) = y.
 g is invertible: there exists a function g-1 such that
xX, g-1(g(x)) = x.
 If fg is invertible, there must exist a function
(fg)-1 s.t. fg-1(fg(x)) = x.
 We wish to show that fg-1 = g-1f-1, i.e.,
x, fg-1(x) = g-1(f-1(x))
September1999
October 1999
The Second Proof
 Theorem. If f, g, and fg are invertible, then
(fg)-1 = g-1f-1.
 Proof. Since f, g, and fg are invertible, then their
inverse functions g-1, f-1, and fg-1 must exist. The
inverse function (fg)-1 exhibits the property that
x, fg-1(fg(x)) = x. We show that g-1f-1 exhibits
this property:
x, g-1(f-1(f(g(x))) = g-1(g(x))
= x.
Since f-1 is the inverse of f
Therefore, g-1f-1 is the inverse of fg.
Q.E.D.
September1999
October 1999
The really hard one…
 HW2, P3 part 2, *1.7.22
 Use the technique given in Exercise 19, together with
the result of Exercise 13b, to find a formula for k=1n k2.
September1999
October 1999
Big-O, , 
 HW2, P4, 1.8.8(a,c)
 (a) f(x) = 2x2 + x3 log x
 (c) f(x) = (x4 + x2 + 1) / (x4 + 1)
September1999
October 1999
Perfect numbers
 2.3.16(a) Show that 6 and 28 are perfect.
 The divisors of 6 are 1, 2, and 3. 1+2+3=6; therefore, 6
is a perfect number.
 The divisors of 28 are 1, 2, 4, 7, and 14. 1+2+4+7+14 =
28; therefore, 28 is a perfect number.
September1999
October 1999
Harder perfect numbers
 2.3.16(b) Show that x=2p-1(2p-1) is a perfect
number when 2p-1 is prime.
 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 divisors are 1 and 2p-1.
September1999
October 1999
Harder perfect numbers cont.
 Therefore, the proper divisors of x are 1, 2, 22, …,
2p-1, 2p-1, 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, 2p-1 (2p-1) is a proper number.
 Q.E.D.
September1999
October 1999
Other requested topics
 Sets, inclusion-exclusion
 |AB| = |A| + |B| - |AB|
 *Algorithms, complexity
 *Quantifiers – 1.3.13 – S(x), F(x), A(x,y)
 (b) Every student has asked Prof. G. a question.
 (c) Every faculty member has either asked Prof. M a
question or been asked a question by Prof. M.
 There are exactly two students who have asked Prof. dJ
a question.
 Functions
 Integers and division
September1999
October 1999