《教学ppt课件：《离散数学导论(第5版)》》由会员分享，可在线阅读，更多相关《教学ppt课件：《离散数学导论(第5版)》（118页珍藏版）》请在金锄头文库上搜索。
1、1离散数学导论（第5版）2第一篇概论本篇是对离散数学的宏观介绍。1 计算机学科与离散数学 介绍离散数学在计算机学科发展中的作用与关系，明确离散数学是掌握与研究计算机学科的基础理论与工具。2离散数学的特征 离散性 可构造性 抽象性 3离散数学的内容 离散数学的主要内容为：集合论 代数结构 图论 数理逻辑3离散数学导论（第5版）4第二篇集合论本篇由集合论初步、关系、函数、有限集与无限集等与集合论相关等四部分内容组成，它们间是一个内容关联的整体。5第1章集合论初步集合论是数学的基础，也是离散数学的基础。故学好集合论十分重要，在本章学习中要掌握：集合中的一个基本概念 集合中的两种关系 集合中的三种特殊
2、集合 集合中的三种表示方法 集合中的五种运算 集合中的21个常用公式61.1集合论基本概念（1）一一个个主主要要的的概概念念集集合合的的基基本本概概念念：一些不同确定的对象全体称集合，而这些对象称集合的元素。（2）集集合合中中的的两两个个关系关系 集合间的比较 关 系：A B，AB，AB，AB。集合与元素间的隶属关系：aA，aA。（3）三三种种特特殊殊的的集合集合 空集 全集E幂集（A）。7（4）集合的三种表示法：集合的三种表示法：枚枚举举法法。即将集合元素一一列举。例：1,2,3,特特性性刻刻划划法法。即用元素的性质刻划集合。例：x|p(x)图图示示法法。即用文氏图表示集合及集合间的关系。例
3、：AAB81.2集合运算（5）集合的五种运算：）集合的五种运算：交运算：AB倂运算：AB差运算：AB补运算：A对称差运算：AB9（6）集合的）集合的21个公式：个公式：交换律：交换律：ABBAABBA结合律：结合律：A（BC）（AB）CA（BC）（AB）C分配律：分配律：A（BC）（AB）（AC）A（BC）（AB）（AC）10同一律：同一律：AAAEA零一律：零一律：AEEA互补律：互补律：AAEAA双补律：双补律：（A）A11E与与 的互补：的互补：EE等幂律：等幂律：AAAAAA吸收律：吸收律：A（AB）AA（AB）A狄狄莫根定律：莫根定律：（AB）AB（AB）AB121.3幂集 幂集定义
4、：集合A的所有子集所组成的集合，可记为（A）。幂集性质：|A|n则|(A)|2n13第2章关系关系研究集合内元素间的关联及集合间元素关联，主要有：一种预备知识 一个基本概念 两种表示方法 三种运算 九个公式 五种性质 六种常用关系142.1关系的预备知识n元有序组与笛卡尔乘积 n元有序组是一种特殊的集合结构形式，它有两个基本概念与一种基本运算（笛卡尔乘积）。基本概念之一：有序偶。例：（a,b）基本概念之二：n元有序组。例：（a1,a2,an）基本运算：笛卡尔乘积。例：AB152.2 关系基本概念 （1）一个主要的概念二元关系的基本概念：关关系系定定义义：从集合A到B的关系R是A B的一个子集。
5、（2）两种表示方法：集集合合表表示示法法：有序偶的集合 图表示法：图表示法：有向图16 2.3关 系 运 算（3）两种运算：关系的复复合合运运算算 关系的逆运算逆运算（4）有关运算的五个公式：复合运算的公式：复合运算的公式：(RS)TR(ST)RmRnRm+n(Rm)nRmn 逆运算的公式：逆运算的公式：RR(RS)RS 172.4 关系重要性质（5）关系的五种性质 关系的自反性 关系的反自反性 关系的对称性 关系的反对称性 关系的传递性18（6）六种常用关系 次序关系之一：偏序关系 次序关系之二：拟序关系 次序关系之三：线性次序关系 次序关系之四：字典次序关系 相容关系 等价关系192.5
6、闭包运算（1）关系的闭包运闭包运算算 自反闭包 r(R)对称闭包 s(R）传递闭包 t(R）（2）闭包的公式：闭包的公式：r（R）RQs（R）RQt（R）Rii=1202.6 次序关系 （7）次序关系 四个定义：偏序关系：X上自反、反对称与传递的关系称偏序关系并用 表示。拟序关系：反自反、传递的关系称拟序关系并用表示。线性次序关系：X上偏序关系R如有x,yx必有xy或yx则称R是X上线性次序关系。字典次序关系：有限字母表 上的偏序关系。如建立上的次序关系：设x=x1,x2,xn,y=y1,y2,ym；x,y*；x1,x2,xn,y1,y2,ym.21（1）x1y1且如x1y1则我们说xLy；如
7、y1x1，则我们说yLx；（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。22四个次序关系间的关系：R是拟序则r(R)=RR是偏序则RQ是拟序 字典次序关系必为线性次序关系 R是拟序则必反对称 八个概念：最大元素（最小元素）极大元素（极小元素）上界（下界）上确界（下确界）232.7 相容关系（8）相容关系 相容关系定义X上自反、对称关系称相容关系并用“”表
8、示。相容关系的极大相容块设有集合X上的相容关系，设A是X的子集，如A中任何元素都互为相容，且XA中的任何元素没有一个与A中的所有元素相容，则称A是X中的极大相容性分块。相容关系完全覆盖X上相容关系，它的极大相容性分块的集合称X的完全覆盖。242.8 等价关系 （9）等价关系 等价关系定义X上自反、对称、传递的关系称等价关系。等价类R是X上等价关系，对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的商集
9、记以XR。25第3章函数函数是一种特殊的关系，它在数学中具有普遍重要价值，函数主要内容有：一个基本概念 两种基本运算 三种性质函数 四种常用函数26 3.1 函数的基本概念（1）一个基本概念函数的基本概念。函数建立了从一个集合到另一个集合的特殊对应关系。设有集合X与Y，如果我们有一种对应关系f，使X的任一元素x能与y中的一个唯一的元素y相对应，则这个对应关系f叫从X到Y的函数或叫从X到Y的映射。x所对应的y内的元素y叫x的像，而x则叫y的像源。上述函数我们可以表示成f：XY；或写成XY；以及yf（x）。（2）三种不同性质函数：满射与内射 一对一与多对一 一一对应（双射）27 y1 y2 y3
10、y4 x1 x2 x3 x4 y1 y2 y3 y4 x1 x2 x3 x4 x5 y1 y2 y3 y4 x1 x2 x3 x4 XYgXYfXYh28从图中可以看出函数f使得Y中的每个元素均有X中的元素与之对应，这种函数叫做从X到Y上的函数，否则叫做从X到Y内的函数。从图中可以看出，函数g使得不但X中的每一个元素xi唯一对应一个Y中的一个元素yj，而且也只有一个xi对应yj，也就是说一个像只有一个像源与之对应，这种函数叫做一对一的函数，否则叫做多对一的函数。从图中可以看出，函数h使得X与Y间建立了一对应的关系，这种函数叫X与了间一对应的函数。293.2 复合函数、反函数、多元函数 （3）两
11、种运算：复合运算（复合函数）设函数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）30 y1 y2 x1 x2 x3 z1 z2YXZhfg31 逆运算（反函数）定定义义：设f：XY是一对应的函数，则f所构成的逆关系叫f的逆映射或叫f的反函数，记以f1：Y X（4）函数分类：一元函数：f(x)二元函数：f(x,y)多元函数：f(x1,x2,xn)323.3常用函数（5）四种常用函数 常值函数：f(x)b恒等函数：f
12、(a)a单调递增函数与严格单调递增函数：ab，必有f(a)f(b)：ab，必有f(a)f(b)单调递减函数与严格单调递减函数：ab，必有f(a)f(b)：ab，必有f(a)f(b)1aA特征函数：f(a)0aA33第4章有限集与无限集 4.1 有限集与无限集基本概念有限集与无限集基本概念 （1）有限集与无限集的基本概念 有限集的两个定义 集合S与Nn一 一对应 非无限集即为有限集 无限集的两个定义 S与一 一对应函数f：SS使得：f(S)SS存在与其等势的真子集344.2有限集 （2）有限集 有限集的基数有限集元素个数 有限集的计数计算有限集中元素个数 有限集计数的四种方法：|AB|A|+|B
13、|AB|A|+|B|AB|ABC|A|+|B|+|C|AB|AC|BC|+|ABC|S1S2Sn|Si|SiSj|SiSjSk|（1）|S1S2Sn|ni=11ijn1ijknn1354.3无限集 （3）四个常用的无限集：）四个常用的无限集：自然数集N 整数集I 有理数集Q 实数集R （4）无限集的势无限集的势 （5）无限集分类（按势分类）无限集分类（按势分类）自然数集自然数集 可可列列集集基基数数为为0 整整 数数 集集 无无限限集集 实实数数集集基基数数为为 有有理数集理数集 更大基数的集更大基数的集（A）36离散数学导论（第5版）37第三篇代数系统代数系统是建立在集合论基础上以代代数数运
14、运算算为为研研究究对对象象的学科。本篇共三章，第5章代数系统基础介绍代数系统的一般原理与性质，第6章群论，主要介绍具有代表性的代数系统群，最后第7章其它代数系统，介绍除群外常见的一些代数系统，如环、域、格与布尔代数等，这三章相互配合构成了代数系统的完整的整体。38第5章代数系统基础 5.1 代数系统一般概念代数系统一般概念 1代数系统中的基本概念 （1）代数系统：集合上具有封闭性的运算组成代数系统（S,）。（2）子代数：代数系统（S,），（S，）满足：SS 如 a,bS，ab=ab则称（S，）为（S,）的子代数。395.2代数系统常见的一些性质（3）代数系统常见性质 1）结合律：（ab）ca（
15、bc）2）交换律：abba3）分配律：a（bc）（ab）（ac）4）单位元：aea5）逆元：aa1e6）零元：a7）吸收律：a（ab）a；a（ab）a8）上界与下界：a1a；a00；a11；a0a；9）补元素：ab1；ab0405.3同构与同态（4）同构：（X，）与（Y，）存在一一对应函数g:XY使得如x1,x2X，则有：g（x1x2）g（x1）g（x2）此时则称（X,）与（Y，）同构。（5）同态：（X,）与（Y，）存在函数g:XY使得如x1,x2X，则有：g（x1x2）g（x1）g（x2）此时则称（X，）与（Y，）同态。5.4 常用代数系统常用代数系统 （6）代数系统的构成41（一个二元运算
16、）上界、下界两亇补元素代数系统代数系统结合律半群半群单位元、逆元群群循环群循环群可换群可换群子群子群循环半群循环半群单元半群单元半群可换半群可换半群单元环单元环域域有补格有补格有界格有界格布尔代数布尔代数（两个二元运算：,)两个运算的结合律、交换律、吸收律格格两个运算的分配律分配格分配格单位元，（两个二元运算：,)可换群,半群,对分配群环环 交换律 可换环可换环,逆元交换律单位元生成元交换律生成元子集上的群42第6章群论 6.1 一些群的定义一些群的定义 （7）半群代数系统满足交换律 （8）单元半群半群存在单位元 （9）群半群存在单位元与逆元 （10）可换群群满足交换律 （11）变换群集合A上所有的变换构成的集合E（A），对于复合变换所构成的代数系统（E（A）,）是一个群，称变换群。（12）循环群群有生成元。（13）有限群：群（S,）中S为有限集。（14）子群：群（G，）上G的子集所构成的群。43（15）正规子群：（H，）是群（G，）的子群，如对aG都有：aH=Ha则称（H，）是（G，）的正规子群。（16）陪集：H是G的子群，Haha|hH,aH=ah|hH分别称H在G中的一个右陪集或
