离散数学试卷二试题与答案

来源：网络收集时间：2026-09-15

导读：试卷二试题与答案一、填空 20% （每小题2分） 1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。 2、论域D={1，2}，指定谓词P P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值

试卷二试题与答案

一、填空 20% （每小题2分）

1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为

；“虽然你努力了，但还是失败了”的翻译为。 2、论域D={1，2}，指定谓词P

P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为。 2、设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是。

3、设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数}，则R=

（列举法）。

R的关系矩阵MR=

。

5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系

R= ；A上既是对称的又是反对称的关系R= 。

6、设代数系统，其中A={a，b，c},

* a b c a b c a b c b b c c c b

则幺元是；是否有幂等性；是否有对称性。

7、4阶群必是群或群。 8、下面偏序格是分配格的是。

9、n个结点的无向完全图Kn的边数为，欧拉图的充要条件是。 10、公式(P?(?P?Q))?((?P?Q)??R的根树表示为

。

二、选择 20% （每小题2分）

1、在下述公式中是重言式为（）

A．(P?Q)?(P?Q)；B．(P?Q)?((P?Q)?(Q?P))； C．?(P?Q)?Q； D．P?(P?Q)。

2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为（），成真赋值的个数为（）。

A．0； B．1； C．2； D．3 。

S3、设S?{?,{1},{1,2}}，则 2 有（）个元素。

A．3； B．6； C．7； D．8 。 4、设S?{ 1, 2, 3 }，定义S?S上的等价关系

R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}则由 R产生

的S?S上一个划分共有（）个分块。

A．4； B．5； C．6； D．9 。 5、设S?{ 1, 2, 3 }，S上关系R的关系图为

则R具有（）性质。

A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性。 6、设 ?,? 为普通加法和乘法，则（）?S,?,??是域。 A．S?{x|x?a?b3,a,b?Q} B．S?{x|x?2n,a,b?Z}

C．S?{x|x?2n?1,n?Z} D．S?{x|x?Z?x?0}= N 。

7、下面偏序集（）能构成格。

8、在如下的有向图中，从V1到V4长度为3 的道路有（）条。

A．1； B．2； C．3； D．4 。 9、在如下各图中（）欧拉图。

设R是实数集合，“?”为普通乘法，则代数系统是（）。

A．群； B．独异点； C．半群。

、

10三、证明 46%

1、设R是A上一个二元关系，

S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证

明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）

2、用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）

3、若f:A?B是从A到B的函数，定义一个函数g:B?2对任意b?B有

Ag(b)?{x|(x?A)?(f(x)?b)}，证明：若f是A到B的满射，则g是从B到 2

A的单射。（10分）

4、若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）

m?12(n?1)(n?2)?25、设G是具有n个结点的无向简单图，其边数

Hamilton图（8分）

，则G是

四、计算 14%

1、设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，

试求出的所有子群及其相应左陪集。（7分）

2、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）

试卷二答案：一、填空 20%（每小题2分）

1、?P?Q；P?Q2、T 3、B31?B00011111?{a4,a5,a6,a7,a8}4、

R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,?11111????11111??00011????11111???00000?? 5、R={<1,2>,<1,3>,<2,1>}；3>,<5,4>,<5,5>,<5,6>}；

R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein四元群；循环群 8、 B 9、

12n(n?1)；图中无奇度结点且连通 10 、

二、

选择 20%（每小题 2分）题目 1 2 答案 B、D D；D 3 D 4 B 5 D 6 A 7 B 8 B 9 B 10 B、C

三、证明 46%

1、（9分）

（1） S自反的

?a?A，由R自反，?(?a,a??R)?(?a,a??R)，??a,a??S

（2） S对称的 ?a,b?A?a,b??S?(?a,c??R)?(?c,b??R)?(?a,c??R)?(?c,b??R)??b,a??S（3） S传递的

?S定义?R对称?R传递

?a,b,c?A?a,b??S??b,c??S?(?a,d??R)?(?d,b??R)?(?b,e??R)?(?e,c??R)?(?a,b??R)?(?b,c??R)?R传递??a,c??S?S定义由（1）、（2）、（3）得；S是等价关系。 2、11分

证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华上述句子符号化为：