中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第一部分 数理逻辑 第一章 命题逻辑（主讲：肖明军）

引言 课程简介 离散数学是现代数学的一个重要分支,是计算 机科学中基础理论的核心课程,它研究的对象 是有限个或可数的离散量。充分描述了计算机 科学离散性的特征。 离散数学是传统的逻辑学、集合论、数论基础、 算法设计、组合分析、离散概率、关系理论、 图论与树、抽象代数、布尔代数、计算模型等 汇集起来的一门综合学科。离散数学的应用遍 及现代科学技术的诸多领域。 离散数学是随着计算机科学的发展而逐步建立 起来的一门新兴的工具性学科,形成于七十年 代

2/73 引言 •课程简介 –离散数学是现代数学的一个重要分支，是计算 机科学中基础理论的核心课程，它研究的对象 是有限个或可数的离散量。充分描述了计算机 科学离散性的特征。 –离散数学是传统的逻辑学、集合论、数论基础、 算法设计、组合分析、离散概率、关系理论、 图论与树、抽象代数、布尔代数、计算模型等 汇集起来的一门综合学科。离散数学的应用遍 及现代科学技术的诸多领域。 –离散数学是随着计算机科学的发展而逐步建立 起来的一门新兴的工具性学科，形成于七十年 代

引言 课程意义 离散数学是计算机科学的数学基础,其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中,是这些课程的基 础课程。 离散数学学习十分有益于概括抽象能力、逻辑思 维能力、归纳构造能力的提高,能够培养提高学生 的数学思维能力和对实际问题的求解能力。 教学内容 数理逻辑、集合论、代数结构、图论 3/73

3/73 引言 •课程意义 –离散数学是计算机科学的数学基础，其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。 –离散数学学习十分有益于概括抽象能力、逻辑思 维能力、归纳构造能力的提高，能够培养提高学生 的数学思维能力和对实际问题的求解能力。 •教学内容 –数理逻辑、集合论、代数结构、图论

引言 教学内容 第一部分数理逻辑 第一章命题逻辑 第二章谓词逻辑 第二部分集合论 第三章集合代数 第四章二元关系 4/73

4/73 引言•教学内容 第一部分 数理逻辑 第一章 命题逻辑 第二章 谓词逻辑 第二部分 集合论 第三章 集合代数 第四章 二元关系

引言 教学内容 第二部分集合论 第五章函数 第六章集合的基数 第三部分代数结构 第七章代数系统 第八章群论

5/73 引言•教学内容 第二部分 集合论 第五章 函数 第六章 集合的基数 第三部分 代数结构 第七章 代数系统 第八章 群论

引言 教学内容 第三部分代数结构 第九章环与域 第十章格与布尔代数 6/73

6/73 引言 •教学内容 第三部分 代数结构 第九章 环与域 第十章 格与布尔代数

第一部分数理逻辑 逻辑学 是一门研究思维形式和规律的科学。分为辩证逻 辑和形式逻辑两种。思维的形式结构包括了概念 判断和推理之间的结构和联系,其中概念是思 维的基本单位,通过概念对事物是否具有某种属 性进行肯定或否定的回答,就是判断。由一个或 几个判断推出另一判断的思维形式就是推理 数理逻辑 用数学方法研究推理的规律称为数理逻辑。所谓 数学方法就是引用一套符号体系的方法,所以数 理逻辑又称作符号逻辑。 7/73

7/73 第一部分 数理逻辑 •逻辑学 –是一门研究思维形式和规律的科学。分为辩证逻 辑和形式逻辑两种。思维的形式结构包括了概念 ﹑判断和推理之间的结构和联系，其中概念是思 维的基本单位，通过概念对事物是否具有某种属 性进行肯定或否定的回答，就是判断。由一个或 几个判断推出另一判断的思维形式就是推理。 •数理逻辑 –用数学方法研究推理的规律称为数理逻辑。所谓 数学方法就是引用一套符号体系的方法，所以数 理逻辑又称作符号逻辑

第一部分数理逻辑 现代数理逻辑 逻辑演算、逻辑演绎、模型论、证明论、 递归函数论、公理化集合论等。 我们要介绍的是数理逻辑中最基本的内容: 命题逻辑和谓词逻辑。即一般所谓的古典 逻辑。 德国数学家莱布尼茨 Leibniz(现代逻辑的 首席创始人);布尔 Boole(奠基人,逻辑 的数学分析);弗雷格(数论的基础) 8/73

8/73 第一部分 数理逻辑 •现代数理逻辑 –逻辑演算、逻辑演绎、模型论、证明论、 递归函数论、公理化集合论等。 –我们要介绍的是数理逻辑中最基本的内容： 命题逻辑和谓词逻辑。即一般所谓的古典 逻辑。 –德国数学家莱布尼茨Leibniz（现代逻辑的 首席创始人）；布尔Boole （奠基人，逻辑 的数学分析）；弗雷格（数论的基础）

第一章命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究 以“命题”为基本单位构成的前提和结论之 间的可推导关系,研究什么是命题?如何表 示命题?怎样由一组前提推导一些结论。 判断 概念 推理 9/73

9/73 第一章 命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究 以“命题”为基本单位构成的前提和结论之 间的可推导关系，研究什么是命题？如何表 示命题？怎样由一组前提推导一些结论。 判断 概念 推理

11命题与命题联结词 11.1命题 定义1.1:具有确切真值的陈述句(或断言)称 为命题( Proposition) 命题的取值称为真值。真值只有“真”和 “假”两种,分别用“T”或“1”和“F”或 0”表示 注意:命题的真值非真即假,只有两种取值, 这样的系统为二值逻辑系统。 0/73

10/73 1.1 命题与命题联结词 1.1.1命题 •定义1.1：具有确切真值的陈述句(或断言)称 为命题(Proposition)。 •命题的取值称为真值。真值只有“真”和 “假”两种，分别用“T”或“1”和“F”或 “0”表示。 •注意：命题的真值非真即假，只有两种取值， 这样的系统为二值逻辑系统

11命题与命题联结词 例1-1:命题示例。 (a):今天下雪(b):3+3=6 (c)2是偶数而3是奇数 (d):陈胜起义那天,杭州下雨 (e):较大的偶数都可表为两个质数之和 ():x+y>4 (g)真好啊! (h):x=3 :你去哪里?(:我正在说谎。 注意:由定义知,一切没有判断内容的句子 如命令,感叹句,疑问句,祈使句,二义性 的陈述句等都不能作为命题。 11/73

11/73 1.1 命题与命题联结词 •例1-1：命题示例。 (a):今天下雪 (b):3+3=6 (c):2是偶数而3是奇数 (d):陈胜起义那天，杭州下雨 (e):较大的偶数都可表为两个质数之和 (f):x+y>4 (g):真好啊! (h):x=3 (i):你去哪里？ (j):我正在说谎。 •注意：由定义知，一切没有判断内容的句子 如命令，感叹句，疑问句，祈使句，二义性 的陈述句等都不能作为命题