24春国家开放大学《离散数学》大作业参考答案.docx

1

离散数学大作业

姓名：

学号：

得分：

教师签名：

大作业时间为第1周到第17周，满分100分，由两部分组成。提交作业方式有以下三种，请务必与辅导教师沟通后选择：

1.将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅。注意选择此种提交方式时仍然需要在网络课提交作业入口处上传说明文档，文档内注明“作业已由线下提交给辅

导老师”。

2.在线提交word文档.

3.自备答题纸张，将答题过程手工书写，并拍照上传.

第一部分

一、公式翻译题(每小题2分，共10分)

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

解：设P:我会英语，Q:我会德语

则命题公式为：PAQ.

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

解：设P:今天是周三，Q:昨天是周二

则命题公式为：P→Q.

3.将语句“小王是个学生，小李是个职员.”翻译成命题公式.

解：设P:小王是个学生，Q:小李是个职员.

2

则命题公式为：PAQ.

4.将语句“如果明天下雨，我们就去图书馆.”翻译成命题公式.

解：设P:明天下雨，Q:我们就去图书馆.

则命题公式为：P→Q.

5.将语句“当大家都进入教室后，讨论会开始进行.”翻译成命题公式.解：设P:大家都进入教室后，Q:讨论会开始进行

则命题公式为：PAQ

二、计算题(每小题10分，共50分)1.设集合A={1,2,3},B={2,3,4},C={2,{3}},

试计算

(1)A-C;(2)A∩B;(3)(A∩B)×C.

解：(1)A-C={1,3}

(2)A∩B={2,3}

(3)(A∩B)×C={2,3}×{2,{3}}={2,2,2,{3},3,2,3,{3}}

2.设G=V,E,={v?,V2,V?,V4,v5},E={(v?,v?),(v?,v?),(v2,v?),

(v?,v4),(v4,v?)},试

(1)给出G的图形表示；

(2)求出每个结点的度数；

(3)画出其补图的图形.

解：(1)G的图形表示

(2)v1,v2,v3,v4,v5结点的度数依次为2,1,3,2,2.

(3)补图如下图

3

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

解：

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

4.求出如下所示赋权图中的最小生成树(要求写出求解步骤),并求此最小生成树的权.

解：

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

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

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

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

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

最小生成树，如图

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

4

5.求P→(QAR)的析取范式与合取范式.

解：P→(Q△R)

?-PV(QAR)

变成

合取析取

→(-PVQ)A(-PVR)

分配律

→(-PVQV(-R△R))A(-PV(-QAQ)VR)

补项

→((-PVQV-R)A(-PVQVR))△(-PV(-QAQ)VR)

分配律2

→(-PVQV-R)A(-PVQVR)A(-PV(-QAQ)VR)

结合律

→(-PVQV-R)A(-PVQVR)A((-PV-QVR)A(-PVQVR))分配律2

→(-PVQV-R)A(-PVQVR)A(-PV-QVR)A(-PVQVR)

结合律

→(-PVQV-R)A(-PV-QVR)A(-PVQVR)

等幂律

得到主合取范式，再检查遗漏的极大项

→M?AM?AM?→(4,5,6)

→-II(0,1,2,3,7)→Z(0,1,2,3,7)?m?Vm?Vm?Vm?Vm?

→-(PVQVR)V-(PVQV-R)V-(PV-QVR)V-(PV-QV-R)V-(-PV-QV-R)

德摩根定律

一(-PA-QA-R)V(-PA-Q△R)V(-PAQA-R)V(-PAQ△R)V(PAQ△R)德摩根定律

得到主析取范式

5

第二部分

从下列选题中选择一个感兴趣的主题，自主查阅文献资料进行深入的研究和学习，并形成一份至少一千字的总结报告。(40分)

1.离散数学在各学科领域的应用；

2.集合论的发展历史和应用；

3.函数概念的发展历史和应用；

4.图论的发展历史和应用；

5.数理逻辑的发展历史和应用；

6.最小生成树的两种算法比较分析；

7.任意自选主题，注意选择前需经过辅导老师认可。

参考答