离散数学-ch1课件.pptVIP

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