国家开放大学《离散数学(本)》下载作业参考答案

国家开放大学《离散数学(本)》下载作业参考答案

一、公式翻译题（每小题4分，共16分）

1．将语句“我会英语，并且会德语．”翻译成命题公式．

参考答案：

设p.我学英语

Q:我学法语

则命题公式为:pΛQ

2．将语句“如果今天是周三，则昨天是周二．”翻译成命题公式．

参考答案：

设P：今天是周三

Q：昨天是周二

则命题公式为：P→Q

3.将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公式．

参考答案：

设P：C3次列车每天上午9点发车

Q：C3次列车每天上午10点发车

则命题公式为：┐(P↔Q)

4.将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．

参考答案：

设P：小王是个学生

Q：小李是个职员

R:而小张是个军人

则命题公式为：P∧Q∧R

二、计算题（每小题12分，共84分）

1．设集合A={{a}, a, b }，B={a, {b}}

试计算：（1）AÇB；    （2）A È B；    （3）A-(AÇB)

参考答案：

（1）AÇB={a}

（2）A È B={{a},a,b{b}}

（3）A-(AÇB)={{a},a,b}-{a}={a,b}

2.设集合A={2, 3, 6, 12, 24, 36}，B为A的子集，其中B={6, 12}，R是A上的整除关系，试

（1）写出R的关系表达式；

（2）画出关系R的哈斯图；

（3）求出B的最大元、极大元、最小上界．

参考答案：

（1）R={<2,2>,<2,6>,<2,12>,<2,24>,<3,3>,<3,6>,<3,12>,<3,24>,<6,6>,<6,12>,<6,24>,<12,12>,<12,24>,<24,24>}

（2）关系R的哈斯图

（3）B的最大元素：12

         极大元素：12

         最小上届：12

3．设G=<V，E>，V={v₁, v₂, v₃, v₄}，E={(v₁,v₂) , (v₁,v₃) , (v₁,v₄) , (v₂,v₃) , (v₃,v₄)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形。

参考答案：

（1）G的图形表示

（2）邻接矩阵

（3）每个结点的度数

Deg(v1)=3

Deg(v2)=2

Deg(v3)=3

Deg(v4)=2

（4）其补图的图形

4.求P→(Q∧R) 的合取范式与主析取范式.

参考答案：

P→(Q∧R)

=┐P∨(Q∧R)

=（┐P∨Q）∧（┐P∨R）合取范式

=（┐P∨Q）∨（R∧┐R）∧（┐P∨R）

=（┐P∨Q）∨（R∧┐R）∧（┐P∨R）∨（Q∧┐Q）

=（┐P∨Q∨R）∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）主合取范式

=（┐P∧┐Q∧┐R）∨（┐P∧┐Q∧R）∨（┐P∧┐Q∧┐R）（┐P∧Q∧R）∨（P∧┐Q∧R）∨（P∧Q∧┐R）∨（P∧Q∧R）主析取范式

5．试画一棵带权为1, 2, 3, 3, 4的最优二叉树,并计算该最优二叉树的权．

参考答案：

最优二叉树的权为1×3+2×3+3×2+3×2+4×2=29

6．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．

参考答案：

W(v2,v6)=1,选(v2,v6)

W(v4,v5)=1,选(v4,v5)

W(v1,v6)=2,选(v1,v6)

W(v3,v5)=2,选(v3,v5)

W(v2,v3)=4,选(v2,v3)

最小生成树，如图

生成树的权W(T)=1+1+2+2+4=10

7.设谓词公式($x)P(x, y)→(“z)Q(x, y, z)，试

（1）写出量词的辖域；

（2）指出该公式的自由变元和约束变元。

参考答案：

（1）$x的辖域为P(x,y)→”zQ(x, y, z)

     “z的辖域为Q(x, y, z)

（2）自由变元

     P(x,y)→”zQ(x, y, z)中的y

约束变元

P(x,y)→”zQ(x, y, z)中的x