离散数学导论-第二篇

1、1 离散数学导论（第离散数学导论（第5版）版） 电子教案电子教案 徐洁磐徐洁磐 2 第二篇第二篇 集合论集合论 本篇由集合论初步、关系、函数、有限集与无 限集等与集合论相关等四部分内容组成，它们间是 一个内容关联的整体。 3 第第1章章 集合论初步集合论初步 集合论是数学的基础，也是离散数学的基础。 故学好集合论十分重要，在本章学习中要掌握： 集合中的一个基本概念 集合中的两种关系 集合中的三种特殊集合 集合中的三种表示方法 集合中的五种运算 集合中的21个常用公式 4 1.1 集合论基本概念集合论基本概念 （1） 一个主要的概念一个主要的概念集合的基本概念集合的基本概念：一些不同确 定的对象

2、全体称集合，而这些对象称集合的元素。 （2）集合中的两个关系集合中的两个关系 集合间的比较关系：AB，AB，AB， AB。 集合与元素间的隶属关系：aA，aA。 （3） 三种特殊的集合三种特殊的集合 空集 全集E 幂集（A）。 5 （4） 集合的三种表示法：集合的三种表示法： 枚举法枚举法。即将集合元素一一列举。例：1, 2, 3, 特性刻划法特性刻划法。即用元素的性质刻划集合。例：x | p (x) 图示法图示法。即用文氏图表示集合及集合间的关系。例： AAB 6 1.2 集合运算集合运算 （5）集合的五种运算：集合的五种运算： 交运算：AB 倂运算：AB 差运算：AB 补运算：A 对称差运

3、算：AB 7 （6）集合的集合的21个公式：个公式： 交换律：交换律： ABBA ABBA 结合律：结合律： A（BC）（AB）C A（BC）（AB）C 分配律：分配律： A（BC）（AB）（AC） A（BC）（AB）（AC） 8 同一律：同一律： AA AEA 零一律：零一律： AEE A 互补律：互补律： AAE AA 双补律：双补律： （A）A 9 E与与 的互补：的互补： E E 等幂律：等幂律： AAA AAA 吸收律：吸收律： A（AB）A A（AB）A 狄狄 莫根定律：莫根定律： （AB）AB （AB）AB 10 1.3 幂集幂集 幂集定义：集合A的所有子集所组成的集合，可记 为

4、（A）。 幂集性质：|A|n 则| (A) |2 n 11 第第2章章 关系关系 关系研究集合内元素间的关联及集合间元素关联，主要有： 一种预备知识 一个基本概念 两种表示方法 三种运算 九个公式 五种性质 六种常用关系 12 2.1 关系的预备知识 n元有序组与笛卡尔乘积 n元有序组是一种特殊的集合结构形式，它有两个基 本概念与一种基本运算（笛卡尔乘积）。 基本概念之一：有序偶。例：（a , b） 基本概念之二： n元有序组。例：（a1, a2,an） 基本运算：笛卡尔乘积。例：AB 13 2.2 关系基本概念 （1）一个主要的概念二元关系的基本 概念： 关系定义：关系定义：从集合A到B的关

5、系R是A B的 一个子集。 （2）两种表示方法： 集合表示法：集合表示法：有序偶的集合 图表示法：图表示法：有向图 14 2 2. .3 3关系运算关系运算 （3）两种运算： 关系的复合运算复合运算 关系的逆运算逆运算 （4）有关运算的五个公式： 复合运算的公式：复合运算的公式： (R S ) TR (S T) RmRnRm+n (Rm)nRmn 逆运算的公式：逆运算的公式： RR (R S) R S 15 2.4 关系重要性质 （5）关系的五种性质 关系的自反性 关系的反自反性 关系的对称性 关系的反对称性 关系的传递性 16 （6）六种常用关系 次序关系之一：偏序关系 次序关系之二：拟序关

