离散数学-数理逻辑.pptxVIP

离散数学

DiscreteMathematics;离散数学课程地位：

计算机系核心课程

信息类专业必修课程

其它类专业的重要选修课程

离散数学的后继课程：

数据结构、操作系统、

算法分析与设计、

数据库、c++语言……

;学习该课程的目的：

一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络、程序设计等，提供必要的数学基础；

另一方面，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础。;教学要求：

通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。

自学要求：

通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。;离散数学课程的学习方法:

强调：逻辑性、抽象性；

注重：概念、方法与应用

离散数学的学习要领：

概念（正确）必须掌握好离散数学中大量的概念

判断（准确）根据概念对事物的属性进行判断

推理（可靠）根据多个判断推出一个新的判断;离散数学的内容

第一部分数理逻辑：命题逻辑、谓词逻辑

第二部分集合论：集合、关系、函数

第三部分代数系统：运算、代数系统、半群、

群、环、域、格、布尔代数

第四部分图论：点与边、路与圈、最短路、

Euler图、Hamilton图、平面图、树;离散数学与计算机的关系;第一章命题逻辑;数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。

上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。

1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。

;数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊??辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。

本章和下一章我们只从语义出发，对数理逻辑中的命题逻辑与谓词逻辑等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。

;第一章命题逻辑;注意:感叹句、祈使句、疑问句都不是命题.陈述句中的悖论以及判断结果不惟一确定的也不是命题。;（1）、（2）、（3）、（4）、（5）和（6）都是命题。其中（1）、（2）、（4）是真命题，（3）是假命题。

至于（5）和（6）真假值是确定的，只是现在无法知道，因此它是命题。

（7）、（8）、（9）、（10）、（11）都不是命题。原因在于（7）是祈使句，（8）是感叹句，（9）是疑问句，而（10）是悖论，即若(10)的真值为真，即“我正在说假话”为真，也就是我说的是假话，因此（10）又是错误的；反之，若(10)的真值为假，即“我正在说假话”为假，也就是我在说真话，因此(10)的真值应为真。

像(10)这样既不为真又不为假的陈述句不是命题，这种陈述句称为悖论。凡是悖论都不是命题。（11）中的x、y的值不确定，某些x、y使为真，某些x、y使为假，即的真假随x、y的变化而变化。因此，的真假无法确定，所以不是命题。;练习判断下列句子是否为命题。

1.100是自然数。

2.太阳从西方升起。

3.北京是中国的首都

4.重庆是中国最大的城市

5.关门!

6.你去哪里?

7.Howdoyoudo?

8.凡石头均可炼成金。

9.x+39

10.皇马中国之行没有提升国家队的水平。;命题表示

在本书中，用大写的英文字母P,Q,R,…，P1,P2,P3…，[1]，[2]等表示命题,用“1(或者T）”、“0（或者F）”分别表示真值的真、假。

如P：太阳从东边升起。

Q：5是负数。

[1]：2008北京举办奥运会。

其真值依次为1、0、1。;命题的分类

简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。

复合命题：由简单命题通过联结词联结而成的陈述句。

如：

命题“如果2是素数，则3也是素数”通过“如果……，则……”组合而成，是复合命题，而“2是素数”和“3是素数”是简单命题。;2.命题联结词;（1）否定联结词

设p为命题，复合命题“非P”（或“P的否定”