引言 课程简介 离散数学是现代数学的一个重要分支，是计算 机科学中基础理论的核心课程，它研究的对象 是有限个或可数的离散量。充分描述了计算机 科学离散性的特征。 离散数学是传统的逻辑学、集合论、数论基础、 算法设计、组合分析、离散概率、关系理论 图论与树、抽象代数、 布尔代数、计算模型等 汇集起来的一门综合学科。离散数学的应用遍 及现代科学技术的诸多领域。 离散数学是随着计算机科学的发展而逐步建立 起来的一门新兴的工具性学科，形成于上上个 世纪七十年代。 2/73
2/73 引言 •课程简介 –离散数学是现代数学的一个重要分支，是计算 机科学中基础理论的核心课程，它研究的对象 是有限个或可数的离散量。充分描述了计算机 科学离散性的特征。 –离散数学是传统的逻辑学、集合论、数论基础、 算法设计、组合分析、离散概率、关系理论、 图论与树、抽象代数、布尔代数、计算模型等 汇集起来的一门综合学科。离散数学的应用遍 及现代科学技术的诸多领域。 –离散数学是随着计算机科学的发展而逐步建立 起来的一门新兴的工具性学科，形成于上上个 世纪七十年代
引言 课程意义 -离散数学是计算机科学的数学基础，其基本概念 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。 离散数学学习十分有益于概括抽象能力、逻辑思 维能力、归纳构造能力的提高，能够培养提高学生 的数学思维能力和对实际问题的求解能力。 教学内容 -数理逻辑、集合论、代数结构、图论 3/73
3/73 引言 •课程意义 –离散数学是计算机科学的数学基础，其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。 –离散数学学习十分有益于概括抽象能力、逻辑思 维能力、归纳构造能力的提高，能够培养提高学生 的数学思维能力和对实际问题的求解能力。 •教学内容 –数理逻辑、集合论、代数结构、图论
第一部分数理逻辑 •逻辑学 -是一门研究思维形式和规律的科学。分为辩证逻 辑和形式逻辑两种。思维的形式结构包括了概念 、 判断和推理之间的结构和联系，其中概念是思 维的基本单位，通过概念对事物是否具有某种属 性进行肯定或否定的回答，就是判断。由一个或 几个判断推出另一判断的思维形式就是推理。 数理逻辑 一用数学方法研究推理的规律称为数理逻辑。所谓 数学方法就是引用一套符号体系的方法，所以数 理逻辑又称作符号逻辑。 773
7/73 第一部分 数理逻辑 •逻辑学 –是一门研究思维形式和规律的科学。分为辩证逻 辑和形式逻辑两种。思维的形式结构包括了概念 ﹑判断和推理之间的结构和联系，其中概念是思 维的基本单位，通过概念对事物是否具有某种属 性进行肯定或否定的回答，就是判断。由一个或 几个判断推出另一判断的思维形式就是推理。 •数理逻辑 –用数学方法研究推理的规律称为数理逻辑。所谓 数学方法就是引用一套符号体系的方法，所以数 理逻辑又称作符号逻辑
第一部分数理逻辑 现代数理逻辑 逻辑演算、逻辑演绎、模型论、证明论、 递归函数论、公理化集合论等 我们要介绍的是数理逻辑中最基本的内容： 命题逻辑和谓词逻辑。即一般所谓的古典 逻辑。 德国数学家莱布尼茨Leibniz（现代逻辑的 首席创始人)；布尔Boole（奠基人，逻辑 的数学分析)；弗雷格 （数论的基础) 8/73
8/73 第一部分 数理逻辑 •现代数理逻辑 –逻辑演算、逻辑演绎、模型论、证明论、 递归函数论、公理化集合论等。 –我们要介绍的是数理逻辑中最基本的内容： 命题逻辑和谓词逻辑。即一般所谓的古典 逻辑。 –德国数学家莱布尼茨Leibniz（现代逻辑的 首席创始人）；布尔Boole （奠基人，逻辑 的数学分析）；弗雷格（数论的基础）
第一章命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究 以“命题”为基本单位构成的前提和结论之 间的可推导关系，研究什么是命题？如何表 示命题？怎样由一组前提推导一些结论。 判断 概念 推理 9/73
9/73 第一章 命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究 以“命题”为基本单位构成的前提和结论之 间的可推导关系，研究什么是命题？如何表 示命题？怎样由一组前提推导一些结论。 判断 概念 推理
1.1命题与命题联结词 1.1.1命题 定义1.1：具有确切真值的陈述句（或断言）称 为命题(Proposition)。 命题的取值称为真值。真值只有“真”和 “假”两种，分别用“T”或“1”和“F”或 “0”表示。 注意：命题的真值非真即假，只有两种取值， 这样的系统为二值逻辑系统。 10/73
10/73 1.1 命题与命题联结词 1.1.1命题 •定义1.1：具有确切真值的陈述句(或断言)称 为命题(Proposition)。 •命题的取值称为真值。真值只有“真”和 “假”两种，分别用“T”或“1”和“F”或 “0”表示。 •注意：命题的真值非真即假，只有两种取值， 这样的系统为二值逻辑系统
1.1命题与命题联结词 例1-1：命题示例。 (a):今天下雪 (b):3+3=6 (c):2是偶数而3是奇数 (:陈胜起义那天，合肥下雨 (e):较大的偶数都可表为两个质数之和 (f):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):我正在说谎。 •注意：由定义知，一切没有判断内容的句子 如命令，感叹句，疑问句，祈使句，二义性 的陈述句等都不能作为命题
1.1命题与命题联结词 例1-2：下列句子哪些是命题，判断命 题的真假。 (1):2是素数 2):北京是中国的首都 (3):这个语句是假的 (4):x+y>0 (5):我喜欢踢足球 (⑥)：地球外的星球上也有人 (7):明年国庆节是晴天 (8)把门关上 9):你要出去吗？ (10):今天天气真好啊！ 12/73
12/73 1.1 命题与命题联结词 •例1-2：下列句子哪些是命题，判断命 题的真假。 (1):2是素数 (2):北京是中国的首都 (3):这个语句是假的 (4):x+y>0 (5):我喜欢踢足球 (6):地球外的星球上也有人 (7):明年国庆节是晴天 (8):把门关上 (9):你要出去吗？ (10):今天天气真好啊！
1.1命题与命题联结词 •注意 一命题一定是通过陈述句来表达；反之，并非一 切的陈述句都一定是命题。 -命题的真值有时可明确给出， 有时还需要依靠 环境条件，实际情况，时间才能确定其真值。 但其真值一定是唯一确定的。 1373
13/73 •注意 –命题一定是通过陈述句来表达；反之，并非一 切的陈述句都一定是命题。 –命题的真值有时可明确给出，有时还需要依靠 环境条件，实际情况，时间才能确定其真值。 但其真值一定是唯一确定的。 1.1 命题与命题联结词
1.1命题与命题联结词 命题可分为两种类型： 简单命题：若一个命题已不能分解成更简单的 命题，则该命题叫原子命题或本原命题或简单 命题(Simple Proposition） 复合命题(Compound Proposition): 可以分 解为简单命题的命题，而耳这些简单命题之间 是通过关联词”（如或者带，“并且，“罘 如果.…则”，“当且仅当” 等)和标点符号复 合而构成一个复合命题。 例，合肥是安徽的省会当且仅当鸟会飞。 ·注意： -命题通常用大写英文字母 (可带下标)来表示。 14/73
14/73 1.1 命题与命题联结词 •命题可分为两种类型： –简单命题：若一个命题已不能分解成更简单的 命题，则该命题叫原子命题或本原命题或简单 命题（Simple Proposition） –复合命题（Compound Proposition）：可以分 解为简单命题的命题，而且这些简单命题之间 是通过关联词（如“或者” , “并且” , “不” ， “如果… 则…” , “当且仅当”等）和标点符号复 合而构成一个复合命题。 例，合肥是安徽的省会当且仅当鸟会飞。 •注意： –命题通常用大写英文字母（可带下标）来表示