# Discrete Review 1. A relation R over the set S = {x, y, z} is defined by: {(x, x), (x, y), (y, x), (x, z),

Discrete Review 1. A relation R over the set S = {x, y, z} is defined by: {(x, x), (x, y), (y, x), (x, z), (y, z), (y, y), (z, z)} What properties hold for this relation? provide only one answer A. Symmetry only B. Reflexivity only C. Reflexivity and Symmetry D. Antisymmetric E. Reflexivity and Transitivity 2. Let A and B be any sets. Prove the following set identity using the laws of set theory (set identities). Justify each step with the law that you used. 3. Let the relation R = {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, 2)} Find R’, the transitive closure of R. 4. Using the predicate symbols shown and appropriate quantifiers, write each English language statement as a predicate wff. (The domain is the whole world.) B(x) is “x is a ball” R(x) is “x is round” S(x) is “ x is a soccer ball” A) All balls are round. B) Not all balls are soccer balls. C) All soccer balls are round. D) Some balls are not round. 5. For all integers n = 1, prove the following statement using mathematical induction. A) Prove the base step: B) State the inductive hypothesis: C) State what you have to show: D) Proof: 6. Prove the expression below is a valid argument using the deduction method (that is, using equivalences and rules of inference in a proof sequence). 7. Let S {0, 2, 4, 6, 8} and T = {1, 3, 5, 7}. Determine whether each of the following sets of ordered pairs is a function with domain S and co-domain T. A) {(2, 1), (4, 5), (6, 3)} B) {(0, 2), (2, 4), (4, 6), (6, 0), (8, 2)} C) {(6, 3), (2, 1), (0, 3), (8, 7), (4, 5)} D) {(2, 3), (4, 7), (0, 1), (6, 5), (8, 7)} E) {(6, 1), (0, 3), (4, 1), (0, 7), (2, 5), (8, 5)} 8. How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15} to guarantee that at least one pair of these numbers add up to 16? Explain. 9. A set of 4 coins is selected from a box containing 8 dimes and 6 quarters. Show all work. A) Find the number of sets of four coins: B) Find the number of sets in which two are dimes and two are quarters: C) Find the number of sets composed of all dimes or all quarters: D) Find the number of sets with three or more quarters: 10. For each of the following characteristics, determine whether the graph exists or why such a graph does not exist. A) Simple graph with seven nodes, each of degree 3. B) Four nodes, two of degree 2 and two of degree 3. C) Three nodes of degree 0, 1, and 3, respectively. D) Complete graph with four nodes, each of degree 2. 11. Draw the minimum-weight spanning tree (or give a list of edges) for the graph below using Kruskal’s algorithm. Calculus Review 1. Find the limit if it exists.