第4章 二元关系和函数[离散数学离散数学(第四版)清华出版社]

《第4章 二元关系和函数[离散数学离散数学(第四版)清华出版社]》由会员分享，可在线阅读，更多相关《第4章 二元关系和函数[离散数学离散数学(第四版)清华出版社]（94页珍藏版）》请在装配图网上搜索。

1、离散数学离散数学授课教师：向胜军笛卡尔积与二元关系笛卡尔积与二元关系关系的运算关系的运算关系的性质关系的性质关系的闭包关系的闭包等价关系和偏序关系等价关系和偏序关系函数的定义和性质函数的定义和性质函数的复合和反函数函数的复合和反函数2(The ordered n-tuple is the ordered collection that has x1 as its first element, x2 as its second element, , and xn as its nth element.)DEFINITION 1. 笛卡尔积与二元关系笛卡尔积与二元关系3(Let A and B b

2、e sets. The Cartesian product of A and B, denoted by AB, is the set of all ordered pairs where xA and yB. Hence, AB = xAyB. )DEFINITION 2. 4AB=, , , , , .EXAMPLE 1 若若A中有中有m个元素，个元素，B中有中有n个元素，个元素，则则AB中有中有mn个元素。个元素。5设集合设集合A = 1, 2，求，求P(A)A .P(A)A=,1,2,1,21,2 =, , , , , .EXAMPLE 2 6(The Cartesian produc

3、t of the sets A1, A2, , An, denoted by A1A2An, is the set of ordered n-tuples , where xi belongs to Ai for i=1,2,n. )DEFINITION 3. 7ABC=, , , ,.EXAMPLE 3 8笛卡尔积运算的性质：笛卡尔积运算的性质：1、若、若A, B中有一个空集，则它们的笛卡尔中有一个空集，则它们的笛卡尔积是空集，即：积是空集，即：B=A=.2、当、当A B且且A, B都不是空集时，有都不是空集时，有AB BA.3、当、当A, B, C都不是空集时，有都不是空集时，有(AB)C

4、 A(BC).9笛卡尔积运算的性质：笛卡尔积运算的性质：4、笛卡尔积运算对、笛卡尔积运算对或或运算满足分配律，运算满足分配律，即：即： A(BC)=(AB)(AC);(BC)A=(BA)(CA);A(BC)=(AB)(AC);(BC)A=(BA)(CA).10证明等式：证明等式：(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) 11注意：注意：二元关系是指满足某规律的有序对的全体。二元关系是指满足某规律的有序对的全体。二

5、元关系二元关系按照某种规定，定义了一个有序对按照某种规定，定义了一个有序对的集合的集合R，其中，其中xA，yB，称，称R为为从从到到B的二元关系的二元关系。DEFINITION 4. 当当A=B时，时，R是是A到到A的二元关系，称为的二元关系，称为A上的二元关系上的二元关系。DEFINITION 5. 对于二元关系对于二元关系R，若，若R，则记作，则记作xRy，若，若 R，则记作，则记作xRy。例：R=|x /y, x,yN是自然数集上的二元关系。12例如： A=张三，李四，王五，赵六 B=100米，跳高，铅球，足球，跨栏穷举法表示： R=， ，是运动会的报名表。二元关系的表示二元关系的表示：

