离散数学CH51特殊关系课件.pptx

1、1 第 5章 特殊关系离散数学第5章 特殊关系 Discrete Mathematics2 第 5章 特殊关系章节引入判定下列关系具有哪些性质？1.在全体中国人所组成的集合上定义的“同姓”关系；2.对任何非空集合A，A上的全关系；3.三角形的4.直线的“平行关系”；。发现：不同的关系却具有多个相同的性质。本章将研究具有不同性质组合的几种特殊关系相容关系、等价关系、拟序关系、偏序关系。3 第 5章 特殊关系学习要求历史人物相容关系等价关系 1内容导航C O N T E N T S次序关系函数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.64 第 5章 特殊关系1646-1716

2、，德国哲学家、数学家，微积分的发现者之一。历史人物1643-17271643-1727，英国数学英国数学家、科学家和哲学家家、科学家和哲学家。经典力学理论经典力学理论开创者。开创者。5 第 5章 特殊关系学习要求历史人物相容关系等价关系 1内容导航C O N T E N T S次序关系函数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.66 第 5章 特殊关系重点1 特殊关系的判定与证明2 等价类和商集的计算3 8个特殊元的判定个特殊元的判定4 复合函数的计算难点1 相容关系与覆盖的联系相容关系与覆盖的联系2等价关系与集合划分的联系等价关系与集合划分的联系3特殊关系的判定与证明

3、特殊关系的判定与证明4 8个特殊元的判定个特殊元的判定5 函数类型的证明函数类型的证明 学习要求7 第 5章 特殊关系学习要求相容关系等价关系内容导航C O N T E N T S次序关系函数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.6历史人物8 第 5章 特殊关系5.1.1 相容关系的定义定义5.1 设R是定义在非空集合A上的关系，如果R是自反的、对称的，则称R是A上的相容关系。例5.1 设A是所有中国人组成的集合，试判断下列关系是否为相容关系。(1)A上的“同性”关系。(2)A上的“朋友”关系。(3)A上的“父子”关系。解题小贴士相容关系的判断方法 R是相容关系 R同

4、时具有自反性和对称性。是是否不具有对称性，自反性不具有对称性，自反性9 第 5章 特殊关系例5.4 例5.4 假设A是由下列英文单词组成的集合。Astudent,boy,work,table,to,girl，A上的关系R|x，yA且x和y有相同字母。（1）写出关系R中的所有元素。（2）写出R的关系矩阵。（3）画出R的关系图。（4）试说明R是相容关系。10 第 5章 特殊关系例5.4 解解 (1)令1=student,2=boy,3=work,4=table,5=to，6=girl，由R的定义可得R,。11 第 5章 特殊关系（4）由R的关系图或者关系矩阵可看出，R具有自反性和对称性，即R是相容

5、关系。1 0 0 1 1 00 1 1 1 1 00 1 1 0 1 11 1 0 1 1 11 1 1 1 1 00 0 1 1 0 1(a)123456(b)（2）R的关系矩阵如图5.1（a）。（3）R的关系图如图5.1（b）。图5.1例5.4 解（续）12 第 5章 特殊关系定义5.4 给定非空集合A，设有集合SA1,A2,Am。如果(1)Ai A且Ai，i=1，2，m；(2)。则S被称作集合A的一个覆盖。1miiAA例如：设A=1,2,3,4,5,6，则 1,2,4,5，2,3,5，6和1,2,4,5，3,5,6都是的A一个覆盖。5.1.2 集合的覆盖显然一个集合的覆盖是不惟一的。13

6、 第 5章 特殊关系定理5.1 定理5.1 给定集合A的一个覆盖SA1,A2,An，设：RA1A1A2A2AnAn （5.1）则R是A上的相容关系。1niiAA14 第 5章 特殊关系例5.3 例5.3 给定非空集合A=a,b,c和A上的两个不同覆盖S1a,b,c和S2=a,b，b,c，a,c，试给出S1和S2确定的相容关系。解 设覆盖S1和S2确定的相容关系分别为R1和R2，则R1a,b,c a,b,c,；R2（a,ba,b）（b,cb,c）（a,ca,c）,。不同的覆盖可以构造出相同的相容关系。15 第 5章 特殊关系学习要求相容关系等价关系内容导航C O N T E N T S次序关系函

