Spring 2007

Homework

**General Instructions:**

- The numbers refer to the exercises at the end of the listed section
in the textbook.
- Write clearly and legibly. Grading will be based on correctness,
clarity, and whether your solution is of the appropriate length.
- Don't forget to acknowledge all sources of assistance.
Unless otherwise instructed, you must write up your homework
on your own. Turn in your homework together with this
cover sheet.
- Homework is always due at the
**beginning**of class. - You are encouraged to work extra problems: the more you work, the more you will learn. The textbook has a wealth of exercises, and you can check your work with the odd-numbered ones.

- Exercises for Section 1.1 (pp. 16-21):
- Ex. 8
- Ex. 10 (a), (c) and (e)
- Ex. 12
- Ex. 18 (a), (c) and (e)
- Ex. 28 (a), (c) and (e)

- Exercises for Section 1.2 (pp. 28-30):
- Ex. 4 (a)
- Ex. 10 (d)
- Ex. 16
- Ex. 46

- Exercises for Section 1.3 (pp. 46-50):
- Ex. 2
- Ex. 6 (a), (c) and (e)
- Ex. 12 (a), (c) and (e)
- Ex. 24 (d)
- Ex. 58

- Exercises for Section 1.4 (pp. 58-62):
- Ex. 8 (a), (b) and (c)
- Ex. 20 (a) and (c)
- Ex. 24 (c)
- Ex. 30 (a), (c) and (e)
- Ex. 42

- Exercises for Section 1.5 (pp. 72-74):
- Ex. 4 (a), (b) and (c)
- Ex. 14 (b)
- Ex. 18
- Ex. 24

- Exercises for Section 1.6 (pp. 85-86):
- Ex. 6
- Ex. 18
- Ex. 26. What kind of proof did you use?

- Exercises for Section 1.7 (pp. 102-104):
- Ex. 4
- Ex. 6
- Ex. 22. Try backward reasoning.
- Ex. 32. Try to adapt a known proof.

- Exercises for Section 2.1 (pp. 119-121):
- Ex. 6
- Ex. 8 (c) and (e)
- Ex. 12 (*OPTIONAL*)
- Ex. 20. Justify your answer.

- Exercises for Section 2.2 (pp. 130-133):
- Ex. 2 (b) and (d) (*2(b) is OPTIONAL, 2(d) is required*)
- Ex. 12 (*OPTIONAL*)
- Ex. 18 (d)
- Ex. 26 (c)
- Ex. 30 (b). Justify your answer.

- Exercises for Section 2.3 (pp. 146-149):
- Ex. 12 (*12(b) and (c) are OPTIONAL; 12(a) and (d) are required*)
- Ex. 16
- Ex. 70 (b)

- Exercises for Section 2.4 (pp. 160-163):
- Ex. 6 (d)
- Ex. 16 (a)
- Ex. 18 (a)
- Ex. 24 (*OPTIONAL*)
- Ex. 32
- Ex. 42

- Exercises for Section 3.1 (pp. 177-179):
- Ex. 14
- Ex. 26
- Ex. 38

- Exercises for Section 3.2 (pp. 191-193):
- Ex. 4
- Ex. 8. Justify your answers and be sure to indicate the specific C and k for each part.
- Ex. 10
- Ex. 17. (Just read and understand the solution; nothing to turn in)
- Ex. 18
- Ex. 20
- Ex. 24 (a), (b) and (d)

- Exercises for Section 3.3 (pp. 199-200):
- Ex. 8
- Ex. 28 (b)

- Exercises for Section 4.1 (pp. 279-283):
- Ex. 4
- Ex. 6
- Ex. 16
- Ex. 18
- Ex. 20
- Ex. 32
- Ex. 46
- Ex. 48

- Exercise for Section 4.2 (pp. 291-294):
- Ex. 4

- Exercises for Section 4.2 (pp. 308-311):
- Ex. 4, (a) and (b)
- Ex. 12. Use induction.
- Ex. 24. This problem refers to polynomials of the form a_0 + a_1*x + a_2*x^2 + ... + a_n*x^n, where n is any nonnegative integer and the a_i's are integers.
- Read solution to Ex. 31 (nothing to turn in)
- Ex. 44
- Ex. 60
- Read solution to Ex. 61 (nothing to turn in)
- Ex. 62

- Exercises for Section 4.4 (pp. 321-322):
- Ex. 8
- Ex. 10
- Ex. 22
- Ex. 28
- Ex. 44
- Read solution to Ex. 49 (nothing to turn in)

- Exercises for Section 4.5 (pp. 327-328):
- Ex. 4
- Ex. 6. Read the solution to Ex. 5 to discover the rule of inference to use.

- Exercises for Section 7.3 (pp. 482-484):
- Ex. 22
- Ex. 24
- Ex. 28
- Ex. 34
- Ex. 36

- Exercises for Section 5.1 (pp. 344-347):
- Ex. 12
- Ex. 14
- Ex. 24 (a)
- Read solution to Exercise 35 (nothing to turn in)
- Read solution to Exercise 39 (nothing to turn in)
- Ex. 50
- Ex. 58 (don't be put off by the star; it's not hard)

- Exercises for Section 5.2 (pp. 353-354):
- Ex. 10 (read solution to Ex 11 for a hint)
- Ex. 14
- Ex. 26

- Exercises for Section 5.3 (pp. 360-362):
- Ex. 6 (c)
- Ex. 24
- Ex. 26

- Exercises for Section 5.4 (pp. 369-370):
- Ex. 2
- Ex. 4
- Ex. 14
- Ex. 22

- Exercises for Section 8.1 (pp. 527-529):
- Ex. 4
- Ex. 6, (a), (c), (f) and (g)
- Ex. 32 (b), (c) and (d)
- Ex. 34 (a), (d) and (g)
- Ex. 56

- Exercises for Section 8.3 (pp. 542-544):
- Ex. 8 for matrix in Ex 4(a), for reflexive, symmetric, antisymmetric and transitive
- Ex. 14 (a), (b), (c) and (d)
- Ex. 22
- Ex. 32 for directed graph in Ex. 27, for reflexive, symmetric, antisymmetric and transitive
- Ex. 36 for union

- Exercises for Section 8.4 (pp. 553-555):
- Ex. 10
- Ex. 22
- Ex. 26 (c)

- Exercises for Section 8.5 (pp. 562-566):
- Ex. 16
- Ex. 24 (b)

- Exercises for Section 8.6 (pp. 578-581):
- Ex. 6
- Ex. 10
- Ex. 24
- Ex. 32
- Ex. 44 (d)

- Exercises for Section 12.1 (pp. 794-796):
- Ex. 30 (a)

- Exercises for Section 12.3 (pp. 814-817):
- Ex. 26
- Ex. 32

- Exercises for Section 12.4 (pp. 825-827):
- Ex. 6
- Ex. 10