离散数学试题及答案
一、填空 20% (每小题2分)
1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
“虽然你努力了，但还是失败了”的翻译为
。
2、论域D={1，2}，指定谓词P
则公式?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},
则幺元是；是否有幂等
性；是否有对称性。
7、4阶群必是 群或 群。
8、下面偏序格是分配格的是 。
第 1 页 共 7 页
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 。
3、设S?{?,{1},{1,2}}，则 2 有()个元素。
A．3；B．6； C．7； D．8 。
4、 设S?{ 1, 2, 3 }，定义S?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的关系图为
第 2 页 共 7 页
则R具有()性质。
A．自反性、对称性、传递性；B．反自反性、反对称性；
C．反自反性、反对称性、传递性； D．自反性 。
6、设 ?,? 为普通加法和乘法，则()?S,?,??是域。
A．S?{x|x?a?b,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、在如下各图中()欧拉图。
是实数集合，“?”为普通乘法，则代数系统 是()。
第 3 页 共 7 页
、设R10
A．群； B．独异点； C．半群 。
三、证明 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?2A 对任意b?B有
Ag(b)?{x|(x?A)?(f(x)?b)}，证明：若f是A到B的满射，则g是从B到 2 的
单射。(10分)
4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。(8分)
5、 设G是具有n个结点的无向简单图，其边数m?
图(8分) 1(n?1)(n?2)?2，则G是Hamilton2
四、计算 14%
1、 设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求
出的所有子群及其相应左陪集。(7分)
2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。(7分)
本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-/a/jisuanjixue/article-21613-1.html
