电大 离散数学 期末考试历届真题试卷

电大 离散数学 期末考试历届真题试卷（2篇）

1.电大 离散数学 期末考试历届真题试卷 篇一

电子科技大学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 passes through(0, 0)and(a, b)and the slope must also equal d/c because the line passes 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 class 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 passing through(1, 2)and(2, 2)does not pass 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)

2.离散数学期末考试 篇二

1、设集合M={a，}，N ={{a}，}则MN=（）。A、 B、{} C、{a} D、{{a}，，a}

2、设关系F={<1，a >，<2，2>，}，G={，，<1，2>}则 FG=（）。

A、{<1，b>，<1，c>，}

B、{，，<1，b>} C、{，<1，2>}

D、{，<2，2>，<1，b>}

3、设集合H={1，2，3，4}，则H上的关系R={

。x +y是偶数}具有（）A、自反性、反对称性和传递性

B、反自反性、反对称性和传递性

C、反自反性、对称性和传递性

D、自反性、对称性和传递性

4、设T是一棵完全二叉树，则T的每个结点都（）。

A、至少有两个子结点

B、至多有两个子结点

C、恰有两个子结点

D、可以有任意多个子结点

5、设R是实数集，“+，—，A、

>是群

B、是群

 >是半群

D、是独异点

6、下面关系中，函数关系是（）。

A、{，，}

B、{，，<1，x>} C、{<1，y>，<1，x>，}

D、{，，}

7、设是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足（）。

A、结合律

B、交换律

C、分配律

D、幂等律

8、设Z是整数集，“—”是整数减法，则下列说法正确的是（）。A、不是代数系统

B、的单位元是0

C、是代数系统

D、的单位元是1

9、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（）。A、简单通路

B、初级通路

C、简单回路

D、初级回路

10、设G有6个3度点，2个4度点，其余顶点的度数均为0，则G的边数是（）。A、10

B、13

C、11

D、6

二、填空题(本大题共8题，共10个空，每空2分，共20分)

1、设关系R={，<2，1>，<2，b>}，则R逆关系R1=_______________________________。

2、在代数系统（Q是有理数集，“+”是有理数加法）中，单位元是______，2的逆元是___________。

3、设集合M={1，2，3，5}，则M的幂集P（M）包含___________个元素。

4、设T是一棵有n(n2)个顶点的树，则T有_____________条边。

5、设是一个代数系统，是S上的二元运算，若存在S，对任意xS，有x=x=，则称是的_______________。

6、设是一个代数系统，若满足结合律且中有单位元，则称为一个___________________。

7、设D是有向图，若D的基图是连通图，则称D是_________________图

8、既不含________________也不含____________________的无向图称为简单图。

三、计算题(本大题共3小题，每小题10分，共30分)

1、用等值演算法求公式A=(pq)(pr)的主析取范式。

2、求公式x(Q(x)G(x，s))(yP(y)zH(y，z))的前束范式。

3、设集合A={1，2，3，4，5}，关系R={（1）列出R的所有元素；（2）写出R的关系矩阵Mx，y A且x整除y}，要求：

R；

（3）求偏序集的极大元、极小元和最小元。

四、应用题(本大题共2小题，每小题5分，共10分)

1、用命题公式将下列命题符号化： 2和5是偶数，当且仅当5>2。

2、用谓词公式将下列命题符号化：

每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。

五、证明题（本大题共2小题，每小题10分，共20分）

1、在命题逻辑系统中用归结法证明下列推理是有效的： 前提：sq，pq，s 结论：p

2、在谓词逻辑系统中写出下列推理的（形式）证明：

前提：x(M(x)P(x))，x(M(x)G(x))，x(G(x))结论：xP(x)

计算题

6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。

7.(9分)设一阶逻辑公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A = {a, b, c, d}.R是A上的二元关系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)画出r(R), s(R), t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：

(1)G =(P∧Q)∨(P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(P∧R))13.设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝

{(a, b),(b, c),(b, d),(d, d)}.(1)试写出R和S的关系矩阵；(2)计算R•S, R∪S, R1, S1•R1.－

－

－证明题

1.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C = A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。4.(本题10分)A, B为两个任意集合，求证：

A－(A∩B)=(A∪B)－B.答案：

1-5

BADBB 6-10 BBABB

1.{<1，a>，<1，2>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱连通 8.平行边

环 三．

(pq)(pr)(pq)(pr)1.(pqr)(pqr)(pqr)(pqr)m011m010m111m1012.x(Q(x)G(x,s))yz(P(y)H(y,z))

yzx((Q(x)G(x,s))(P(y)H(y,z))3.(1)R{1,1,2,2,3,3,4,4,5,5,1,2,1,3,1,4,1,5,2,4}

12(2)MR345123451111101010

（3）最小元=1 极小元=1 极大元=5 001000001000001四

1.令p表示2是偶数；令q表示5是偶数；r表示5>2；

(pq)r

2.S（x）：x是计算机专业的学生；G（x）：x要学《编译原理》； F（x）：x学经济学；

x(S(x)G(x))x(S(x)F(x))

五 1，（1）

s

前提引入（2）

sq

前提引入（3）

qs

置换规则

（4）

q

1,3析取三段论（5）

pq

前提引入（6）

p

4,5拒取

（1）

x(M(x)G(x))

前提引入（2）

M（x）v G（x）

EI规则（3）

x(G(x))

前提引入（4）

G(x)（5）

M(x)

AI规则

2,4析取三段论

（6）

x(M(x)P(x))

前提引入（7）

M(x)→P（x）

AI规则（8）

P（x）

5,7假言推理（9）

xP(x)

EG规则

6.G = (P→Q)∨(Q∧(P→R))

= (P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x)

= (xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)= xyz((P(x)∧Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)

关系图: abr(R)dcabs(R)dabt(R)dc c

11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3 ＝(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝(3, 6, 7)G,H的主析取范式相同，所以G = H.1013.(1)MR00000011000000

MS10001000010001 01(2)R•S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1•R1＝{(b, a),(d, c)}.－－四 证明题

1.证明：{P→Q, R→S, P∨R}蕴涵Q∨S

(1)P∨R

(2)R→P(3)P→Q(4)R→Q(5)Q→R(6)R→S

P Q(1)P Q(2)(3)Q(4)P

(7)Q→S(8)Q∨S Q(5)(6)Q(7)2.证明：(A-B)-C =(A∩~B)∩~C

3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)证明：{A∨B, C→B, C→D}蕴涵A→D(1)A D(附加)P(2)A∨B(3)B Q(1)(2)P Q(4)(4)C→B(5)B→C(6)C

Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D

所以 {A∨B, C→B, C→D}蕴涵A→D.1.证明：A－(A∩B)