大作业word版答案.docxVIP

PAGE2

离散数学大作业

姓名：

姓名：

学号：

得分：

教师签名：

第一部分

一、公式翻译题（每小题2分，共10分）

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

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

则命题公式为：P?Q

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

解：设P：如果今天是周三Q：明天是周二

则命题公式为：P→Q

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

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

则命题公式为：P∧Q

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

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

则命题公式为：P→Q

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

解：设P：大家都进入教师后Q：讨论会开始进行

则命题公式为：P∧Q

二、计算题（每小题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={v1,v2,v3,v4,v5}，E={(v1,v3),(v1,v5),(v2,v3),(v3,v4),(v4,v5)}，试

（1）给出G的图形表示；

（2）求出每个结点的度数；

（3）画出其补图的图形．

解：（1）G的图形表示

（2）v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度为2，v5结点度数为2

（3）补图的图形如下图

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

解：

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

4．求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．

?

?

?

?

?

?

v6

v1

v2

v5

v3

?

v4

1

6

2

4

5

7

9

3

1

5

2

解：

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

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

解：P→(Q∧R)

=?Pv（Q∧R）

=（PvQ）∧（PvR）合取范式

=（PvQ）v（R∧R）∧（PvR）

=（PvQ）v（R∧R）∧（PvR）v（Q∧Q）

=（PvQvR）∧（PvQvR）∧（PvQvR）主合取范式

=（P∧Q∧R)v（P∧Q∧R)v（P∧Q∧R)（P∧Q∧R)v

（P∧Q∧R)v（P∧Q∧R)v（P∧Q∧R)主析取范式

第二部分

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

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

离散数学(Discretemathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

由此可见，离散数学在计算机