离散数学大作业
姓名：学号：得分：教师签名：
大作业时间为第1周到第17周，满分100分，由两部分组成。提交作业方式有以下三种，请务必与辅导教师沟通后选择：
1.将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅。注意选择此种提交方式时仍然需要在网络课提交作业入口处上传说明文档，文档内注明“作业已由线下提交给辅导老师”。
2.在线提交word文档.
3.自备答题纸张，将答题过程手工书写，并拍照上传.
第一部分
一、公式翻译题(每小题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)ANB={2,3};
(3)(ANB)×C={2,2,2,{3},3,2,3,{3}}。
2.设G=V,E,V={v,V2,V3,V4,vs},E={(v,v),(v,vs),(v,Vs),(vs,v4),(v4,Vs)},试
(1)给出G的图形表示；
(2)求出每个结点的度数；
(3)画出其补图的图形.
答：(1)G的图形表示如图所示
(2)v1,v2,v3,v4,v5结点的度数依次为2,1,3,2,2
V2
(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(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
5.求P→(QAR)的析取范式与合取范式.
P→(QAR)
=7Pv(QAR)
=(7PVQ)^(7PvR)合取范式=(7PvQ)v(RAR)^(PVR)
=(7PVQ)v(R?R)A(7PvR)v(QA7Q)
=(7PvQVR)^(7PvQv7R)A(7Pv?QVR)主合取范式
=(7P?QAR)v(7PA7QAR)v(7PAQA?R)(7PAQAR)v(PAjQAR)v(PAQA?R)v(PAQAR)主析取范式
第二部分
从下列选题中选择一个感兴趣的主题，自主查阅文献资料进行深入的研究和学习，并形成一份至少一千字的总结报告。(40分)
1.离散数学在各学科领域的应用；
2.集合论的发展历史和应用；
3.函数概念的发展历史和应用；
4.图论的发展历史和应用；
5.数理逻辑的发展历史和应用；
6.最小生成树的两种算法比较分析；
7.任意自选主题，注意选择前需经过辅导老师认可。
离散数学在各学科领域的应用研究报告
一、引言
离散数学是数学的一个重要分支，它主要研究的是非连续的、分离的对象，如整数、集合、图形等。它的理论广泛应用于计算机科学、工程学、物理学、经济学等各个学科领域。这份报告将探讨离散数学在这些学科领域中的应用，并深入学习和理解这些应用。
二、计算机科学中的应用
在计算机科学中，离散数学的应用尤为广泛。计算机科学本质上处理的是离散的数据和概念，如二进制数、逻辑运算、图论等。离散数学为计算机科学提供了基础的理论工具，如集合论为数据结构和算法设计提供了基础，图论为网络设计和分析提供了基础，数理逻辑则为计算机程序设计和人工智能提供了基础。
1.数据结构