离散数学试题与答案.docx

试卷二试题与参考答案
一、填空
P：你努力，Q：你失败。
“除非你努力，否则你将失败”符号化为；
“虽然你努力了，但还是失败了”符号化为。
2、论域D={1，2}，指定谓词P
P(1,1)P(1,2)P(2,1)P(2,2)TTFF则公式真值为。
3设A={2，3，4，5，6}上的二元关系，则
R= （列举法）。
R的关系矩阵MR=
。
4、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=；A上既是对称的又是反对称的关系R=。
5、设代数系统<A，*>，其中A={a，b，c},
*abca
b
cabc
bbc
ccb

则幺元是；是否有幂等性；是否有对称性。
6、4阶群必是群或群。
7、下面偏序格是分配格的是。

8、n个结点的无向完全图Kn的边数为，欧拉图的充要条件是
。
二、选择
1、在下述公式中是重言式为（）
A．；B．；
C．；D．。
2、命题公式中极小项的个数为（），成真赋值的个数为（）。
A．0；B．1；C．2；D．3。
3、设，则有（）个元素。
A．3；B．6；C．7；D．8。
4、设，定义上的等价关系
则由R产生的上一个划分共有（）个分块。
A．4；B．5；C．6；D．9。
5、设，S上关系R的关系图为

则R具有（）性质。
A．自反性、对称性、传递性；B．反自反性、反对称性；
C．反自反性、反对称性、传递性；D．自反性。
6、设为普通加法和乘法，则（）是域。
A．B．
C．D．=N。
7、下面偏序集（）能构成格。

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

A．1；B．2；C．3；D．4。
9、在如下各图中（）欧拉图。
10、10、设R是实数集合，“”为普通乘法，则代数系统<R，×>是（）。
A．群；B．独异点；C．半群。
三、证明
1、设R是A上一个二元关系，

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。
用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。
3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。
4、设G是具有n个结点的无向简单图，其边数，则G是Hamilton图。
四、计算
1、设<Z6,+6>是一个群，这里+6是模6加法，Z6={[0]，[1]，[2]，[3]，[4]，[5]}，试求出<Z6,+6>的所有子群及其相应左陪集。
2、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。

试卷二参考答案：
填空
1、；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>}；

4、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}
5、a；否；有
6、Klein四元群；循环群
7、B
8、；图中无奇度结点且连通

二、选择
题目12345678910答案B、DD；DDBDABBBB、C三、证明
1、
S自反的
，由R自反，，
S对称的

S传递的

由（1）、（2）、（3）得；S是等价关系。
2、
证明：设P(x)：x是个舞蹈者；Q(x)：x很有风度；S(x)：x是个学生；a：王华
上述句子符号化为：
前提：、结论：……3分
① 前提引入
② 前提引入
③ ②US
④ ①化简
⑤ ③④假言推理I
⑥ ①化简
⑦ ⑤⑥合取
⑧ ⑦EG ……11分
３、证明：

。
4、证明：设G中两奇数度结点分别为u和v，若u，v不连通，则G至少有两个连通分支G1、G2，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。
5、证明：证G中任何两结点之和不小于n。
反证法：若存在两结点u，v不相邻且,令，则G-V1是具有n-2个结点的简单图，它的边数,可得，这与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。