6、因为二元关系本身也是集合，：因为二元关系本身也是集合，也可用穷举法，描述法来表示，还可用表格、图也可用穷举法，描述法来表示，还可用表格、图示、矩阵法表示。示、矩阵法表示。DEFINITION 6. 13 100 米 跳高 铅球 足球 跨栏 张三 李四 王五 赵六 用字母数字来代替这些元素 A a，b，c，d B 1，2，3，4，5 表格表示法：表格表示法：用表格表示一目了然14 a b c d 1 2 3 4 5 图示法：图示法：关系图，直观15相关矩阵法表示：相关矩阵法表示：把A, B集合内元素排好序R)(00001100000001101100ijadcba 1 2 3 4 516二元关系

7、是笛卡尔二元关系是笛卡尔AB的子集。的子集。若若R=AB，则相关矩阵元素全为，则相关矩阵元素全为1。R111111111 17注：（注：（1）若）若RAB，称此二元关系为全域关系；，称此二元关系为全域关系； （2）设）设Ax1，x2，xn Rxi，xjA 若若RxiA 称称R为恒等关系，用为恒等关系，用IA表示，是单位矩阵。表示，是单位矩阵。A= 1000010000100001 18关系关系R的的定义域定义域domR，值域值域ranR和和域域fldR分别是：分别是： domR=x | y(R). ranR=y | x(R). fldR=domRranR.当定义域与值域交换得当定义域与值域交换

8、得 R-1=| yRx ，称为，称为R的的逆关系逆关系。DEFINITION 7. 关系的运算关系的运算19 二元关系是集合，集合存在并、交、差、二元关系是集合，集合存在并、交、差、非和对称差的运算，故二元关系也存在这非和对称差的运算，故二元关系也存在这样的运算。样的运算。设设R1和和R2是是A到到B的二元关系，则：的二元关系，则：（1）R1R2R1R2（2）R1R2R1R2（3）R1-R2R1 R2 （5）R1 R2R1R2 R1R2（4）1R AB R1 20例1：A1，2，3，4，I为整数集， Ra，bA，2ba Sa，bA，3ba, ab0 求：求：RS，RS，R，RS，SR，SR 解

9、：R与S都是A上的二元关系 R=, , S=21R, , R-S=R，S-R=S，SR=RS RS=, ,RS= 22例2： R是父子关系，则R=R R是祖孙关系。设设F, G为任意的关系，为任意的关系，A为集合，为集合，F与与G的的复合关系复合关系（合成合成）记作）记作F G，F G = | z(xGzzFy)DEFINITION 8. 23例 3： A=4321aaaa李兰，陈平，王兵，张华是学生集合， B=4321bbbb遥感，自动化，硬件，软件是专业集合， C=4321cccc离散数学，操作系统，电子线路，工程制图 是课程集合， 则：R1=, ,是各专业本学期必修课的二元关系。24R3

10、 = R1 R2 =, , ,是选双学位学生本学期必修课的二元关系。R2=,， ,是学生选双学位专业的二元关系。25 A=)(ijanm， B=)(jkbln， 则：C=AB=)(ikclm cik)(jkijn1jbaV 普通的矩阵乘法：普通的矩阵乘法：二元关系的复合的布尔型矩阵乘法：二元关系的复合的布尔型矩阵乘法：其中，ciknjjkijba1 26对例 3，有： R11010001111101100，R2=1001110010100101 R3R2R11110101111101111 在行处标上姓名，列处标上课程，就知谁该必在行处标上姓名，列处标上课程，就知谁该必修哪些课了。修哪些课了。

11、27设设R为为A上的二元关系，上的二元关系，n为自然数，则为自然数，则R的的n次幂次幂规定如下：规定如下：(1) R0=xA；(2) Rn= Rn-1 R, n 1. DEFINITION 8. 28例4： R=,是集合0,1,2,3上的二元关系，R的关系图如下：29R2=, ,30Rn的关系图的构造：的关系图的构造： 可由可由R的关系图来构造，从的关系图来构造，从R的每个结点的每个结点xi出发，出发，数数n条边。若通过数条边。若通过数n条边能到达结点条边能到达结点xj，则有，则有Rn。关系图中从。关系图中从xi出发到出发到xj的边是存在的。的边是存在的。 这样处理容易出错，用相关矩阵的布尔型

12、乘法来这样处理容易出错，用相关矩阵的布尔型乘法来做，简单，又不容易错，还适宜于计算机处理。做，简单，又不容易错，还适宜于计算机处理。31R2=RR= 101111010000110101001011000010010100101100001001 0100101100001001R 32定理：定理：设设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 (GH) =(F G)(F H)；(6) F (GH) (F

13、 G)(F H)；(7) (GH) F=(G F)(H F)；(8) (GH) F (G F)(H F).33证明：证明：(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-134证明：证明：(7)任取任取， (GH) F z( F GH) z( F ( G H) z( F G ) ( F H) G F H F (G F)(H F) (GH) F=(G F)(H F)35设设R是是A上的二元关系，上的二元关系，R=(rij)n*n(1)自反性自反性：对对 xA，R，则，则R称为自反的二元关系

14、。称为自反的二元关系。显然，显然，rii=1(i=1,2,n) 反自反性反自反性：对对 xA， R，则，则R称为反自反的二元关系。称为反自反的二元关系。即即rii=0(i=1,2,n)注注： 自反和反自反性互斥，但不互补。自反和反自反性互斥，但不互补。 如：如：rii中既有中既有0又有又有1，则，则R既不是自反的也不既不是自反的也不是反自反的。是反自反的。 关系的性质关系的性质36(2)对称性对称性： 若若xy, R,必有必有R，称，称R为对称的为对称的二元关系。即二元关系。即R的相关矩阵为对称阵，的相关矩阵为对称阵，rij=rji. 反对称性反对称性： 若若xy，R,则则 R，称，称R为反对

15、称的为反对称的二元关系。二元关系。注注：(1)R的相关矩阵是反对称的，即：的相关矩阵是反对称的，即：rijrji =0 (ij)(2)若若rij=1，则，则rji=0；但；但rij=0时，不要求时，不要求rji=1，即即rij=rji=0是允许的。是允许的。(3)对称性与反对称性既不互斥，又不互补。对称性与反对称性既不互斥，又不互补。37例： 恒等关系：既是对称的，又是反对称的； 而相关矩阵为1001010001001001的二元关系， 既不是对称的，又不是反对称的。 38注注：若若rij，rjk中有一个不是，中有一个不是， 则则 (rijrjk) =1， rik就可以任意。就可以任意。 即：

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

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

18、41例：R1=xy， x,yN 自反的，rii=1； 不是对称的，R1，而R1； 反对称的，传递的。注注：将将改为，则无自反性，且是反自反的。改为，则无自反性，且是反自反的。例2：R2=x|y，x,yN 自反的，不是对称的，反对称的，传递的。例3：R3=S1S2，S1,S2P(S)其中P(S)是S的幂集。 自反的，不是对称的，反对称的，传递的。注注：若若 改为改为 ，则无自反性。，则无自反性。42例4：R4=x+y=偶数，x,yN 自反的，对称的，传递的。因为，若x+y=偶数，y+z=偶数，则：0 x+z=(x+y)+(y+z)-2y=偶数与偶数之差=偶数。例5：R5=x与y互为素数，x,yN

19、 对称的，但不是自反的，也无传递性。（1）素数：素数：素数是一个比1大，其因子只有1和它本身，没有其它数可以整除它的数。素数是无限的。例如：2，3，5，7。 （2）两个数互为素数：两个数互为素数：指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如，4和9，13和27等。43定理定理1：设：设R是是A上的二元关系，则上的二元关系，则RIA一定是一定是自反的，而且是包含自反的，而且是包含R，具有自反性的最小关系。，具有自反性的最小关系。（其中（其中IA是是A上的恒等关系）。上的恒等关系）。定义定义1：称：称RIA是是R的的自反闭包自反闭包，记为，记为r(R)。证明：对证明：

20、对 xA，IA RIA，且，且R RIA。 若若R 包含包含R且具有自反性，则且具有自反性，则IA R，R R，IAR R。即。即IAR为最小。为最小。推论推论1：当且仅当：当且仅当R是自反闭包，是自反闭包，R具有自反性。具有自反性。证明： (1)R是自反闭包，R=IARIA R； (2)R具有自反性，IA R，RIA=R.关系的闭包关系的闭包44定理定理2：设：设R是是A上的二元关系，则上的二元关系，则RR-1是对是对称的，包含称的，包含R的最小关系。的最小关系。（其中（其中R-1是是R的逆关系）。的逆关系）。定义定义2：称：称RR-1是是R的的对称闭包对称闭包，记为，记为s(R)。 证明：

21、(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。45推论推论2：当且仅当：当且仅当R是对称闭包时，是对称闭包时，R具有对称性。具有对称性。证明：(1)R具有对称性， 若R，则R， 又R-1 即R-1，R R R-1RRR-1R；(2)R是对称闭包时，RRR-1R具有对称性。46定理定理3：传递闭包传递闭包t(R)RR2R3例6：设A=1,2,3，R=,，求t(R) 。解： R000100011,R2000000111R3 故 t(R)RR2R30001

22、00111 t(R)， 47 定义定义1 等价关系：等价关系： A上的二元关系上的二元关系R，如果，如果R是是 (1) 自反的自反的 (2) 对称的对称的 (3) 传递的传递的 称称R为为等价关系等价关系。若若R，称，称x与与y等价，记作等价，记作xy。等价关系和偏序关系等价关系和偏序关系48定义定义2 等价类等价类：把中的等价元素归为一类，称为等把中的等价元素归为一类，称为等价类。价类。注注：等价关系等价关系R把的元素分为若干类，各类之间没把的元素分为若干类，各类之间没有公共元素。确定的有公共元素。确定的R是对集合进行的划分。是对集合进行的划分。定义定义3 集合的集合的划分划分：把集合：把集

23、合A分为若干子集分为若干子集A1,A2 , ,满足：满足： (1) 当当 i j 时，时，AiAj (2) xA， i， 使使xAi (i，)，则集合则集合 = A1，A2，An， 称为的一个划分。称为的一个划分。 49定理定理1： A在等价关系在等价关系R下的等价类正是下的等价类正是A的一种的一种划分，划分，A的任一种划分，也必有的任一种划分，也必有A上的一个等上的一个等价关系价关系R与之对应。与之对应。注注：(1) P(A)（A的幂集）；的幂集）；(2) 当且仅当当且仅当A = ， = P(A)=；(3) A非空时，非空时， P(A).50证明： R是等价关系， xA，由R的自反性，R，即

24、x与x属于同一等价类，即i，xAi. 若ij，AiAj，而AiAj 。则zAiAj，zAi，且zAj , 对xAi，xz，zAj 对yAj，yz，即zy(对称性) 由传递性，xy. 由x，y的任意性，故AiAj 与Ai和Aj 为不同的等价类矛盾。 故AiAj = 所以，R完成了等价类的划分。51 若A已进行了划分，则构造二元关系R。(1) xA，使R.(2) 分别对每一等价类内所有两个不同元素x，y，R，使R. 显然，R是自反的，对称的，而且也是传递的，因为若R，R，则x，y，z均在同一等价类内， 故R。52例1： A52张扑克 R1x与y同花，x，y是扑克 R2x与y同点，x，y是扑克 则：

25、 R1把分为四类同花类， R2把分为13类同点类。例2： A0，1，2，3，4，5 R，53R是等价关系，但不直观，用关系图表示。是等价关系，但不直观，用关系图表示。三个不连通的图三个不连通的图二元关系二元关系R是自反的，对称的，传递的，且把分成是自反的，对称的，传递的，且把分成了三个等价类，了三个等价类，0，1，2，3，4，554定义定义 商集的元素个数（即商集的元素个数（即A在在R下的等价类个数）下的等价类个数）称为称为R的的秩秩。定义定义 商集商集：等价关系：等价关系R将将A分成若干等价类，每分成若干等价类，每个类选个代表组成新的集合称为个类选个代表组成新的集合称为A关于关于R的商集，的

26、商集，表示为表示为A/R。例：在上例中 A/R0，1，455例3： Rxy（mod），x，yZ是整数集合Z上模3同余的二元关系，证明R是等价关系。证明：(1) xx(mod 3). 自反性(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，56 定义定义 偏序关系偏序关系： 是上的二元关系，如果满足：是上的二元关系，如果满足： (1) 自反的自反的 (2) 反对称的反对称

27、的 (3) 传递的传递的则称是上偏序关系，简称偏序。记作则称是上偏序关系，简称偏序。记作。57例：例： ， ， 1 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可为可为 ，|， 。 58注注： （1）用矩阵表示偏序关系，不能明显看到）用矩阵表示偏序关系，不能明显看到 二元关系的特征。二元关系的特征。 （2）用简化的关系图表示较适合。）用简化的关系图表示较适合。 简化的关系图简化的关系图： (1)(1)自反性自反性：每个顶点都有自回路

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

29、线连接。并符合简化的关系图的绘制，称这样得到的关系图为称这样得到的关系图为Hasse图。图。上例中偏序关系的上例中偏序关系的Hasse图如下：图如下：60 1 2 3 4 5 6 7 8 9 R1R1616263定义定义 全序全序： 上偏序关系，如果上偏序关系，如果 x，y，都有，都有xy，或或yx，则称为上的，则称为上的全序关系全序关系。注注： (1) (1) 全序的含义：中每两个元素均能比大小，即全序的含义：中每两个元素均能比大小，即任何两个元素都相关。任何两个元素都相关。 (2) (2) 偏序则是部分有序。偏序则是部分有序。 (3) (3) 上例中，上例中，1 1是全序，是全序，2 2，

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

31、是是上的全序，则此上的全序，则此 称为全序集。称为全序集。 是全序集。显然，全序集是偏序是全序集。显然，全序集是偏序集的特例。又如：（集的特例。又如：（，）实数全体，在）实数全体，在下是全序集；下是全序集；当然也是全序集。当然也是全序集。66定义定义 极大元极大元与与极小元极小元： 设设是偏序集，是偏序集，B A，若，若yB，且在，且在B中找不到一个元素中找不到一个元素x（xy），使），使yx (xy)，则称，则称y为为B中的极大元（极小元）。中的极大元（极小元）。例例：是偏序集，是偏序集， B，则则 B中极大元：，中极大元：， 极小元：，极小元：，注注： 极大元，极小元并不要求唯一，且同一元

32、素，极大元，极小元并不要求唯一，且同一元素，可以既是极大元，又是极小元，如，。可以既是极大元，又是极小元，如，。67注注： 极大元，极小元必须是子集极大元，极小元必须是子集B B中的元素。中的元素。 定义定义 最大元最大元与与最小元最小元： 设设 是偏序集，是偏序集，B B A，若，若yByB， xBxB，xy (yx)xy (yx)，则称，则称y y为为B B的最大元（最小元）。的最大元（最小元）。例：在上例中，例：在上例中，HasseHasse图如下所示：图如下所示：68结论结论： 子集子集B B中是不存在最大元（最小元）的。中是不存在最大元（最小元）的。69例：例： A，, 3 s1 s

33、2， s1，s2P(A)，是偏序集。是偏序集。 设设B， 其其HasseHasse图如下所示：图如下所示：70结论结论： B存在最小元存在最小元 ，没有最大元。，没有最大元。注注： 最大元（最小元）本身应属于子集最大元（最小元）本身应属于子集B，且与，且与B中任一元素都有关系。中任一元素都有关系。71定义定义 上界上界与与下界下界： 设设是偏序集，是偏序集，B A， 若若yA，对，对 x xB，xy (yx)称称y为为B的的上界（下界）。上界（下界）。注注： (1) 上例中，上例中，B无最大元，但存在无最大元，但存在B的上的上 界，。界，。 (2) 为为B的最小元，也是的最小元，也是B的下界。

34、的下界。 (3) 最大（小）元是最大（小）元是B的一个上（下）界。的一个上（下）界。 (4) 上（下）界可以不唯一，也可以不存在。上（下）界可以不唯一，也可以不存在。72 定义定义 上确界上确界与与下确界下确界： 设设A 是偏序集，是偏序集，B B A A，若，若y y是是B B的一的一个上界（下界），而个上界（下界），而对于任意的对于任意的B B的上界（下的上界（下界）界）x x，都有，都有yxyx（xyxy），则称），则称y y是是B B的上确的上确界（下确界）。界（下确界）。注注：上确界：最小上界：上确界：最小上界 下确界：最大下界下确界：最大下界 如果存在上（下）确界，则上（下）如果存

35、在上（下）确界，则上（下）确界一定是唯一的。确界一定是唯一的。73例：例： P(A) 中取中取B B=， ， ，则，则 ， 与与 ， 是是B B的上界，的上界， ， 是是B B的上确界。的上确界。注注：存在上（下）界，并不一定存在上（下）确界。存在上（下）界，并不一定存在上（下）确界。 74结论：结论：(1)(1)，是的上界。，是的上界。 (2)(2)与无法比大小，不存在上确界。与无法比大小，不存在上确界。 (3)(3)的下界不存在，不存在下确界。的下界不存在，不存在下确界。例：，例：， ， 75 设设F为二元关系，若为二元关系，若 x domF都存在唯都存在唯一的一的y ranF使使xFy成

36、立，则称成立，则称F为为函数函数。 设设A,B为集合，若为集合，若f 为函数，且为函数，且domf =A，ranf B，则称，则称f 为为从从A到到B的函数的函数，记作，记作f :AB. DEFINITION 1. 函数的定义和性函数的定义和性质质76 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 rang

37、e of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that 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. 77 设设f :AB, A A, 则则A A在在f f下的象下的象是是F (A)=f (x)| x A.当当A=A时，称时，称f (A)

38、=f (A)=ranf 是是函数的象函数的象。(Let f be a function from the set A to the set B and let A 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. 78 设设A,B为集合，所有从为集合，所有从A到到B的函数构成的函数构成集合集合BA，读做，读做“B上上A”，即，即BA =f | f :AB. 一般的，若一般的，若|A|=m,

39、 |B|=n, m,n不全是不全是0，则则|BA|=nm。DEFINITION 4. 如，如，A=0, 1, 2, B=a, b，BA= f 1, f 2, f 3, f 4, f 5, f 6, f 7, f 8 . 79 设函数设函数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 func

40、tion f is called a surjection (满函数满函数) if it is onto. )映上的，满函数，满射映上的，满函数，满射DEFINITION 5. 80 设函数设函数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 abcd123f81 设函数设函数f :AB，若对于任何的，若对于任何的x1, x2 A, x1 x2, 都有都有f (x1) f (x2)，则称，则称f 是是单射单射的的（或（或一对一的一对一的）。）。(

41、A function f is said 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. 82 设函数设函数f :AB，其中，其中A=a, b, c, d, B=1, 2, 3, 4, 5，f(a)=4, f(b

42、)=5, f(c)=1, f(d)=3. 问：问：f是单射的吗？是单射的吗？EXAMPLE 2 abcd12345f83 设函数设函数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. 84 设设f :RR，对于任意的，对于任意的x1, x2 R，若，若x1x2，则有

43、，则有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)f(y) whenever xf(y) whenever x

44、y and x and y are in the domain of f. )DEFINITION 8. 85DEFINITION 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，它把，它把A中的元素中的元素a映射到映射到a的等价类的等价类a，称，称g是从是从A到商集到商集A/R

45、的的自然映射自然映射。1a A0 a A-A86EXAMPLE 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.87 设函数设函数g :AB, f :BC，则，则复合函数复合函数 f g :AC定义为：定义为： 对任意的对任意的xA，有，有(f g)(x) = f (g (x). Let g be a function from the set A to the set B and le

46、t f be a function from the set B to the set C. The composition of the functions f and g, denoted by f g, is defined by (f g)(x) = f (g (x).函数的复合运算，积运算函数的复合运算，积运算DEFINITION 10. 函数的复合和反函函数的复合和反函数数88 设设f :ZZ, 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) +

47、 3 = 6x + 7 (g f )(x) = g(f (x) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11EXAMPLE 4 89定理定理：设设f :AB, g:BC。（1）若）若f, g都是满射，则都是满射，则g f :AC也是满射；也是满射；（2）若）若f, g都是单射，则都是单射，则g f :AC也是单射；也是单射；（3）若）若f, g都是双射，则都是双射，则g f :AC也是双射。也是双射。证明证明(2)：对任意：对任意x1A，x2A且且x1x2，由于，由于f 是单是单射，故有：射，故有： f (x1) f (x2)记记 f (x1 ) =y1， f (

48、x2 ) =y2 . 又因为又因为g是单射，所以，是单射，所以，g(y1) g(y2)从而，从而，g(f (x1) g(f (x2)，即，即 g f (x1) g f (x2).90 对于双射函数对于双射函数f :AB，称，称f -1-1:BA是是f 的的反函数反函数。 对于任意对于任意xA, yB，若，若f (x)=y，则，则f -1-1(y)=x.反函数反函数DEFINITION 11. 91定理定理： 设设f :AB是双射的，则是双射的，则f -1-1是函数，且是函数，且是从是从B到到A的双射函数。的双射函数。 对任何双射函数对任何双射函数f :AB和它的反函数和它的反函数f -1-1

49、:BA，它们的复合函数都是恒等函，它们的复合函数都是恒等函数，且满足数，且满足f -1-1 f = IA , f f 1 1= IB .92图中定义了函数图中定义了函数f , g和和h.EXAMPLE 5 1234 1234f1234 1234g 12341234h(1) 求求f , g和和h的象。的象。(2) 求求g f , f h和和g g .(3) 指出指出f, g, h中哪些函数是单射的，哪些函数是满射的。中哪些函数是单射的，哪些函数是满射的。(4) f, g, h种哪些函数存在反函数，给出其反函数的表达式。种哪些函数存在反函数，给出其反函数的表达式。93解：解：(1) 令令A=1,2

50、,3,4，则，则f, g, h都是从都是从A到到A的函数，的函数，f(A)=1, 2, 4, g(A)=1, 2, 3, 4=A, h(A)=1, 3.(2) g f :AA, g f (1)=4, g f (2)=2, g f (3)=2, g f (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.离散数学离散数学授课教师：向胜军