离散数学和其应用DiscreteMathematics.ppt

《离散数学和其应用DiscreteMathematics.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学及其应用DiscreteMathematics张清华蒲兴成尹邦勇刘勇重庆邮电大学2021/7/30重庆邮电大学理学院12021/7/30重庆邮电大学理学院离散数学类课程地位：计算机相关专业核心课程信息类部分专业必修课程其它部分专业的选修课程离散数学的后继课程：数据结构、操作系统、算法分析与设计、人工智能、数据库、C++语言，……22021/7/30重庆邮电大学理学院学习该课程的目的：一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络、程序设计等，提供必要的数学基础（逻辑、关系、代数系统、图论等）；另一方面

2、，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的理论基础。32021/7/30重庆邮电大学理学院教学要求：通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。自学要求：通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。42021/7/30重庆邮电大学理学院离散数学课程的学习方法：强调：逻辑推理、抽象思维；注重：概念、方法与应用离散数学的学习要领：概念（正确）熟练掌握大量的基本概念（多、散）判

3、断（准确）根据概念对属性进行判断（巧）推理（可靠）根据多个结论推出新的论断（难）5课程主要内容第一部分数理逻辑：命题逻辑、谓词逻辑。第二部分集合论：集合、关系、函数。第三部分代数系统：二元运算、代数系统、半群、群。第四部分图论：图的基本概念、路与圈、最短路、欧拉图、哈密尔顿图、树、平面图。2021/7/30重庆邮电大学理学院6离散数学与计算机的关系（简要）第一部分数理逻辑计算机是数理逻辑和电子学相结合的产物，本章是智能科学中的知识表示、知识推理的基础。第二部分集合论集合是一种重要的数据结构关系，关系数据库的理论基础函数，所有计算机语言中不可缺少的一部分。

4、第三部分代数系统计算机编码和纠错码理论数字逻辑设计基础计算机使用的各种运算，信息安全的密码学需要代数系统为基础。第四部分图论数据结构、操作系统、编译原理计算机网络原理的基础。2021/7/30重庆邮电大学理学院7课程教学学时与作业课程学时：64学时：主要讲述第一部分数理逻辑、第二部分集合与关系，第三部分代数系统（讲到群的定义及其性质）；第四部分图论。48学时：主要讲述第一部分数理逻辑（主要讲命题逻辑）、第二部分集合与关系；第四部分图论。成绩构成：30%的平时成绩+70%期末考试成绩。2021/7/30重庆邮电大学理学院8第一章命题逻辑数理逻辑是研究推理（

5、即研究人类思维的形式结构和规律）的科学，起源于17世纪，它采用数学符号化的方法，因此也称为符号逻辑。从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题逻辑演算、谓词逻辑演算，但现在提到数理逻辑，一般是指命题逻辑和谓词逻辑。本书也只研究这两个逻辑演算。2021/7/30重庆邮电大学理学院9数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联

6、。1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。2021/7/30重庆邮电大学理学院10数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。本章和下一章我们只从简单语义出发，对数理逻辑中的命题逻辑与谓词逻辑等作一简单的、直接的、非形式化的介绍，不涉及公理系统。2021/7/30重庆邮电大学理学院11第一章命题逻辑1.命题及其表示命题：是指具有确定真值的陈述句或者能够判断真假的陈述句。命

7、题的真值：命题的判断结果。真值只取两个值：真（1或T）、假（0或F）。真命题：真值为真的命题。假命题：真值为假的命题。判断命题的两个步骤：1、是否为陈述句？2、是否有确定的、唯一的真值？1.1节命题及联结词2021/7/30重庆邮电大学理学院12注意:感叹句、祈使句、疑问句都不是命题。陈述句中的悖论以及判断结果不惟一确定的也不是命题。例1.1下列句子中那些是命题？（1）重庆是直辖市。（2）教师是人类灵魂的工程师。（3）4是素数。（4）1+1＝2。（5）2100年的春节是晴天。（6）火星上有生物。（7）请安静！（8）今天天气多好啊!（9）现在是几点钟?（1

8、0）我正在说假话。（11）2021/7/30重庆邮电大学理学院13（1）、（2）