6、系 次序关系之三：线性次序关系 次序关系之四：字典次序关系 相容关系 等价关系 17 2.5 闭包运算 （1）关系的闭包运算闭包运算 自反闭包 r (R) 对称闭包 s (R） 传递闭包 t (R） （2）闭包的公式：闭包的公式： r（R）R Q s（R） R Q t（R）Ri i=1 18 2.6 次序关系 （7）次序关系 四个定义： 偏序关系：X上自反、反对称与传递的关系称偏序关系 并用 表示。 拟序关系：反自反、传递的关系称拟序关系并用 表示。 线性次序关系：X上偏序关系R如有x , yx必有x y或y x则称R是X上线性次序关系。 字典次序关系：有限字母表 上的偏序关系。 如建立上的次

7、序关系： 设x=x1, x2,xn , y=y1, y2,ym ；x , y*；x1 , x2,xn ,y1 , y2 ,ym. 19 （1）x1y1且如x1y1则我们说xLy；如y1x1，则我们说yLx； （2）如存在一个最大的K且Kmin (n，m)，使得x1y1，x2 y2，xkyk而xk1yk+1，如果xk1yk1，则我们 说xLy；如yk1xk1，则我们说yLx； （3）如存在一个最大的Kmin (n，m)，使得x1y1，x2 y2，xnyn，此时如nm，则我们说xLy；如mn，则 我们说yLx。 20 四个次序关系间的关系： R是拟序则r (R) = R R是偏序则RQ是拟序 字典

8、次序关系必为线性次序关系 R是拟序则必反对称 八个概念： 最大元素（最小元素） 极大元素（极小元素） 上界（下界） 上确界（下确界） 21 2.7 相容关系 （8）相容关系 相容关系定义X上自反、对称关系称相容关系并用 “”表示 。 相容关系的极大相容块设有集合X上的相容关系， 设A是X的子集，如A中任何元素都互为相容，且XA中的 任何元素没有一个与A中的所有元素相容，则称A是X中的极 大相容性分块。 相容关系完全覆盖X上相容关系，它的极大相 容性分块的集合称X的完全覆盖。 22 2.8 等价关系 （9）等价关系 等价关系定义X上自反、对称、传递的关系称等 价关系。 等价类R是X上等价关系，对

9、xX可构造一个X的 子集xR称为x 对R的等价类。 划分S的子集A1，A2，An满足： Ai均分离 (i=1，2，n) A1A2AnS则AA1，A2， An为S的划分，而Ai称为划分的块（i=1, 2,n）。 商集X上等价关系R所构成的类产生X的划分叫X 关于R的商集记以XR。 23 第第3章章 函数函数 函数是一种特殊的关系，它在数学中具有普遍 重要价值，函数主要内容有： 一个基本概念 两种基本运算 三种性质函数 四种常用函数 24 3.1 3.1 函数的基本概念函数的基本概念 （1）一个基本概念函数的基本概念。 函数建立了从一个集合到另一个集合的特殊对应关系。设有 集合X与Y，如果我们有一

10、种对应关系f，使X的任一元素x能与y中 的一个唯一的元素y相对应，则这个对应关系f叫从X到Y的函数或 叫从X到Y的映射。x所对应的y内的元素y叫x的像，而x则叫y的像 源。上述函数我们可以表示成f：XY；或写成XY；以及yf （x）。 （2）三种不同性质函数： 满射与 一对一与多对一 一一对应（双射） 25 y1 y2 y3 y4 x1 x2 x3 x4 y1 y2 y3 y4 x1 x2 x3 x4 x5 y1 y2 y3 y4 x1 x2 x3 x4 X Y g X Y f X Y h 26 从图中可以看出函数f使得Y中的每个元素均有X中的 元素与之对应，这种函数叫做从X到Y上的函数，否则

11、叫 做从X到Y内的函数。 从图中可以看出，函数g使得不但X中的每一个元素xi 唯一对应一个Y中的一个元素yj，而且也只有一个xi对应 yj，也就是说一个像只有一个像源与之对应，这种函数叫 做一对一的函数，否则叫做多对一的函数。 从图中可以看出，函数h使得X与Y间建立了一对应 的关系，这种函数叫X与了间一对应的函数。 27 3 3. .2 2 复合函数复合函数、反函数反函数、多元函数多元函数 （3）两种运算： 复合运算（复合函数）设函数f：XY，g：YZ则复合 函数hgf：XZ是一个新的函数。 定义：设函数f：XY，g：YZ，它们所组成的复合函数 或叫复合映射gf，也是一个函数h：XZ，即： h

12、gf：(x , z)|xX , zZ且至少存在一个yY，有y=f （x），zg（y） 28 y1 y2 x1 x2 x3 z1 z2 Y XZ h f g 29 逆运算（反函数） 定义：定义：设f：XY是一对应的函数，则f所构成的 逆关系叫f的逆映射或叫f的反函数，记以f1：Y X （4）函数分类： 一元函数：f (x) 二元函数：f (x , y) 多元函数：f (x1, x2, xn) 30 3.3常用函数常用函数 （5） 四种常用函数 常值函数：f (x)b 恒等函数：f (a)a 单调递增函数与严格单调递增函数：ab，必有f (a)f (b) ：ab，必有f (a)f (b) 单调递减

13、函数与严格单调递减函数 ：ab，必有f (a)f (b) ：ab，必有f (a)f (b) 1 aA 特征函数： f (a) 0 aA 31 第第4章章 有限集与无限集有限集与无限集 4.1 有限集与无限集基本概念有限集与无限集基本概念 （1）有限集与无限集的基本概念 有限集的两个定义 集合S与Nn一 一对应 非无限集即为有限集 无限集的两个定义 S与一 一对应函数f：SS使得：f (S) S S存在与其等势的真子集 32 4.2 有限集有限集 （2）有限集 有限集的基数有限集元素个数 有限集的计数计算有限集中元素个数 有限集计数的四种方法： |AB|A|+|B| |AB|A|+|B|AB| |ABC| |A|+|B|+|C| |AB| |AC| |BC|+|ABC| |S1S2Sn|Si|SiSj| |SiSjSk|（1）|S1S