离散数学模拟题及部分答案(英文).doc

Discrete Mathematic TestEditor: Jin PengDate: 2008.5.6Contents:Discrete Mathematic Test (Unit 1)3Discrete Mathematic Test (Unit 2)8Discrete Mathematic Test (Unit 3)13Discrete Mathematic Test 117Discrete Mathematic Test 222Appendix1 Answer to Discrete Mathematic Test(Unit 1)27Appendix2 Answer to Discrete Mathematic Test 231Discrete Mathematic Test (Unit 1)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, B, and C be sets such that AB=AC, then B=C. ( )2. Let A and B be subsets of a set U, and AB, then AB=A-B and AB=. ( )3. Let p and q and r be three statements. If pq pr, then q and r have the same value. ( )4. Let A, B be sets such that both AB and AB is possible. ( )5. Let p and q be two statements, then (pq) (（pq）(pq) 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 AB，BC，then AC. ( )8. Let A, B be sets, if A=, B=P(P(A), then B andB. ( ) 9. Let x be real number, then xx-x and xx-x. ( )10. Let A, B, and C be sets, then A- (BC) = (A- B) (A- C). ( )11. If A=xx, then xA and xA. ( )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)=(AB) - (AC). ( )14. The argument formula (pq) (rs), (st)w pw 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. SAB . 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 xN, it exist a nature number y N, such that xy.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 Lj and Lj+1 are such that LjLj+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 AB 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,3then R is transitive. ( )3. Let R=(1,1),(2,2),(2,3),(3,3) be relations on the set A=1,2,3then 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,cthen 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 y and v are partition of a given set A,then yv is also a partition of A.( )10.Let R and S are equivalence relations on a set A, Let y be the set of all equivalence class of R,and v be the set of all equivalence class of S, if RS, then yv =F. ( )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 MRSMRMS. ( )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 if a) 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 is find (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 n1 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+xyxw+xyzw+xyzw+xyzw+xyzw+xyzw7. (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 AB 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 PQPR,then Q and R have the same value. ( )5. Let P and Q be two statements.then （pq）(pq) 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 AB is a relation. ( )8.Let A= 1,2,3and R=, , , , ,so R is an equivalence Relation on A. ( )9.Let R be a relation on set A.then R is an equivalence Relation on A if and only if R. ( )10. 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 equal Lines. ( )12. Let A be a nonempty set.then is identity of (A)，). ( )13The sum of the odd degrees of all vertices of a graph is even. ( )14. Any graph G and its complement Gcan 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 1617 based on the theory of Knowledge Set .16.Let A,B,and C be sets.Prove A(B-C)=(AB)-(AC). 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 1719 based on the theory of knowledge logic .18.Show that （PQ），QR ，R |= P19、show that x（F(x) A(x)），x（A(x)B(x)，$x B(x) |= $x F(x)Part ( 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 transitivclosures of the relations . 21.Let A, A, AAbe a partition of a given set X.Difine a relation R on S as follows: For all a,bX,(a,b) R if and only if there exists A such that a,bA.Prove R is an equivalence relation on X.22.Conseder the poset(S,),where S=k|k%96=0and the relation is the divisibility relation.1)Find all minimal and maximal elements.2)Find all lower bounds of6, 12, 16.3)Find all upper bounds of6, 12, 16.4)Find the glb and lub of 6, 12, 16.Part ( Mathematical system)Directions: in this part,you need to provide solutions for question 23 based on the theory of knowledge mathematical system.23.Show that (G, *) is a monoids,where G=（a,b）a，bR，b0 and（a，b）*(c,d)=(bc+a，bd).Part ( Graph and tree)Directions: in this part,you need to provide solutions for question 24 based on the theory of knowledge graph.24Discrete Mathematic Test 2Part I (T/F questions)Make your own judgment, and then put T (True) or F (False) after each following statement:1）. Let A and B be nonempty sets .Then AB 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 PQ PR, then Q and R have the same value. ( )5）. Let P and Q be two statements. then （pq） (pq) is not a tautology. ( )6）. Let A and B be sets. Any subset of A B is a relation. ( )7）.Let A= 1,2,3,4 and R= (1, 1), (2, 2), (3, 3), (3, 1), (1, 3), (3, 2), (2, 3), so R is an equivalence relation on A. ( ) 8）.Let R be a relation on set A. Then R is an equivalence Relation on A if and only if R. ( )9）. R is an equivalence Relation on A.R- equivalence class is not a partition of A.( )10）The sum of the odd degrees of all vertices of a graph is even. ( )11）. Any graph G and its complement G can not be isomorphic. ( )12）. A graph G with n vertices .G is connected if and only if G is a tree. ( )13）. A circuit either is a cycle or can be reduced to a cycle. ( )14）. A connected graph is a circuit if the degree of each vertex is 2. ( )15）. For any simple connected planar gragh G that X (G) 6. ( )Part 1 Let A, B, and C be sets. Prove A (B - C) = (AB) -（AC). 2Show that （PQ），QR ，R |= P.3Show that x（F(x) A(x)），x（A(x)B(x)，$x B(x) |= $x F(x).4Let A=1,2,3,4, R=(1,2),(2,3),(3,1) , L=(1,4),(2,2),(3,3),(4,3), find the transitive closure of the relations .5Let A, A, AA be a pa