Assignment No. 4: CIS*1910 - Discrete Structures in Computing I.

Assignment No. 4: CIS*1910 - Discrete Structures in Computing I. Total: 39.5 marks    (The following questions should be submitted and will be marked.) 1.    (1.5 marks) Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. (a)    integers not divisible by 3 (b)    integers divisible by 5 but not by 7 (c)    the real numbers with decimal representations of all 1s or 9s 2.    (1.0 marks) Suppose that Hilbert’s Grand Hotel is fully occupied, but the hotel closes all the even numbered rooms for maintenance. Show that all guests can remain in the hotel. 3.    (1.0 marks) Find f ?g and g ? f, where f(x) = x2 + 1 and g(x) = x + 2 are functions from R to R. 4.    (1.0 marks) Draw the graph of the function f(x) = bx/2c from R to R. 5.    (2.0 marks) Suppose that you know that a golfer plays the first hole of a golf course with an infinite number of holes and that if this golfer plays one hole, then the golfer goes on to play the next hole. Prove that this golfer plays every hole on the course. 6.    (2.0 marks) Prove that 1 * 1!+ 2 *2! + ...+ n * n! = (n + 1)!- 1 whenever n is a positive integer. 7.    (3.0 marks) Let P(n) be the statement that n! < nn, where n is an integer greater than 1. Prove the statement using mathematical induction. (a)    What is the statement P(2)? (b)    Show that P(2) is true, completing the basis step of the proof. (c)    What is the inductive hypothesis? (d)    What do you need to prove in the inductive step? (e)    Complete the inductive step. (f)    Explain why these steps show that this inequality is true whenever n is an integer greater than 1. 8.    (2.0 marks) Prove that if A1,A2,...,An and B1,B2,...,Bn are sets such that Aj ? Bj for j = 1,2,...,n, then . 9.    (1.5 marks) (a)    List all the ordered pairs in the relation R = {(a,b)|adivides b} on the set {1,2,3,4,5,6}. (b)    Display this relation graphically. (c)    Display this relation in tabular form. 10.    (4.0 marks) Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y) ? R if and only if (a)    x + y = 0. (b)    x = ±y. (c)    x - y is a rational number. (d)    x = 2y. (e)    xy = 0. (f) xy = 0. (g)    x = 1. (h)    x = 1 or y = 1. 11.    (2.0 marks) Let R1 = {(1,2),(2,3),(3,4)} and R2 = {(1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(3,4)} be relations from {1,2,3} to {1,2,3,4}. Find (a)    R1 ? R2. (b) R1 n R2. (c) R1 - R2. (d) R2 - R1. 12.    (4.0 marks) Consider the following relations on the set of real numbers. R1 = {(a,b) ? R2|a > b}, the “greater than” relation, R2 = {(a,b) ? R2|a = b}, the “greater than or equal to” relation, R3 = {(a,b) ? R2|a < b}, the “less than” relation, R4 = {(a,b) ? R2|a = b}, the “less than or equal to” relation, R5 = {(a,b) ? R2|a = b}, the “equal to” relation. Find (a)    R1 ? R3. (b)    R1 ? R5. (c)    R2 n R4. (d) R3 n R5. (e)    R1 - R2. (f)    R2 - R1. (g) R1 ? R3. (h) R2 ? R4. 13.    (4.0 marks) Consider the following relations on the set of real numbers. R1 = {(a,b) ? R2|a > b}, the “greater than” relation, R2 = {(a,b) ? R2|a = b}, the “greater than or equal to” relation, R3 = {(a,b) ? R2|a < b}, the “less than” relation, R4 = {(a,b) ? R2|a = b}, the “less than or equal to” relation, R5 = {(a,b) ? R2|a = b}, the “equal to” relation, R6 = {(a,b) ? R2|a 6= b}, the “unequal to” relation. Find (a)    R1 ? R1. (b)    R1 ? R2. (c)    R1 ? R3. (d)    R1 ? R4. (e)    R1 ? R5. (f)    R1 ? R6. (g)    R2 ? R3. (h)    R3 ? R3. 14.    (2.0 marks) Let R be the relation on the set {1,2,3,4,5} containing the ordered pairs (1,1),(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(3,5),(4,2),(4,5),(5,1),(5,2),(5,4). Find (a)    R2. (b)    R3. (c)    R4. (d) R5. 15.    (1.0 marks) Show that the relation R consisting of all pairs (x,y) such that x and y are bit strings of length three or more that agree except perhaps in their first three bits is an equivalence relation on the set of all bit strings of length three or more. 16.    (1.0 marks) Let R be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) ? R if and only if ad = bc. Show that R is an equivalence relation. 17.    (2.0 marks) What is the congruence class [4]m when m is (a)    2?(b) 3? (c) 6? (d) 8? 18.    (2.5 marks) Which of these collections of subsets are partitions of the set of integers? (a)    the set of even integers and the set of odd integers (b)    the set of positive integers and the set of negative integers (c)    the set of integers divisible by 3, the set of integers leaving a remainder of 1 when divided by 3, and the set ofintegers leaving a remainder of 2 when divided by 3 (d)    the set of integers less than -100, the set of integers with absolute value not exceeding 100, and the set of integersgreater than 100 (e)    the set of integers not divisible by 3, the set of even integers, and the set of integers that leave a remainder of 3 when divided by 6 19.    (2.0 marks) List the ordered pairs in the equivalence relations produced by these partitions of {a,b,c,d,e,f,g}, (a)    {a,b}, {c,d}, {e,f,g} (b)    {a}, {b}, {c,d}, {e,f}, {g} (c)    {a,b,c,d},{e,f,g} (d)    {a,c,e,g}, {b,d}, {f}