离散数学期末考试_春季_试卷A_答案及评分细则_离散数学期末试卷a

离散数学期末考试_春季_试卷A_答案及评分细则由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学期末试卷a”。

电子科技大学2012-2013学年第 2学期期 末 考试 A 卷

答案及评分细则

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

I.Multiple Choice(15%, 10 questions, 1.5 points each)C, C, B, A, B, B, D, A, B, C II.True or False(10%, 10 questions, 1 point each)F, T, T, T, F, F, F, F, T, F

III.Fill in the Blanks(20%, 10 questions, 2 points each)27=128, [-1,1], (aa)(bb)(cc)(ab)(ba), (12)(23)(33)(42), Some tests are easy, gcd（45，12）=3=12  4  45 (1), 6!, 52, ∀x ∃y(xy 0), {(a,b)2|ab}

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

(1 point for each row)

2.Ans:(a)0123

(3points)

(b)[612).(2points)113.Ans: 001110011100.(one entry 1 point)114.Ans:

(one point for each step)

5.Ans: Encrypted form: CTOA.(one character 1 point)6.Ans: 5  11k.(the inverse of 5 module 11 is 9, 3 points, the result 2 points)7.Ans: The graphs are isomorphic(2 points): A–7, B–4, C–3, D–6, E–5, F–2, G–1.(3 points)

V.(6%)

(a)R is reflexive:(a, b)and(a, b)lie on the same line through the origin, namely on the line y = bx/a(if a≠0), or else on the line x = 0(if a = 0).(1 point)

R is symmetric: if(a, b)and(c, d)lie on the same line through the origin, then(c, d)and(a, b)lie on the same line through the origin.(1 point)R is transitive: suppose(a, b)and(c, d)lie on the same line L through the origin and(c, d)and(e, f)lie on the same line M through the origin.Then L and M both contain the two distinct points(0, 0)and(c, d).Therefore L and M are the same line, and this line contains(a, b)and(e, f).Therefore(a, b)and(e, f)lie on the same line through the origin.(1 point)Note: The proof that R is an equivalence relation can be carried out using analytic geometry: if(a, b)and(c, d)lie on the same nonvertical line through the origin, then the slope must equal b/a because the line paes through(0, 0)and(a, b)and the slope must also equal d/c because the line paes through(0, 0)and(c, d);thus, b/a = d/c, or ad = bc.If(a, b)and(c, d)lie on the same vertical line through the origin, then the points must have the form(0, b)and(0, d), and again it must happen that ad = bc.Therefore,(a, b)R(c, d)means that ad = bc.This equation can be used to verify that R is reflexive, symmetric, and transitive.(b)Each equivalence cla is the set of points of A on a line of the form y = mx or the vertical line x = 0.(2 points)(c)If A is replaced by the entire plane, R is not an equivalence relation.It fails to satisfy the transitive property;for example,(1, 2)R(0, 0)and(0, 0)R(2, 2), but(1, 2)R(2, 2)because the line paing through(1, 2)and(2, 2)does not pa through the origin.(1 point)

VI(7%)

Using the variables: p: Lynn works part time;f: Lynn works full time;t: Lynn plays on the team;b: Lynn is busy, the argument can be written in symbols:

(3 points)If p∨f;t →p;t → b;f Then b

(1 point)One method to find whether the argument is valid is to construct the truth table:

We need to examine all cases where the hypotheses(columns 5, 6, 7, 8)are all true.There is only one case in which all four hypotheses are true(row 5), and in this case the conclusion is also true.Therefore, the argument is valid.(3 points)Alternately, rules of logic can be used to give a proof that the argument is valid.We begin with the four hypotheses and show how to derive the conclusion, b.1.p∨f;premise 2.t →p premise 3.t → b premise 4.f premise 5.p disjunctive syllogism on(1)and(4)

(1 point)6.p → t contrapositive of(2)

7.t modus ponens on(5)and(6)

(1 point)8.b modus ponens on(7)and(3)

(1 point)

VI I(7%)

Ans: {a} {a, b} {a, b, c}

(2points){a, b, c, d} {a, b, c, d, e} {a, b, c, d, e, f}(2points)The shortest path is a-b-c-d-e-f with cost 13.(2points)