元关系和函数[离散数学离散数学(第四版)清华出版社课件

《元关系和函数[离散数学离散数学(第四版)清华出版社课件》由会员分享，可在线阅读，更多相关《元关系和函数[离散数学离散数学(第四版)清华出版社课件（94页珍藏版）》请在金锄头文库上搜索。

1、离散数学离散数学授课教师：向胜军第四章第四章 二元关系二元关系和函数和函数笛卡尔积与二元关系笛卡尔积与二元关系关系的运算关系的运算关系的性质关系的性质1 12 23 34 45 56 67 7关系的闭包关系的闭包等价关系和偏序关系等价关系和偏序关系函数的定义和性质函数的定义和性质函数的复合和反函数函数的复合和反函数 设设n为一正整数，由为一正整数，由n个元素个元素x1,x2,xn按按一定顺序排列成的一个序列一定顺序排列成的一个序列称称为为有序有序n元组元组。(The ordered n-tuple is the ordered collection that has x1 as its fir

2、st element, x2 as its second element, , and xn as its nth element.)DEFINITION 1. 笛卡尔积与二元关系笛卡尔积与二元关系1 1二元关系和函数二元关系和函数2 设设设设A,BA,B为集合，用为集合，用为集合，用为集合，用A A中元素为第一元素，中元素为第一元素，中元素为第一元素，中元素为第一元素，B B中元素为第二元素，构成有序对，所有这样中元素为第二元素，构成有序对，所有这样中元素为第二元素，构成有序对，所有这样中元素为第二元素，构成有序对，所有这样的有序对组成的集合叫做的有序对组成的集合叫做的有序对组成的集合叫做的

3、有序对组成的集合叫做A A和和和和B B的的的的笛卡尔积笛卡尔积笛卡尔积笛卡尔积，记做记做记做记做AB. (AB. (Let A and B be sets. The Let A and B be sets. The Cartesian Cartesian productproduct of A and B, denoted by A of A and B, denoted by A B, is the set B, is the set of all ordered pairs where xof all ordered pairs where xA and A and y yB. Henc

4、e, B. Hence, A A B = B = x xA Ay yB B . . ) )DEFINITION 2. 笛卡尔积与二元关系笛卡尔积与二元关系3 设集合设集合A = 1, 2，B = a, b, c，求求A与与B的笛卡尔积。的笛卡尔积。AB=, , , , , .EXAMPLE 1 若若A中有中有m个元素，个元素，B中有中有n个元素，个元素，则则AB中有中有mn个元素。个元素。笛卡尔积与二元关系笛卡尔积与二元关系4设集合设集合A = 1, 2，求，求P(A)A .P(A)A=,1,2,1,21,2 =, , , , , .EXAMPLE 2 笛卡尔积与二元关系笛卡尔积与二元关系5

5、设设设设A A1 1, A, A2 2, ,A,An n是集合是集合是集合是集合(n(n 2)2)，它们的，它们的，它们的，它们的n n阶阶阶阶笛卡尔积笛卡尔积笛卡尔积笛卡尔积记作记作记作记作A A1 1AA2 2 AAn n，其中，其中，其中，其中， A A1 1AA2 2 AAn n=x= x xi iA Ai i , , i=1,2,i=1,2,n,n. (. (The Cartesian product of the sets The Cartesian product of the sets A A1 1, A, A2 2, , , A, An n, denoted by A, de

6、noted by A1 1AA2 2 AAn n, is the , is the set of ordered n-tuples xset of ordered n-tuples , where x, where xi i belongs to Abelongs to Ai i for i=1,2, for i=1,2,n.,n. ) )DEFINITION 3. 笛卡尔积与二元关系笛卡尔积与二元关系6 设集合设集合设集合设集合A=0, 1, B=1, 2, C=0, 1, 2 A=0, 1, B=1, 2, C=0, 1, 2 ，求，求，求，求A, BA, B和和和和C C的笛卡尔积的笛卡

7、尔积的笛卡尔积的笛卡尔积ABCABC。ABC=, , , ,.EXAMPLE 3 笛卡尔积与二元关系笛卡尔积与二元关系7笛卡尔积运算的性质：笛卡尔积运算的性质：1、若、若A, B中有一个空集，则它们的笛卡尔中有一个空集，则它们的笛卡尔积是空集，即：积是空集，即：B=A=.2、当、当A B且且A, B都不是空集时，有都不是空集时，有AB BA.3、当、当A, B, C都不是空集时，有都不是空集时，有(AB)C A(BC).笛卡尔积与二元关系笛卡尔积与二元关系8笛卡尔积运算的性质：笛卡尔积运算的性质：4、笛卡尔积运算对、笛卡尔积运算对或或运算满足分配律，运算满足分配律，即：即： A(BC)=(AB

8、)(AC);(BC)A=(BA)(CA);A(BC)=(AB)(AC);(BC)A=(BA)(CA).笛卡尔积与二元关系笛卡尔积与二元关系9证明等式：证明等式：(BC)A=(BA)(CA) .证明：对于任意的证明：对于任意的, (BC)A x BC y A (x B x C) y A (x B y A) (x C y A) BA CA (BA)(CA) (BC)A=(BA)(CA) 笛卡尔积与二元关系笛卡尔积与二元关系10注意：注意：二元关系是指满足某规律的有序对的全体。二元关系是指满足某规律的有序对的全体。二二元元关关系系按按照照某某种种规规定定，定定义义了了一一个个有有序序对对的的集集合合

9、R，其其中中x A，y B，称称R为为从从到到B的二元关系的二元关系。DEFINITION 4. 当当A=B时，时，R是是A到到A的二元关系，称为的二元关系，称为A上的二元关系上的二元关系。DEFINITION 5. 对对于于二二元元关关系系R，若若 R，则则记记作作xRy，若若 R，则记作，则记作xRy。例：R=|x /y, x,yN是自然数集上的二元关系。笛卡尔积与二元关系笛卡尔积与二元关系11例如： A=张三，李四，王五，赵六 B=100米，跳高，铅球，足球，跨栏穷举法表示： R=， ，是运动会的报名表。二二元元关关系系的的表表示示：因因为为二二元元关关系系本本身身也也是是集集合合，也也

10、可可用用穷穷举举法法，描描述述法法来来表表示示，还还可可用用表表格格、图图示、矩阵法表示。示、矩阵法表示。DEFINITION 6. 笛卡尔积与二元关系笛卡尔积与二元关系12 用字母数字来代替这些元素 A a，b，c，d B 1，2，3，4，5 表格表示法：表格表示法：用表格表示一目了然笛卡尔积与二元关系笛卡尔积与二元关系13图示法：图示法：关系图，直观笛卡尔积与二元关系笛卡尔积与二元关系14相关矩阵法表示：相关矩阵法表示：把A, B集合内元素排好序1 2 3 4 5笛卡尔积与二元关系笛卡尔积与二元关系15二元关系是笛卡尔二元关系是笛卡尔AB的子集。的子集。若若R=AB，则相关矩阵元素全为，则

11、相关矩阵元素全为1。笛卡尔积与二元关系笛卡尔积与二元关系16注：（注：（1）若）若RAB，称此二元关系为全域关系；，称此二元关系为全域关系； （2）设）设Ax1，x2，xn Rxi，xj A 若若Rxi A 称称R为恒等关系，用为恒等关系，用IA表示，是单位矩阵。表示，是单位矩阵。笛卡尔积与二元关系笛卡尔积与二元关系17关系关系R的的定义域定义域domR，值域值域ranR和和域域fldR分别是：分别是： domR=x | y( R). ranR=y | x( R). fldR=domR ranR.当定义域与值域交换得当定义域与值域交换得 R-1=| yRx ，称为，称为R的的逆关系逆关系。DE

12、FINITION 7. 二元关系和函数二元关系和函数关系的运算关系的运算2 218 二二元元关关系系是是集集合合，集集合合存存在在并并、交交、差差、非非和和对对称称差差的的运运算算，故故二二元元关关系系也也存存在在这这样的运算。样的运算。设设R1和和R2是是A到到B的二元关系，则：的二元关系，则：（1）R1 R2 R1 R2（2）R1R2 R1 R2（3）R1-R2 R1 R2 （5）R1 R2 R1 R2 R1R2关系的运算关系的运算 19例1：A1，2，3，4，I为整数集，解：R与S都是A上的二元关系 R=, , S=关系的运算关系的运算20RS=, ,RS= 关系的运算关系的运算21例2

13、： R是父子关系，则R=R R是祖孙关系。设设F, G为为任任意意的的关关系系，A为为集集合合，F与与G的的复合关系复合关系（合成合成）记作）记作F G，F G = | z(xGzzFy)DEFINITION 8. 关系的运算关系的运算22则：R1=, ,是各专业本学期必修课的二元关系。关系的运算关系的运算23R3 = R1 R2 =, , ,是选双学位学生本学期必修课的二元关系。R2=,， ,是学生选双学位专业的二元关系。关系的运算关系的运算24普通的矩阵乘法：普通的矩阵乘法：二元关系的复合的布尔型矩阵乘法：二元关系的复合的布尔型矩阵乘法：关系的运算关系的运算25 在在行行处处标标上上姓姓名

14、名，列列处处标标上上课课程程，就就知知谁谁该该必必修哪些课了。修哪些课了。关系的运算关系的运算26设设R为为A上上的的二二元元关关系系，n为为自自然然数数，则则R的的n次幂次幂规定如下：规定如下：(1) R0=x A；(2) Rn= Rn-1 R, n 1. DEFINITION 8. 关系的运算关系的运算27例4： R=,是集合0,1,2,3上的二元关系，R的关系图如下：关系的运算关系的运算28R2=, ,关系的运算关系的运算29Rn的关系图的构造：的关系图的构造： 可由可由R的关系图来构造，从的关系图来构造，从R的每个结点的每个结点xi出发，出发，数数n条边。若通过数条边。若通过数n条边能

15、到达结点条边能到达结点xj，则有，则有Rn。关系图中从。关系图中从xi出发到出发到xj的边是存在的。的边是存在的。 这样处理容易出错，用相关矩阵的布尔型乘法来这样处理容易出错，用相关矩阵的布尔型乘法来做，简单，又不容易错，还适宜于计算机处理。做，简单，又不容易错，还适宜于计算机处理。关系的运算关系的运算30关系的运算关系的运算31定理：定理：设设F, G, H是任意的二元关系，则：是任意的二元关系，则：(1) (F-1)-1=F；(2) domF-1=ranF, ranF-1=domF；(3) (F G) H=F (G H)；(4) (F G)-1=G-1 F-1；(5) F (G H) =(

16、F G) (F H)；(6) F (GH) (F G)(F H)；(7) (G H) F=(G F) (H F)；(8) (GH) F (G F)(H F).关系的运算关系的运算32证明：证明：(4)任取任取， (F G)-1 F G z( G F) z( G-1 F-1) z( F-1 G-1 ) G-1 F-1 (F G)-1 = G-1 F-1关系的运算关系的运算33证明：证明：(7)任取任取， (GH) F z( F GH) z( F ( G H) z( F G ) ( F H) GF HF (G F)(H F) (GH) F=(G F)(H F)关系的运算关系的运算34设设R是是A上

17、的二元关系，上的二元关系，R=(rij)n*n(1)自反性自反性：对对 x A， R，则，则R称为自反的二元关系。称为自反的二元关系。显然，显然，rii=1(i=1,2,n) 反自反性反自反性：对对 x A， R，则，则R称为反自反的二元关系。称为反自反的二元关系。即即rii=0(i=1,2,n)注注： 自反和反自反性互斥，但不互补。自反和反自反性互斥，但不互补。 如如：rii中中既既有有0又又有有1，则则R既既不不是是自自反反的的也也不不是反自反的。是反自反的。 二元关系和函数二元关系和函数关系的性质关系的性质3 335(2)对称性对称性： 若若xy, R,必必有有 R，称称R为为对对称称的

18、的二二元关系。即元关系。即R的相关矩阵为对称阵，的相关矩阵为对称阵，rij=rji. 反对称性反对称性： 若若xy， R,则则 R，称称R为为反反对对称称的的二元关系。二元关系。注注：(1)R的相关矩阵是反对称的，即：的相关矩阵是反对称的，即：rij rji =0 (ij)(2)若若rij=1，则，则rji=0；但；但rij=0时，不要求时，不要求rji=1，即即rij=rji=0是允许的。是允许的。(3)对称性与反对称性既不互斥，又不互补。对称性与反对称性既不互斥，又不互补。关系的性质关系的性质36关系的性质关系的性质37注注：若若rij，rjk中有一个不是，中有一个不是， 则则 (rij

19、rjk) =1， rik就可以任意。就可以任意。 即即：若若,中中有有一一个个不不属属于于R，则则讨讨论论是否属于是否属于R，无意义。，无意义。 也就是说，没有传递的条件，也不需传递的结果。也就是说，没有传递的条件，也不需传递的结果。如：如：A=a,b,c,d，R=,(3)传递性传递性： 若若， R，则则 R，称称R为为传传递的二元关系。递的二元关系。 即：即： (rij rjk) rik=1 关系的性质关系的性质38二元关系的性质对应于二元关系的性质对应于关系图关系图，有：，有：(1)自反性：每个顶点都有环；自反性：每个顶点都有环；(2)反反自反性：每个顶点都没有环；自反性：每个顶点都没有环

20、；(3)对对称称性性：任任意意两两个个顶顶点点间间或或没没有有边边，或或有有两两条条方方向向相反的边；相反的边；(4)反对称性：任意两个顶点间至多只有一条有向边；反对称性：任意两个顶点间至多只有一条有向边；(5)传递性：若传递性：若xi到到xj有边，有边，xj到到xk有边，有边， 则则xi到到xk必有边。必有边。关系的性质关系的性质39错误结论错误结论：由对称性与传递性可推出自反性。由对称性与传递性可推出自反性。理由：理由： 若若 R，由对称性，由对称性， 有有 R，由传递性，由传递性， 有有 R。如：如： 若若R的的相相关关矩矩阵阵是是全全0矩矩阵阵，是是对对称称的的，传传递递的，反自反的，

21、但不是自反的。的，反自反的，但不是自反的。错误原因：不是错误原因：不是 x， y， 使使 R。关系的性质关系的性质40例：R1=xy， x,yN 自反的，rii=1； 不是对称的，R1，而R1； 反对称的，传递的。注注：将将改为，则无自反性，且是反自反的。改为，则无自反性，且是反自反的。例2：R2=x|y，x,yN 自反的，不是对称的，反对称的，传递的。例3：R3=S1S2，S1,S2P(S)其中P(S)是S的幂集。 自反的，不是对称的，反对称的，传递的。注注：若若 改为改为 ，则无自反性。，则无自反性。关系的性质关系的性质41例4：R4=x+y=偶数，x,yN 自反的，对称的，传递的。因为，

22、若x+y=偶数，y+z=偶数，则：0x+z=(x+y)+(y+z)-2y=偶数与偶数之差=偶数。例5：R5=x与y互为素数，x,yN 对称的，但不是自反的，也无传递性。（1）素数：素数：素数是一个比1大，其因子只有1和它本身，没有其它数可以整除它的数。素数是无限的。例如：2，3，5，7。 （2）两个数互为素数：两个数互为素数：指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如，4和9，13和27等。关系的性质关系的性质42定定理理1：设设R是是A上上的的二二元元关关系系，则则R IA一一定定是是自自反反的的，而而且且是是包包含含R，具具有有自自反反性性的的最最小小关关系

23、系。（其中（其中IA是是A上的恒等关系）。上的恒等关系）。定义定义1：称：称R IA是是R的的自反闭包自反闭包，记为，记为r(R)。证明：对证明：对 x A， IA R IA，且，且R R IA。 若若R 包包含含R且且具具有有自自反反性性，则则IA R，R R，IA R R。即。即IA R为最小。为最小。推论推论1：当且仅当：当且仅当R是自反闭包，是自反闭包，R具有自反性。具有自反性。证明： (1)R是自反闭包，R=IARIA R； (2)R具有自反性，IA R，RIA=R.二元关系和函数二元关系和函数4 4关系的闭包关系的闭包43定定理理2：设设R是是A上上的的二二元元关关系系，则则R R

24、-1是是对对称称的，包含的，包含R的最小关系。的最小关系。（其中（其中R-1是是R的逆关系）。的逆关系）。定义定义2：称：称R R-1是是R的的对称闭包对称闭包，记为，记为s(R)。 证明：(1)若RR-1，则 R 或R-1， R-1 或R 故RR-1（对称性）。 (2)若R为包含R，且对称的二元关系， 则对RR-1， RR； R-1 R R 又R具有对称性，R， 故RR-1R。关系的闭包关系的闭包44推论推论2：当且仅当：当且仅当R是对称闭包时，是对称闭包时，R具有对称性。具有对称性。证明：(1)R具有对称性， 若R，则R， 又R-1 即R-1，R R R-1RRR-1R；(2)R是对称闭包

25、时，RRR-1R具有对称性。关系的闭包关系的闭包45定理定理3：传递闭包传递闭包t(R)RR2 R3 例6：设A=1,2,3，R=,，求t(R) 。关系的闭包关系的闭包46 定义定义1 等价关系：等价关系： A上的二元关系上的二元关系R，如果，如果R是是 (1) 自反的自反的 (2) 对称的对称的 (3) 传递的传递的 称称R为为等价关系等价关系。若若 R，称，称x与与y等价，记作等价，记作xy。二元关系和函数二元关系和函数5 5等价关系和偏序关系等价关系和偏序关系47定定义义2 等等价价类类：把把中中的的等等价价元元素素归归为为一一类类，称称为为等等价类。价类。注注：等等价价关关系系R把把的

26、的元元素素分分为为若若干干类类，各各类类之之间间没没有有公共元素。确定的公共元素。确定的R是对集合进行的划分。是对集合进行的划分。定义定义3 集合的集合的划分划分：把集合：把集合A分为若干子集分为若干子集A1,A2 , ,满足：满足： (1) 当当 i j 时，时，AiAj (2) x A， i， 使使x Ai (i，)，则集合则集合 = A1，A2，An， 称为的一个划分。称为的一个划分。 等价关系和偏序关系等价关系和偏序关系48定理定理1： A在在等等价价关关系系R下下的的等等价价类类正正是是A的的一一种种划划分分，A的的任任一一种种划划分分，也也必必有有A上上的的一一个个等等价关系价关系

27、R与之对应。与之对应。注注：(1) P(A)（A的幂集）；的幂集）；(2) 当且仅当当且仅当A = ， = P(A)=；(3) A非空时，非空时， P(A).等价关系和偏序关系等价关系和偏序关系49证明： R是等价关系， xA，由R的自反性，R，即x与x属于同一等价类，即i，xAi. 若ij，AiAj，而AiAj 。则zAiAj，zAi，且zAj , 对xAi，xz，zAj 对yAj，yz，即zy(对称性) 由传递性，xy. 由x，y的任意性，故AiAj 与Ai和Aj 为不同的等价类矛盾。 故AiAj = 所以，R完成了等价类的划分。等价关系和偏序关系等价关系和偏序关系50 若A已进行了划分，

28、则构造二元关系R。(1) xA，使R.(2) 分别对每一等价类内所有两个不同元素x，y，R，使R. 显然，R是自反的，对称的，而且也是传递的，因为若R，R，则x，y，z均在同一等价类内， 故R。等价关系和偏序关系等价关系和偏序关系51例1： A52张扑克 R1x与y同花，x，y是扑克 R2x与y同点，x，y是扑克 则： R1把分为四类同花类， R2把分为13类同点类。例2： A0，1，2，3，4，5 R，等价关系和偏序关系等价关系和偏序关系52R是等价关系，但不直观，用关系图表示。是等价关系，但不直观，用关系图表示。三个不连通的图三个不连通的图等价关系和偏序关系等价关系和偏序关系二二元元关关系

29、系R是是自自反反的的，对对称称的的，传传递递的的，且且把把分分成成了三个等价类，了三个等价类，0，1，2，3，4，553定定义义 商商集集的的元元素素个个数数（即即A在在R下下的的等等价价类类个个数数）称为称为R的的秩秩。定定义义 商商集集：等等价价关关系系R将将A分分成成若若干干等等价价类类，每每个个类类选选个个代代表表组组成成新新的的集集合合称称为为A关关于于R的的商商集集，表示为表示为A/R。例：在上例中 A/R0，1，4等价关系和偏序关系等价关系和偏序关系54例3： Rxy（mod），x，yZ是整数集合Z上模3同余的二元关系，证明R是等价关系。证明：(1) xx(mod 3). 自反性

30、(2) 若xy(mod 3)，则yx(mod 3). 对称性(3) 若xy(mod 3)，yz(mod 3)， 则xz(mod 3). 满足传递性。故R是等价关系。商集：ZR0，1，2其中，0，-6，-3，0，3，6， 1，-5，-2，1，4，7， 2，-4，-1，2，5，8，等价关系和偏序关系等价关系和偏序关系55 定义定义 偏序关系偏序关系： 是上的二元关系，如果满足：是上的二元关系，如果满足： (1) 自反的自反的 (2) 反对称的反对称的 (3) 传递的传递的则称是上偏序关系，简称偏序。记作则称是上偏序关系，简称偏序。记作。等价关系和偏序关系等价关系和偏序关系56例：例： ， ， 1

31、1xy xyxy，x x，yy 2 2xy x|yx|y，x x，yy 3 3s s s1 1 s s2 2， s s1 1，s s2 2P(P() )记号：记号： = | xy, x x，yy，其其中中R可为可为 ，|， 。 等价关系和偏序关系等价关系和偏序关系57注注： （1）用矩阵表示偏序关系，不能明显看到）用矩阵表示偏序关系，不能明显看到 二元关系的特征。二元关系的特征。 （2）用简化的关系图表示较适合。）用简化的关系图表示较适合。 简化的关系图简化的关系图： (1)(1)自反性自反性：每个顶点都有自回路，省去。：每个顶点都有自回路，省去。 (2)(2)反对称性反对称性：两个顶点间只可

32、能有一个箭头：两个顶点间只可能有一个箭头 从左从左右，或从下右，或从下上的方向，上的方向， 从小到大安置顶点，可省略箭头。从小到大安置顶点，可省略箭头。 (3)(3)传递性传递性：由于有：由于有xy，yRzR， 则则xRzR， 故只画故只画xy，yz对应的边，对应的边， 省略边省略边xz。等价关系和偏序关系等价关系和偏序关系58 定义定义 ：HasseHasse图图 设设是是A上上的的一一个个偏偏序序关关系系，如如果果xy，则则将将x画画在在y下下面面，且且不不 z，使使xz，zy，则则x，y间间用用直直线线连连接接。并并符符合合简简化化的的关关系系图图的的绘绘制制，称这样得到的关系图为称这样

33、得到的关系图为Hasse图。图。上例中偏序关系的上例中偏序关系的Hasse图如下：图如下：等价关系和偏序关系等价关系和偏序关系59R1R1等价关系和偏序关系等价关系和偏序关系60等价关系和偏序关系等价关系和偏序关系61等价关系和偏序关系等价关系和偏序关系62定义定义 全序全序： 上上偏偏序序关关系系，如如果果 x，y，都都有有xy，或或yx，则称为上的，则称为上的全序关系全序关系。注注： (1) (1) 全全序序的的含含义义：中中每每两两个个元元素素均均能能比比大大小小，即即任何两个元素都相关。任何两个元素都相关。 (2) (2) 偏序则是部分有序。偏序则是部分有序。 (3) (3) 上例中，

34、上例中，1 1是全序，是全序，2 2，3 3都是偏序。都是偏序。 如如：2 2中中，都都排排成成了了序序，但但与与，与与，与与，在整除的意义上来说无法排出大小来。，在整除的意义上来说无法排出大小来。等价关系和偏序关系等价关系和偏序关系63定义定义 偏序集偏序集： 集集合合及及上上的的一一个个偏偏序序关关系系组组成成的的二二元元组组，称为偏序集，记为，称为偏序集，记为或或。注注： 同同一一集集合合上上的的两两个个不不同同的的偏偏序序关关系系，所所构构成成的的是是两个偏序集，两个偏序集， 如：如： 1和和2都都定定义义在在，上上，但但与与显显然然不是一样的偏序集。不是一样的偏序集。等价关系和偏序关

35、系等价关系和偏序关系64 定义定义 全序集全序集： 偏偏序序集集 中中的的偏偏序序关关系系是是上的全序，则此上的全序，则此 称为全序集。称为全序集。 是是全全序序集集。显显然然，全全序序集集是是偏偏序序集集的的特特例例。又又如如：（，）实实数数全全体体，在在下是全序集；下是全序集；当然也是全序集。当然也是全序集。等价关系和偏序关系等价关系和偏序关系65定义定义 极大元极大元与与极小元极小元： 设设是是偏偏序序集集，B A，若若yB，且且在在B中中找找不不到到一一个个元元素素x（xy），使使yx (xy)，则则称称y为为B中的极大元（极小元）。中的极大元（极小元）。例例：是偏序集，是偏序集， B

36、，则则 B中极大元：，中极大元：， 极小元：，极小元：，注注： 极极大大元元，极极小小元元并并不不要要求求唯唯一一，且且同同一一元元素素，可以既是极大元，又是极小元，如，。可以既是极大元，又是极小元，如，。等价关系和偏序关系等价关系和偏序关系66注注： 极大元，极小元必须是子集极大元，极小元必须是子集B B中的元素。中的元素。 定义定义 最大元最大元与与最小元最小元： 设设 是是偏偏序序集集，B B A，若若yByB， xBxB，xy xy (yx)(yx)，则则称称y y为为B B的最大元（最小元）。的最大元（最小元）。例：在上例中，例：在上例中，HasseHasse图如下所示：图如下所示：

37、等价关系和偏序关系等价关系和偏序关系67结论结论： 子集子集B B中是不存在最大元（最小元）的。中是不存在最大元（最小元）的。等价关系和偏序关系等价关系和偏序关系68例：例： A，, 3 s1 s2， s1，s2P(A)，是偏序集。是偏序集。 设设B， 其其HasseHasse图如下所示：图如下所示：等价关系和偏序关系等价关系和偏序关系69结论结论： B存在最小元存在最小元 ，没有最大元。，没有最大元。注注： 最最大大元元（最最小小元元）本本身身应应属属于于子子集集B，且与，且与B中任一元素都有关系。中任一元素都有关系。等价关系和偏序关系等价关系和偏序关系70定义定义 上界上界与与下界下界：

38、设设是偏序集，是偏序集，B A， 若若yA，对对 x xB，xy (yx)称称y为为B的的上上界（下界）。界（下界）。注注： (1) 上例中，上例中，B无最大元，但存在无最大元，但存在B的上的上 界，。界，。 (2) 为为B的最小元，也是的最小元，也是B的下界。的下界。 (3) 最大（小）元是最大（小）元是B的一个上（下）界。的一个上（下）界。 (4) 上（下）界可以不唯一，也可以不存在。上（下）界可以不唯一，也可以不存在。等价关系和偏序关系等价关系和偏序关系71 定义定义 上确界上确界与与下确界下确界： 设设A 是是偏偏序序集集，B B A A，若若y y是是B B的的一一个个上上界界（下下

39、界界），而而对对于于任任意意的的B B的的上上界界（下下界界）x x，都都有有yxyx（xyxy），则则称称y y是是B B的的上上确确界（下确界）。界（下确界）。注注：上确界：最小上界：上确界：最小上界 下确界：最大下界下确界：最大下界 如如果果存存在在上上（下下）确确界界，则则上上（下下）确界一定是唯一的。确界一定是唯一的。等价关系和偏序关系等价关系和偏序关系72例：例： P(A) 中中取取B B=， ， ，则则 ， 与与 ， 是是B B的的上上界界， ， 是是B B的上确界。的上确界。注注：存在上（下）界，并不一定存在上（下）确界。存在上（下）界，并不一定存在上（下）确界。 等价关系和偏

40、序关系等价关系和偏序关系73结论：结论：(1)(1)，是的上界。，是的上界。 (2)(2)与无法比大小，不存在上确界。与无法比大小，不存在上确界。 (3)(3)的下界不存在，不存在下确界。的下界不存在，不存在下确界。例：，例：， ， 等价关系和偏序关系等价关系和偏序关系74 设设F为二元关系，若为二元关系，若 x domF都存在唯都存在唯一的一的y ranF使使xFy成立，则称成立，则称F为为函数函数。 设设A,B为集合，若为集合，若f 为函数，且为函数，且domf =A，ranf B，则称，则称f 为为从从A到到B的函数的函数，记作，记作f :AB. DEFINITION 1. 二元关系和函

41、数二元关系和函数6 6函数的定义和性函数的定义和性质质75 If f is a function from A to B, we say that A is the domain of f and B is the codomain of f. If f (x)=y , we say that y is the image of x and x is a pre-image of y. The range of f is the set of all images of elements of A. Also, if f is a function from A to B, we say th

42、at f maps A to B.A：定义域：定义域/domain of f, x: y的原象的原象/pre-image,B：陪域：陪域/codomain of f, y: x的象的象/image,f(A)：值域：值域/range of f.DEFINITION 2. 函数的定义和性质函数的定义和性质76 设设f :AB, A A, 则则A A在在f f下的象下的象是是F (A)=f (x)| x A.当当A=A时，称时，称f (A)=f (A)=ranf 是是函数的象函数的象。(Let f be a function from the set A to the set B and let A

43、 be a subset of A. The image of A is the subset of B that consists of the images of the elements of A. )A的子集的子集A的象的象DEFINITION 3. 函数的定义和性质函数的定义和性质77 设设A,B为集合，所有从为集合，所有从A到到B的函数构成的函数构成集合集合BA，读做，读做“B上上A”，即，即BA =f | f :AB. 一般的，若一般的，若|A|=m, |B|=n, m,n不全是不全是0，则则|BA|=nm。DEFINITION 4. 如，如，A=0, 1, 2, B=a, b，

44、BA= f 1, f 2, f 3, f 4, f 5, f 6, f 7, f 8 . 函数的定义和性质函数的定义和性质78 设函数设函数f :AB，若，若ranf =B，则称，则称f 是是满射满射的（或的（或映上映上的）。的）。(A function f from A to B is called onto, or surjective, if and only if for every element yB there is an element xA with f(x)=y. A function f is called a surjection (满函数满函数) if it is o

45、nto. )映上的，满函数，满射映上的，满函数，满射DEFINITION 5. 函数的定义和性质函数的定义和性质79 设函数设函数f :AB，其中，其中A=a, b, c, d, B=1, 2, 3，f (a)=3, f (b)=2, f (c)=1, f (d)=3. 问：问：f 是满射的吗？是满射的吗？EXAMPLE 1 abcd123f函数的定义和性质函数的定义和性质80 设函数设函数f :AB，若对于任何的，若对于任何的x1, x2 A, x1 x2, 都有都有f (x1) f (x2)，则称，则称f 是是单射单射的的（或（或一对一的一对一的）。）。(A function f is s

46、aid to be one-to-one, or injective, if and only if f(x1)=f(x2) implies that x1=x2 for all x1 and x2 in the domain of f. A function is said to be an injection(单函数单函数) if it is one-to-one. )一对一，单函数，单射一对一，单函数，单射DEFINITION 6. 函数的定义和性质函数的定义和性质81 设函数设函数f :AB，其中，其中A=a, b, c, d, B=1, 2, 3, 4, 5，f(a)=4, f(b)

47、=5, f(c)=1, f(d)=3. 问：问：f是单射的吗？是单射的吗？EXAMPLE 2 abcd12345f函数的定义和性质函数的定义和性质82 设函数设函数f :AB，若，若f 既是满射的，又是单既是满射的，又是单射的，则称射的，则称f 是是双射双射的（或的（或一一对应一一对应的）。的）。(The function f is a one-one correspondence, or a bijection, if it is both one-to-one and onto. )一一对应，双射一一对应，双射DEFINITION 7. 函数的定义和性质函数的定义和性质83 设设f :RR

48、，对于任意的，对于任意的x1, x2 R，若，若x1x2，则有，则有f (x1)f (x2)，就称，就称f 为为单调递增单调递增的。若的。若x1x2，则有，则有f (x1)f (x2) ，就称，就称f 为为严格单调递增严格单调递增的。类似的也可的。类似的也可以定义以定义单调递减单调递减和和严格单调递减严格单调递减的函数。它们统称的函数。它们统称为为单调函数单调函数。( A function f whose domain and codomain are subsets of the set of real numbers is called strictly increasing if f(x

49、)f(y) whenever xf(y) whenever xy and x and y are in the domain of f. )DEFINITION 8. 函数的定义和性质函数的定义和性质84DEFINITION 9. 设设f :AB，若存在，若存在y B使得对所有的使得对所有的x A都有都有f(x)=y，则称，则称f :AB是是常函数常函数。 设设A为集合，对于任意的为集合，对于任意的A A，A的的特征函数特征函数 A :A 0,1定义为定义为 A (a) = 设设R是是A上的等价关系，定义一个从上的等价关系，定义一个从A到到A/R的函的函数数g:AA/R且且g(a)=a，它把，

50、它把A中的元素中的元素a映射到映射到a的等价类的等价类a，称，称g是从是从A到商集到商集A/R的的自然映射自然映射。1a A0 a A-A函数的定义和性质函数的定义和性质85EXAMPLE 3 1. 设设A=a, b, c, A=a，则有函数，则有函数 A :A0, 1， A (a)=1, A (b)=0, A (c)=0. 2. 设设A=1, 2, 3, R=,IA，则有函数则有函数g:AA/R，g(1)=g(2)=1, 2, g(3)=3.函数的定义和性质函数的定义和性质86 设函数设函数g :AB, f :BC，则，则复合函数复合函数 f g :AC定定义为：义为： 对任意的对任意的xA

51、，有，有(f g)(x) = f (g (x). Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted by fg, is defined by (f g)(x) = f (g (x).函数的复合运算，积运算函数的复合运算，积运算DEFINITION 10. 二元关系和函数二元关系和函数7 7函数的复合和反函函数的复合和反函数数87 设设f :ZZ,

52、 f(x) = 2x + 3, g:ZZ, g(x) = 3x + 2. 求求 f g和和g f.(f g )(x) = f (g(x) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7 (g f )(x) = g(f (x) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11EXAMPLE 4 函数的复合和反函数函数的复合和反函数88定理定理：设设f :AB, g:BC。（1）若）若f, g都是满射，则都是满射，则gf :AC也是满射；也是满射；（2）若）若f, g都是单射，则都是单射，则gf :AC也是单射；也是单射；（3）若）若f, g都

53、是双射，则都是双射，则gf :AC也是双射。也是双射。证明证明(2)：对任意：对任意x1A，x2A且且x1x2，由于，由于f 是单是单射，故有：射，故有： f (x1) f (x2)记记 f (x1 ) =y1， f (x2 ) =y2 . 又因为又因为g是单射，所以，是单射，所以，g(y1) g(y2)从而，从而，g(f (x1) g(f (x2)，即，即 gf (x1) gf (x2).函数的复合和反函数函数的复合和反函数89 对于双射函数对于双射函数f :AB，称，称f -1-1:BA是是f 的的反函数反函数。 对于任意对于任意xA, yB，若，若f (x)=y，则，则f -1-1(y)

54、=x.反函数反函数DEFINITION 11. 函数的复合和反函数函数的复合和反函数90定理定理： 设设f :AB是双射的，则是双射的，则f -1-1是函数，且是函数，且是从是从B到到A的双射函数。的双射函数。 对任何双射函数对任何双射函数f :AB和它的反函数和它的反函数f -1-1 :BA，它们的复合函数都是恒等函数，它们的复合函数都是恒等函数，且满足且满足f -1-1 f = IA , f f 1 1= IB .函数的复合和反函数函数的复合和反函数91图中定义了函数图中定义了函数f , g和和h.EXAMPLE 5 1234 1234f1234 1234g 12341234h(1) 求求

55、f , g和和h的象。的象。(2) 求求g f , f h和和g g .(3) 指出指出f, g, h中哪些函数是单射的，哪些函数是满射的。中哪些函数是单射的，哪些函数是满射的。(4) f, g, h种哪些函数存在反函数，给出其反函数的表达式。种哪些函数存在反函数，给出其反函数的表达式。函数的复合和反函数函数的复合和反函数92解：解：(1) 令令A=1,2,3,4，则，则f, g, h都是从都是从A到到A的函数，的函数，f(A)=1, 2, 4, g(A)=1, 2, 3, 4=A, h(A)=1, 3.(2) gf :AA, gf (1)=4, gf (2)=2, gf (3)=2, gf (4)=3. f h:AA, f h(1)=2, f h(2)=1, f h(3)=2, f h(4)=1.g g:AA, g g(1)=4, g g(2)=3, g g(3)=2, g g(4)=1.(3) 只有只有g是单射的，满射的。是单射的，满射的。(4) 只有只有g有反函数有反函数g-1 -1 :AA, g-1-1(1)=3, g-1-1(2)=1, g-1-1(3)=4, g-1-1(4)=2.函数的复合和反函数函数的复合和反函数93离散数学离散数学授课教师：向胜军谢谢！谢谢！