离散数学模拟题及部分答案（英⽂）Discrete Mathematic TestEditor: Jin PengDate: 2008.5.6Discrete Mathematic Test (Unit 1) (2)Discrete Mathematic Test (Unit 2) (8)Discrete Mathematic Test (Unit 3) (13)Discrete Mathematic Test 1 (17)Discrete Mathematic Test 2 (22)Appendix1 Answer to Discrete Mathematic Test(Unit 1) (26)Appendix2 Answer to Discrete Mathematic Test 2 (31)Discrete Mathematic Test (Unit 1)In this part, you will have 15 statements. Make your own judgment, and then put T (True) or F (False) after each statement.1. Let A, B, and C be sets such that A∪B=A∪C, then B=C. ( )2. Let A and B be subsets of a set U, and A B, then A△B=A Band A∩B’=. ( ) 3. Let p a nd q and r be three statements. If ~pú~q ≡ ~pú~r, then q and r have the same value. ( )4. Let A, B be sets such that both AíB and A?B is possible. ( )5. Let p and q be two statements, then (p?～q) ?(（～pú～q）(p?～q)) is a tautology.( ) 6.Let A, B be sets, P(A) is the power set of A, then P(A B)=P(A)P(B). ( )7. Let A, B, and C be sets, then if A?B，BíC，then AíC. ( )8. Let A, B be sets, if A={?}, B=P(P(A)), then {?}?B and{?}íB. ( )9. Let x be real number, then x?{x}{{x}} and {x}í{x}{{x}}. ( )10. Let A, B, and C be sets, then A(B∪C) = (A B) ∪(A C). ( )11. If A={x}∪x, then x?A and xíA. ( )12. (x)（P(x)∧Q(x)）and (x)P(x) ∧(x)Q(x) are equivalent. ( )13. Let A and B be sets, then A×(B C)=(A×B) (A×C). ( )14. The argument formula (púq)? (r s), (sút)?w╞ p?w is valid. ( )15. (x)（P(x) ?Q(x)）and (x)P(x) ? (x)Q(x) are equivalent. ( )Part II (1 Foundations: Sets Logic, and Algorithms , 85 Scores)1. (8 points)What sets so each of the Venn diagrams in following Figure represent?2. (8 points)Let U={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Let A={1,5,6,9,10,15} and B={5,6,8,9,12,13}. Determine the following: Find a. SA b. SA’ c. SB d. SA∩B .3. (8 points) A class of 45 students has 3 minors for options, respectively A, B and C. A is the set of students taking algebra, B is the set of students who play basketball, C is the set of students taking the computer programming course. Among the 45 students, 12 choose subject A, 8 choose B and another 6 choose C. Additionally, 9 students choose all of the three subjects.What is the at least number of students do not taking the algebra course and the computer programming course and playing basketball?4. (8 points)Find a formula A that uses the variables p and q such that A is true only when exactly one of p and q is true.5. (8 points)Prove the validity of the logical consequences.Anne plays golf or Anne plays basketball. Therefore, Anne plays golf.6. (9 points)Prove the validity of the logical consequences.If the budget is not cut then prices remain stable if and only if taxes will be raised. If the budget is not cut, then taxes will be raised. If price remain stable, then taxes will not be raised. Therefore, taxes will not be raised.7. (8 points) (1) What is the universal quantification of the sentence: x2 +x is an even integer, where x is an even integer? Is the universal quantification a true statement?(2) What is the existential quantification of the sentence: x is a prime integer, where x is an odd integer? Is the existential quantification a true statement?8. (12 points)Symbolize the following sentences by using predicates, quantifiers, and logical connectives.(1) Any nature number has only one successor number.(2) For all x,y N, x+y=x if and only if y=0.(3) Not all nature number x N, it exist a nature number y N, such that x≤y.9. (8 points)Show that x（～F(x)∨A(x)），x（A(x) →B(x)），x F(x)|= x B(x)10. (8 points)In the bubble sort algorithm, if successive elements L[j] and L[j+1] are such that L[j]>L[j+1], then they are interchanged, that is, swapped. Therefore, the bubble sort algorithm may require elements to be swapped. Show how bubble sort sorts the elements 7 5 6 3 1 4 2 in increasing order. Draw figures.Discrete Mathematic Test (Unit 2)Part I (T/F questions, 15 Scores)In this part, you will have 15 statements. Make your own judgment, and then put T (True) or F (False) after each statement.1.Let A and B be sets such that any subsets of A B is a relation from A to B. ( )2. Let R={(1,1),(1,2),,(3,3) ,(3,1) ,(1,3)} be relations on the set A={1,2,3}then R is transitive. ( )3. Let R={(1,1),(2,2),(2,3),(3,3)} be relations on the set A={1,2,3}then R is symmetric.( ) 4. Let R be a symmetric relation. then Rn is symmetric for all positive integers n.( ) 5. Let R and S are reflexive relations on a set A then maybe not reflexive.( ) 6. Let R={(a,a),(b,b),(c,c) ,(a,b) ,(b,c)} be relations on the set A={a,b,c}then R is equivalence relation. ( )7. If R is equivalence relation,then the transitive closure of R is R. ( )8. Let R be relations on a set A,then R maybe symmetric and antisymmetic. ( )9. If and are partition of a given set A,then ∪ is also a partition of A.( )10.Let R and S are equivalence relations on a set A, Let ψ be the set of all equivalence class of R,and ? be the set of all equivalence class of S, if R≠S, then ψ∩? =Φ. ( ) 11. Let (S,) be a poset such that S is a finite nonempty set,then S has ninimal element,and the elements is unique. ( )12. Let R and S are relations on a set A,then MR∩S MR∧MS. ( )13. If a relation R is symmetric .then there is loop at every vertex of its directed graph.( ) 14. A directed graph of a partial order relation R cannot contain a closed directed path other than loops. ( ) 15. The poset,where P(S) is the power set of a set S is not a chain. ( )Part II (1 Foundations: Sets Logic, and Algorithms , 85 Scores)1. (8 points) Let R be the relation {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)}, and let S be relation {(2, 1), (3, 1), (3, 2), (4, 2)}. Find S R.and R3.2. (8 points)Determine whether the relations represented by the following zero-one matrices are partial orders.3. (8 points)Determine the number of different equivalence relations on a set with three elements by listing them.4. (8 points)Let R ={ (a , b)∈A| a divides b }, where A={1,2,3,4}. Find the matrix MR of R. Then determine whether R is reflexive, symmetric, or transitive.5. (8 points)Determine whether the relation R on the set of all people is reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) R if and only ifa) a is taller than b.b) a and b were born on the same day.c) a has the same first name as b.6. (8 points) Define a equivalence relations on the set of students in your discrete mathematics class .Determine the equivalence classes for these equivalence relations.7. (10 points) Let R be the relation on the set of ordered pairs of positive integers such that if and only if . Show that R is an equivalence relation.8. (8 points) Answer the following questions for the partial order represented by the following Hasse diagram.9. (9 points) Let R be the relation on the set A={a,b,c,d} such that the matrix of R isfind(1) reflexive closure of R.(2) symmetric closure of R.(3) transitive closure of R.10. (10 points)(1)Show that there is exactly one greatest element of a poset, if such an element exists.(2) Show that the least upper bound of a set in poset is unique if it exists.Discrete Mathematic Test (Unit 3)Part I (T/F questions, 15 Scores)In this part, you will have 15 statements. Make your own judgment, and then put T (True) or F (False) after each statement.1. There exist a simple graph with four edges and degree sequence 1,2,3,4. ( )2. There are at least two people whith exactly the same number of friends in any gathering of n>1 people.. ( )3. The number of edges in a complete graph with n vertices is n(n-1). ( )4. The complement of graph G is not possible a subgraph of G. ( )5. Tthat any cycle-free graph contains a vertex of degree 0 or 1.( )6. The graph G, either G or its complement G’, is a connected graph. ( )7. Any graph G and its complement G’ can not be isomorphic ( )8. An Eulerian is a Hamiltonian graph,but a Hamiltonian graph is not An Eulerian .( ) 9. If every member of a party of six people knows at least three people ,prove that they can sit around a table in such a way that each of them knows both his neighbors. ( )10. A circuit either is a cycle or can be reduced to a cycle. ( )11. A graph G with n vertices .G is connected if and only if G is a tree. ( )12. A connected graph is a circuit if the degree of each vertex is 2. ( )13.A circuit either is a cycle or can be reduced to a cycle. ( )14.For any simple connected planar gragh G that X (G) 6. ( )15. ．The sum of the odd degrees of all vertices of a graph is even. ( )Part II (1 Foundations: Sets Logic, and Algorithms , 85 Scores)1. (10 points) Does there exist a simple graph with degree sequence 1,2,3,5? Justify you answer.2. (10 points) Suppose there are 90 small towns in a country. From each town there is a direct bus route to a least 50 towns. Is it possible to go from one town to ant other town by bus possibly changing from one bus and then taking another bus to another town?3. 10 points) Find the number of distinct paths of length 2 in graphs K5.4. (5 points Draw all different graphs with two vertices and two edges.5. (10 points) Determine where the graphs in Figure 1 have Euler trails.If the graph has an Euler trail, exhibit one.6．(10 points) Use a K-map to find the minimized sum-of-product Boolean expressions of the expressions.xyzw+xyzw’+xyx’w’+xy’zw’+x’yzw+x’yzw’+x’y’z’w’+x’y’z’w7. (10 points) Insert 5, 10, and 20, in this order, in the binary search tree of following Figure. Draw the binary search tree after each insertion.8．(8 points) Does there exist a simple connected planar graph with 35 vertices and 100 edges?9. (10 points) Let G be a simple connected graph with n vertices. Suppose the degree of each vertex is at lease n 1. Does it imply the existence of a Hamiltonian cycle in G?Discrete Mathematic Test 1Part I (T/F questions)Directions: in this part, you will have 15 statements. Make your own judgment, and then put T (True) or F (False) after each statement.1. Let A and B be nonempty sets .Then A?B if and only if A-B=?. ( )2. Let A and B be nonempty sets. If B≠Φ，then A-B? A. ( )3. “Is Hangzhou a beautiful city?” This sentence is a statement. ( )4. Let P and Q and R be three statements.if P∧Q≡P∧R,then Q and R have the same value.( ) 5. Let P and Q be two statements.then （～p∨～q）→(p→～q) is not a tautology.( )6. (x)（P(x)∧Q(x)）and (x)P(x) ∧(x)Q(x) are equivalent. ( )7. Let A and B be sets.any subset of A×B is a relation. ( )8.Let A={ 1,2,3}and R=={<1, 1>, <2, 2>, <1, 3>, <3, 1>, <2, 3>},so R is an equivalence Relation on A. ( ) 9.Let R be a relationon set A.then R is an equivalence Relation on A if and only ifR??R. ( ) R10. R is an equivalence Relation on A.R- equivalence class is not a partition of A .( )11.If a mathematical system has an identity,so the cayley table has no equalLines. ( ) 12. Let A be a nonempty set.then Φis identity of (ρ(A)，∩). ( ) 13．The sum of the odd degrees of all vertices of a graph is even. ( )14. Any graph G and its complement G’can not be isomorphic.( )15. A graph G with n vertices .G is connected if and only if G is a tree. ( )Part Ⅱ ( set questions)Directions: in this part,you need to provide solutions for question 16~17 based on the16.Let A,B,and C be sets.Prove A∩(B-C)=(A∩B)-(A∩C).17. A class of 40 students has 3 minors for options, respectively A, B and C. Among the 40 students, 15 choose subject A, 10 choose B and another 6 choose C. Additionally, 5 students choose all of the three subjects. Our question is at least how many students do not choose any subject.Part Ⅲ ( LOGIC questions)Directions: in this part, you need to provide solutions for question 17~19 based on the theory of knowledge logic .18.Show that ～（P∧～Q），～Q∨R ，～R |= ～PPart Ⅳ ( Relations and Posets questions)Directions: in this part,you need to provide solutions for question 20-22 based on the theory of knowledge relations and posets.20.Let A={1,2,3,4},R={(1,2),(2,3),(3,1) }, L={(1,4),(2,2),(3,3),(4,3)},find the transitiv closures of the relations LR .21.Let {A1, A2, A3………An}be a partition of a given set X.Difine a relation R on S asfollows:For all a,b∈X,(a,b) ∈R if and only if there exists Ai such that a,b∈Ai.Prove R is an equivalence relation on X.。
