国开《离散数学》大作业及答案.docxVIP

大作业及答案

1.在线提交word文档第一部分

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

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

设p.我学英语

Q:我学法语

则命题公式为：pAQ

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

参考答案：

设P:今天是周三

Q:昨天是周二

则命题公式为：P→Q

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

参考答案：

设P:小王是个学生

Q:小李是个职员

则命题公式为：PAQ

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

设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,2,2,{3},3,2,3,{3}}.

2.设G=V,E,={v?,V?,V?,V4,V?},E={(v?,v?),(v?,v?),(v?,v?),(v?,V4),(v4,v?)},试

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

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

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

参考答案：

(1)关系图

(2)

deg(v1)=3

deg(v2)=2

deg(v3)=3

deg(v4)=2

deg(v5)=2

(3)补图

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

参考答案：

权为1×3+2×3+3×2+3×2+4×2=29

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

参考答案：

解：用Kruskal

算法求产生的最小生成树，步骤为：

w(V2,V?)=1

选(v?,V?)

w(V4,V5)=1

w(v?,V?)=2

选(v4,V5)选(v?,V?)

w(V3,V5)=2

选(v?,V5)

w(V?,V3)=4

选(v?,v?)

最小生成树如图所示：

最小生成树的权w(T)=1+1+2+2+4=10.

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

参考答案：

解：

(PVQ)→R

今┐(PVQ)VR

?(┐P┐Q)VR(析取范式)

?(┐PVR)Λ(┐QVR)(合取范式)

第二部分

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

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

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

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

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

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

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

参考答案：

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

引言

离散数学，作为现代数学的一个重要分支，专注于研究离散量的结构及其相互关系。所谓“离散”,指的是不同的、连接在一起的元素，与连续变化的量

形成鲜明对比。离散数学的研究对象通常是有限个或可数个元素，这些元素可能以集合、图、序列等形式出现。离散数学的核心概念包括集合论、图论、代数结构、组合数学以及数理逻辑等，为理解和分析离散现象提供了强有力的数学工具。本文将探讨离散数学在各学科领域中的广泛应用。

一、计算机科学领域

离散数学在计算机科学中的应用尤为广泛，它是许多计算机科学领域不可或缺的基础。

数据结构与算法：离散数学为数据结构(如数组、链表和树)和算法(如排序和有哪些信誉好的足球投注网站)的设计和分析提供了基础。例如，集合论用于描述数据结构，图论用于解决路径问题，组合数学用于计算算法复杂度等。

编译器：离散数学用于设计编译器，它们将高层次语言翻译成计算机能够理解的低层次语言。

密码学：离散数学是密码学的基础，涉及加密和解密信息。代数结构中的群、环等概念被用于构建加密算法，确保信息的安全传输。

计算机网络：离散数学用于设计和分析计算机网络的协议和拓扑结构。

数据库系统：离散数学用于关系数据库的建模、查询和优化。树、图等结构被广泛应用于数据组织、查询优化等方面。

人工智能：离散数学用于设计用于机器学习和人工智能的算法。数理逻辑为机器推理、知识表示等提供了理论基础，而组合数学则用于解决有哪些信誉好的足球投注网站、优化等复杂问题。

二