《离散数学模拟题及部分答案(英文)》由会员分享，可在线阅读，更多相关《离散数学模拟题及部分答案(英文)（37页珍藏版）》请在金锄头文库上搜索。
1、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 Disc
2、rete 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
3、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 powe
4、r 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
5、)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 s
6、o 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.
7、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 th
8、e 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 conseque
9、nces.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, t
10、hen 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
11、: 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
12、 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,
13、 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
