计算机模拟试卷

课程名称：__离散数学 考试形式： 闭 卷

学习中心：_________ 考试时间： 90分钟

姓 名：_____________ 学 号：

一 填空题（每空2分，合计20分）

1. 任意两个不同小项的合取为 ，全体小项的析取式为 。

2. 设R为集合A上的等价关系，对aA，集合[a]R= ，称为元素a形成的R等价类，[a]R，因为 。

3. 设A{0,1}，N为自然数集，f(x)0，x是奇数，1，x是偶数。AA， 若f：NA，则f是 射的。 则f是 射的，若f：4. 设S为非空有限集，代数系统2,中幺元为 ，零元为 。

5. 若GV,E为汉密尔顿图，则对于结点集V的每个非空子集S，均有W(G-S) S成立，其中W(G-S)是 。 二 选 择（每题2分，合计20分） 1．命题公式P(QP)是（ ）。

A、 矛盾式； B、可满足式； C、重言式； D、等价式。

第 1 页 （共 11 页）

S2．下列各式中哪个不成立（ ）。

A、x(P(x)Q(x))xP(x)xQ(x) ； B、x(P(x)Q(x))xP(x)xQ(x)； C、x(P(x)Q(x))xP(x)xQ(x)； D、x(P(x)Q)xP(x)Q。

3．谓词公式x(P(x)yR(y))Q(x)中的 x是（ ）。 A、自由变元； B、约束变元；

C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。

14．设f和g都是X上的双射函数，则(fg)为（ ）。

A、f1g1 ； B、(gf)1 ； C、g1f1 ； D、gf1。

5．下面集合（ ）关于减法运算是封闭的。

A、N ； B、{2xxI} ； C、{2x1xI} ； D、{xx是质数}。

6．具有如下定义的代数系统G,，（ ）不构成群。

A、G{1,10}，*是模11乘 ； B、G{1,3,4,5,9}，*是模11乘 ； C、GQ（有理数集），*是普通加法 ； D、GQ（有理数集），*是普通乘法。 7．设G{23幺元为（ ）。

第 2 页 （共 11 页）

mnm,nI}，*为普通乘法。则代数系统G,的

A、不存在 ； B、e23 ； C、e23 ； D、e28．下面集合（ ）关于整除关系构成格。

00131。

A、{2，3，6，12，24，36} ； B、{1，2，3，4，6，8，12} ； C、{1，2，3，5，6，15，30} ； D、{3，6，9，12}。

9．无向图GV,E，如下图所示，下面哪个边集不是其边割集（ ）。

A、{v1,v4,v3,v4}； B、{v1,v5,v4,v6}； C、{v4,v7,v4,v8}； D、{v1,v2,v2,v3}。

10．有n个结点(n3)，m条边的连通简单图是平面图的必要条件（ ）。

A、 B、 C、 D、 n3m6；n3m6；m3n6；m3n6。三 计 算（每题8分， 合计40分）

1．设A{a,b,c}上的关系 {a,a,a,b,b,c,c,b}，求出 r(),s()和t()。

第 3 页 （共 11 页）

2. 集合A{2,3,6,12,24,36}上的偏序关系

B{6,12}，C{2,3,6}，试画出

为整除关系。设

的哈斯图，并求A，B，C的最

大元素、极大元素、下界、上确界。

3. 图给出的赋权图表示五个城市v1，v2，v3，v4，v5及对应两城镇间

公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。

2，3，4，5，6}，7为模7乘法。试说明G，4. 已知G{1，7是否

构成群？是否为循环群？若是，生成元是什么？

第 4 页 （共 11 页）

5. 给定命题公式(P(QR))(SW)，试给出相应的二元树。

四 证明题（每题10分， 合计20分）

1. 试证明若G,是群，HG，且任意的aH，对每一个xG，有axxa，则H,是G,的子群。

第 5 页 （共 11 页）

2. 符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。

第 6 页 （共 11 页）

西安电子科技大学网络教育 2010学年上学期期末考试答题纸

课程名称：__离散数学 考试形式： 闭 卷

学习中心：_________ 考试时间： 90分钟

姓 名：_____________ 学 号：

题号 题分 得分

一 20 二 20 三 40 四 20 总分 一 填空题（每空2分，合计20分） 1 永假式（矛盾

式），永真式（重言式） 5

二 选 择（每题2分，合计20分，在正确答案上划√） 1 4 7 A A A B B √ D √ D D 2 5 8 √ B A A C D D 3 6 9 A A A B B √ D C √ D 2 [a]{xxA,aRx}3 双射 4

R满射 ；a[a]R

 ，S

；GS的连通分支数。

√ C B √ C B C √ D √ C 10 A

√ 三 计 算（每题8分 合计40分）

第 7 页 （共 11 页）

1．解r(){a,a,a,b,b,c,c,b,b,b,c,c}， s(){a,a,a,b,b,c,c,b,b,a}， 2{a,a,a,b,a,c,b,b,c,c}，

3{a,a,a,b,a,c,a,b,b,c,c,b}22t(){a,a,a,b,a,c,b,b,c,c,b,c,c,b}2．解：

的哈斯图为

集合 A B C 最大元 无 12 6 极大元 24，36 12 6 下界 无 6，2，3 无 上确界 无 12 6 3．解：此问题的最优设计方案即要求该图的最小生成树， 由破圈法或避圈法得最小生成树为： 其权数为1+1+3+4 = 9 。

4．解：G，7既构成群，又构成循环群，其生成元为3，5。因为：7的运算表为：

第 8 页 （共 11 页）

7 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 1 2 3 4 5 6 1）由运算表知，7封闭； 2）7可结合（可自证明） 3）1为幺元； 4）111，214，315，412，513，616，

综上所述，G，7构成群。

1 由33，32，36，34，35，31。所以，3

23456为其生成元，3的逆元5也为其生成元。 故G，7为循环群。

5．解：命题公式对应的二元树见右图。

四 证明题（每题10分 合计20分）

第 9 页 （共 11 页）

1.

（1）设群G,的幺元为e，则xG 有 xeex，∴eH即H非空。

（2）a,bH，则 xG 有 axxa,bxxb，从而

(ab1)x(ab111)x(bb1)a(bb)xb1(ax)b11

x(ab),abH 故 H,是G,的子群。 2.

设P(x)：x喜欢美术，Q(x)：x喜欢体育，R(x)：x喜欢音乐。论域：人。

x(P(x)Q(x))，x(Q(x)R(x))，xR(x) 命题形式化为：前提：

结论：xP(x)。

证明：（1）xR(x) P (2) R(a) ES(1) (3) x(Q(x)R(x)) P (4) Q(a)R(a) US(4) (5) Q(a) T(2)(4)I (6) x(P(x)Q(x)) P (7) P(a)Q(a) US(6) (8) P(a) T(5)(7)I

第 10 页 （共 11 页）

(9) xP(x) EG(8) ∴ 结论有效。

第 11 页 （共 11 页）