电子科技大学英才学院2012 -2013学年第 1学期期 末 考试 A卷离散数学 课程考试题 A 卷 （ 120分钟） 考试形式：闭卷 考试日期 2013 年 月 日课程成绩构成：平时 分， 期中 分， 实验 分， 期末 100 分一二三四五六七八九十合计I. Multiple Choice (15%, 1.5 points each)（A ）1.(pq)(pq) is logically equivalent toa) T b) pq c) F d) pq（A ）2.If P(A) is the power set of A, and A = , what is |P(P(P(A)|?a) 4 b) 24 c) 28 d) 216（C ）3.Which of these statements is NOT a proposition? a) Today is Monday. b) 1+1=2.c) Am I right? d) Go and play with me.（C ）4.Which of these propositions is not logically equivalent to the other three?a) (p q) (r q) b) (p r) qc) (pr) q d) The contrapositive of q (p r)（B ）5.Suppose | A | = 3 and | B | = 8. The number of 1-1 functions f : A B is a) 24 b) P(8,3).c) 38 d) 83（B ）6.Let R be a relation on the positive integers where xRy if x is a factor of y. Whichof the following lists of properties best describes the relation R?a) symmetric, transitiveb) antisymmetric, transitive, reflexivec) antisymmetric, symmetric, reflexived) symmetric, transitive, reflexive（C ）7.Which of the following are partitions of ?a) . b) c) . d) （C ）8.The function f(x)=x2log(x3+78) is big-Oof which of the following functions?a) x2 b) x(logx)3 c) x2logx d) xlogx（A ）9.If , then R is: a) reflexive b) symmetric c) antisymmetric d) transitive.（B ）10.Which of the followings is a function from Z to R?a) . b) .c) d) II. True or False (10%, 1 point each)（T ）1.If 1 2), then p + q is composite.（F ）8.If the relation R is defined on the set Z where aRb means that ab 0, then R is an equivalence relation on Z.（T ）9.(A - B) (A - C) = A - (B C).（T ）10.The set ,a,a, is the power set of some setIII. Fill in the Blanks (20%, 2 points each)1.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”: If I am a criminal them I rob banks.2.P(x,y) means “x + 2y = xy”, where x and y are integers. The truth value of $xyP(x,y) is False. 3.The negation of the statement “No tests are easy.” is some tests are easy.4.If then is .5.Suppose A= x, y. Then is , x, y,x,y.6.Suppose g : AA and f :AA 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 fog =(1,2),(2,3),(3,3),(4,2).7.The sum of 2 + 4 + 8 + 16 + 32 + . + 210 is 211 - 2 .8.The expression of gcd(45, 12) as a linear combination of 12 and 45 is 12 4 + 45 (-1).9.There are 5! permutations of the seven letters A,B,C,D,E,F have A immediately to the left of E.10.The twos complement of -13 is 1 0011 .IV. Answer the Questions (32%, 4points each)：1. Determine whether the following argument is valid:p rq rq r_ pAns:Not valid: p true, q true, r true2. 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?Ans:(a) Assume p, prove q. (b) Assume q, prove p. (c) Assume p q, show that this leads to a contradiction.3. Prove that by giving a proof using logical equivalence.Ans: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).Ans:(a) 0,1,2,3 (b) 6,12).5. Use the definition of big-oh to prove that is O(n3).Ans:, if n 2.6. Solve the linear congruence 5x 3 (mod 11).Ans:5 + 11k.7. Use the Principle of Mathematical Induction to prove that for all n 0.Ans:P(0): , which is true since 1 = 1. P(k) P(k + 1): .8Encrypt the message NEED HELP by translating the letters into numbers, applying the encryption function f (p) = (3p + 7) mod 26, and then translating the numbers back into letters.Ans:Encrypted form: UTTQ CTOA.V. (6%) Without using the truth table, show that the following are tautologiesa) p(pq)q b) p(pq)q Ans:a) p(pq)(pp)(p q)flasep(pq)q falseqfalseqtrueqtrue (3points)b)p(pq)q(p(