内容发布更新时间 : 2024/5/20 7:15:42星期一 下面是文章的全部内容请认真阅读。

电子科技大学英才学院2012-2013学年第 2学期期 末 考试 B 卷

答案及评分细则

课程名称： 离散数学 考试形式： 闭卷 考试日期：2013 年 月 日 考试时长：120分钟

I. Multiple Choice (15%, 10 questions, 1.5 points each ) C, D, D, D, B,A, A, D, B,B

II. True or False (10%, 10 questions, 1 point each) F, F, T, F, F, F, F, F, T, T

III. Fill in the Blanks (20%, 10 questions, 2 points each)

0, -84, ?(1?1)?, ?(1?1)?(2?1)?(3?2)?(4?1)?, Roses are not red or violets are not blue, ?x(T(x)?F(x)) , O(n), 1?2, ?x?y (xy <>0)., {(a,b)??|a?b},

2IV. Answer the Questions (35%,7 questions, 5 points each)：

1.

(q?(p??q))??p??(q?(?p??q))??p??((q??p)?(q??q))??p??(q??p)??p???(q??p)??p??(?q?p)??p ???q?(p??p)

Grading rubric: -3 points for making wrong assumptions. -2 points for not being able to complete the proof. -1 to -3 points for illegal usage of equivalence rules.

2. (a) ?0?1?2?3? (3 points) (b) [6?12). (2 points)

3. Ans: A is a knave, B is a knight. (2.5 points each )

4. Ans: A?B?A?B : Let x?A?B . ? x ? A ? B? ? x ? A or x?B? ? x?A

or x?B? ? x?A?B (3 points) Reversing the steps shows that

A?B?A?B .(2 points)

5. Ans: Encrypted form: YZUV. (one character 1 point)

6. Ans: 120 ? 4 ? 450 ? (?1). ( 1 point each step, the result, 2 points)

6n?4n5?46n5?4n510n553???n, if n ? 2.（2 points each step) 7. Ans:

7n2?37n2?n26n23V. (6%) Ans:

Grading rubric: -3 points for making wrong assumptions. -2 points for not being able to complete the proof.

-1 to -3 points for illegal usage of equivalence relation.

VI (7%) Define a recursive function listmax() whose input is a finite set of integers Ln = {x1, x2, . . . , xn} with n ? 2, and whose output is the maximum element in the set. You may assume the existence of a function max({a, b}) whose input is a list of length 2, and whose output is the maximum element of the list. Solution:

function listMax(list l) if(l.length==1) return l[0]; else

return max(l[0],listMax(l.removeFirstElement())

Grading rubric:

2 points for stopping condition. 4 points recusrive formula.

1 point out of 7 for nonrecursive solution.

VII(7%) We will use S(x) to mean “x is a student in this class”, J(x) to mean “x is a Junior”, and P(x) to mean “x passed the final exam”, where the universe for x consists of all people. (2 points) The proof is:

1. ?x (S(x) → J(x)) premise (1 point) 2. ?x(J(x) → P(x)) premise

3. S(Allen) → J(Allen) universal instantiation on (1) (1 point) 4. J(Allen) → P(Allen) universal instantiation on (2) (1 point) 5. S(Allen) → P(Allen) hypothetical syllogism on (3) and (4) (1 point) 6. S(Allen) premise

7. P(Allen) modus ponens on (5) and (6) (1 point)