II. HomeworkHomework 1 Basic Techniques 1 CS 341 Homework 1 Basic Techniques 1. What are these sets? Write them using braces, commas, numerals, … (for infinite sets), and ∅ only. (a) ({1, 3, 5} ∪ {3, 1}) ∩ {3, 5, 7} (b) ∪{{3}, {3, 5}, ∩{{5, 7}, {7, 9}}} (c) ({1, 2, 5} - {5, 7, 9}) ∪ ({5, 7, 9} - {1, 2, 5}) (d) 2{7, 8, 9} - 2{7, 9} (e) 2∅ (f) {x : ∃y ∈ N where x = y2} (g) {x : x is an integer and x2 = 2} 2. Prove each of the following: (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (c) A ∩ (A ∪ B) = A (d) A ∪ (A ∩ B) = A (e) A - (B ∩ C) = (A - B) ∪ (A - C) 3. Write each of the following explicitly: (a) {1} × {1, 2} × {1, 2, 3} (b) ∅ × {1, 2} (c) 2{1,2} × {1, 2} 4. Let R = {(a, b), (a, c), (c, d), (a, a), (b, a)}. What is R ° R, the composition of R with itself? What is R-1, the inverse of R? Is R, R ° R, or R-1 a function? 5. What is the cardinality of each of the following sets? Justify your answer. (a) S = N - {2, 3, 4} (b) S = {∅, {∅}} (c) S = 2{a, b, c} (d) S = {a, b, c} × {1, 2, 3, 4} (e) S = {a, b, … , z} × N 6. Consider the chart of example relations in Section 3.2. For the first six, give an example that proves that the relation is missing each of the properties that the chart claims it is missing. For example, show that Mother-of is not reflexive, symmetric, or transitive. 7. Let A, B be two sets. If 2A = 2B, must A = B? Prove your answer. 8. For each of the following sets, state whether or not it is a partition of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. (a) {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}} (b) {∅, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}} (c) {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}} (d) {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10}} 9. For each of the following relations, state whether it is a partial order (that is not also total), a total order, or neither. Justify your answer. (a) DivisibleBy, defined on the natural numbers. (x, y) ∈ DivisibleBy iff x is evenly divisible by y. So, for example, (9, 3) ∈ DivisibleBy but (9, 4) ∉ DivisibleBy.Homework 1 Basic Techniques 2 (b) LessThanOrEqual defined on ordered pairs of natural numbers. (a, b) ≤ (x, y) iff a ≤ x or (a = x and b ≤ y). For example, (1,2) ≤ (2,1) and (1,2) ≤ (1,3). (c) The relation defined by the following boolean matrix: 1 1 1 1 1 1 1 1 10. Are the following sets closed under the following operations? If not, what are the respective closures? (a) The odd integers under multiplication. (b) The positive integers under division. (c) The negative integers under subtraction. (d) The negative integers under multiplication. (e) The odd length strings under concatenation. 11. What is the reflexive transitive closure R* of the relation R = {(a, b), (a, c), (a, d), (d, c), (d, e)} Draw a directed graph representing R*. 12. For each of the following relations R, over some domain D, compute the reflexive, symmetric, transitive closure R′. Try to think of a simple descriptive name for the new relation R′. Since R′ must be an equivalence relation, describe the partition that R induces on D. (a) Let D be the set of 50 states in the US. ∀xy, xRy iff x shares a boundary with y. (b) Let D be the natural numbers. ∀xy, xRy iff y = x+3. (c) Let D be the set of strings containing no symbol except a. ∀xy, xRy iff y = xa. (i.e., if y equals x concatenated with a). 13. Consider an infinite rectangular grid (like an infinite sheet of graph paper). Let S be the set of intersection points on the grid. Let each point in S be represented as a pair of (x,y) coordinates where adjacent points differ in one coordinate by exactly 1 and coordinates increase (as is standard) as you move up and to the right. (a) Let R be the following relation on S: ∀(x1,y1)(x2,y2), (x1,y1)R(x2,y2) iff x2= x1+1 and y2=y1+1. Let R′ be the reflexive, symmetric, transitive closure of R. Describe in English the partition P that R′ induces on S. What is the cardinality of P? (b) Let R be the following relation on S: ∀(x1,y1)(x2,y2), (x1,y1)R(x2,y2) iff (x2= x1+1 and y2=y1+1) or (x2= x1-1 and y2=y1+1). Let R′ be the reflexive, symmetric, transitive closure of R. Describe in English the partition P that R′ induces on S. What is the cardinality of P? (c) Let R be the following relation on S: ∀(x1,y1)(x2,y2), (x1,y1)R(x2,y2) iff (x2,y2) is reachable from (x1,y1) by moving two squares in any one of the four directions and then one square in a perpendicular direction. Let R′ be the reflexive, symmetric, transitive closure of R. Describe in English the partition P that R′ induces on S. What is the cardinality of P? 14. Is the transitive closure of the symmetric closure of a binary relation necessarily reflexive? Prove it or give a counterexample. 15. Give an example of a binary relation that is not reflexive but has a transitive closure that is reflexive. 16. For each of the following functions, state whether or not it is (i) one-to-one, (ii) onto, and (iii) idempotent. Justify your answers. (a) +: P × P → P, where P is the set of positive integers, and +(a, b) = a + b (In other words, simply addition defined on the positive integers) (b) X : B × B → B, where B is the set {True, False}Homework 1 Basic Techniques 3 X(a, b) = the exclusive or of a and b 17. Consider the following set manipulation problems: (a) Let S = {a, b}. Let T = {b, c}. List the elements of P, defined as P = 2S ∩ 2T. (b) Let Z be the set of integers. Let S = {x ∈ Z: ∃y ∈ Z and x = 2y}. Let T = {x ∈ Z: ∃y ∈ Z and x = 2y}. Let W = S – T. Describe W in English. List any five consecutive elements of W. Let X = T – S. What is X? Solutions 1. (a) {3, 5} (b) {3, 5, 7} (c) {1, 2, 7, 9} (d) {8}, {7, 8}, {8, 9}, {7, 8, 9} (e) {∅} (f) {0, 1, 4, 9, 25, 36…} (the perfect squares) (g) ∅ (since the square root of 2 is not an integer) …
View Full Document
Unlocking...