双语教师的考核激励制度与应用电子科技大学2011 -2012学年第 2学期期 末 考试 A 卷
课程名称： 离散数学 考试形式： 闭卷 考试日期： 2012 年 6 月 日 考试时长：120分钟 课程成绩构成：平时 10 %， 期中 20 %， 实验 0 %， 期末 70 % 本试卷试题由____ _部分构成，共_____页。
题号 得分 一 二 三 四 五
六 七 八 九 十 合计 I.
（ ） （ ） （ ） （ ）
（ ）
（ ）
（ ）
Multiple Choice (15%)
1. (?p∧q)→(p∨q) is logically equivalent to
a) T b) p∨q c) F d)?? p∧q 2. If P(A) is the power set of A, and A = , what is |P(P(P(A)))|?
4816
a) 4 b) 2 c) 2 d) 2 3. Which of these statements is NOT a proposition?
a) Tomorrow will be Friday. b) 2+3=4.
c) There is a dog. d) Go and play with me.
4. The notation Kn denotes the complete graph on n vertices. Kn is the simple graph that
contains exactly one edge between each pair of distinct vertices. How many edges comprise a K20?
a) 190 b) 40 c) 95 d) 380
5. Suppose ? A ? ? 5 and ? B ? ? 9. The number of 1-1 functions f ? A ? B is
a) 45 b) P(9?5). c) 59 d) 95
6. Let R be a relation on the positive integers where xRy if x divides y. Which
of the following lists of properties best describes the relation R?
a) reflexive, symmetric, transitive b) reflexive, antisymmetric, transitive c) reflexive, symmetric, antisymmetric d) symmetric, transitive 7. Which of the following are partitions of U?{1,2,3,4,5,6,7,8}?
a) {1},{1,2,3},{3,4,5,6,7,8} b) {1},{2,3},{3,4,5,6,7,8}
（ ） 8. （ ） 9.
c) {1,4,7},{2,3},{5,6,8} d) {1,2},{2,3},{4,5,6,7,8}
The function f(x)=3x2log(x3+21) is big-Oof which of the following functions? a) x3 b) x2(logx)3 c) x2logx d) xlogx In the graph that follows, give an explanation for why there is no path from a back to a that passes through each edge exactly once.
页脚内容6
双语教师的考核激励制度与应用a) There are vertices of odd degree, namely {B,D}. b) There are vertices of even degree, namely {A,C}. c) There are vertices of even degree, namely {B,D}. d) There are vertices of odd degree, namely {A,C}.
（ ） 10. Which of the followings is a function from Z to R?
2
a) f(n)??(n?1). ` b) f(x)?x?1. c) f(x)? II. True or False (10%)
（ ） 1. If 3 ? 2, then 7 ? 6. （ ） 2. （ ） 3. （ ） 4. （ ） 5. （ ） 6. （ ） 7. （ ） 8.
p ∧ (q ∨ r)≡ (p ∧ q) ∨ r
If A, B, and C are sets, then (A-C)-(B-C)=A-B. Suppose A ? ?a?b?c?, then ??a?? ? P(A).
x d) f(n)?1
n2?1h(x)?x?100 is defined as a function with domain R and codomain R.
Suppose g ? A ? B and f ? B ? C, where f ? g is 1-1 and f is 1-1. g must be 1-1? If p and q are primes (? 2), then p ? q is composite.
If the relation R is defined on the set Z where aRb means that ab ? 0, then R is an equivalence relation on Z.
（ ） 9. Every Hamilton circuit for Wn has length n .
（ ） 10. There exists a simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7.
1. 2. 3. 4. 5. 6. 7.
III. Fill in the Blanks (20%)
Let p and q be the propositions “I am a criminal” and “I rob banks”. Express in simple English the proposition “if p then q”: .
P(x?y) means “x ? 2y ? xy”, where x and y are integers. The truth value of ?x?yP(x?y) is . The negation of the statement “No tests are easy.” is . ??11If Ai?{x|x?R???x?} then Aiis . iii?1Suppose A???x??y?. Then P(A) is . Suppose g ??A?A and f ?A?A where A??1?2?3?4?,g???(1??4)??(2?1)??(3?1)??(4?2)??and
f??(1?3)?(2?2)?(3?4)?(4?2)?.Then f?g =?????????????????????????????????????????????????. The sum of 2 ? 4 ? 8 ? 16 ? 32 ? ??? ? 210 is .
页脚内容6
双语教师的考核激励制度与应用8. 9.
The expression of gcd(45, 12) as a linear combination of 12 and 45 is . There are permutations of the seven letters A,B,C,D,E,F have A immediately to the left of E.
10. If G is a planar connected graph with 18 vertices, each of degree 3, then G has _ __ regions. IV. Answer the Questions (32%)：
1. Determine whether the following argument is valid:
p ? r q ? r q ? ?r ________ ? ?p
2. Suppose you wish to prove a theorem of the form “if p then q”. (a) If you give a direct proof, what do you assume and what do you prove? (b) If you give an indirect proof, what do you assume and what do you prove? (c) If you give a proof by contradiction, what do you assume and what do you prove?
3. Prove that A?B?A?B by giving a proof using logical equivalence.
6
页脚内容双语教师的考核激励制度与应用4. Suppose f ? R ? R where f(x) ? ?x?2?. (a) If S ? ?x ? 1 ? x ? 6?, find f(S). (b) If T ? ?3?4?5?, find f?1(T).
5. Use the definition of big-oh to prove that 6n?4n5?47n2?3 is O(n3).
6. Solve the linear congruence 5x ? 3 (mod 11).
3n?17. Use the Principle of Mathematical Induction to prove that 1?3?9?27?????3n??12n ? 0.
??1111?8. Draw the directed graph for the relation defined by the matrix?0111???0011??. ?0001??
页脚内容6
for all
双语教师的考核激励制度与应用 V. (6%) Without using the truth table, show that the following are tautologies
a) [?p?(p?q)]→q b) [p?(p→q)]→q
VI. (6%) Devise an algorithm which will find the minimum of n integers. What is the worst case
time complexity of this algorithm?
VII. (5%) Give the definition of a transitive relation, and Prove or disprove that the union of
two transitive relations is transitive.
页脚内容6
双语离散数学期末考试_2012年春季_试卷A
