离散数学集合论.ppt

《离散数学集合论.ppt》由会员分享，可在线阅读，更多相关《离散数学集合论.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学集合论现在学习的是第1页，共32页第四章 集合论初步 集合论是数学的基础，也是离散数学的基础。故学好集合论十分重要，在本章学习中要掌握：集合中的一个基本概念 集合中的两种关系 集合中的三种特殊集合 集合中的四种表示方法 集合中的五种运算 集合中的21个常用公式现在学习的是第2页，共32页4.1 集合论基本概念集合论基本概念（1）一一个个主主要要的的概概念念集集合合的的基基本本概概念念：一些不同确定的对象全体称集合，而这些对象称集合的元素。（2）集合中的两个关系集合中的两个关系 集合间的比较关系：AB，AB，AB，AB。集合与元素间的隶属关系：aA，aA。（3）三种特殊的集合三种特殊的集

2、合 空集 全集E 幂集（A）。现在学习的是第3页，共32页（4）集合的四种表示法：集合的四种表示法：枚枚举举法法。即将集合元素一一列举。例：1,2,3,特特性性刻刻划划法法。即用元素的性质刻划集合。例：x|p(x)图图示示法法。即用文氏图表示集合及集合间的关系。例：运运算算法法。即用已知集合的运算构造新的集合。例：SA（BC）AAB现在学习的是第4页，共32页（5）集合的五种运算：）集合的五种运算：交运算：AB 倂运算：AB 差运算：AB 补运算：A 对称差运算：AB现在学习的是第5页，共32页（6）集合的）集合的21个公式：个公式：交换律：交换律：ABBAABBA结合律：结合律：A（BC）（

3、AB）CA（BC）（AB）C分配律：分配律：A（BC）（AB）（AC）A（BC）（AB）（AC）现在学习的是第6页，共32页同一律：同一律：AAAEA零一律：零一律：AEEA互补律：互补律：AAEAA双补律：双补律：（A）A现在学习的是第7页，共32页E与与 的互补：的互补：EE等幂律：等幂律：AAA AAA吸收律：吸收律：A（AB）A A（AB）A狄狄莫根定律：莫根定律：（AB）AB（AB）AB现在学习的是第8页，共32页 4.5 有限集与无限集 （1）有限集与无限集的基本概念 有限集的两个定义 集合S与Nn 一 一对应 非无限集即为有限集 无限集的两个定义 S与一 一对应函数f：SS使得：

4、f(S)S S存在与其等势的真子集现在学习的是第9页，共32页 （2）有限集 有限集的基数有限集元素个数 有限集的计数计算有限集中元素个数 有限集计数的四种方法：|AB|A|+|B|AB|A|+|B|AB|ABC|A|+|B|+|C|AB|AC|BC|+|ABC|S1S2Sn|Si|SiSj|SiSjSk|（1）|S1S2S n|ni=11ijn1ijkn现在学习的是第10页，共32页 无限集无限集 （3）四个常用的无限集：）四个常用的无限集：自然数集N 整数集I 有理数集Q 实数集R （4）无限集的势无限集的势 （5）无限集分类（按势分类）无限集分类（按势分类）自然数集自然数集 可列集可列集

5、基数为基数为0 整整 数数 集集 无限集无限集 实数集实数集基数为基数为 有理数集有理数集 更大基数的集更大基数的集（A）现在学习的是第11页，共32页 幂集、幂集、n元有序组与笛卡尔乘积元有序组与笛卡尔乘积 （7）幂集 幂集定义：集合A的所有子集所组成的集合，可记为（A）。幂集性质：|A|n 则|(A)|2 n 现在学习的是第12页，共32页 （8）n元有序组与笛卡尔乘积元有序组与笛卡尔乘积 n元有序组是一种特殊的集合结构形式，它有两个基本概念与一种基本运算（笛卡尔乘积）。基本概念之一：有序偶。例：（a,b）基本概念之二：n元有序组。例：（a1,a2,an）基本运算：笛卡尔乘积。例：AB现在

