国际软工1302班《离散数学》第一份.doc

Final-Exam of International College, Semester 2 of 2014-2015 Discrete Mathematics Test form: Open-book exam Teachers: David Paper created by: David For Grade 2013 Undergraduate (Bachelor) Whether scratch paper needed: N ( )/Y ( )Major: _Class: _ Name: _Student No.: _ Class No.: _PartsIIIIIITotalSignatureScore Notes: 1 Answers need to be written on the exam papers. 2 Students are not allowed to take away exam papers out of the exam room.Part I- True or False (20 points, 1 points for each) ScoreSignature1. If T is a tree with 17 vertices, then there is a simple path in T of length 17.2. There is a tree with degrees 3, 3, 2, 2, 1, 1, 1, 1.3. If two trees have the same number of vertices and the same degrees, then the two trees are isomorphic.4. Every tree is planar.5. 1 + 1 = 3 if and only if 2 + 2 = 3. 6. If 2 + 1 = 3, then 2 = 3 1. In the following questions suppose A = x, y and B = x, x. 7 8 In the following questions suppose A = a, b, c. 9 10 In the following questions suppose A = 1, 2, 3, 4, 5.11 12 13 In the following questions, suppose A = a, b, c and B = b, c. 14 15 16 17 Assume that the statement applies to all sets.18 19 20 Part II - Short answer questions (40 points, 2 points for each)ScoreSignatureWhat is the negation of the propositions in the following?21 Abby has more than 300 friends on facebook.22. Prove that (q (p q) p is a tautology using propositional equivalence and the laws of logic.23. Suppose you are allowed to give either a direct proof or a proof by contraposition of the following: if 3n + 5 is even, then n is odd. Which type of proof would be easier to give? Explain why.24. For each of the pairs of sets in the following determine whether the first is a subset of the second, the second is a subset of the first, or neither is a subset of the other.The set of students studying a programming language, the set of students studying Java.25. Prove or disprove: .26. Prove that by giving an element table proof.27. Prove that by giving a proof using logical equivalence.28. Find three subsets of 1, 2, 3, 4, 5, 6, 7, 8, 9 such that the intersection of any two has size 2 and the intersection of all three has size 1.In the following questions, suppose that g:A B and f:B C where A = B = C = 1, 2, 3, 4, g =(1, 4), (2, 1), (3, 1), (4, 2), and f = (1, 3), (2, 2), (3, 4), (4, 2).29. Find 30. Find In the following questions suppose g:A B and f:B C where A = 1, 2, 3, 4, B = a, b, c, C = 2, 8, 10, and g and f are defined by g = (1, b), (2, a), (3, b), (4, a) and f = (a, 8), (b, 10), (c, 2).31. Find.32. Explain why is not a function.33. Find f(2) and f(3) if f(n) = 2f(n 1) + 6, f(0) = 3.34 What is the probability that a randomly selected day of the year (366 days) is in May?Major: _Class: _ Name: _Student No.: _ Class No.: _35. List the reflexive relations on the set 0, 1.In the following questions , determine whether the binary relation is:（1）reflexive, (2) symmetric, (3) antisymmetric, (4) transitive.36 . The relation R on w, x, y, z where R = (w,w), (w, x), (x,w), (x, x), (x, z), (y, y), (z, y), (z, z).In the following questions , suppose R and S are relations on a, b, c, d, where R = (a, b), (a, d), (b, c), (c, c), (d, a) and S = (a, c), (b, d), (d, a). Find the combination of relations.37 . R2.In the following questions, find the matrix that represents the given relation. Use elements in the order given to determine rows and columns of the matrix.38. R on 1, 2, 3, 4 where aR b means.39. Which of the following are partitions of 1, 2, 3, . . . , 10?(a) 2, 4, 6, 8, 1, 3, 5, 9, 7, 10. (b) 1, 2, 4, 8, 2, 5, 7, 10, 3, 6, 9.(c) 3, 8, 10, 1, 2, 5, 9, 4, 7, 8. (d) 1, 2, . . . , 10.(e) 1, 2, . . . , 10.In the following questions , either give an example or prove that there are none.40. A simple digraph with indegrees 0, 1, 1, 2 and outdegrees 0, 1, 1, 1.Part III Graphing and Table Problems (40 points, 5 points for each)ScoreSignature41. Consider the graph at the right.(a) Does it have an Euler circuit?(b) Does it have an Euler path?(c) Does it have a Hamilton circuit?(d) Does it have a Hamilton path?42. Draw all nonisomorphic trees with 5 vertices.43. Write the truth table for the proposition (r q) V (p r).44. Construct a combinatorial circuit using inverters, OR gates, and AND gates, that produces the outputs in the following from input bits p, q and r. 45 Prove that by giving a Venn diagram proof.46. Draw the directed graph for the relation defined by the matrix .47. A simple digraph with indegrees 0, 1, 2 and outdegrees 0, 1, 2.48. Draw the undirected graph with adjacency matrix