7、数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.6历史人物16 第 5章 特殊关系问题引入具有具有。假设集合A是由10个红色、蓝色或绿色球组成的集合，如图5.4所示。定义A上的关系R为：如果x和y属于关系R，则x和y有相同的颜色。关系R具有哪些性质？17 第 5章 特殊关系5.4.1 等价关系的定义定义5.3 设R是定义在非空集合A上的关系，如果R是自反的、对称的、传递的，则、称R为A上的等价关系。等价关系的判断方法R是等价关系 R同时具有自反性、对称性和传递性。注意：R是等价关系，则R一定是相容关系；反之不然。18 第 5章 特殊关系例5.4 试判定例5.1中的关系是否为等

8、价关系。(1)A上的“同性”关系。(2)A上的“朋友”关系。(3)A上的“父子”关系。例5.4不具有传递性 是否否不具有对称性，自反性19 第 5章 特殊关系例5.5 针对图5.4中集合A上定义的关系R。（1）写出R中的所有元素。（2）画出R的关系图。（3）证明R是一个等价关系。例5.5解（1）根据R的定义得：R,，,，,，,，,，,，,。20 第 5章 特殊关系（2）R的关系图如图5.3所示。例5.5 解（续）21 第 5章 特殊关系例5.5 解 (续)显然，关系R将集合A分成了三个互不相交的子集，且它们的并集为A。22 第 5章 特殊关系例5.6例5.6 设n为正整数，考虑整数集合Z上的整

