离散数学第五版第四章二元关系和函数

1、离散数学,第四章 二元关系和函数,4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数,4.1迪卡尔乘积与二元关系,定义4.1,一、有序对,由两个元素x和y（允许x=y）按一定的顺序排列成的二元 组叫做一个有序对或序偶，记作，其中x是它的第一 元素，y是它的第二元素。,有序对性质,当xy时，,=的充分必要条件是x=u且y=v,集合中的元素具有无序性，但是有序对中的元素是有序的。,4.1迪卡尔乘积与二元关系,例1：已知= 求x和y,解得：x=3，y=-2,有序n元组,一个有序n元组

2、(n=3)是一个有序对，其中第一个元素是 一个有序n-1元组，一个有序n元组记作，即,=,xn,例如：空间直角坐标系中点的坐标、等有序 3元组。n维空间中点的坐标或n维向量都是有序n元组。,4.1迪卡尔乘积与二元关系,定义4.3,二、迪卡尔乘积,设A，B为集合，用A中元素为第一元素，B中元素为第二 元素构成有序对。所有这样的有序对组成的集合叫做A 和B的迪卡尔乘积，记作AB。符号化表示为： AB=|xA yB,4.1迪卡尔乘积与二元关系,迪卡尔乘积的性质,如果|A|=m,|B|=n，则|AB|=mn,对任意集合A，根据定义有：A=，A=,一般地说，迪卡尔乘积运算不满足交换律，即： ABBA(当

3、A B AB时),迪卡尔乘积运算不满足结合律，即： （AB）CA（BC）（当A B C ）,4.1迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(1)A（BC）= (AB)(AC）,证明： 对于任意的 A（BC） xA yBC xA (yB y C) (xAyB)(xAyC) AB AC (AB)(AC),4.1迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(2)（BC）A= (BA)(CA）,证明： 对于任意的 （BC）A xBC yA (xB x C) yA (xB yA)(xC yA) BA CA (BA)(CA),4.1迪卡尔乘积与二元关系,迪卡

4、尔乘积运算对并和交运算满足分配律，即：,(3)A（BC）= (AB)(AC）,证明： 对于任意的 A（BC） xA yBC xA (yB y C) (xAyB) (xAyC) AB AC (AB)(AC),4.1迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(4)（BC）A= (BA)(CA）,证明： 对于任意的 （BC）A xBC yA (xB x C) yA (xB yA)(xC yA) BA CA (BA)(CA),4.1迪卡尔乘积与二元关系,AC BD AB CD,证明： 对于任意的 AB xA y B xC y D xCD 所以：AB CD,4.1迪卡尔乘积与二元

5、关系,n阶迪卡尔乘积（定义4.4）,设A1，A2，An是集合(n=2)，它们的n阶迪卡尔乘积记作 A1A2An，其中： A1A2An =|x1A1 x2A2 xnAn,4.1迪卡尔乘积与二元关系,例2：设A=1,2，求P(A)A,解：P(A)=,1,2,1,2 P(A)A=, , , ,4.1迪卡尔乘积与二元关系,例3：设A,B,C,D为任意集合，判断以下等式是否成立？,（1）(AB)(CD)=(AC)(BD),证明： 对于任意的 (AB)(CD) xAB yCD xA xB yC yD (xA yC)(xB yD) AC BD (AC)(BD),4.1迪卡尔乘积与二元关系,（2）(AB)(C

6、D)=(AC)(BD),证明：设A=、B=1、C=2、D=3 (AB)(CD)=、 (AC)(BD)=、 所以：等式不成立,（3）(A-B)(C-D)=(AC)-(BD),证明：设A=1、B=1、C=2、D=3 (A-B)(C-D)= (AC)-(BD)= 所以：等式不成立,4.1迪卡尔乘积与二元关系,（4）(AB)(CD)=(AC)(BD),证明：设A=1、B=1、C=2、D=3 (AB)(CD)= (AC)(BD)=, 所以：等式不成立,4.1迪卡尔乘积与二元关系,例4：设A,B,C,D为任意集合，判断真假。,（1）AB=ACB=C,证明：若A=，B=1，C=2 则AB=AC=，而BC。

7、所以：命题真假不定,4.1迪卡尔乘积与二元关系,（2）A-(BC)=(AB)-(AC),证明：若A=0，B=1，C=2 则A-(BC)=0 (AB)-(AC)= 所以：命题真假不定,4.1迪卡尔乘积与二元关系,（3）A=B C=D (AC)=(BD),证明：对任意 AC xA yC xB yD x 所以：命题真值为1,4.1迪卡尔乘积与二元关系,（4）存在集合A，使得AAA,证明：令A=则AA= 所以：AAA 该命题真值为1,4.1迪卡尔乘积与二元关系,定义4.5,三、二元关系,如果一个集合满足以下条件之一： 集合非空，且它的元素都是有序对 集合是空集 则称这样的集合为二元关系，记作R。二元关

8、系也可以简 称为关系。对于二元关系R，如果R，可记作xRy。,例：R1=,，R2=,a,b 则R1为二元关系；R2不是二元关系，仅仅是一个集合。,4.1迪卡尔乘积与二元关系,集合上元素的关系（定义4.6）,三、二元关系,设A，B为集合，AB的任何子集所定义的二元关系叫做 从A到B的二元关系，特别当A=B是则叫做A上的二元关系。,例：A=0,1、B=1,2,3， 那么R1=，R2=AB，R3=，R4=等都是 A到B的二元关系。R3和R4是A上的二元关系。,集合A上的二元关系的数目依赖于A中的元素数：设|A|=n，则|AA|= 。AA的子集有 个。每个子集代表一个A上的二元关系，所以A上的二元关系

9、数目为： 。,4.1迪卡尔乘积与二元关系,全域关系与恒等关系,例：A=0,1 A上的全域关系为：,. A上的恒等关系为：,.,对于任意集合A，定义： EA=|xA yA=AA IA =|xA LA =|x,yA x|x,yA x整除y ,这里A,4.1迪卡尔乘积与二元关系,例：A=4,0.5,-1,B=1,2,3,6，则,LA=, , LB=, ,4.1迪卡尔乘积与二元关系,例5：设A=a,b，R是P(A)上的包含关系，,R=|x,yP(A)xy,解：P(A)=,a,b,a,b R=, , ,4.1迪卡尔乘积与二元关系,关系的表示方法,集合表达式：,例6：设A=1,2,3,4，下面各式定义的R

10、都是A上的 关系，试用列元素法表示R R1=|x是y的倍数 R2=|(x-y)(x-y)A R3=|x/y是素数 R4=|xy,4.1迪卡尔乘积与二元关系,关系的表示方法,关系矩阵：,4.1迪卡尔乘积与二元关系,关系的表示方法,关系图：,设A=x1,x2,xn，R是A上的关系，令图G=， 其中顶点集合V=A，边集为E。对于xi，xjV，满足 ExiRxj 称图G为R的关系图，记作GR。,第四章 二元关系和函数,4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数,4.2 关系的运

11、算,关系的定义域、值域、域（定义4.8）,一、关系的基本运算,设R是二元关系。,R中所有有序对的第一元素构成的集合称为R的定义 域，记作domR，形式化表示为： domR=x|y(R),R中所有有序对的第二元素构成的集合称为R的值 域，记作ranR，形式化表示为： ranR=y|x(R),4.2 关系的运算,R的定义域和值域的并集称为R的域，记作fldR，形式化 表示为： fldR=domR ranR,例1：设R=,，则,domR=1,2,4 ranR=2,3,4 fldR=1,2,3,4,4.2 关系的运算,例2：下列关系都是整数集Z上的关系，分别求出它们的 定义域和值域。,(1)R1=|x

12、,yZ x=y,(2)R2=|x,yZ x*x+y*y=1,(3)R3=|x,yZ y=2x,(4)R4=|x,yZ |x|=|y|=3,4.2 关系的运算,关系的逆运算（定义4.9）,设R为二元关系，R的逆关系，简称R的逆，记作 ，其中,关系的合成运算（定义4.9）,设F，G为二元关系，F和G的合成记作FG，其中 FG=|z(xGz zFy),4.2 关系的运算,例3：设F=,，G=，则,FG=,=,GF=,例4：设F=|x,yN y=x*x， G=|x,yN y=x+1， 求,4.2 关系的运算,限制与像（定义4.9）,设F为二元关系，A是集合,4.2 关系的运算,例5：设R=, 则,R1

13、=2,3,R=,R2,3=2,4,4.2 关系的运算,关系的运算的顺序,关系运算中的逆运算优先于其他运算； 所有的关系运算都优先于集合运算； 没有规定优先权的运算以括号决定运算顺序。,4.2 关系的运算,定理4.1,二、关系基本运算的性质,设F,G,H是任意的关系，则,=F,dom =ranF,ran =domF,(FG)H =F(GH),(FG) =G F,4.2 关系的运算,定理,设R为A上的关系，则,RIA=IAR=R,定理4.2,F(GH)=FG FH,(GH)F=GF HF,F(GH)FG FH,(GH)FGF HF,4.2 关系的运算,定义4.10,三、关系的n次幂,注：(1) 。

14、 (2) 。,4.2 关系的运算,例6：设A=a,b,c,d,R=, 求,=IA=,=,=,=,=,=,4.2 关系的运算,定理4.3,第四章 二元关系和函数,4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数,4.3关系的性质,自反性、反自反性,一、关系的性质,A上的全域关系EA、恒等关系IA、都是A上的自反关系。,小于等于关系LA、整除关系DB分别为A和B上的自反关系。,小于关系、真包含关系是给定集合或集合族上的反自反关系。,4.3关系的性质,例8：设A=1,2,3，R1，

15、R2和R3是A上的关系，其中 R1=, R2=, R3= 说明R1，R2和R3是否为A上的自反关系和反自反关系。,R3是A上的反自反关系，R2是A上的自反关系。,4.3关系的性质,对称性、反对称性,A上的全域关系EA、恒等关系IA、空关系都是A上的对称关系。,恒等关系IA、空关系也是A上的反对称关系。,4.3关系的性质,例9：设A=1,2,3，R1，R2和R3是A上的关系，其中 R1=, R2=, R3=, R4=, 说明R1，R2，R3和R4是否为A上的对称关系和反对称关系。,4.3关系的性质,传递性,A上的全域关系EA、恒等关系IA、空关系都是A上的传递关系。,小于或等于LA、整除关系和包

16、含关系也是相应集合上的的传递关系。,小于关系、真包含关系也是相应集合上的的传递关系。,4.3关系的性质,例10：设A=1,2,3，R1，R2和R3是A上的关系，其中 R1=, R2=, R3= 说明R1，R2，R3和R4是否为A上的传递关系。,4.3关系的性质,定理,二、关系性质的相关定理,设R是A上的关系，则,R在A上的自反当且仅当IAR。,R在A上的反自反当且仅当RIA=。,R在A上的对称当且仅当 。,R在A上的反对称当且仅当 。,R在A上的传递当且仅当 。,4.3关系的性质,例11：设A是集合，R1和R2是A上的关系，证明： (1)若R1，R2是自反的和对称的，则R1R2也是自反的和对称

17、的。,证明：（1）,4.3关系的性质,例11：设A是集合，R1和R2是A上的关系，证明： (2)若R1和R2是传递的，则R1R2也是传递的。,证明：（2）,4.3关系的性质,五种性质在关系矩阵和关系图中的特点,4.3关系的性质,关系运算与关系性质,第四章 二元关系和函数,4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数,4.4关系的闭包,一、关系闭包的定义,设R是非空集合A上的关系，R的自反（对称或传递）闭包 是A上的关系R，使得R满足以下条件：,（1）R是自反的（对称或传递

18、的）,（2）RR,（3）对A上的任何包含R的自反（对称或传递）关系R 有R R,一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).,4.4关系的闭包,例1：设A=a,b,c,d，R=, 则R关系图如下图，则如何求A上关系R的闭包？,4.4关系的闭包,设R为非空集合A上的二元关系，则有,二、关系闭包的求法（关系运算方法）,；,；,。,4.4关系的闭包,例2：设A=a,b,c,d，R=,则R和r(R),s(R),t(R)的关系图如下图，则如何求A上关系R的闭包？,r(R)=,IA =,s(R)=, =,t(R)=, =, ,4.4关系的闭包,设R为非空集合A上的二元关系，

19、则有,三、关系闭包的求法（矩阵运算方法）,Mr=M+E；,Ms=M+M；,。,4.4关系的闭包,三、关系闭包的性质（1）,R是自反的当且仅当r(R)=R；,R是对称的当且仅当s(R)=R;,R是传递的当且仅当t(R)=R;,设R是非空集合A上的关系，则,4.4关系的闭包,三、关系闭包的性质（2）,r(R1) r(R2)；,s(R1) s(R2);,t(R1) t(R2);,设R1和R2是非空集合A上的关系，且R1R2，则,4.4关系的闭包,三、关系闭包的性质(3),；,；,。,设R是非空集合A上的关系，则,4.4关系的闭包,三、关系闭包的性质(4),r(s(R)=s(r(R)。,r(t(R)=

20、t(r(R)。,s(t(R)t(s(R)。,设R是非空集合A上的关系，则,第四章 二元关系和函数,4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数,4.5等价关系与偏序关系,一、等价关系的定义,设R为非空集合A上的关系，如果R是自反的、对称的、 传递的，则称R为A上的等价关系。对任何x,yA，如果 等价关系R，则记作xy。,4.5等价关系与偏序关系,例4：A=1,2,3,8,R=|x,yA xy(mod 3), 其中xy(mod 3)的含义就是x-y可以被3整除。求证：R 是

21、否为等价关系？,对任何正整数n可以定义整数集合Z上模n的等价关系： R=|x,yZ xy(mod n),4.5等价关系与偏序关系,例5:,在一群人的集合上，年龄相等的关系、朋友关系。,动物是按种属分类的，“具有相同种属”的关系。,集合上的恒等关系。,在同一平面上，三角形之间的相似关系。,在同一平面上，直线间的平行关系。,4.5等价关系与偏序关系,二、等价类的定义,设R是非空集合A上的等价关系，对任意的xA，令 xR=y|yA xRy, 则称xR为x关于R的等价类，简称为x的等价类，简记为x。,集合A=1,2,3,8,R=|x,yA xy(mod 3)中的 等价类有：1=4=7=1,4,7 2=

22、5=8=2,5,8 3=6=3,6,4.5等价关系与偏序关系,三、等价关系、等价类的性质,x，且xA;,若xRy，则x=y;,若R，则xy=;,;,4.5等价关系与偏序关系,四、商集的定义,设R是非空集合A上的等价关系，以R的不交的等价类为元素的 集合叫做A在R下的商集，记作A/R，即 A/R=xR|xA。,集合A=1,2,3,8,R=|x,yA xy(mod 3)，则 A在R下的商集是： A/R=1,4,7，2,5,8，3,6,4.5等价关系与偏序关系,例6:,非空集合A上的全域关系EA是A上的等价关系，对任意xA 有x= ,商集A/EA=,非空集合A上的恒等关系IA是A上的等价关系，对任意

23、xA 有x= ,商集A/EA= 。,4.5等价关系与偏序关系,五、划分的定义,设A是非空集合，如果存在一个A的子集族(P(A)满足以下 条件：,，,中任意两个元素不交，,中所有元素的并集等于A，,则称为A的一个划分，且称中的元素为划分块。,4.5等价关系与偏序关系,例7:考虑集合A=a,b,c,d的下列子集族，哪些是A的划分,a,b,c,d,a,b,c,d,a,b,c,a,d,a,b,c,d,a,b,c,集合A上的等价关系与集合A的划分是一一对应的。,4.5等价关系与偏序关系,例8:设A=1,2,3，求出A上所有的等价关系。,R1=,=EA,R2=,R3=,R4=,R5=,=IA,4.5等价关

24、系与偏序关系,五、偏序关系的定义,设R为非空集合A上的关系，如果R是自反的、反对称的和传递 的，则称R为A上的偏序关系，简称偏序，记作 。,例如：集合A=1,2,3 ,R=,则 关系R是偏序关系。 整数集合上的小于等于关系为偏序关系； 集合幂集上的子集关系为偏序关系。,4.5等价关系与偏序关系,六、可比和盖住的定义,设为偏序集，对于任意x,yA，如果x y或者y x成立 则称x与y是可比的，如果xy(即x y xy)，且不存在 zA使得xzy，则称y盖住x。,例如：集合A=1,2,3,4,5 , 是整除关系。那么，对于任意xA都有1 x，所以1和1，2，3，4，5都是可比的。但2和3不可比。又

25、12，且24所以4不能盖住1。,4.5等价关系与偏序关系,七、全序关系的定义,设为偏序集，对于任意x,yA，x和y都可比，则称 为A上的全序关系，且称为全序集。,例如：集合A=1,2,3,4,5 上的小于等于关系为全序关系，而整除 关系不是全序关系。,4.5等价关系与偏序关系,八、最小元、最大元、极小元和极大元,设为偏序集，BA.,若yB，使得x(xB yx)成立，则称y为B的最小元。,若yB，使得x(xB xy)成立，则称y为B的最大元。,若yB，使得x(xB xy)成立，则称y为B的极小元。,若yB，使得x(x B yx)成立，则称y为B的极大元。,4.5等价关系与偏序关系,例9:设偏序集

26、，求A的极小元，最小元，极大元，最大元,4.5等价关系与偏序关系,九、上界、下界、上确界和下确界,设为偏序集，BA.,若yA，使得x(xB xy)成立，则称y为B的上界。,若yA，使得x(xB yx)成立，则称y为B的下界。,若C=y|y为B的上界，则称C的最小元为B的最小上界或上确界。,若D=y|y为B的下界，则称D的最大元为B的最大下界或下确界。,第四章 二元关系和函数,4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数,4.6 函数的定义与性质,一、函数的定义（定义4.2

27、2）,设F为二元关系，若对任意的xdomF都存在唯一的yranF 使得xFy成立，则称F为函数。,例1：设 F1=, F2=, 判断他们是否为函数。,4.6 函数的定义与性质,二、集合A到B的函数（定义4.23）,设A，B为集合，如果函数f满足以下条件 （1）domf=A （2）ranfB 则称f是从A到B的函数，记作f:A-B。,例如： f:N-N，f(x)=2x g:N-N，g(x)=2,4.6 函数的定义与性质,三、集合A到B的函数（定义4.24）,所有从A到B的函数的集合记作BA，读作“B上A”。符号化 表示为 BAf|f:A-B,4.6 函数的定义与性质,f0=,例2：设A=1,2,

28、3,B=a,b,求,=f0,f1,f7，其中：,f1=,f2=,f3=,f4=,f5=,f6=,f7=,根据排列组合得知： |A|=m,|B|=n |BA|=nm,4.6 函数的定义与性质,设函数f:AB，AA，,四、函数的像（定义4.25）,令f(A)=f(x)|xA，称f(A)为A在f下的像。 特别地，当A=A时称f(A)=f(A)=ranf为函数的像。,xA, f(x)与f(A)的区别？,4.6 函数的定义与性质,例3：设f：NN，且,令A=0,1,B=2,那么有：,f(A)=f(0,1)=f(0),f(1)=0,2,4.6 函数的定义与性质,五、满射、单射和双射的定义（定义4.26）,若ranf=B，则称f:AB是满射的。,若对于任意x1,x2A,x1x2都有f(x1)f(x2)则f是单射的。,若f既是满射又是单射的，则称f是双射的。,设f:AB，,4.6