离散数学导论（第四版）徐洁磐.pptVIP

离散数学导论（第四版） 电子教案 徐洁磐 第一篇 绪言 本篇是对离散数学的宏观介绍。 1． 计算机学科与离散数学 介绍离散数学在计算机学科发展中的作用与关系，明确离散数学是掌握与研究计算机学科的基础理论与工具。 2．离散数学的特征 ? 离散性 ? 可构造性 ? 抽象性 3．离散数学的内容 离散数学的主要内容为： ? 集合论 ? 代数结构 ? 图论 ? 数理逻辑 第二篇 集合论 本篇由集合论初步、关系、函数、有限集与无限集等与集合论相关等四部分内容组成，它们间是一个内容关联的整体。 第一章 集合论初步 集合论是数学的基础，也是离散数学的基础。故学好集合论十分重要，在本章学习中要掌握： ? 集合中的一个基本概念 ? 集合中的两种关系 ? 集合中的三种特殊集合 ? 集合中的三种表示方法 ? 集合中的五种运算 ? 集合中的21个常用公式 §1.1 集合论基本概念 （1） 一个主要的概念——集合的基本概念：一些不同确定的对象全体称集合，而这些对象称集合的元素。 （2）集合中的两个关系 ? 集合间的比较关系：A＝B，A≠B，A?B，A?B。 ? 集合与元素间的隶属关系：a?A，a?A。 （3） 三种特殊的集合 ? 空集? ? 全集E ? 幂集?（A）。 （4） 集合的三种表示法： ? 枚举法。即将集合元素一一列举。例：{1, 2, 3,…} ? 特性刻划法。即用元素的性质刻划集合。例：{x | p (x)} ? 图示法。即用文氏图表示集合及集合间的关系。例： § 2.2 集合代数 （5）集合的五种运算： ? 交运算：A∩B ? 倂运算：A∪B ? 差运算：A－B ? 补运算：～A ? 对称差运算：A＋B （6）集合的21个公式： 交换律： A∪B＝B∪A A∩B＝B∩A 结合律： A∪（B∪C）＝（A∪B）∪C A∩（B∩C）＝（A∩B）∩C 分配律： A∪（B∩C）＝（A∪B）∩（A∩C） A∩（B∪C）＝（A∩B）∪（A∩C） 同一律： A∪?＝A A∩E＝A 零一律： A∪E＝E A∩?＝? 互补律： A∪～A＝E A∩～A＝? 双补律： ～（～A）＝A E与? 的互补： ～E＝? ～?＝E 等幂律： A∪A＝A A∩A＝A 吸收律： A∪（A∩B）＝A A∩（A∪B）＝A 狄·莫根定律： ～（A∪B）＝～A∩～B ～（A∩B）＝～A∪～B §1.3 幂集 ? 幂集定义：集合A的所有子集所组成的集合，可记为?（A）。 ? 幂集性质：|A|＝n 则| ? (A) |＝2 n 第二章 关系 关系研究集合内元素间的关联及集合间元素关联，主要有： ? 一种预备知识 ? 一个基本概念 ? 两种表示方法 ? 三种运算 ? 九个公式 ? 五种性质 ? 六种常用关系 §2.1 关系的预备知识－ n元有序组与笛卡尔乘积 n元有序组是一种特殊的集合结构形式，它有两个基本概念与一种基本运算（笛卡尔乘积）。 ? 基本概念之一：有序偶。例：（a , b） ? 基本概念之二： n元有序组。例：（a1 , a2 ,…an ） ? 基本