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

离散数学大作业姓名：姓名：学号：得分：教师签名：大作业时间为第1周到第17周，满分100分，由两部分组成。提交作业方式有以下三种，请务必与辅导教师沟通后选择：1.将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅。注意选择此种提交方式时仍然需要在网络课提交作业入口处上传说明文档，文档内注明“作业已由线下提交给辅导老师”。2.在线提交word文档．3.自备答题纸张，将答题过程手工书写，并拍照上传．第一部分一、公式翻译题（每小题2分，共10分）1.将语句“我会英语，并且会德语．”翻译成命题公式．解：设P：我会英语，Q：我会德语则命题公式为：P∧Q．2.将语句“如果今天是周三，则昨天是周二．”翻译成命题公式．解：设P：今天是周三，Q：昨天是周二则命题公式为：P→Q．3.将语句“小王是个学生，小李是个职员．”翻译成命题公式．解：设P：小王是个学生，Q：小李是个职员．则命题公式为：P∧Q．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）AC；（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，v2，v3，v4，v5结点的度数依次为2，1，3，2，2．（3）补图如下图3.试画一棵带权为1,2,3,3,4的最优二叉树,并计算该最优二叉树的权．解：最优二叉树的权为：1×3+2×3+3×2+3×2=4×2=294.求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．v6v1v2v5v3v416245793152解：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=105.求P→(Q∧R)的析取范式与合取范式.解：P→(Q∧R)⇔¬P∨(Q∧R)变成合取析取⇔(¬P∨Q)∧(¬P∨R)分配律⇔(¬P∨Q∨(¬R∧R))∧(¬P∨(¬Q∧Q)∨R)补项⇔((¬P∨Q∨¬R)∧(¬P∨Q∨R))∧(¬P∨(¬Q∧Q)∨R)分配律2⇔(¬P∨Q∨¬R)∧(¬P∨Q∨R)∧(¬P∨(¬Q∧Q)∨R)结合律⇔(¬P∨Q∨¬R)∧(¬P∨Q∨R)∧((¬P∨¬Q∨R)∧(¬P∨Q∨R))分配律2⇔(¬P∨Q∨¬R)∧(¬P∨Q∨R)∧(¬P∨¬Q∨R)∧(¬P∨Q∨R)结合律⇔(¬P∨Q∨¬R)∧(¬P∨¬Q∨R)∧(¬P∨Q∨R)等幂律得到主合取范式，再检查遗漏的极大项⇔M₄∧M₅∧M₆⇔∏(4,5,6)⇔¬∏(0,1,2,3,7)⇔∑(0,1,2,3,7)⇔m₀∨m₁∨m₂∨m₃∨m₇⇔¬(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)德摩根定律得到主析取范式第二部分从下列选题中选择一个感兴趣的主题，自主查阅文献资料进行深入的研究和学习，并形成一份至少一千字的总结报告。（40分）离散数学在各学科领域的应用；集合论的发展历史和应用；函数概念的发展历史和应用；图论的发展历史和应用；数理逻辑的发展历史和应用；最小生成树的两种算法比较分析；任意自选主题，注意选择前需经过辅导老师认可。参考答案：离散数学在各学科领域的应用离散数学是数学的一个重要分支，主要研究离散对象和结构以及它们之间的关系和规律。在现代科技的推动下，离散数学已经渗透到各个学科领域，成为众多学科不可或缺的理论基础。本文将从多个方面探讨离散数学在各学科领域的应用。（一）计算机科学基础计算机科学的核心概念，如逻辑运算、集合论、图论等，都是离散数学的重要组成部分。逻辑运算是计算机内部信息处理的基础，而集合论和图论则在数据结构、算法分析和系统设计等领域发挥着重要作用。（二）数据结构与算法离散数学为数据结构和算法的设计提供了理论基础。图论中的树、图等概念是数据结构中的关键要素，如二叉树、堆、图等。同时，离散数学中的组合数学、优化理论等为算法设计提供了有效工具，如动态规划、贪心算法等。（三）网络与通信网络中的节点和链路可以抽象为离散数学中的图和边的概念。图论在网络拓扑结构、路由算法、流量控制等方面有着广泛应用。此外，离散数学在编码理论、错误检测与纠正等方面也为通信技术提供了重要支持。（四）数据库理论数据库的设计和管理离不开离散数学的理论支持。关系数据库中的关系、属性、元组等概念与集合论、关系代数紧密相关。同时，离散数学中的图论和数理逻辑也为数据库查询优化、事务处理等提供了理论依据。（五）人工智能与机器学习人工智能和机器学习领域的许多问题都可以转化为离散数学问题。例如，搜索算法、知识表示和推理、模式识别等都与离散数学密切相关。图论、组合优化等离散数学理论在机器学习中也有着广泛的应用，如决策树、关联规则挖掘等。（六）密码学与信息安全密码学是信息安全的核心，而离散数学在密码学中扮演着举足轻重的角色。数论、群论、有限域等离散数学理论为加密算法的设计提供了坚实的数学基础。同时，离散数学也在信息隐藏、数字签名、身份认证等方面发挥着重要作用。（七）电子商务与信息系统电子商务和信息系统的设计和优化也离不开离散数学的理论支持。离散数学在数据建模、信息检索、数据挖掘等方面提供了有效的工具和方法。同时，离散数学在电子商务的安全性和隐私保护方面也发挥着重要作用。（八）社会科学与决策分析离散数学在社会科学和决策分析领域也有广泛的应用。例如，图论和网络分析可以用于社交网络分析、舆论传播等；数理逻辑和集合论可以用于决策支持系统、知