Problem Set I, for Friday, October 12

Mathematics 61

Sets (page 37 in Discrete Source or page 86 in Discrete Mathematics):

• Exercise 54.
• Exercise 66.   If the statement is true, then no proof is required.   If it is false, then give a specific counterexample (rather than an explanation of where an attempted proof might run into difficulty).

Functions (page 51 in Discrete Source or page 100 in Discrete Mathematics):

• Exercise 5.
• Exercise 26.
• Exercise 39.

Sequences and Strings (page 63 in Discrete Source or page 112 in Discrete Mathematics):

• Exercise 121.   (Don't forget that strings can be null.)   For example the string qqr has six substrings: the empty string, q, r, qq, qr, qqr.)   But neither rq nor rr is a substring of qqr.

Relations (page 81 in Discrete Source or page 124 in Discrete Mathematics):

• Exercise 14
• Exercise 36.   Give some brief explanation in each of the five cases.
• Exercise 38, but give the answers as digraphs.
• Exercise 45.   See the above comment for Exercise 66 on Sets.   By "true" is meant "true for all R and S meeting the stated conditions."
• Exercise 54.   The same comment applies.
• Exercise 58.   The same comment applies.

Click here for answers in .pdf format (for Acrobat Reader).