离散数学及应用

《离散数学及应用》由会员分享，可在线阅读，更多相关《离散数学及应用（1148页珍藏版）》请在金锄头文库上搜索。

1、2019/5/13,1,离散数学(Discrete Mathematics),计算机科学与技术学院 （ School of Computer Science & Technology) 魏雪丽,2019/5/13,计算机科学与技术学院,引 言,一. 离散数学与计算机 计算机开辟了脑力劳动机械化和自动化的新纪元。 计算机的诞生，人们就要为它进一步发展创建新的理论，就要寻找合适的数学工具。 例：为了描述新开拓的应用领域中的各种数据的结构，就需要适宜的数学工具。,2019/5/13,计算机科学与技术学院,引 言（续）,故计算机各分支领域中的理论问题，交错地使用着现代数学的各种不同的论题。 因为计算机

2、系统从本质上说是一种离散性的结构 ，它的许多性质可以在有限数学系统的框架中来理解，从中选出一些必要而且是基本的主干论题称为离散数学。 因此，离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。,2019/5/13,计算机科学与技术学院,引 言（续）,离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，是计算机科学与技术专业的核心、骨干课程。 它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。,2019/5/13,计算机科学与技术学院,引 言（续）,二、该课程的主要内容： 离

3、散数学课程的主要内容可以分为四个部分： 数理逻辑，包括命题逻辑和谓词逻辑。(教材的第一、二章) 集合论，包括集合、关系和函数。（教材的第三、四章） 代数系统，包括代数系统的一般概念，几类典型的代数系 统和格。（教材的第五、六章） 图论，包括图的基本概念，几种特殊的图。 (教材的第七章),2019/5/13,计算机科学与技术学院,引 言（续）,三、学习该课程的目的： 1. 为学习计算机后继课程，如数据结构、编译理论、操作系统、数据库原理、形式语言及自动机、软件工程与方法学、计算机网络和人工智能、高级程序设计语言等，提供必要的数学基础；为阅读计算机文章作充分的数学准备。,2019/5/13,计算机

4、科学与技术学院,引 言（续）,数理逻辑：人工智能，数据库，形式语言及自动机， 高级程序设计语言。 集合论： 信息结构与检索，数据结构。 图论： 可计算性理论，计算机网络,数据结构。 代数结构：开关理论，逻辑设计和程序理论，语法 分析。 2. 通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，获得解决实际问题能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础。,2019/5/13,计算机科学与技术学院,引 言（续）,四、教学要求： 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。 五、自学要求： 由于课时少，内容多且抽

5、象，故要求课前预习，课后复习；认真完成习题，通过做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。 作业每星期一交，作为平时成绩。,2019/5/13,计算机科学与技术学院,引 言（续）,六、参考教材： 1.离散数学及其应用魏雪丽等编著 机械工业出版社 2 .离散数学 左孝凌等著 上海科技文献出版社 3. 离散数学 理论分析题解 左孝凌等著 上海科技文献出版社 4. Discrete Mathematics and Its Applications （英文版） (美)Kenneth H.Rosen 著 机械工业出版社,2019/5/13,计算机科学与技术学

6、院,引 言（续）,七、考核方式： 期末考试成绩占70%, 平时成绩占30%.,2019/5/13,计算机科学与技术学院,第一部分 数理逻辑（Mathematical Logic),逻辑：是研究推理的科学。公元前四世纪由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。 逻辑可分为：1. 形式逻辑（通过数学方法） 数理逻辑 2. 辩证逻辑 指引进一套符号体系的方法。 辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。,2019/5/13,计算机科学与技术学院,第一部分 数理逻辑（Mathematic

7、al Logic),形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。 数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。,2019/5/13,计算机科学与技术学院,第一部分 数理逻辑（Mathematical Logic),1931年Godel不完全性定理的提出，以及递归

8、函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。 从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书课程只研究这两个演算。,2019/5/13,计算机科学与技术学院,第一部分 数理逻辑（Mathematical Logic),数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic）,1.

9、1 命题及其表示方法(Proposition and Its Expression) 1.2 逻辑联结词(Logical Connectives) 1.3 命题公式与翻译(Propositional Formula & Its Translation) 1.4 真值表与等价公式(Truth Tables and Prepositional Equivalences),2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic）,1.5 重言式与蕴含式(Tautology and Implication ) 1.6 其它联结词(Other Connecti

10、ves) 1.7 对偶与范式(Dual & Normal Form) 1.8 推理理论(Inference Theory ),2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic）,1.1 命题及其表示方法 1.1.1 命题 1.1.2 命题的表示方法 1.1.3 命题的分类,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,1.1.1 命题（Proposition) 数理逻辑研究的中心问题是推理（inference),而推理的前提和结论都是表达判断的陈述句，因而表达判断

11、的陈述句构成了推理的基本单位。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 真命题：判断为正确的命题，即真值为真的命题。 假命题：判断为错误的命题，即真值为假的命题。,2019/5/13,计算机科学与技术学院,因而又可以称命题是具有唯一真值的陈述句。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 例：判断下列句子是否为命题。

12、(1). 100是自然数。 T (2). 太阳从西方升起。 F,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,(3). 3+3=8 . F (4). How do you do ? 疑问句，不是命题 (5). 明年的十月一日是晴天。是命题，其真值到明年十月一日方可知道。 (6). x+39 不是命题 (7). 我正在说谎。是悖论,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic）

13、 1.1 命题及其表示方法,(8). 1+101=110 二进制中为真，十进制中为假。 (9). 如果太阳从西方升起，那么2是奇数。T (10). 国足能杀入2006世界杯当且仅当2+2=4。F (11). 今天天气多好啊！ 感叹句，不是命题 (12). 请你关上门！ 祁使句，不是命题， (13). 别的星球上有生物。 是命题，客观上能判断真假。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,说明： （1）只有具有确定真值的陈述句才是命题。 一切没有判断内容的句子，无所谓 是非的句子，如感叹句、祁使句、 疑问 句

14、等都不是命题。 （2） 因为命题只有两种真值，所以“命题 逻 辑”又称 “二值逻辑”。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,(3) “具有确定真值”是指客观上的具有，与我们 是否知道它的真值是两回事。如上例中 的（5）和（13）。 1.1.2 命题的表示方法 在本书中，用大写英文字母A,B,P,Q或带下标的字母P1,P2,P3 , ,或数字(1),2, ,等表示命题，称之为命题标识符。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其

15、表示方法,例如： P：罗纳尔多是球星。 Q：5是负数。 P3：明天天气晴。 (2)：太阳从西方升起。 皆为符号化的命题，其真值依次为1、0、1或0、0。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,命题标识符又有命题常量、命题变元和原子变元 之分。 命题常量：表示确定命题的命题标识符。 命题变元：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元。 原子变元：当命题变元表示原子命题时，该变元称为 原子变元。 命题变元也用A,B,P,Q,P1,P2,P3 , , 表示。,2019/5/13,计算机科学与技术

16、学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,1.1.3 命题的分类： 简单/原子命题：不能分解为更简单的陈述语 句的命题(如上例中的命题)。 复合命题：由简单命题通过联结词联结而成 的命题。联结词就是复合命题中的运算符。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,注意： （1）一个符号(如P), 它表示的是命题常量还是命题变元，一般由上下文来确定。 （2）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。,2019/5/13,计算机科学与技术学院,第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法,小结：本节主要介绍了命题、命题的真值、 原子命题、复合命题、命题标识符、命题常量、 命题变元和原子变元的概念。 重点理解和掌握命题、命题变元、简单（原子） 命题、复