离散数学试题与答案

试卷二试题与参考答案

一、填空

1、 P：你努力，Q：你失败。

2、 “除非你努力，否则你将失败”符号化为 ；

“虽然你努力了，但还是失败了”符号化为 。

2、论域D={1，2}，指定谓词P

P (1,1) P (1,2) P (2,1) P (2,2)

T T F F

则公式),(xyyPx真值为 。

3设A={2，3，4，5，6}上的二元关系}|,{是质数xyxyxR，则

R= （列举法）。

R的关系矩阵MR=

。

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

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

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

6、4阶群必是 群或

群。

7、下面偏序格是分配格的是 。 * a b c

a

b

c a b c

b b c

c c b

8、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是

。

二、选择

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

A．)()(QPQP；B．))()(()(PQQPQP；

C．QQP)(； D．)(QPP。

2、命题公式 )()(PQQP 中极小项的个数为（ ），成真赋值的个数为（ ）。

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

3、设}}2,1{},1{,{S，则 S2 有（ ）个元素。

A．3； B．6； C．7； D．8 。

4、设} 3 ,2 ,1 {S，定义SS上的等价关系

},,,, | ,,,{cbdaSSdcSSbadcbaR则由 R产 生的SS上一个划分共有（ ）个分块。

A．4； B．5； C．6； D．9 。

5、设} 3 ,2 ,1 {S，S上关系R的关系图为

则R具有（ ）性质。

A．自反性、对称性、传递性； B．反自反性、反对称性；

C．反自反性、反对称性、传递性； D．自反性 。 6、设 , 为普通加法和乘法，则（ ）,,S是域。

A．},,3|{QbabaxxS B．},,2|{ZbanxxS

C．},12|{ZnnxxS D．}0|{xZxxS= N 。

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

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

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

9、在如下各图中（ ）欧拉图。

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

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

三、证明

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

)},,,(),(|,{RbcRcaAcAbabaS且有对于某一个

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。

2、 用逻辑推理证明：

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

3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。 4、设G是具有n个结点的无向简单图，其边数2)2)(1(21nnm，则G是Hamilton图。

四、计算

1、设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出的所有子群及其相应左陪集。

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

试卷二参考答案：

一、 填空

1、QP；QP 2、T

3、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,3>,<5,4>,<5,5>,<5,6>}；

0000011111110001111111111 4、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}

5、a ；否；有

6、Klein四元群；循环群

7、 B

8、)1(21nn；图中无奇度结点且连通

二、选择

题目 1 2 3 4 5 6 7 8 9 10

答案 B、D D；D D B D A B B B B、C

三、证明

1、

（1） S自反的

Aa，由R自反，),(),(RaaRaa，Saa,

（2） S对称的

传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,, （3） S传递的 定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,,,, 由（1）、（2）、（3）得；S是等价关系。

2、

证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华

上述句子符号化为：

前提：))()((xQxPx、)()(aPaS 结论：))()((xQxSx ……3分

①)()(aPaS 前提引入

②))()((xQxPx 前提引入

③)()(aQaP ②US

④)(aP ①化简

⑤).(aQ ③④假言推理I

⑥)(aS ①化简

⑦)()(aQaS ⑤⑥合取

⑧)()((xQxSx ⑦EG ……11分

３、证明 ：)(,,2121bbBbbAaaf21,满射

21212211,),()(,)(,)(aafafafbafbaf是函数由于且使

)()()(),()(),()})(()(|{)()},)(()(|{)(21122122112211bgbgbgabgabgabgabxfAxxbgbxfAxxbg但又

为单射任意性知由gbb,,21。

4、证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。

5、证明： 证G中任何两结点之和不小于n。

反证法：若存在两结点u，v 不相邻且1)()(nvdud,令},{1vuV，则G-V1是具有n-2个结点的简单图，它的边数)1(2)2)(1(21'nnnm,可得1)3)(2(21'nnm，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。

所以G为Hamilton图.

四、 计算

解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>

{[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]}

{[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]}

{[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]}

Z6的左陪集：Z6 。