Department of Computer Science & Software Engineering Comp232 Mathematics for Computer Science Winter 2017 Assignment 3. Due date: March 30, by 23:59 EDT 1. For each of the following, determine whether it is valid or invalid. If valid then give a proof. If invalid then give a counter example. (a) A B B A. (b) B C A (C A) (B A) = . 2. Let f R Z, where f (x) = 2x 1. (a) Find f (A), where A = {x R 1 x 4}. (b) Find f 1 (B), where B = {9, 8}. 3. Give an example of a function (a) f Z N that is both 1-1 and onto. (b) f N Z that is both 1-1 and onto. 4. Let f Z Z Z Z be defined as f (m, n) = (3m + 7n, 2m + 5n). Is f a bijection, i.e., oneto-one and onto? If yes then give a formal proof, based on the definitions of one-to-one and onto, and derive a formula for f 1 . If no then explain why not. 5. (a) Suppose that Hilberts Grand Hotel is fully occupied, but the hotel closes all even numbered rooms for maintenance. Show that all guests can remain in the hotel. (b) Show that a countably infinite number of guests arriving at Hilbert's fully occupied Grand Hotel can be given rooms without evicting any current guest. 6. If f and f g are one-to-one, does it follow that g is one-to-one? Justify your answer. 7. Let A = {1, 2, 3, 4, 5}. (a) How many total functions f A A are there? (b) How many of the functions in (a) are one-to-one? 8. Suppose f R R and g R R where g(x) = 2x + 1 and g f (x) = 2x + 11. Find the rule for f. 9. Prove or disprove the statements below. (a) For all positive real numbers x and y, x y x y. (b) For all positive real numbers x and y, x y x y. 10. (a) Show that if a b ( mod m) and c d ( mod m), where a, b, c, d, and m are integers with m 2, then a c b d ( mod m). (b) Show that if am b, k and m are integers such that k 1, m 2, and a b ( mod m), then ak bk ( mod m) 1