北交《离散数学》复习题 A-B卷答案.doc

PAGE

北交《离散数学》复习题A

填空题

设A＝｛1,2,3,4,5,6｝，B={1,2,3}，从A到B的关系R＝｛〈x,y〉|x=y2｝，则R=__{1,1,4,2}_________。

素数阶群一定是_循环______群,它的生成元是___任一非单位元______。

公式(PQ)(PQ)可化简为______P_______。

令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为___?x(R(x)Q(x))__________。

设S={1,2,3,4}，A上的关系R＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝则RR=__{〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}_______________。

计算题

用推导法求公式的主析取范式。

答案：

一棵树有1个结点度数为5，2个结点度数为4，5个结点度数为2，14个结点度数为1，问度数为3的结点有几个？

答案：设T是(n,m)图,度为3的结点数为,

则n=1+2+5+14+=22+

由握手定理2m=

将m=n-1代入得2m=2(n-1)=2(22+x-1)=37+3x,x=5

所以度数为3的结点有5个。

证明题

证明：

答案：

试证明群G;*的两个子群的交集也构成G;*的子群。

答案：设为的任意两个子群,那么,

且G的单位元,因此,,,

那么,且,而为群,故,,

因此有,同理,因此,

故也是子群。

北交《离散数学》复习题B

填空题

在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是__k_____。

设P，Q的真值为0，R，S的真值为1，则的真值=1。

设集合A＝{a,b,c},B={a,b},那么P(A)－P(B)={{c},{a,c},{b,c},{a,b,c}}P(B)－P(A)=?。

设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的m-n+1条边。

n阶无向完全图Kn的边数是，每个结点的度数是__n-1______。

计算题

化简。

答案：

题目如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。

答案：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：

树权C(T)=23+1+4+9+3+17=57即为总造价。

证明题

证明如果非空集合A上的二元关系R和S是偏序关系，则也是A上的偏序关系。

考核知识点解析：R是一偏序关系，满足：1）、(a,a)∈R自反性2）、（a,b)∈R,(b,a)∈R，则a=b偏序性3）、(a,b)∈R，(b,c)∈R,则（a,c)∈R传递性。

答案：①，所以有自反性；

②因为R，S是反对称的，

所以，R?S有反对称性．

③，因为R，S是传递的，

所以，有传递性。

证明

考核知识点解析：详见课件谓词逻辑推算理论。

答案： ①?Q?R P

②?RP

③?Q①，②析取三段论

④P?QP

⑤③，④拒取式

⑥P??SP

⑦?S⑤，⑥析取三段论