Massachusetts Institute of Technology Handout 7 6.042J/18.062J: Mathematics for Computer Science September 12, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 2

Due: 2:35pm in lecture, September 19, 2000.

Self-study: Read: Rosen, Discrete Mathematics and Its Applications, Section 2.3 up to p. 122 Self-study problems: (not to be handed in) Rosen, Section 2.3, exercises 1, 5, 7, 9, 11, 15, 29, 31, 33, 35, 37

Note: The self-study reading covers basic mathematical topics that we will not explicitly cover in lecture. We recommend that you read them and discuss any topics that are unclear to you with your TA during the weekly tutorial. The self-study problems are intended for you to get some practice with the mathematical topics covered by the self-study readings. The weekly mini-quiz will be based on that week’s self-study reading and/or problems.

—————————————————————————– Reading: Velleman, How to Prove It, Chapter 2; Sections 3.3, 6.1-6.4 Rosen, Sections 1.1, 3.1-3.3

Problem 1

(a) Rosen 1.3, 24 (c), (d), (e)

(b) Rosen 1.3, 34

(c) Rosen 1.3, 52

Problem 2

(a) Give a formal reason for each starred line in the following structured proof. Refer to previous steps wherever you think that will be helpful in understanding your proof.

Given: ∀x∀y[P (x) ∨ Q(y)] Prove: (∀xP (x)) ∨ (∀yQ(y))

1. Assume ¬∀xP (x) 2(*). ∃x¬P (x) 3(*). Choose x_{0} such that ¬P (x_{0}). 4(*). ∀y(P (x_{0}) ∨ Q(y))

5. ∀yQ(y)

1. Pick an arbitrary y_{0} 2(*). P (x_{0}) ∨ Q(y_{0})

2 Handout 7: Problem Set 2 3(*). Q(y_{0})

4(*). QED (∀yQ(y))

6(*). QED ((∀xP (x)) ∨ (∀yQ(y)))

(b) Write your own structured proof of the other direction, complete with reasons: Given: (∀xP (x)) ∨ (∀yQ(y)) Prove: ∀x∀y[P (x) ∨ Q(y)]

Problem 3 Rosen 3.2, exercise 16. Problem 4 Velleman 6.1, problem 7 Problem 5 Velleman 6.2, problem 6 Problem 6

(a) What is the smallest natural number h such that towers of all heights greater than or equal to h can be built out of blocks of height 5, 6, and 9?

(b) Prove that h is the smallest such number.

(c) Prove that all heights h or greater can be built of of blocks of height 5, 6, and 9. Problem 7 Velleman 6.4, problem 5 (a) (d) Note: By convention, the book considers F_{1} to be 1, F_{2} to be 1, F_{3} to be 2, and so on. In other places, you may see F_{0} = 1, F_{1} = 1, F_{2} = 2, etc.