离散数学期末考试试卷A答案及评分细则.doc

电子科技大学英才学院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(pq)q(p(pq)q(pp)(pq)qpqqtrue (3points)VI. (6%) Devise an algorithm which will find the minimum of n integers. What is the worst case time complexity of this algorithm?a) procedure min(a1, a2, , an: integers) (4points) v := a1 largest element so far for i := 2 to n go thru rest of elems if ai v then v := ai found smaller? at this point vs value is the same as the smallest integer in the listreturn vb) the worst case time complexity of this algorithm is O(n). (2points)VII. (5%) Give the definition of a transitive relation, and Prove or disprove that the union of two transitive relations is transitive.Ans:A relation R on a set A is called transitive if only if (a,b) R and (b,c) R ,then (a,c) R ,for a,b,c A. (2points)The union of two transitive relations may be not transitive. A counter-example:A=1,2,3, R1= , , R2= R1R2=, , which is not transitive. (3points)VIII. (6%) Give an argument using rules of inference to show that the conclusion follows from the hypotheses. List all the steps in your argument.Hypotheses: All computer scientists like Star Trek. Sarah does not like Star Trek. Therefore, Sarah is not a computer scientist.Solution:Hypotheses: x(ComputerScientist(x) Likes(x, StarTrek)Likes(Sarah, StarTrek)Conclusion: ComputerScientist(Sarah)Step 1: x(ComputerScientist(x) Likes(x, StarTrek) (Hypothesis)Step 2: ComputerScientist(Sarah) Likes(Sarah, StarTrek) (Univ. Inst. Step 1)Step