6、学习的是第13页，共32页第五章 关系 关系研究集合内元素间的关联及集合间元素关联，主要有：一个基本概念 两种表示方法 三种运算 九个公式 五种性质 六种常用关系现在学习的是第14页，共32页 5.1 5.1 关系基本概念关系基本概念 （1）一个主要的概念二元关系的基本概念：关系定义：关系定义：从集合A到B的关系R是A B的一个子集。（2）两种表示方法：集合表示法：集合表示法：有序偶的集合 图表示法：图表示法：有向图现在学习的是第15页，共32页5.2 5.2 关系运算关系运算（3）两种运算：关系的复合运算复合运算 关系的逆运算逆运算（4）有关运算的五个公式：复合运算的公式：复合运算的公式：(

7、R S)TR (S T)Rm RnRm+n(Rm)nRmn 逆运算的公式：逆运算的公式：RR(R S)R S 现在学习的是第16页，共32页5.3 5.3 关系重要性质关系重要性质（5）关系的五种性质 关系的自反性 关系的反自反性 关系的对称性 关系的反对称性 关系的传递性现在学习的是第17页，共32页（6）六种常用关系 次序关系之一：偏序关系 次序关系之二：拟序关系 次序关系之三：线性次序关系 次序关系之四：字典次序关系 相容关系 等价关系现在学习的是第18页，共32页5.4 5.4 闭包运算闭包运算（1）关系的闭包运算闭包运算 自反闭包 r(R)对称闭包 s(R）传递闭包 t(R）（2）闭

8、包的公式：闭包的公式：r（R）R s（R）RR t（R）Ri i=1现在学习的是第19页，共32页 5.5 5.5 次序关系次序关系 （7）次序关系 四个定义：偏序关系：X上自反、反对称与传递的关系称偏序关系并用 表示。拟序关系：反自反、传递的关系称拟序关系并用 表示。线性次序关系：X上偏序关系R如有x,yx必有x y或y x则称R是X上线性次序关系。字典次序关系：有限字母表 上的偏序关系。如建立上的次序关系：设x=x1,x2,xn,y=y1,y2,ym；x,y*；x1,x2,xn,y1,y2,ym.现在学习的是第20页，共32页（1）x1y1且如x1y1则我们说xLy；如y1x1，则我们说y

9、Lx；（2）如存在一个最大的K且Kmin(n，m)，使得x1y1，x2y2，xkyk而xk1yk+1，如果xk1yk1，则我们说xLy；如yk1xk1，则我们说yLx；（3）如存在一个最大的Kmin(n，m)，使得x1y1，x2y2，xnyn，此时如nm，则我们说xLy；如mn，则我们说yLx。现在学习的是第21页，共32页 四个次序关系间的关系：R是拟序则r(R)=R R是偏序则RQ是拟序 字典次序关系必为线性次序关系 R是拟序则必反对称 八个概念：最大元素（最小元素）极大元素（极小元素）上界（下界）上确界（下确界）现在学习的是第22页，共32页 5.6 5.6 相容关系相容关系 （8）相容

10、关系 相容关系定义X上自反、对称关系称相容关系并用“”表示。相容关系的极大相容块设有集合X上的相容关系，设A是X的子集，如A中任何元素都互为相容，且XA中的任何元素没有一个与A中的所有元素相容，则称A是X中的极大相容性分块。相容关系完全覆盖X上相容关系，它的极大相容性分块的集合称X的完全覆盖。现在学习的是第23页，共32页 5.7 5.7 等价关系等价关系 （9）等价关系 等价关系定义X上自反、对称、传递的关系称等价关系。等价类R是X上等价关系，对xX可构造一个X的子集xR 称为x 对R的等价类。划分S的子集A1，A2，An满足：Ai均分离(i=1，2，n)A1A2AnS则AA1，A2，An为

11、S的划分，而Ai称为划分的块（i=1,2,n）。商集X上等价关系R所构成的类产生X的划分叫X关于R的商集记以XR。现在学习的是第24页，共32页第六章 函数 函数是一种特殊的关系，它在数学中具有普遍重要价值，函数主要内容有：一个基本概念 两种基本运算 三种性质函数 四种常用函数现在学习的是第25页，共32页 6.1 6.1 函数的基本概念函数的基本概念 （1）一个基本概念函数的基本概念。函数建立了从一个集合到另一个集合的特殊对应关系。设有集合X与Y，如果我们有一种对应关系f，使X的任一元素x能与y中的一个唯一的元素y相对应，则这个对应关系f叫从X到Y的函数或叫从X到Y的映射。x所对应的y内的元

12、素y叫x的像，而x则叫y的像源。上述函数我们可以表示成f：XY；或写成XY；以及yf（x）。（2）三种不同性质函数：满射与内射 一对一与多对一 一一对应（双射）现在学习的是第26页，共32页 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 Yg X Yf X Yh现在学习的是第27页，共32页 从图中可以看出函数f使得Y中的每个元素均有X中的元素与之对应，这种函数叫做从X到Y上的函数，否则叫做从X到Y内的函数。从图中可以看出，函数g使得不但X中的每一个元素xi唯一对应一个Y中的一个元素yj

13、，而且也只有一个xi对应yj，也就是说一个像只有一个像源与之对应，这种函数叫做一对一的函数，否则叫做多对一的函数。从图中可以看出，函数h使得X与Y间建立了一对应的关系，这种函数叫X与了间一对应的函数。现在学习的是第28页，共32页 6.2 6.2 复合函数、反函数、多元函数复合函数、反函数、多元函数 （3）两种运算：复合运算（复合函数）设函数f：XY，g：YZ则复合函数hgf：XZ是一个新的函数。定义：设函数f：XY，g：YZ，它们所组成的复合函数或叫复合映射gf，也是一个函数h：XZ，即：hg f：(x,z)|xX,zZ且至少存在一个yY，有y=f（x），zg（y）现在学习的是第29页，共32页 y1 y2 x1 x2 x3 z1 z2YXZhfg现在学习的是第30页，共32页 逆运算（反函数）定定义义：设f：XY是一对应的函数，则f所构成的逆关系叫f的逆映射或叫f的反函数，记以f1：Y X （4）函数分类：一元函数：f(x)二元函数：f(x,y)多元函数：f(x1,x2,xn)现在学习的是第31页，共32页 6.3 常用函数常用函数（5）四种常用函数 常值函数：f(x)b 恒等函数：f(a)a 单调递增函数与严格单调递增函数：单调递减函数与严格单调递减函数：1 aA 特征函数：f(a)0 aA 现在学习的是第32页，共32页