1、1第七章第七章:二元关系二元关系q主要内容主要内容l 有序对与笛卡儿积有序对与笛卡儿积l 二元关系的定义与表示法二元关系的定义与表示法l 关系的运算关系的运算l 关系的性质关系的性质l 关系的闭包关系的闭包l 等价关系与划分等价关系与划分l 偏序关系偏序关系q本章与后面各章的关系本章与后面各章的关系l 是函数的基础是函数的基础l 是图论的基础是图论的基础2第七章第七章:二元关系二元关系 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积3引言引言q关系是数学中最重要的概念之一关系是数学中最重要的概念之一v父子关系、师生关系父子关系、师生关系v等于、大于、小于关系等于、大于、小于关系v直线的平行、
2、垂直关系直线的平行、垂直关系q在计算机科学中有广泛应用在计算机科学中有广泛应用v人工智能人工智能v程序设计程序设计v数据库管理数据库管理关系数据库关系数据库47.1 有序对与笛卡儿积有序对与笛卡儿积q有序对（序偶）：有序对（序偶）：由两个元素由两个元素x，y(允许允许x=y)按给定顺序排列组成的二元组合按给定顺序排列组成的二元组合v符号化：符号化：vx为第一元素，为第一元素，y为第二元素为第二元素v例：平面直角坐标系中的一个点的坐标例：平面直角坐标系中的一个点的坐标v1,31,3和和3,13,1是表示平面上两个不同的点是表示平面上两个不同的点q =当且仅当当且仅当x=u，y=vv如果如果x y
3、，那么那么x，y y，x57.1 有序对与笛卡儿积有序对与笛卡儿积q例：已知例：已知=，求，求x,y解：根据有序对等式定义，只需求解方程式解：根据有序对等式定义，只需求解方程式 x+2=5+2=5 和和 2 2x+y=4=4 得到：得到：x=3,=3,y=-2=-267.1 有序对与笛卡儿积有序对与笛卡儿积AB：集合集合A中元素为第一元素，中元素为第一元素，集合集合B中元素为第二元素的有序对集中元素为第二元素的有序对集vAB=x A y Bq例：例：设集合设集合A=a，b，c，B=0，1，求求AB，BA，(AB)(BA)vAB=，vBA=，v(AB)(BA)=77.1 有序对与笛卡儿积有序对与
4、笛卡儿积q例：例：设集合设集合A=1，2，求求P(A)A解：解：P(A)=，11，22，11，22P(A)A =1，2，11，12，21，22，11，1287.1 有序对与笛卡儿积有序对与笛卡儿积v如如A，B均是有限集，均是有限集，A=m,B=n，则必有则必有 A B=mn97.1 有序对与笛卡儿积有序对与笛卡儿积q笛卡儿积的性质：笛卡儿积的性质：v对于任意集合对于任意集合A，A=，A=v一般不满足交换律，当一般不满足交换律，当A，B，A B时，时，A B B Av一般不满足结合律，即当一般不满足结合律，即当A，B，C均非空时，均非空时，(A B)C A(B C)107.1 有序对与笛卡儿积有
5、序对与笛卡儿积q笛卡儿积的性质（续）：笛卡儿积的性质（续）：v对任意三个集合对任意三个集合A，B，C有有 （1）A(B C)=(A B)(A C)（2）A(B C)=(A B)(A C)（3）(B C)A=(B A)(C A)（4）(B C)A=(B A)(C A)（5）A C B D AB CD117.1 有序对与笛卡儿积有序对与笛卡儿积q证明：证明：v对任意三个集合对任意三个集合A，B，C有有 A(B C)=(A B)(A C)证明：证明：A(B C)xA yB C xA (yB yC)(xA yB)(xA yC)A B A C (A B)(A C)127.1 有序对与笛卡儿积有序对与笛卡
6、儿积q例：例：设设A，B，C，D是任意集合，判断下列命是任意集合，判断下列命题是否正确？题是否正确？vA B A C B C 不正确不正确。取取A，B C，A B=A C=vA-(B C)=(A-B)(A-C)不正确。不正确。取取A=B=1，C=2，A-(B C)=1-=1 而而(A-B)(A-C)=1=137.1 有序对与笛卡儿积有序对与笛卡儿积q例：例：设设A，B，C，D是任意集合，判断下列命是任意集合，判断下列命题是否正确？题是否正确？vA=B，C=D A C B D 正确正确。v存在集合存在集合A使得使得A A A 正确。正确。取取A=时，时，A A A14第七章第七章:二元关系二元关
7、系 第二节：二元关系第二节：二元关系 157.2 二元关系二元关系q关系是指事物之间（个体之间）的相互联系关系是指事物之间（个体之间）的相互联系q二元关系二元关系R：满足下列条件之一的集合：满足下列条件之一的集合v集合非空，且它的元素都是有序对集合非空，且它的元素都是有序对v集合为空集集合为空集q定义：定义：A，B是集合，是集合，AB的子集叫做从的子集叫做从A到到B的一个二元关系的一个二元关系q例：例：A=0，1，B=1，2，3vR1=，R2=vR3=167.2 二元关系二元关系q几类特殊关系：几类特殊关系：v全域关系全域关系EAAAv恒等关系恒等关系IA|xA v空关系空关系177.2 二元
8、关系二元关系q例：例：A=0,1,2vEA=,v恒等关系恒等关系IA=,187.2 二元关系二元关系q包含关系包含关系vA是一个集合是一个集合,定义定义P(A)上的一个关系上的一个关系vR =u P(A)，v P(A)，且，且u vvA=a，b，P(A)=，a，b，AvR=，q例：例：A=2，3，4，5，6vR=a是是b的倍数的倍数vR=，197.2 二元关系二元关系q 关系表示方法关系表示方法v 枚举法（直观法、列举法）枚举法（直观法、列举法）xRy表示特定的序偶表示特定的序偶x，y Rv 谓词公式表示法（暗含法）谓词公式表示法（暗含法）v 关系矩阵表示法关系矩阵表示法v 关系图表示法关系图
9、表示法207.2 二元关系二元关系q 关系表示方法关系表示方法v 枚举法（直观法、列举法）枚举法（直观法、列举法）xRy表示特定的序偶表示特定的序偶x，y Rv 谓词公式表示法（暗含法）谓词公式表示法（暗含法）v 关系矩阵表示法关系矩阵表示法v 关系图表示法关系图表示法217.2 二元关系二元关系q 关系矩阵表示法关系矩阵表示法设集合设集合A=a1,am,B=b1,bn,R是是A到到B的关系的关系,则则R的关系矩阵是一个的关系矩阵是一个m m n n阶的矩阶的矩阵阵 MR R=(=(rijij)m m n n其中其中rijij=1,=1,当当 R ri j =0,=0,当当 R如果如果R是是A
10、上的关系时上的关系时,则其关系矩阵是一个方阵则其关系矩阵是一个方阵227.2 二元关系二元关系例：例：A=a,b,c,d,B=x,y,z,A=4，B=3,R=,则则MR是是4 4 3 3的矩阵的矩阵 1 0 11 0 1MR=0 1 00 1 0 0 0 1 0 0 1 0 1 0 0 1 0其中其中r1313=1 1表示表示 R,而而r2323=0,表示表示 R237.2 二元关系二元关系q 关系表示方法关系表示方法v 枚举法（直观法、列举法）枚举法（直观法、列举法）xRy表示特定的序偶表示特定的序偶x，y Rv 谓词公式表示法（暗含法）谓词公式表示法（暗含法）v 关系矩阵表示法关系矩阵表示
11、法v 关系图表示法关系图表示法247.2 二元关系二元关系q 关系图：关系图：A=a1,am，B=b1,bnv 结点：结点：m+nm+n个空心点分别表示个空心点分别表示a1 1,am m和和b1 1,bn nv 有向边：有向边：如果如果 R,则由结点则由结点ai i向结点向结点bj j通一条有向弧通一条有向弧,箭头指向箭头指向bj jv 自回路：自回路：R,则画一条以则画一条以ai i到自身的一到自身的一条有向弧条有向弧v 这样形成的图称为关系这样形成的图称为关系R的关系图的关系图257.2 二元关系二元关系q 例：例：A=2,3,4,5,6(1)(1)R1 1=a是是b的倍数的倍数(2)(2
12、)R2 2=(a-b)2 A 536425364226第七章第七章:二元关系二元关系 第三节：关系的运算第三节：关系的运算277.3 关系的运算关系的运算q二元关系的定义域和值域二元关系的定义域和值域v定义域：定义域：v值域：值域：q例例vX=1,2,3,4,5,6,Y=a,b,c,d,e,fvR=,vdomR=1,2,3,4vranR=a,b,c,d),(|RyxyxdomR),(|RyxxyranR287.3 关系的运算关系的运算q二元关系的逆关系二元关系的逆关系vR-1就是将就是将R中的所有有序对的两个元素交换次序中的所有有序对的两个元素交换次序成为成为R-1，故，故|R|=|R-1|q
13、说明说明vR-1 的关系矩阵是的关系矩阵是R的关系矩阵的转置，即的关系矩阵的转置，即 MR-1=(MR)TvR-1的关系图就是将的关系图就是将R的关系图中的弧改变方向即的关系图中的弧改变方向即可以可以,|,1RxyyxR297.3 关系的运算关系的运算q例：例：vR=，vR-1=，1 0 0 1 1 0 1 0 0 0 0 1 0 0 1 0 MR=1 1 0 0 MR-1=MRT=0 0 0 1 0 0 1 0 1 1 0 0 307.3 关系的运算关系的运算q例：例：vR=，vR-1=，dbcabcadR的关系图R-1的关系图317.3 关系的运算关系的运算q 关系的右复合关系的右复合q
14、例例v A=1,2,3,4,5,B=3,4,5,C=1,2,3v R=|x+y=6 =,v S=y-z=2 =,v R S=,),(|,GytFtxtyxGFo327.3 关系的运算关系的运算q 例（续）例（续）5435432132154321321从而从而R R S S的关系图的关系图337.3 关系的运算关系的运算q 例：例：A=a,b,c,d,ev R=,v S=,v R S=,v S R=,v R R=,v S S=q 注意：注意：R S S R 347.3 关系的运算关系的运算q 定义：定义：R是二元关系，是二元关系，A是集合是集合v R在在A上的限制上的限制 v A在在R下的像下的
15、像,|RAx yxRyxA)(ARranARARA357.3 关系的运算关系的运算q例：例：R=,求：求：R 1R 2,3R R 1R2,3R367.3 关系的运算关系的运算q优先顺序：优先顺序：l 逆运算优先于其他运算逆运算优先于其他运算l 关系运算优先于集合运算关系运算优先于集合运算l 没有规定优先权的运算以括号决定运算顺序没有规定优先权的运算以括号决定运算顺序377.3 关系的运算关系的运算q 定理：设定理：设F是任意的关系，则是任意的关系，则v(F-1)-1=Fv domF-1=ranF,ranF-1=domF387.3 关系的运算关系的运算q 定理：设定理：设F，G，H是任意的关系是
16、任意的关系(F G)H=F(G H)(F G)-1=G-1 F-1证明：证明：(F G)-1 F G t(F G)t(G-1 F-1)G-1 F-1397.3 关系的运算关系的运算q 例例v R=,v S=,v R S=,v(R S)-1=,v R-1=,v S-1=,v S-1 R-1=,407.3 关系的运算关系的运算q 定理定理:设设R为为A上关系，则上关系，则 R IAIA RRq 定理定理:v R(ST)=R SR Tv R(ST)R SR Tv(ST)X=S XT Xv(ST)X S XT X417.3 关系的运算关系的运算q 证明证明 R(ST)=R SR T R(ST)y(RS
17、T)y(R(ST)y(RS)(RT)y(RS)y(RT)R S R T R SR T427.3 关系的运算关系的运算q证明证明 R(ST)R SR T R(ST)t(RST)t(RST)t(RS)(RT)t(RS)t(RT)R SR T R SR T437.3 关系的运算关系的运算q 定理定理:v R(AB)=R AR Bv RAB=RARBv R(AB)=R AR Bv RAB RARB447.3 关系的运算关系的运算q 定理定理:RAB RARB证明：证明：yRAB x(RxAB)x(RxAxB)x(RxA)(R xB)x(RxA)x(R xB)yRAyRB yRARB457.3 关系的运
18、算关系的运算q R的的n次幂次幂v 记为记为Rnv R0=Av Rn+1=Rn Rq 定理定理:设设R是集合是集合A上的关系，上的关系，m,nNv Rm Rn=Rm+nv(Rm)n=Rmn证明思路：使用归纳法并利用复合关系的结合律证明思路：使用归纳法并利用复合关系的结合律467.3 关系的运算关系的运算q 例例R=,v R0=,v R1=Rv R2=,v R3=R2 R =,v R4=R3 R =,v R5=R4 R =,477.3 关系的运算关系的运算从关系图来看关系的从关系图来看关系的n次幂次幂 R：1 2 3 4 5R2就是所有在就是所有在R中通过中通过二条弧二条弧连接的点，则在连接的点
19、，则在R2这两点间直接有条弧。这两点间直接有条弧。1 2 3 4 5R3,R4487.3 关系的运算关系的运算q 定理：定理：R是是A上的二元关系，若存在自然数上的二元关系，若存在自然数s和和t，且，且st，使，使Rs=Rt，则，则 对所有的对所有的k0，则，则Rs+k=Rt+k 对所有的对所有的k,i0，则有，则有Rs+kp+i=Rs+ip=t-s 设设S=R0,R1,R2,Rt-1，则，则R的每一次幂都的每一次幂都是是S的元素，即对任意的元素，即对任意qN,RqS 497.3 关系的运算关系的运算q 定理：定理：R是是A上的二元关系，若存在自然数上的二元关系，若存在自然数s和和t，且，且s
20、t，使，使Rs=Rt 对所有的对所有的k0，则，则Rs+k=Rt+k 对所有的对所有的k,i0，则有，则有Rs+kp+i=Rs+ip=t-s 设设S=R0,R1,R2,Rt-1，则，则R的每一次幂是的每一次幂是S的元素，即对任意的元素，即对任意qN,RqS 507.3 关系的运算关系的运算证明：对证明：对k进行归纳。进行归纳。k=0时时Rs+kp+i=Rs+i显然成立显然成立假设假设Rs+kp+i=Rs+i，这里，这里p=t-s，那么，那么Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+i Rp=Rs+i Rp=Rs+p+i=Rs+t-s+i=Rt+i=Rs+i517.3 关系的运算关
21、系的运算q 定理：定理：R是是A上的二元关系，若存在自然数上的二元关系，若存在自然数s和和t，且，且st，使，使Rs=Rt 对所有的对所有的k0，则，则Rs+k=Rt+k 对所有的对所有的k,i0，则有，则有Rs+kp+i=Rs+ip=t-s 设设S=R0,R1,R2,Rt-1，则，则R的每一次幂是的每一次幂是S的元素，即对任意的元素，即对任意qN,RqS 527.3 关系的运算关系的运算证明：若证明：若qt，则，则RqS。若若qt，则存在自然数，则存在自然数k，i使得使得 q=s+kp+i其中其中0 ip-1，所以，所以 Rq=Rs+kp+i=Rs+i由于由于0 ip-1 s+i s+p-1
22、=s+t-s-1=t-153第七章第七章:二元关系二元关系 第四节：关系的性质第四节：关系的性质547.4 关系的性质关系的性质q自反性自反性v aA，有，有R，则，则R为为A上的上的自反自反关系关系q反自反性反自反性v aA，有，有 R，R为为A上的上的反自反反自反关系关系q例例 A=a,b,cvR1=,vR2=,vR3=,557.4 关系的性质关系的性质q例：例：R是是I+上的整除关系，则上的整除关系，则R具有自反性具有自反性v证明：证明：xI+，x能整除能整除x，vR，R具有自反性具有自反性q例：例：R是是I上的同余关系，则上的同余关系，则R具有自反性具有自反性v证明：证明：xI，(x-
23、x)/k=0I,vx与与x同余同余RR具有自反性具有自反性q其它其它，关系，均是自反关系关系，均是自反关系567.4 关系的性质关系的性质q例：例：N上的互质关系是反自反关系上的互质关系是反自反关系v证明：证明：xN，x与与x是不互质的，是不互质的，v R，R具有反自反关系具有反自反关系q实数上的实数上的,关系关系,均是反自反关系均是反自反关系577.4 关系的性质关系的性质q关系矩阵的特点？关系矩阵的特点？v自反关系的关系矩阵的对角元素均为自反关系的关系矩阵的对角元素均为1v反自反关系的关系矩阵的对角元素均为反自反关系的关系矩阵的对角元素均为0q关系图的特点？关系图的特点？v自反关系的关系图
24、中每个顶点都有环自反关系的关系图中每个顶点都有环v反自反关系的关系图中每个顶点都没有环反自反关系的关系图中每个顶点都没有环q定理：定理：R是是A上的关系，则：上的关系，则：vR是自反关系的充要条件是是自反关系的充要条件是IA RvR是反自反关系的充要条件是是反自反关系的充要条件是RIA=587.4 关系的性质关系的性质q对称关系对称关系Rv a,bA,如果如果R,则必有则必有R q例例vR1,vR1是对称的是对称的vR2,vR2是对称的是对称的vR3,vR3不是对称的不是对称的 597.4 关系的性质关系的性质q关系矩阵特点？关系矩阵特点？v对称关系的关系矩阵是对称矩阵对称关系的关系矩阵是对称
25、矩阵q关系图特点？关系图特点？v如果两个顶点之间有边，一定是一对方向相反的如果两个顶点之间有边，一定是一对方向相反的边（无单边）边（无单边）q定理：定理：R在在A上对称当且仅当上对称当且仅当R=R-1证明：证明：必要性必要性 R R R-1充分性充分性 R R-1 R607.4 关系的性质关系的性质q反对称关系反对称关系Rv a,bA,如果如果R且且R,则必有则必有abv a,bA,如果如果ab,R,则必有则必有 Rq例例:Aa,b,cvR,vS,vT,vR,S是反对称的是反对称的,T不是反对称的不是反对称的617.4 关系的性质关系的性质q例例:实数集合上实数集合上关系是反对称关系关系是反对
26、称关系v x,y实数集实数集,如如xy,且且xy,则则yx不成立不成立q例：例：,关系关系,均是反对称关系均是反对称关系q反对称关系矩阵和关系图特点？反对称关系矩阵和关系图特点？v若若rij=1，且，且ij，则则rji=0v如果两个顶点之间有边，一定是一条有向边（无如果两个顶点之间有边，一定是一条有向边（无双向边）双向边）q定理：定理：R在在A上反对称当且仅当上反对称当且仅当RR-1 IA627.4 关系的性质关系的性质q传递关系传递关系v a,b,cA,如果如果R,R,必有必有Rq例例vR1,v是传递关系是传递关系vR2,v是传递关系是传递关系vR3,v不是传递关系不是传递关系637.4 关
27、系的性质关系的性质q例例:整除关系整除关系DI是是I上的传递关系上的传递关系v x,y,zI,如如DI,DI,即即x能整除能整除y,且且y能整除能整除z,则必有则必有x能整除能整除z,DIq例例:P(A)上的包含关系上的包含关系 具有传递性具有传递性v若若u v,v w,则必有则必有u wq例例:实数集上的实数集上的关系具有传递性关系具有传递性v若若xy,yz必有必有xz647.4 关系的性质关系的性质q传递关系关系图特点？传递关系关系图特点？v如果结点如果结点a能通过有向弧组成的有向路径通向结能通过有向弧组成的有向路径通向结点点x,则则a必须有有向弧直接指向必须有有向弧直接指向x,否则否则R
28、就不是就不是传递的传递的q例：例：R=,q定理：定理：R在在A上传递当且仅当上传递当且仅当R R Rdcba657.4 关系的性质关系的性质自自 反：反：反自反：反自反：对对 称：称：反对称：反对称：传传 递：递：)(xRxXxx xRx)Xx(x )(yRxxRyXyXxyx )(yxyRxxRyXyXxyx )(xRzyRzxRyXzXyXxzyx 667.4 关系的性质关系的性质q 设设A是集合，是集合，R1和和R2是是A上的关系上的关系 若若R1，R2是自反和对称的，则是自反和对称的，则R1 R2也是自反也是自反的和对称的的和对称的 若若R1和和R2是传递的，则是传递的，则R1 R2也
29、是传递的也是传递的677.4 关系的性质关系的性质q 设设A是集合，是集合，R1和和R2是是A上的关系上的关系若若R1，R2是自反的和对称的，则是自反的和对称的，则R1 R2也是自反也是自反的和对称的的和对称的证明：证明：R1，R2是自反的是自反的 IA R1，IA R2所以所以IA R1 R2R1，R2是对称的是对称的 R1=R1-1和和R2=R2-1所以所以(R1 R2)-1=R1-1 R2-1=R1 R2687.4 关系的性质关系的性质q例：例：X=1,2,3，判断关系的性质，判断关系的性质vR1=,n R2=,n反对称反对称n反自反反自反n反对称反对称n可传递可传递697.4 关系的性
30、质关系的性质qR3=,qR4=Ex n 自反，对称，可传递的自反，对称，可传递的 n自反，对称，反对称，可传递的自反，对称，反对称，可传递的707.4 关系的性质关系的性质qX=1,2,3,R5=n反自反的，对称的，反对称的，可传递的反自反的，对称的，反对称的，可传递的q若若X=，X上的空关系上的空关系n自反的，反自反的，对称的，反对称的，可传递自反的，反自反的，对称的，反对称的，可传递的的71第七章第七章:二元关系二元关系 第五节：关系的闭包第五节：关系的闭包727.5 关系的闭包关系的闭包q定义：定义：R是非空集合是非空集合A上的关系上的关系,若若A上另外有上另外有一个关系一个关系R满足如
31、下三条：满足如下三条：vR是是自反的自反的(对称的对称的，传递的传递的）vR RvA上任何一个满足以上两条的关系上任何一个满足以上两条的关系R”，均有，均有R R”，称关系称关系R为为R的的自反自反(对称对称,传递传递)闭包闭包,记作记作r(R)(s(R),t(R)737.5 关系的闭包关系的闭包q解释解释vR是在是在R的基础上添加有序对的基础上添加有序对v添加元素的目的是使添加元素的目的是使R具有自反性具有自反性(对称性对称性,传递传递性性)v添加后使之具有自反性添加后使之具有自反性(对称性对称性,传递性传递性)的所有关的所有关系中系中R是最小的一个是最小的一个747.5 关系的闭包关系的闭
32、包q例例A=a,b,c，R=,v自反闭包自反闭包r(R)v,v对称闭包对称闭包s(R)v,v传递闭包传递闭包t(R)v,r(Rr(R)a b ccbaacbcbabac757.5 关系的闭包关系的闭包q定理：定理：R是非空集合是非空集合A上的关系上的关系,则则r(R)=RA证明证明:R RA，RA是自反的是自反的设设R”满足满足R R”,R”是自反的是自反的 RA则则 R或或A 如如 R,由由R R”知知 R”如如A,由由R”的自反性知的自反性知 R”均有均有 R”RA R”767.5 关系的闭包关系的闭包q定理定理:设设R是非空集是非空集A的关系的关系,则则s(R)=R R-1 证明证明:v
33、R R R-1满足定义第满足定义第2条条v R R-1 R R-1 R-1 R R R-1 R R-1是对称的是对称的777.5 关系的闭包关系的闭包v如如R R”,且且R”是对称的是对称的 R R-1 R或或 R-1如如 R,由由R R”,则则 R”如如 R-1,则则 R,则则 R”因因R”对称对称 R”,R R-1 R”满足定义第满足定义第3条条787.5 关系的闭包关系的闭包q例例:设设A=1,2,3,A上的关系上的关系R如图如图,求求r(R),s(R)解解:R=,r(R)=RA =,s(R)=R R-1 =,1 2 3797.5 关系的闭包关系的闭包定理定理:设设R是非空集合是非空集合
34、A上的关系上的关系,则则t(R)=R1 R2 证明：证明：首先证明首先证明R1 R2 t(R)，使用归纳法。，使用归纳法。n=1，显然，显然R1=R t(R)假设假设Rk t(R)，对任意，对任意有有 Rk+1=Rk R1 t(Rk R1)t(t(R)t(R)t(R)其次，其次，t(R)R1 R2 即证即证R1 R2 传递传递推论推论:设设A是非空有限集，是非空有限集，R是集合是集合A上的二元关系，上的二元关系，则存在正整数则存在正整数n，使得，使得t(R)=R R2 Rn807.5 关系的闭包关系的闭包q例例 A=a,b,c,dvR=,vS=,求求t(R),t(S)q解解:R2=,R3=t(
35、R)=R,S2=,S3=,S4=t(S)=S,a b c dR a b c d S817.5 关系的闭包关系的闭包q给定关系给定关系R，r(R)，s(R)，t(R)的关系矩阵的关系矩阵分别为分别为M，Mr，Ms，Mt，那么：，那么：vMr=M+EvMs=M+MvMt=M+M2+M3+827.5 关系的闭包关系的闭包q关系图分别为关系图分别为G，Gr，Gs，Gt，那么：，那么：v考察考察G的每个顶点，如果没有环就加上一个环的每个顶点，如果没有环就加上一个环，最终得到的是，最终得到的是Grv考察考察G的每一条边，如果有一条从的每一条边，如果有一条从xi到到xj的单的单向边，则在向边，则在G中加一条
36、中加一条xj到到xi的反方向边，最的反方向边，最终得到终得到Gsv考察考察G的每个顶点的每个顶点xi，找出从，找出从xi出发的所有出发的所有2步，步，3步，步，n步长的路径。设路径的终点步长的路径。设路径的终点为为xj1，xj2，xjk。如果没有从。如果没有从xi到到xjl的边，就加上这条边，最终得到的边，就加上这条边，最终得到Gt837.5 关系的闭包关系的闭包q定理：设定理：设A是一集合，是一集合，R是是A上的二元关系，上的二元关系，则有：则有：vR是自反的当且仅当是自反的当且仅当r(R)RvR是对称的当且仅当是对称的当且仅当s(R)RvR是可传递的当且仅当是可传递的当且仅当t(R)RqR
37、是自反的当且仅当是自反的当且仅当r(R)R证明：证明：R r(R)。由自反闭包定义，。由自反闭包定义，r(R)R。847.5 关系的闭包关系的闭包q定理：设定理：设A是集合，是集合，R1和和R2是是A上的二元关系上的二元关系，R1 R2，则有：，则有：vr(R1)r(R2)vs(R1)s(R2)vt(R1)t(R2)qr(R1)r(R2)证明：证明：r(R1)=R1A，r(R2)=R2A857.5 关系的闭包关系的闭包q定理：设定理：设X是一集合，是一集合，R是是X上的二元关系，上的二元关系，则有：则有：v若若R是自反的，则是自反的，则s(R),t(R)也自反也自反v若若R是对称的，则是对称的
38、，则r(R),t(R)也对称也对称v若若R是可传递的，则是可传递的，则r(R)也可传递也可传递867.5 关系的闭包关系的闭包q定理：设定理：设X是一集合，是一集合，R是是X上的二元关系，上的二元关系，则有：则有：v若若R是对称的，则是对称的，则t(R)也对称也对称证明：证明：归纳法证明若归纳法证明若R是对称，则是对称，则Rn也对称也对称n=1，显然成立，显然成立假设假设Rn对称，对任意对称，对任意 Rn+1 t(Rn R)t(Rn R)R Rn Rn+1 877.5 关系的闭包关系的闭包q定理：设定理：设X是一集合，是一集合，R是是X上的二元关系，上的二元关系，则有：则有：v若若R是对称的，
39、则是对称的，则t(R)也对称也对称证明：证明：R Rn Rn+1 任取任取，有，有 t(R)n(Rn)n(Rn)t(R)887.5 关系的闭包关系的闭包q若若R是传递的，是传递的，s(R)不一定是传递的不一定是传递的v反例：反例：R=,，R是传递的是传递的 s(R)=,s(R)不是传递的不是传递的89第七章第七章:二元关系二元关系 第六节：等价关系与划分第六节：等价关系与划分907.6 等价关系与划分等价关系与划分q等价关系：非空集合等价关系：非空集合A上的关系，满足：上的关系，满足：v自反的自反的v对称的对称的v可传递的可传递的q例例v实数实数(或或I、N集上集上)集合上的集合上的“=”关系
40、关系v全集上集合的相等关系全集上集合的相等关系v命题集合上的命题等价关系命题集合上的命题等价关系917.6 等价关系与划分等价关系与划分例：设例：设A=1,2,3,4,5,6,7R=|x,yA(x-y)可被可被3整除整除试证明试证明R是等价关系是等价关系解：解：(1)R=，927.6 等价关系与划分等价关系与划分(2)R的关系矩阵的关系矩阵1001001001001001001001001001001001001001001001001RMn R满足自反、对称和可传递的满足自反、对称和可传递的937.6 等价关系与划分等价关系与划分q等价类：等价类：设设R是非空是非空A集合上的等价关系，对集合
41、上的等价关系，对于任何于任何xA，令：，令：vxR=y|yA xRyvxR是由是由xA生成的生成的R等价类等价类vx为等价类为等价类xR的表示元素的表示元素947.6 等价关系与划分等价关系与划分q讨论讨论v等价类等价类xR是一个集合，是一个集合，xR A(xR是是A的子集的子集)vxR中的元素是在中的元素是在A中，所有与中，所有与x具有等价关系具有等价关系R的元素所组成的集合的元素所组成的集合v在等价关系中的关系图中，一个最大连通子图中在等价关系中的关系图中，一个最大连通子图中的点就是一个等价类的点就是一个等价类957.6 等价关系与划分等价关系与划分q例：例：vA=a,b,c,dvR=，v
42、aR=a,b=bR vcR=c,d=dR967.6 等价关系与划分等价关系与划分q例：设例：设A=NvR=|xAyA(x-y)可被可被3整除整除q等价类等价类v0R=0，3，6，9 v1R=1，4，7，10 v2R=2，5，8，11977.6 等价关系与划分等价关系与划分q定理定理 设设A是一个集合，是一个集合，R是是A上的等价关系，上的等价关系，xRy当且仅当当且仅当x=yq证明：证明：v充分性，因为充分性，因为xx=y,即即xy，所以，所以xRy。v必要性，已知必要性，已知xRy，考虑，考虑x的任意元素的任意元素z，有，有zRx。根据。根据R的传递性，有的传递性，有zRy，因此，因此zy。
43、证明。证明x y。类似可证明。类似可证明y x，所以，所以x=y987.6 等价关系与划分等价关系与划分q定理：定理：设设A是一个集合，是一个集合，R是是A上的等价关系，上的等价关系，v对于所有对于所有x,yA，或者，或者x=y，或者，或者 x y=证明：证明：只需证明如果只需证明如果xRy，则，则xy=反证法：反证法：假设假设xy，则，则 z xy R R R(矛盾矛盾!)997.6 等价关系与划分等价关系与划分q定理：定理：设设R是集合是集合A上的等价关系，则上的等价关系，则 A=x|x A证明：证明：首先易证首先易证 x|x A A 其次，对任意其次，对任意y A y A y y y A
44、 y x|x A 所以：所以：A x|x A1007.6 等价关系与划分等价关系与划分q商集商集：R是是A上的等价关系，上的等价关系，vR的所有等价类构成的集合的所有等价类构成的集合v记为记为A/R：xR|x Aq例：例：A为全班同学的集合，为全班同学的集合，|A|=n，(nN)v按指纹的相同关系按指纹的相同关系R1是一个等价关系是一个等价关系vA/R1=x1R1,xnR1 v同姓关系同姓关系R2是一等价关系是一等价关系vA/R2=张张，李李，1017.6 等价关系与划分等价关系与划分q 划分：划分：给定一非空集合给定一非空集合A，A的一个划分为非的一个划分为非空子集族空子集族S=A1,A2,
45、Am，满足：，满足：S x y(x,y S xyx y=)A1 A2 Am=A1027.6 等价关系与划分等价关系与划分q例：例：A=a,b,c,下列哪些下列哪些Ai为为A的一个划分？的一个划分？vA1=a,b,c vA2=a,c,bvA3=a,a,b,cvA4=a,b,c,vA5=a,a,b,c1037.6 等价关系与划分等价关系与划分q等价关系与划分有一一对应关系等价关系与划分有一一对应关系q划分到等价关系转化划分到等价关系转化：A是一非空集合，是一非空集合，S是是A的一个划分，下述关系必定是一个等价关系的一个划分，下述关系必定是一个等价关系vR=|x,y A x,y在在S的同一划分的同一
46、划分q等价关系到划分的转化：等价关系到划分的转化：设设A是非空集合，是非空集合，R是是A上的等价关系。上的等价关系。R的商集是的商集是A的划分的划分1047.6 等价关系与划分等价关系与划分q例：例：A=a,b,c,d,evS=a,b,c,d,e 对应划分对应划分S的等价关系为的等价关系为 vR=a,ba,bccd,ed,e=,105第七章第七章:二元关系二元关系 第七节：偏序关系第七节：偏序关系1067.7 偏序偏序关系关系q次序在现实生活中常见：次序在现实生活中常见：v小于，包含小于，包含等等q研究序理论的动机：研究序理论的动机：v研究一般次序关系研究一般次序关系v推导出一般序关系的性质推
47、导出一般序关系的性质v这些关系可以应用于所有特定的序关系这些关系可以应用于所有特定的序关系1077.7 偏序偏序关系关系q偏序关系偏序关系R(记作记作)v自反性自反性:aA，有，有Rv反对称性反对称性:a,bR,如果如果R且且R,则必有则必有abv传递性传递性:a,b,cA,如果如果R,R,必有必有Rq例例:偏序关系偏序关系vAa,b,cvR,abc1087.7 偏序偏序关系关系q 例：例：A是非零自然数集是非零自然数集,是是A上的整除关系上的整除关系。v aA,a能整除能整除a 具有自反性具有自反性v a,bA,如如a能整除能整除b,且且b能整除能整除a,则则ab 具有反对称性具有反对称性
48、v a,b,cA,如如a能整除能整除b,b能整除能整除c,则则a能整除能整除c,具有传递性具有传递性q 是是A上的偏序关系上的偏序关系1097.7 偏序偏序关系关系q小于小于：a ba b abq可比：可比：a与与b可比可比 a b b av可比不同于等于可比不同于等于q例：例：A=1，2，3，是是A上的整除关系上的整除关系v1，3可比可比q全序关系全序关系R：R是是A上的偏序关系上的偏序关系,满足：满足：v a,bA,a与与b可比可比 q例：实数上的例：实数上的,关系是全序关系关系是全序关系1107.7 偏序偏序关系关系q哈斯图哈斯图v得名于德国数学家得名于德国数学家Helmut Hasse
49、v用来表示有限偏序集的一种数学图表用来表示有限偏序集的一种数学图表 偏序集：偏序集：1117.7 偏序偏序关系关系q 覆盖：覆盖：，b覆盖覆盖a如果如果v a b，不存在，不存在c A，a c bq 哈斯图思路：哈斯图思路：所有结点的自回路均省略所有结点的自回路均省略 省略所有弧上的箭头省略所有弧上的箭头,适当排列适当排列A中元素的位置中元素的位置,如如a b,则则a画在画在b的下方的下方 如如a b,b c,则必有则必有a c,a到到b有边有边,b到到c有有边边,则则a到到c的无向弧省略的无向弧省略条件条件2，3等于说如果等于说如果b覆盖覆盖a,则画一条从则画一条从a到到b的弧线，否则不画的
50、弧线，否则不画1127.7 偏序偏序关系关系q例：画出下列偏序集的哈斯图。例：画出下列偏序集的哈斯图。vvR整除整除=,1253461137.7 偏序偏序关系关系q例：例：A=a,b,c,包含关系包含关系R是是P(A)上的偏上的偏序关系序关系,哈斯图如下哈斯图如下:vP(A)=,a,b,c,a,b,a,c,b,c,a,b,c aa a,ba,b bb a,b,ca,b,c b,cb,c cc a,ca,c 1147.7 偏序偏序关系关系q最小最小(大大)元：元：设设是偏序集是偏序集,集合集合B Av最大元最大元bB：aB,均有均有a bv最小元最小元bB：aB,均有均有b aq说明说明v如果如