9、除关系如下：R=|x,yZ(n|(x-y)证明 R是一个等价关系。23 第 5章 特殊关系例5.6 证明24 第 5章 特殊关系以n为模的同余关系整数集Z上的整除关系R又被称为Z上以n为模的同余关系(Congruence Relation)，记xRy为x y(mod n)(5.4)通常称(5.4）为同余式（Congruence）。如用resn(x)表示x除以n的余数，则x y(mod n)resn(x)resn(y)。25 第 5章 特殊关系以n为模的同余关系Z上的整除关系R将Z分成了下面n个互不相交的子集，且这些子集的并集为Z。S0=,2n,n,0,n,2n,；S1=,2n1,n1,1,n1

10、,2n1,；Sn-1=,2n1,n1,1,n1,2n1,。26 第 5章 特殊关系5.4.2 集合的划分定义5.3 给定非空集合A，设有集合S=A1,A2,Am。如果满足(1)Ai A且Ai，i1,2,m；(2)AiAj，ij，i,j1,2,m；(3)。m mi ii=1i=1A=AA=A则称S为集合A的一个(Partition)，而A1,A2,Am叫做这个划分的(Block)或(Class)。注意：集合的一个划分一定是该集合的一个覆盖，反之不然。27 第 5章 特殊关系例5.7试给出非空集合A上2个不同的划分解（1）在A中设定一个非空真子集A1，令A2=A-A1，则根据集合划分的定义，A1,

11、A2就构成了集合A的一个划分，见图(a)；（2）在A中设定两个不相交非空真子集A1和A2，令A3=A-(A1A2)，则根据集合划分的定义，A1,A2,A3就构成了集合A的一个划分，见图(b)。(a)AA1(b)(b)A AA A1 1A A2 2注意：对同一个集合，划分的方法不同，得到的划分也不同。28 第 5章 特殊关系问题引入u1,4,8,10,2,7,9,3,5,6是集合A1,2,10的一个划分；u S0,S1,Sn-1是整数集Z的一个划分。像这种由等价关系产生的划分又被称为集合A上关于R的商集，划分中的每一块被称为等价类。29 第 5章 特殊关系5.4.3 等价类与商集解题小贴士等价类

12、xR的计算方法对A中的任意x，找出以x为第一元素的所有序偶，将其第二元素构成集合，这个集合就是xR。30 第 5章 特殊关系例5.8例5.8 设A1,2,3,4,5,6,7,8,9，R是A上以4为模的同余关系。（1）写出R中的所有元素。（2）计算R的所有等价类。（3）画出R的关系图。解：解：（1 1）根据）根据R R的定义得：的定义得：R R,。31 第 5章 特殊关系例5.8 解（续）解：（2）由例5.6知，A上的关系R是一个等价关系。于是有1R5R9R1,5,9；2R6R2,6；3R7R3,7；4R8R4,8。（3 3）R R对应的关系图如图对应的关系图如图5.55.5所示所示。32 第

13、5章 特殊关系 R Rx Ax Ax x定理5.433 第 5章 特殊关系定理5.4 证明34 第 5章 特殊关系 b)y xR R 假设xRyR，则 xRyR zxRyR RR RR （R是对称的）R （R是传递的）显然与 R矛盾。从而xRyR成立。定理5.4 证明（续）35 第 5章 特殊关系 R Rx Ax Ax x R Rx Ax Ax x R Rx Ax Ax x R Rx Ax Ax x定理5.4 证明（续）R Rx Ax Ax x36 第 5章 特殊关系商 集定义5.5 设R是非空集合A上的等价关系，由R确定的一切等价类构成的集合，称为集合A上关于R的商集(Quotient Se

14、t)，记为A/R，即 A/RxR|(xA)（5.4）例如，例5.8中A关于R的商集A/R=1R,2R,3R,4R1,5,9,2,6,3,7,4,8。37 第 5章 特殊关系例5.9例5.9 设A=1,2,3，在P(A)上规定二元关系如下：R=|s,tP(A)|s|=|t|试证明R是A上的等价关系，并计算商集P(A)/R。38 第 5章 特殊关系例5.939 第 5章 特殊关系计算商集A/R的通用过程解题小贴士A是有限集或可数集，商集P(A)/R的计算步骤如下：（1）任选A中一个元素a，计算aR；（2）如果aRA，任选一个元素bAaR，计算bR；（3）如果aRbRA，任选一个元素cAaRbR，计

15、算cR。以此类推，直到A中所有元素都包含在计算出的等价类中。40 第 5章 特殊关系5.4.4 等价关系与划分41 第 5章 特殊关系5.4.4 等价关系与划分给定集合给定集合A A的的一个划分一个划分=A=A1 1,A,A2 2,A,An n，则由该划分确定的则由该划分确定的关系关系R=(AR=(A1 1A A1 1)(A)(A2 2A A2 2)(A An nA An n)是是A A上的等价关系上的等价关系,称此关系称此关系R R为由划分为由划分所导出的等价关系。所导出的等价关系。42 第 5章 特殊关系5.4.4 等价关系与划分 R Rx Ax Ax x43 第 5章 特殊关系5.4.4

16、 等价关系与划分注意：集合A上的等价关系与集合A的划分是一一对应的。44 第 5章 特殊关系例5.10例5.10 设A1,2,3,4,5,6，求出与下列划分对应的等价关系。（1）S11,2,3,5,4；（2）S21,3,2,4,5。解 （1）设与划分S1对应的等价关系为R1，则R1(1,21,2)(3,53,5)(44),。45 第 5章 特殊关系例5.10 解(续)（2）设与划分S2对应的等价关系为R2，则 R2(1,31,3)(2,3,52,3,5),。46 第 5章 特殊关系例5.11例5.11 设A=a,b,c，求A上所有的等价关系及其对应的商集。解 只有1个划分块的划分为S1，见图(

17、a)；具有2个划分块的划分为S2、S3和S4，见图(b)、(c)和(d)，具有3个划分块的划分为S5，见图(e)。bcabcabcabcabca (a)(b)(c)(d)(e)(a)(b)(c)(d)(e)47 第 5章 特殊关系例5.11(续）假设由Si导出的对应等价关系为Ri，i=1,2,3,4,5，则有 R1=S1S1=AA，A/R1=1,2,3；R2=1,21,233=,A/R2=1,2,3；R3=1,31,322=,A/R3=1,3,2；48 第 5章 特殊关系R4=2,32,311=,，A/R4=1,2,3；R5=112233=,=IA，A/R5=1,2,3。例5.11(续）49

18、第 5章 特殊关系学习要求相容关系等价关系内容导航C O N T E N T S次序关系函数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.6历史人物50 第 5章 特殊关系问题引入制作一道四川名菜四川麻婆豆腐，需执行下面的任务：（1）把豆腐切块；（2）牛肉剁成牛肉馅；（3）把蒜苗切成段，蒜和姜切成小粒；（4）锅里倒清水烧热，下豆腐块，加盐煮一下捞出；（5）油温烧至7成热，下蒜、老姜、豆瓣酱翻炒，然后加 牛肉馅炒香；（6）加豆腐块、辣椒粉、水煮开，加蒜苗炒香，装盘上桌。图5.7这些任务之间存在“先后”关系，这种“先后”关系被称为次序关系。拟序关系偏序关系次序关系51 第 5章

19、特殊关系5.3.1 拟序关系定义5.6 设R是非空集合A上的关系，如果R是反自反、反对称和传递的，则称R是A上的拟序关系(Quasi-Order Relation)，简称拟序，记为“”，读作“小于”，并将“”记为“ab”。序偶称为拟序集(Quasi-Order Set)。解题小贴士拟序关系的判断方法R是拟序关系 R同时具有反自反性、反对称性和传递性。注意：“”的逆关系“-1”也是拟序，用“”表示，读作“大于”。52 第 5章 特殊关系例5.12例5.12 判断下列关系是否为拟序关系（1）集合A的幂集P(A)上定义的“”；（2）实数集Z上定义的“大于”关系()；不具有反自反性 否是53 第 5章

20、 特殊关系例5.13例5.13 如果关系R在非空集合A上是反自反和传递的，那么R一定是反对称的吗？用反证法。假设R不是反对称的关系，则存在x0,y0A，且x0y0，满足 R并且R。因为R具有传递性，从而有R。这与R的反自反性矛盾，从而假设错误，即R一定是反对称的。定义5.7 设R是非空集合A上的关系，如果R是反自反和传递的，则称R是A上的 拟序关系。54 第 5章 特殊关系问题引入假设集合A是制作四川麻婆豆腐的任务集，即A1,2,3,4,5,6，A上的关系R定义为：R 如果ij或者任务i必须在任务j之前完成。则关系R具有什么性质？是拟序关系吗？不具有反自反性 否具有自反性、反对称性和传递性的。

21、偏序关系55 第 5章 特殊关系5.3.2 偏序关系 设R是非空集合A上的关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系(Partial Order Relation)，简称偏序，记为“”，读作“小于等于”，并将“”记为ab。序偶称为偏序集(PartialOrder Set)。解题小贴士偏序关系的判断方法R是偏序关系 R同时具有自反性、反对称性和传递性。注意：（1 1）“”的逆关系是“”，“”记为“abab”，读作“a a大于等于b”b”。（2 2）“”“I IA A”为A A上的拟序关系，“”“I”“IA A”为A A上的偏序关系。56 第 5章 特殊关系例5.13 试判断下

22、列关系是否为偏序关系（1）设A=1,2,3，A上的关系R=,。（2）设A=1,2,3，A上的关系S=,。（3）整数集Z上的模m同余关系T。例5.13不具有自反性 否是否不具有反对称性 57 第 5章 特殊关系例5.14 证明整数集Z上的整除关系“|”是偏序关系。例5.1458 第 5章 特殊关系例5.15例5.15 试写出制作四川麻婆豆腐的任务集A1,2,3,4,5,6上的关系R中的元素，并画出它的关系图。解 根据R的定义，有R,其关系图如图5.8所示。59 第 5章 特殊关系哈斯图如果已知R是偏序关系，那么它的关系图一定具有如下特点：（1）每个结点都有自环（自反性）；（2）任意两个结点要么有

23、且仅有一条边相连，要么没有边相连（反对称性）；（3）如果元素a到元素b有边相连，元素b到元素c有边相连，则元素a到元素c必然有边相连（传递性）。R是偏序关系 R同时具有自反性、反对称性和传递性。60 第 5章 特殊关系哈斯图1.用小圆圈或点表示A中的元素，省掉关系图中所有的环；（因自反性)2.对任意x,yA，若xy，则将x画在y的下方，可省掉关系图中所有边的箭头；（因反对称性）3.对任意x,yA，若xy，且不存在zA，使得xz,zy，则x与y之间用一条线相连，否则无线相连。（因传递性）按照（1），（2）和（3）作成的图被称为R的哈斯图（Hasse图）。如果A上的关系R是偏序关系，那么可以按照下

24、面的方式简化它的关系图。61 第 5章 特殊关系例5.16例5.16 画出例5.15中关系R的哈斯图。解 例5.15中关系R的哈斯图如图5.9所示。62 第 5章 特殊关系例5.17例5.17 设A1,2,3,4,6,12，“”是A上的整除关系R，先写出R中元素，并判定能否画出R的哈斯图。如果能，请画出其哈斯图。解 由题意可得 R,。其哈斯图如图5.10所示。最大元最小元63 第 5章 特殊关系特殊元素 64 第 5章 特殊关系例5.18例5.18 设B12,4,6,12，B21,2,3是例5.17中集合A的子集，试求出B1，B2的最大元和最小元。解 子集B1，B2形成的哈斯图分别如图5.11

25、（a）和5.11（b）。从图5.11（a）可以看出，B1的最大元是12，最小元是2。从图5.11（b）可以看出，图的最上端存在 两个元素2和3，它们之间不能比较，因此 B2无最大元，最小元是1。极大元65 第 5章 特殊关系特殊元素 66 第 5章 特殊关系例5.19 例5.19 设B31,2,3,4,6，B44,6,12是例5.17中集合A的子集，试求出B3，B4的最大元、最小元、极大元和极小元。解 子集B3，B4形成的哈斯图分别如图5.12（a）和5.12（b）。B3，B4的最大元、最小元、极大元和极小元如下表所示。集合最大元极大元最小元极小元B3无4,611B41212无4,667 第

26、5章 特殊关系定义5.1168 第 5章 特殊关系由定义5.3.5知解题小贴士69 第 5章 特殊关系例5.40例5.40 试求出例5.18和5.19中A的子集B1，B2，B3和B4的上界、下界、上确界和下确界。解 集合B1，B2，B3和B4的上界、下界、上确界和下确界如表5.4所示。集合集合上界上界上确界上确界下界下界下确界下确界B B1 1B B2 2B B3 3B B4 412121,226,1261112121112121,2270 第 5章 特殊关系例5.41例5.41 A=x1,x2,x3,x4，A上定义偏序集的哈斯图如右图所示。求B=x1,x2和C=x3,x4最大元、最小元、极大

27、元、极小元、上界、下界、上确界和下确界。解 见下表。最大元极大元最小元极小元BC无x3,x4无无x1,x2无无无x x1 1x x3 3x x2 2x x4 4无无无无x1,x2x1,x2x3,x4x3,x471 第 5章 特殊关系定理5.5定理5.5 设是一偏序集，B是A的子集。则：（1）b是B的最大元 b是B的极大元、上界、上确界；（2）b是B的最小元 b是B的极小元、下界、下确界；（3）a是B的上确界，且aB a是B的最大元；（4）a是B的下确界，且aB a是B的最小元。72 第 5章 特殊关系定理5.6定理5.6 设是一偏序集，B是A的子集。则：（1）若B存在最大元，则B的最大元是惟一

28、的；（2）若B存在最小元，则B的最小元是惟一的；（3）b是B的最大元 b是B的惟一极大元；（4）b是B的最小元 b是B的惟一极小元；（5）若B存在上确界，则B的上确界是惟一的；（6）若B存在下确界，则B的下确界是惟一的。73 第 5章 特殊关系问题引入在偏序关系中，为什么A的非空子集B通常存在多个极大元或极小元呢？因为这些极大元或者极小元之间不存在偏序关系！如果在给定偏序关系中增加“A中任意两个元素均存在偏序关系”，那么这样的偏序关系被称为全序关系。74 第 5章 特殊关系5.3.3 全序关系75 第 5章 特殊关系例5.42例5.42 试判断下列关系是否为全序关系，如果是，请画出其哈斯图。（

29、1）设集合A=a,b,c，其上的关系“”=,（2）实数集R上的大于等于关系“”；（3）集合A的幂集P(A)上定义的包含关系“”。76 第 5章 特殊关系例5.42 解（1）是全序集，其哈斯图见图(a)；（2）是全序集，其哈斯图是数轴，见图(b)，其中x,y,zR；不是全序关系；（3）当|A|2时，P(A)上定义的“”是全序关系，是全序集，其哈斯图见图(c)；当|A|2，则不是全序集。aa(c)(c)a ab bc c(a)(a)x xy ya a(b)(b)A的任何非空子集都有最小元，像这样的全序关系被称为良序关系77 第 5章 特殊关系5.3.4 良序关系 设是一偏序集，若A的任何一个非空子

30、集都有最小元素，则称“”为良序关系（Well Order Rrelation），简称良序，此时称为良序集（Well Order Set）。解题小贴士非空集合A上的关系R是良序关系的判断方法（1）确定关系R是偏序关系；（2）A的任何一个非空子集都有最小元。78 第 5章 特殊关系例5.43例5.43 试判断例5.42中的(1)和(2)是否为良序关系。（1）设集合A=a,b,c，其上的关系“”=,（2）实数集R上的大于等于关系“”。是否存在非空子集(0,1)开区间没有最小元79 第 5章 特殊关系5.3.6次序关系的应用计算机科学中常用的字典排序如下：设是一有限的字母表。上的字母组成的字母串叫上的

31、字；*是包含空字“”的所有字组成的集合，建立*上的字典次序关系L：设x=x1x2xn，y=y1y2ym，其中xi,yj(i=1,2,n；j=1,2,m)，则x,y*。80 第 5章 特殊关系总结自反性反自反性对称性反对称性传递性相容关系 等价关系 拟序关系 偏序关系 81 第 5章 特殊关系学习要求相容关系等价关系内容导航C O N T E N T S次序关系函数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.6历史人物82 第 5章 特殊关系问题引入 函数也叫函数也叫映射、变换或对应映射、变换或对应。函数本质上是函数本质上是一种关系一种关系。任何一个从任何一个从A A到到B

32、B的关系都可以成为的关系都可以成为A A到到B B的一个函数的一个函数吗？吗？No，No满足什么条件的从A到B的关系才是A到B的函数呢？83 第 5章 特殊关系5.4.1函数的基本概念函数的定义设f是集合A到B的关系，如果对每个xA，都存在惟一的yB，使得f，则称关系f为A到B的函数(Function)(或映射(Mapping)、变换(Transform)，记为f:AB。其中 A为函数f的定义域，记为domf=A；f(A)为函数f的值域，记为ranf=f(A)。当f时，通常记为y=f(x)，这时称x为函数f的自变量，y为x在f下的函数值(或象)，也称x为y在f下的原象。84 第 5章 特殊关系

33、例5.24例5.24 设P是接受一个整数作为输入并产生一个整数作为输出的计算机程序。令A=B=Z，则由P确定的关系fp定义如下：如果fp当且仅当输入m时，由程序P所产生的输出是n。请判断fp是否为函数。解 fp是一个函数。因为计算结果是可重复的，即对相同的输入，程序每次运行都有相同的结果，所以根据程序P的规定，对任意一个特殊的输入，一定对应惟一的输出。事实上，计算机的输入输出关系都可以被看作函数。85 第 5章 特殊关系例5.25例5.25 设集合A1,2，Ba,b，试判断下列关系哪些是函数。如果是函数，请写出它的值域。（1）R1。（2）R2,。（3）R3,。（4）R4,。是否是否不满足（1）

34、不满足（2）ranR3=aranR4=a,b86 第 5章 特殊关系例5.26例5.26 对例5.25中的集合A和B，请分别写出所有A到B的不同关系和不同函数。解 因为AB,，所以从A到B的不同的关系有2|AB|=24=16个。分别如下：R0=；R1=；R2=；R3=；R4=；R5=,；R6=,；R7=,；R8=,；R9=,；R10=,；R11=,；R12=,；R13=,；R14=,；R15=,。从A到B的不同的函数通常，将从A到B的一切函数构成的集合记为BA：BA f|f：AB。87 第 5章 特殊关系函数与关系的差别当A和B都是有限集合时，函数和一般关系具有如下差别：（1）从A到B的不同的

35、关系有2|A|B|个；但从A到B的不同的函数却仅有|B|A|个。(个数差别)（2）关系的第一个元素可以相同；函数的第一元素一定是互不相同的。(集合元素的第一个元素存在差别)（3）每一个函数的基数都为|A|个(|f|=|A|)，但关系的基数却为从零一直到|A|B|。(集合基数的差别)88 第 5章 特殊关系2 函数的类型89 第 5章 特殊关系解题小贴士注意 若f是从有限集A到有限集B的函数，则有：（1）f是单射的必要条件为|A|B|；（2）f是满射的必要条件为|B|A|；（3）f是双射的必要条件为|A|B|。90 第 5章 特殊关系例5.27例5.27 试分别构造单射、满射、双射和变换。解 （

36、1）构造单射函数如下：设A=1,2,3，B=a,b,c,d。f1:AB定义为：,；（2）构造满射函数如下：设A=1,2,3,4，B=a,b,c。f2:AB定义为：,；（3）构造双射函数如下：设A1,2,3，B=a,b,c。f3:AB定义为：,；（4）构造变换如下：设A1,2,3，B1,2,3，f4：AB定义为：,。91 第 5章 特殊关系定理5.7定理5.7 设A，B是有限集合，且|A|=|B|，f是A到B的函数，则f是单射当且仅当f是满射。证明 必要性()：设f是单射。显然，f是A到f(A)的满射，故f是A到f(A)的双射，因此|A|=|f(A)|。由|f(A)|=|B|，且f(A)B，得f

37、(A)=B，故f是A到B的满射。92 第 5章 特殊关系定理5.7（续）充分性()：设f是满射。任取x1,x2A，x1x2，假设f(x1)=f(x2)，由于f是A到B的满射，所以f也是A-x1到B的满射，故|A-x1|B|，即|A|-1|B|，这与|A|=|B|矛盾。因此f(x1)f(x2)，故f是A到B的单射。93 第 5章 特殊关系例5.28 设A1,2,3,n，f是A到A的满射，并且具有性质：f(xi)yi，i1,2,3,k，kn，xi,yiA。求f的个数。例5.28：f f是有限集是有限集A A到到A A的满射，可知的满射，可知f f是是A A到到A A的双射。的双射。由于由于f f已

38、将已将A A中的某中的某k k个元素与另外个元素与另外k k个元素的对应，所以只需考虑剩下个元素的对应，所以只需考虑剩下n-n-k k个元素的对应，为此，令个元素的对应，为此，令B BA-A-x xi i|i|i1,2,3,1,2,3,k;C,k;CA-A-y yi i|i|i1,2,3,1,2,3,k,k则从则从B B到到C C的满射个数的满射个数(即是双射个数即是双射个数)就是就是f f的个数。根据推论的个数。根据推论2.3.12.3.1有，有，从从A A到到A A的满足题目条件的不同满射个数共有的满足题目条件的不同满射个数共有(n-k)!(n-k)!。94 第 5章 特殊关系例5.29例

39、5.29 设X=0,1,2,，Y=1,1/2,1/3,，f:XY的定义如下：(1)f1=,（2）f2=,（3）f3=,。试判断它们的类型。95 第 5章 特殊关系例5.29 解（1）由已知得，根据函数f1(n)的表达式和单射函数的定义知，f1是单射函数；但是，Y中元素1没有原象，所以f1不是满射函数；(2)由已知得，显然f2是满射函数。但是，X中元素0和1有相同的象1，所以f2不是单射函数；1 1f(n)=,n=0,1,2,f(n)=,n=0,1,2,n+2n+21,0,11,0,1f(n)=f(n)=1 1,n=2,3,n=2,3,n n96 第 5章 特殊关系例5.29 解(续）（3）由已

40、知得，显然，f3是双射函数。1 1f(n)=,n=0,1,2,f(n)=,n=0,1,2,n+1n+197 第 5章 特殊关系例5.30 设R是集合A上的一个等价关系，g：AA/R称为A对商集A/R的典型(自然)映射，其中g(a)aR，aA.证明：典型映射是一个满射。例5.30分析：分析：由等价类的定义，对任意由等价类的定义，对任意aaR RA/RA/R，aaaaR R，即，即任意任意A/RA/R中的元中的元 素都有原象，素都有原象，所以典型映射是满射。所以典型映射是满射。证明过程留给读者。证明过程留给读者。98 第 5章 特殊关系例5.31 设是偏序集，对任意aA，令：f(a)x|(xA)(

41、xa)证明：f是从A到P(A)的单射函数，并且f保持与的偏序关系，即：对任意a,bA，若ab，则f(a)f(b)。例5.31 证明：1)f是映射。任取aA，由于f(a)x|(xA)(xa)A，所以f(a)P(A)，即f是从A到P(A)的函数。99 第 5章 特殊关系2)f是单射。对任意a,bA，ab 若a,b存在偏序关系，不妨设ab a b ba b b f f(a)(a)x|(x|(xAxA)xaxa （“”是反对称的）又因为 bb （“”是自反的）bb bf(b)x|(xA)xb 所以f(a)f(b)，从而f是单射。若a,b不存在偏序关系，则有：ab a f(b)x|(xA)xb 又因为

42、aa （“”是自反的）aa af(a)，即f(a)f(b)，从而f是单射。因此对 a，bA，当ab，总有f(a)f(b)。从而f是从A到P(A)的单射。例5.31(续)100 第 5章 特殊关系例5.31(续)101 第 5章 特殊关系3.一些重要的函数i iAiAii i1uA1uAf(u)=f(u)=0uA0uA102 第 5章 特殊关系定义5.16（4）对有理数x，f(x)为大于等于x的最小的整数，则称f(x)为上取整函数(Floor Functions)(强取整函数)(，记为f(x)=；（5）对有理数x，f(x)为小于等于x的最大的整数，则称f(x)为下取整函数(弱取整函数)，记为f(

43、x)=；（6）如果f(x)是集合A到集合B0,1上的函数，则称f(x)为布尔函数（Boolean Function）。x x x x 103 第 5章 特殊关系定义5.17定义5.17 设A和B是两个集合。（1）如果A=R，B=(0,1)，则Sigmoid函数定义为：（2）如果A=R，B=(-1,1)，则tanh函数定义为：（3）如果A=R，B=0,+），则ReLU函数定义为：ReLU(x)=max(0,x)x1(x)1exxxxsinh(x)eetanh(x)cosh(x)ee104 第 5章 特殊关系例5.32例5.32 设A=B=R(实数集)。试指出下列函数的类型。（1）f1=|xR；（

44、2）f2=|xR,aR；（3）f3=|xR；（4）f4=|xR。解（1）f1是恒等函数，（2）f2是常值函数，（3）f3是上取整函数，（4）f4是下取整函数。x x x x 105 第 5章 特殊关系5.4.2 函数的运算1.函数的复合运算定义5.18 设f：AB，g：BC是两个函数，如果f与g的复合关系f g|xAzC y(fg)是从A到C的函数，则称fog为f与g的复合函数（Composition Function)。106 第 5章 特殊关系例5.33例5.33 设A=1,2,3，B=a,b,c。函数f：AA，g：AB分别为：f,，g,求fog和gof。解 （1）fog,（2）gof不能

45、计算，因为g的值域不是f的定义域的子集。107 第 5章 特殊关系例5.33例5.33 设f:RR，g:RR，h:RR，满足f(x)=2x，g(x)x2，h(x)ex。计算：（1）(f g)h，f(g h)；（2）f h，h f。解（1）(fg)h)(x)h(fog)(x)h(g(f(x)h(g(2x)h(2x)2)。(f(gh)(x)(gh)(f(x)h(g(f(x)。（2）foh(x)h(f(x)h(2x)e2x，hof(x)f(h(x)f(ex)2ex。24ex24ex108 第 5章 特殊关系定理5.8 设f和g分别是A到B和从B到C的函数，则：(1)如f,g是满射，则f g也是从A到

46、C满射；(2)如f,g是单射，则f g也是从A到C单射；(3)如f,g是双射，则f g也是从A到C双射。定理5.8 109 第 5章 特殊关系定理5.8 证明110 第 5章 特殊关系定理5.9定理5.9 设f和g分别是A到B和B到C的函数，则（1）如fog是A到C的满射，则g是B到C 的满射；（2）如fog是A到C的单射，则f是A到B的单射；（3）如fog是A到C的双射，则f是A到B的单射，g是B到C的满射。111 第 5章 特殊关系定理5.9 证明112 第 5章 特殊关系2.函数的逆运算问题引入：每个关系都有其逆关系，每个函数是否都有其逆函数呢？No，No例如 设A=1,2,3，R=,，

47、S=,是A上的关系，则有 R-1=,S-1=,不是是113 第 5章 特殊关系2.函数的逆运算定义5.19 设f:AB的函数。如果f-1|xAyBf是从B到A的函数，则称f-1：BA的逆函数(Inverse Function)。解题小贴士f逆函数的计算方法（1）确定f是双射。（2）对集合表示的函数，互换f中每个序偶两个元素的位置即可；对表达式形式的函数如y=f(x)，首先反解f(x)，用y表示x，然后x与y的位置互换即可。114 第 5章 特殊关系例5.34例5.34 试判断下列函数是否具有逆函数，如果有，试求出其逆函数。（1）f1,是A上的函数，其中A1,2,3。（2）f2,是A上的函数，其

48、中A1,2,3。（3）f3(x)x2，xR。（4）f4(x)x+1，xR。无f1不是A上的双射函数f2-1,无f1不是A上的双射函数f4-1(x)=x-1115 第 5章 特殊关系定理5.10 定理5.10 设f是A到B的双射函数，则：f-1 fIB|bB；f f-1IA|aA；IA ff IBf。略。116 第 5章 特殊关系定理5.11 定理5.11 若f是A到B的双射，则f的逆函数f1也是B到A的双射。117 第 5章 特殊关系5.4.3 置换函数当A是有限集合时，这种情况具有特殊重要性。有限集合上的双射函数在数学、计算机科学和物理学中有着非常广泛的应用。5.4.1基本概念定义5.19

49、设A=a1,a2,an是有限集合。从A到A的双射函数称为A上的置换或排列(Permutation)，记为P:AA，n称为置换的阶(Order)。n阶置换P:AA常表示为：123n123n123n123naaaaaaaaP=P=P(a)P(a)P(a)P(a)P(a)P(a)P(a)P(a)118 第 5章 特殊关系例5.35例5.35 设A1,2,3，请写出A上的所有置换P。解 A上的所有置换P如下：11 2 3P1 2 321 2 31 3 2P31 2 32 1 3P41 2 32 3 1P51 2 33 1 2P61 2 33 2 1P119 第 5章 特殊关系学习要求相容关系等价关系内

50、容导航C O N T E N T S次序关系函数 5.1 5.4 5.3 5.4特殊关系的应用 5.5作业 5.6历史人物120 第 5章 特殊关系5.5.1 等价关系的应用例5.36 在下图中，点i和j之间有路当且仅当从结点i通过图中的边能够到达结点j。规定对任意结点i，i和i之间一定有路。定义R如下：Ri和j之间有路。试说明该关系R是否可以给定结点集A=1,2,3,4,5,6,7,8一个划分？如果能，请给出具体的划分。7 75 56 68 83 31 12 24 4121 第 5章 特殊关系解（1）由于规定任意结点i与他自身之间一定有路，因此R，即R具有自反性；（2）若R，则两个结点i和j