离散数学 东南大学 计算机科学与工程学院 周德宇 dzhou@seu.edu.cn
1 东南大学 计算机科学与工程学院 周德宇 d.zhou@seu.edu.cn
②序言一:什么是离散数学 口研究离散量的结构及相互关系的数学科学 令离散结构:集合、关系、图等 离散量是指分散开来的、不存在中间值的量 口研究对象:有限或可数个元素 自然数、整数,真假值,有限节点等 口计算机技术的支撑科学:计算机只能处理离散 的或离散化了的数量关系
3 序言一：什么是离散数学 ❑研究离散量的结构及相互关系的数学科学 ❖离散结构：集合、关系、图等 离散量是指分散开来的、不存在中间值的量 ❑研究对象:有限或可数个元素 ❖自然数、整数，真假值，有限节点等 ❑计算机技术的支撑科学：计算机只能处理离散 的或离散化了的数量关系
②序言二:与其他专业课关系 人工智能 可计算性理论 编译原理 离散结构 数据结构基础 操作系统 数据库原理 软件工程 4
4 序言二：与其他专业课关系 离散结构 数据结构基础 数据库原理 软件工程 操作系统 编译原理 人工智能 可计算性理论
数理逻辑 口逻辑学分类 ◇辩证逻辑:是研究事物发展的客观规律 形式逻辑:是研究思维的概念、判断和推理的问题 令数理逻辑 口数理逻辑 ◆数学方法研究形式逻辑的一门科学 令一般认为由莱布尼茨( Leibniz)率先提出 令最基本组成部分:命题演算、谓词演算 ☆应用:逻辑电路、自动控制、人工智能等
7 数理逻辑 ❑逻辑学分类 ❖辩证逻辑：是研究事物发展的客观规律 ❖形式逻辑：是研究思维的概念、判断和推理的问题 ❖数理逻辑… ❑数理逻辑 ❖数学方法研究形式逻辑的一门科学 ❖一般认为由莱布尼茨（Leibniz）率先提出 ❖最基本组成部分：命题演算、谓词演算 ❖应用：逻辑电路、自动控制、人工智能等
引语 两栖动物数量的下降清楚地说明全球空气和水质 的污染。在加州 Yosemite国家公园对于两栖动物 所进行的两次研究证实了我的结论。1915年公园 中有7种两栖动物,每种的数量都很丰富。然而 到了1992年在公园中只观察到4种两栖动物,并 且每种动物的数量都显著下降。 Yosemite公园两 栖动物数量的下降曾被归因于始于1920年的在公 园水域引入鲑鱼的行为(我们知道鲑鱼捕食两栖 动物的卵)。但鲑鱼的引入不会是 Yosemite两栖 动物数量下降的真正原因,因为它并不能解释全 球范围的数量下降
8 引语 两栖动物数量的下降清楚地说明全球空气和水质 的污染。在加州Yosemite国家公园对于两栖动物 所进行的两次研究证实了我的结论。1915年公园 中有7种两栖动物，每种的数量都很丰富。然而 到了1992年在公园中只观察到4种两栖动物，并 且每种动物的数量都显著下降。Yosemite公园两 栖动物数量的下降曾被归因于始于1920年的在公 园水域引入鲑鱼的行为（我们知道鲑鱼捕食两栖 动物的卵）。但鲑鱼的引入不会是Yosemite两栖 动物数量下降的真正原因，因为它并不能解释全 球范围的数量下降
问题分析 逻辑主线:全球空气和水质的污染导致了全球两栖动物 数量的下降 错误逻辑:鲑鱼不能解释全球两栖动物下降所以不能解 释公园两栖动物数量下降。 存在问题: 1.在加洲国家公园对两栖动物进行的研究不能推理除全球范围的两 栖动物的数量下降。只能推理除公园里的两栖动物下降。 2.公园内两栖动物数量的下降并不能排除是由鲑鱼引入导致的,逻 辑推理中不可以随意的将影响因素扩大化或缩小化 3.最大得逻辑错误,转化逻辑主体,试图以全球两栖动物数量下降 的事实证明鲑鱼不是 yosemite公园里两栖动物下降得原因。两者 间完全没有逻辑联系 9
9 问题分析 逻辑主线： 全球空气和水质的污染导致了全球两栖动物 数量的下降 错误逻辑： 鲑鱼不能解释全球两栖动物下降所以不能解 释公园两栖动物数量下降。 存在问题： 1. 在加洲国家公园对两栖动物进行的研究不能推理除全球范围的两 栖动物的数量下降。只能推理除公园里的两栖动物下降。 2. 公园内两栖动物数量的下降并不能排除是由鲑鱼引入导致的，逻 辑推理中不可以随意的将影响因素扩大化或缩小化。 3. 最大得逻辑错误，转化逻辑主体，试图以全球两栖动物数量下降 的事实证明鲑鱼不是yosemite公园里两栖动物下降得原因。两者 间完全没有逻辑联系
第一部分数理逻辑 口主要内容(8周的时间) ●命题逻辑基本概念 ●命题逻辑等值演算 ●命题逻辑推理理论 阶逻辑基本概念 一阶逻辑等值演算与推理 10
10 ❑主要内容（8周的时间） ⚫ 命题逻辑基本概念 ⚫ 命题逻辑等值演算 ⚫ 命题逻辑推理理论 ⚫ 一阶逻辑基本概念 ⚫ 一阶逻辑等值演算与推理 第一部分 数理逻辑
第1章命题逻辑基本概念 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值
11 第1章 命题逻辑基本概念 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值
学习要点 命题的概念:定义、逻辑值、符号化表示 2、从简单命题到复合命题: 逻辑联接词:运算方法、运算优先级 3、从命题常量到命题变量, 从复合命题到命题公式: 命题公式的真值描述:真值表 4、命题公式的分类: 永真公式、永假公式、可满足公式、一般公式 12
12 学习要点 1、命题的概念：定义、逻辑值、符号化表示 2、从简单命题到复合命题： 逻辑联接词：运算方法、运算优先级 3、从命题常量到命题变量， 从复合命题到命题公式： 命题公式的真值描述：真值表 4、命题公式的分类： 永真公式、永假公式、可满足公式 、一般公式
91.1命题与联接词 口命题:具有唯一真值陈述句 ◆唯一性:或真或假但不能两者都是的 今命题所用符号:常用小写26个英文字母 口例子 ◆十是整数 2100年人类将在月球生活 ☆X=3 现在是几点? 1+1=2 ☆我现在说假话 X悖论! 13
13 1.1 命题与联接词 ❑命题：具有唯一真值陈述句 ❖唯一性：或真或假但不能两者都是的 ❖命题所用符号：常用小写２６个英文字母 ❑例子 ❖十是整数 ❖2100年人类将在月球生活 ❖x=3 ❖现在是几点？ ❖1+1=2 ❖我现在说假话 悖论！