1第七章第七章: 二元关系二元关系q主要内容主要内容l有序对与笛卡儿积有序对与笛卡儿积l二元关系的定义与表示法二元关系的定义与表示法l关系的运算关系的运算l关系的性质关系的性质l关系的闭包关系的闭包l等价关系与划分等价关系与划分l偏序关系偏序关系q本章与后面各章的关系本章与后面各章的关系l是函数的基础是函数的基础l是图论的基础是图论的基础2第七章第七章: 二元关系二元关系 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积3引言引言q关系是数学中最重要的概念之一关系是数学中最重要的概念之一v父子关系、师生关系父子关系、师生关系v等于、大于、小于关系等于、大于、小于关系v直线的平行、垂直关系直线的平行、垂直关系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，那么那么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 有序对与笛卡儿积有序对与笛卡儿积q笛笛笛笛卡卡卡卡尔尔尔尔积积积积A B：集集合合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 有序对与笛卡儿积有序对与笛卡儿积q例：例：设集合设集合A=1，2，求求P(A) A解：解：P(A)=，11，22，11，22P(A)A = 1， 2，11，12，21，22， 11，1287.1 有序对与笛卡儿积有序对与笛卡儿积q说明：说明：说明：说明：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 有序对与笛卡儿积有序对与笛卡儿积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 有序对与笛卡儿积有序对与笛卡儿积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第七章第七章: 二元关系二元关系 第二节：二元关系第二节：二元关系 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|x A v空关系空关系177.2 二元关系二元关系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关系图表示法关系图表示法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上的关系时上的关系时, ,则其关系矩阵是一个方阵则其关系矩阵是一个方阵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关系矩阵表示法关系矩阵表示法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)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,d287.3 关系的运算关系的运算q二元关系的逆关系二元关系的逆关系vR-1就是将就是将R中的所有有序对的两个元素交换次序中的所有有序对的两个元素交换次序成为成为R-1 ，故，故|R|=| R-1 | q说明说明vR-1 的关系矩阵是的关系矩阵是R的关系矩阵的转置，即的关系矩阵的转置，即 MR-1=(MR)TvR-1的关系图就是将的关系图就是将R的关系图中的弧改变方向即的关系图中的弧改变方向即可以可以297.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例例vA=1,2,3,4,5,B=3,4,5,C=1,2,3vR=|x+y=6 =,vS= y-z=2 =,vR S=,327.3 关系的运算关系的运算q例（续）例（续）5435432132154321321从而从而R R S S的关系图的关系图337.3 关系的运算关系的运算q例：例： A=a,b,c,d,evR=,vS=,vR S=,vS R=,vR R=,vS S=q注意：注意：R S S R 347.3 关系的运算关系的运算q定义：定义：R是二元关系，是二元关系，A是集合是集合vR在在A上的限制上的限制 vA在在R下的像下的像ARA357.3 关系的运算关系的运算q例：例：R = , , , , , 求：求： 367.3 关系的运算关系的运算q优先顺序：优先顺序：l逆运算优先于其他运算逆运算优先于其他运算l关系运算优先于集合运算关系运算优先于集合运算l没有规定优先权的运算以括号决定运算顺序没有规定优先权的运算以括号决定运算顺序377.3 关系的运算关系的运算q定理：设定理：设F是任意的关系，则是任意的关系，则v(F-1)-1=FvdomF-1 =ranF, ranF-1 =domF387.3 关系的运算关系的运算q定理：设定理：设F，G，H是任意的关系是任意的关系(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例例vR=,vS=,vR S=, ,v(R S)-1=, ,vR-1=, ,vS-1=, vS-1 R-1=, ,407.3 关系的运算关系的运算q定理定理: 设设R为为A上关系，则上关系，则 R IAIA RRq定理定理:vR (S T)=R S R TvR (ST) R SR Tv(S T) X=S X T Xv(ST) X S XT X417.3 关系的运算关系的运算q证明证明 R (S T)=R S R T R (S T) y( R S T) y( R ( S T) y( R S) ( R T) y( R S) y( R T) R S R T R S R T427.3 关系的运算关系的运算q证明证明 R (ST) R SR T R (ST) t ( R ST) t ( R S T) t ( R S) ( R T) t ( R S) t ( R T) R S R T R SR T437.3 关系的运算关系的运算q定理定理:vR (A B) = R A R BvRA B = RA RBvR (AB) = R AR BvRAB RARB447.3 关系的运算关系的运算q定理定理: RAB RARB证明：证明： y RAB x( R x AB) x( R x A x B) x( R x A) ( R x B) x( R x A) x( R x B)y RA y RB y RARB457.3 关系的运算关系的运算qR的的n次幂次幂v记为记为RnvR0 = AvRn+1=Rn Rq定理定理: 设设R是集合是集合A上的关系，上的关系，m,n NvRm Rn=Rm+nv(Rm)n=Rmn证明思路：使用归纳法并利用复合关系的结合律证明思路：使用归纳法并利用复合关系的结合律467.3 关系的运算关系的运算q例例R=,vR0= ,vR1=RvR2=,vR3=R2 R =,vR4=R3 R =,vR5=R4 R =,477.3 关系的运算关系的运算从关系图来看关系的从关系图来看关系的n次幂次幂 R： 1 2 3 4 5R2就是所有在就是所有在R中通过中通过二条弧二条弧连接的点，则在连接的点，则在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的元素，即对任意的元素，即对任意q N, Rq S 497.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的元素，即对任意的元素，即对任意q N, Rq S 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 关系的运算关系的运算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的元素，即对任意的元素，即对任意q N, Rq S 527.3 关系的运算关系的运算证明：若证明：若qt，则，则Rq S 。若若qt，则存在自然数，则存在自然数k，i使得使得 q=s+kp+i其中其中0 ip-1，所以，所以 Rq= Rs+kp+i = Rs+i由于由于0 ip-1 s+i s+p-1 = s+t-s-1=t-153第七章第七章: 二元关系二元关系 第四节：关系的性质第四节：关系的性质547.4 关系的性质关系的性质q自反性自反性v a A，有，有 R，则，则R为为A上的上的自反自反关系关系q反自反性反自反性v a A，有，有 R，R为为A上的上的反自反反自反关系关系q例例 A=a,b,cvR1=,vR2=,vR3=,557.4 关系的性质关系的性质q例：例：R是是I+上的整除关系，则上的整除关系，则R具有自反性具有自反性v证明：证明： x I+，x能整除能整除x，v R，R具有自反性具有自反性q例：例：R是是I上的同余关系，则上的同余关系，则R具有自反性具有自反性v证明：证明： x I，(x-x)/k=0 I, v x与与x同余同余 RR具有自反性具有自反性q其它其它，关系，均是自反关系关系，均是自反关系567.4 关系的性质关系的性质q例：例：N上的互质关系是反自反关系上的互质关系是反自反关系v证明：证明： x N，x与与x是不互质的，是不互质的，v R，R具有反自反关系具有反自反关系q实数上的实数上的,关系关系,均是反自反关系均是反自反关系577.4 关系的性质关系的性质q关系矩阵的特点？关系矩阵的特点？v自反关系的关系矩阵的对角元素均为自反关系的关系矩阵的对角元素均为1v反自反关系的关系矩阵的对角元素均为反自反关系的关系矩阵的对角元素均为0q关系图的特点？关系图的特点？v自反关系的关系图中每个顶点都有环自反关系的关系图中每个顶点都有环v反自反关系的关系图中每个顶点都没有环反自反关系的关系图中每个顶点都没有环q定理：定理：R是是A上的关系，则：上的关系，则：vR是自反关系的充要条件是是自反关系的充要条件是IA RvR是反自反关系的充要条件是是反自反关系的充要条件是RIA=587.4 关系的性质关系的性质q对称关系对称关系Rv a,b A,如果如果 R,则必有则必有 R q例例vR1,vR1是对称的是对称的vR2,vR2是对称的是对称的vR3,vR3不是对称的不是对称的 597.4 关系的性质关系的性质q关系矩阵特点？关系矩阵特点？v对称关系的关系矩阵是对称矩阵对称关系的关系矩阵是对称矩阵q关系图特点？关系图特点？v如果两个顶点之间有边，一定是一对方向相反的如果两个顶点之间有边，一定是一对方向相反的边（无单边）边（无单边）q定理：定理： R在在A上对称当且仅当上对称当且仅当R=R-1证明：证明：必要性必要性 R R R-1充分性充分性 R R-1 R607.4 关系的性质关系的性质q反对称关系反对称关系Rv a,b A,如果如果 R且且 R,则必有则必有abv a,b A,如果如果ab, R,则必有则必有 Rq例例: Aa,b,cvR,vS,vT,vR,S是反对称的是反对称的,T不是反对称的不是反对称的617.4 关系的性质关系的性质q例例: 实数集合上实数集合上关系是反对称关系关系是反对称关系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,c A,如果如果 R, R, 必有必有 Rq例例vR1,v是传递关系是传递关系vR2,v是传递关系是传递关系vR3,v不是传递关系不是传递关系637.4 关系的性质关系的性质q例例:整除关系整除关系DI是是I上的传递关系上的传递关系v x,y,z I,如如 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就不是传就不是传递的递的q例：例：R=,q定理：定理：R在在A上传递当且仅当上传递当且仅当R R Rdcba657.4 关系的性质关系的性质自自 反：反：反自反：反自反： 对对 称：称：反对称：反对称：传传 递：递： 667.4 关系的性质关系的性质q设设A是集合，是集合，R1和和R2是是A上的关系上的关系若若R1，R2是自反和对称的，则是自反和对称的，则R1 R2也是自反也是自反的和对称的的和对称的若若R1和和R2是传递的，则是传递的，则R1 R2也是传递的也是传递的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 关系的性质关系的性质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满足如下三条：满足如下三条：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 关系的闭包关系的闭包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 证明证明:vR 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是非空集合是非空集合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(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中加一条中加一条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是自反的当且仅当是自反的当且仅当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是对称的，则是对称的，则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是对称的，则是对称的，则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集上集上)集合上的集合上的“=”关系关系v全集上集合的相等关系全集上集合的相等关系v命题集合上的命题等价关系命题集合上的命题等价关系917.6 等价关系与划分等价关系与划分例：设例：设A=1,2,3,4,5,6,7R=|x,y A (x-y)可被可被3整除整除试证明试证明R是等价关系是等价关系解解 ： (1)R=， ， ， ， ， ， ， ， ， ， ， ，927.6 等价关系与划分等价关系与划分(2) R的关系矩阵的关系矩阵n R满足自反、对称和可传递的满足自反、对称和可传递的937.6 等价关系与划分等价关系与划分q等价类：等价类：设设R是非空是非空A集合上的等价关系，对集合上的等价关系，对于任何于任何x A，令：，令：vxR =y|y A xRyvxR是由是由x A生成的生成的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=， ， ， ，vaR =a,b= bR vcR =c,d= dR967.6 等价关系与划分等价关系与划分q例：设例：设A=NvR=|x A y A (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充充分分性性，因因为为x x=y,即即x y ，所所以以xRy。v必必要要性性，已已知知xRy，考考虑虑x的的任任意意元元素素z，有有zRx。根根据据R的的传传递递性性，有有zRy，因因此此z y。证证明明x y。类类似似可可证证明明y x ，所所以以x=y987.6 等价关系与划分等价关系与划分q定理：定理：设设A是一个集合，是一个集合，R是是A上的等价关系，上的等价关系，v对于所有对于所有x,y A，或者，或者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 y x | x A 所以：所以： A x | x A1007.6 等价关系与划分等价关系与划分q商集商集：R是是A上的等价关系，上的等价关系，vR的所有等价类构成的集合的所有等价类构成的集合v记为记为A/R：xR | x Aq例：例：A为全班同学的集合，为全班同学的集合，|A|=n，(n N)v按指纹的相同关系按指纹的相同关系R1是一个等价关系是一个等价关系vA/R1=x1R1,xnR1 v同姓关系同姓关系R2是一等价关系是一等价关系vA/ R2 =张张，李李，1017.6 等价关系与划分等价关系与划分q划划分分：给给定定一一非非空空集集合合A，A的的一一个个划划分分为为非非空空子集族子集族S=A1, A2, 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的同一划分的同一划分q等价关系到划分的转化：等价关系到划分的转化：设设A是非空集合，是非空集合，R是是A上的等价关系。上的等价关系。R的商集是的商集是A的划分的划分1047.6 等价关系与划分等价关系与划分q例：例：A =a,b,c,d,evS=a,b,c,d,e 对应划分对应划分S的等价关系为的等价关系为 vR=a,ba,b cc d,ed,e=,105第七章第七章: 二元关系二元关系 第七节：偏序关系第七节：偏序关系1067.7 偏序偏序关系关系q次序在现实生活中常见：次序在现实生活中常见：v小于，包含小于，包含等等q研究序理论的动机：研究序理论的动机：v研究一般次序关系研究一般次序关系v推导出一般序关系的性质推导出一般序关系的性质v这些关系可以应用于所有特定的序关系这些关系可以应用于所有特定的序关系1077.7 偏序偏序关系关系q偏序关系偏序关系R (记作记作 )v自反性自反性: a A，有，有 Rv反对称性反对称性: a,b R,如果如果 R且且 R,则必有则必有abv传递性传递性: a,b,c A,如果如果 R, R, 必有必有 Rq例例:偏序关系偏序关系vAa,b,cvR, ,abc1087.7 偏序偏序关系关系q例：例：A是非零自然数集是非零自然数集, 是是A上的整除关系。上的整除关系。v a A, a能整除能整除a 具有自反性具有自反性v a,b A,如如a能整除能整除b,且且b能整除能整除a,则则ab 具有反对称性具有反对称性 v a,b,c A,如如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,b A, a与与b可比可比 q例：实数上的例：实数上的,关系是全序关系关系是全序关系1107.7 偏序偏序关系关系q哈斯图哈斯图v得名于德国数学家得名于德国数学家Helmut Hassev用来表示有限偏序集的一种数学图表用来表示有限偏序集的一种数学图表偏序集：偏序集：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的弧线，否则不画的弧线，否则不画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最大元最大元b B： a B,均有均有a bv最小元最小元b B： a B,均有均有b aq说明说明v如果如果A的子集的子集B存在最大存在最大(小小)元素元素,则最大则最大(小小)元元素是唯一的素是唯一的v最大最大(小小)元可能不存在元可能不存在1157.7 偏序偏序关系关系例例:A1,2,3,4,5,6,R是整除关系是整除关系,哈斯图为哈斯图为125346 A中不存在最大元中不存在最大元1167.7 偏序偏序关系关系q极大极大(小小)元：元：设设是偏序集是偏序集,B Av极大元极大元b B： a B,如如b a,则则ab不存在不存在a B，b av极小元极小元b B： a B,如如a b,则则ab不存在不存在a B，a bq说明说明v极大元未必是最大元极大元未必是最大元v极大元未必是唯一的极大元未必是唯一的v如果如果B是有限集是有限集,则则B必存在极大元必存在极大元v最大元就是极大元最大元就是极大元1253461177.7 偏序偏序关系关系q例：下列哈斯图表示的偏序集是否有最大例：下列哈斯图表示的偏序集是否有最大(小小)元？是否有极大元？是否有极大(小小)元？元？ aa a,ba,b bb a,b,ca,b,c b,cb,c cc a,ca,c 1187.7 偏序偏序关系关系q上上(下下)界：界：设设是偏序集是偏序集, B A, a AvB的上界的上界a：对每个对每个b B,有有b avB的下界的下界a：对每个对每个b B,有有a bq说明说明v上下界不一定唯一上下界不一定唯一1197.7 偏序偏序关系关系q例：例：, A=2,3,6,12,24,36 B:2,3,2,3,6,6,12,6,12,24,36A 上界上界下界下界B2,36,12,24,36 6,12,24,36 2,3,66,12,24,366,12,24,366,1212,24,36 12,24,36 2,3,6 2,3,6 6,12,24,362,3,6 2,3,6 1207.7 偏序偏序关系关系q上上(下下)确界：确界：设设是偏序集是偏序集, B Av最小上界：最小上界：C=b|b为为B的上界的上界的最小元的最小元v最大下界：最大下界：D=b|b为为B的下界的下界的最大元的最大元q说明说明vB的的最最小小元元一一定定是是B的的下下界界，同同时时也也是是B的的最最大大下下界界；B的最大元一定是的最大元一定是B的上界，同时也是的上界，同时也是B的最小上界的最小上界v最小上界或最大下界可能不存在最小上界或最大下界可能不存在v若存在最小上界或最大下界，是唯一的若存在最小上界或最大下界，是唯一的1217.7 偏序偏序关系关系例例:A，R整除整除, A=2,3,6,12,24,36 B:2,3,2,3,6,6,12,6,12,24,36A 上确界上确界下确界下确界B2 2,3 3 6 62 2,3 3,6 6 6 66 6,1212 12126 6 6 6,1212,2424,3636 6 6 1227.7 偏序偏序关系关系q拓扑排序：拓扑排序：给定一个非空有限的偏序集合给定一个非空有限的偏序集合，构造出一个全序集合，构造出一个全序集合 ，使，使得每当得每当a b有有a b，方法如下：，方法如下：v选取选取A的极小元的极小元a，使，使a是是列表表示中的列表表示中的第一个元素第一个元素v对子集对子集A-a重复这一过程，每次一个新的极小重复这一过程，每次一个新的极小元素被找到，它在元素被找到，它在的列表表示中成为下的列表表示中成为下一个元素一个元素v重复这一过程，直到重复这一过程，直到A的元素被抽完的元素被抽完1237.7 偏序偏序关系关系q例：求下列偏序集对应的全序集例：求下列偏序集对应的全序集 1 12 23 34 46 68 812122424 1 13 32 26 64 48 812122424124第七章第七章 习题课习题课 l有序对：有序对：由两个元素由两个元素x，y按给定顺序排列组成的二元组合按给定顺序排列组成的二元组合l笛卡儿积：笛卡儿积：集合集合A中元素为第一元素，集合中元素为第一元素，集合B中元素为第二元素的有序对集中元素为第二元素的有序对集l二元关系二元关系R：满足下列条件之一的集合：满足下列条件之一的集合：v集合非空，且它的元素都是有序对集合非空，且它的元素都是有序对v集合为空集集合为空集l从从A到到B的关系：的关系：A，B是集合，是集合，AB的任何子集所定义的二元关系的任何子集所定义的二元关系lA上的关系：上的关系：A=Bl空关系，全域关系，恒等关系，包含关系空关系，全域关系，恒等关系，包含关系l关系的表示法：关系的表示法：集合表达式、关系矩阵、关系图集合表达式、关系矩阵、关系图125第七章第七章 习题课习题课l关系的八种运算：关系的八种运算：u定义域：定义域：u值域：值域：u域：域：u逆：逆：u右复合：右复合：u限制：限制：u像：像：u幂：幂：vR0 = A；Rn+1=Rn R126第七章第七章 习题课习题课l关系运算的五种性质关系运算的五种性质: u自自 反：反：u反自反：反自反： u对对 称：称：u反对称：反对称：u传传 递：递： 127第七章第七章 习题课习题课l关系的三种闭包：关系的三种闭包：u自反闭包：自反闭包： r(R)=RAu对称闭包：对称闭包： s(R)=R R-1 u传递闭包：传递闭包： t(R)= R1 R2 128第七章第七章 习题课习题课lA上的等价关系：上的等价关系：v自反的；对称的；可传递的自反的；对称的；可传递的l等价类：等价类：vxR =y|y A xRyl商集：商集：vR的所有等价类构成的集合，的所有等价类构成的集合，v记为记为A/R：xR | x Al划分：划分： A的非空子集族的非空子集族S=A1, A2, Am，满足：，满足：vSv x y(x, y S xyxy=)vA1A2 Am= AlA上的偏序关系与偏序集上的偏序关系与偏序集129基本要求基本要求l熟练掌握关系的三种表示法熟练掌握关系的三种表示法 l能够判定关系的性质，以及等价关系、偏序关系能够判定关系的性质，以及等价关系、偏序关系l掌握含有关系运算的集合等式掌握含有关系运算的集合等式l掌握等价关系、等价类、商集、划分、哈斯图、偏序集等掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念概念l计算计算A B, dom R, ranR, fldR, R 1, R S , Rn , r(R), s(R), t(R)l求等价类和商集求等价类和商集A/Rl给定给定A的划分的划分 ，求出，求出 所对应的等价关系所对应的等价关系l求偏序集中的极大元、极小元、最大元、最小元、上界、求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界下界、上确界、下确界l掌握基本的证明方法掌握基本的证明方法 证明涉及关系运算的集合等式证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系证明关系的性质、证明关系是等价关系或偏序关系130练习练习11设设A = 1, 2, 3, R = | x, y A且且x+2y 6 ， S = , , 求求: (1) R的集合表达式的集合表达式(2) R 1(3) dom R, ran R, fld R(4) RS, R3(5) r(R), s(R), t(R)131解答解答(1) R = , , , , (2) R 1 = , , , , (3) domR = 1, 2, 3, ranR = 1,2, fldR = 1, 2, 3 (4) RS = , , , , , R3 = , , , , , (5) r(R) = , , , , , s(R) = , , , t(R) = , , , , , 132练习练习22设设A=1,2,3,4，在，在A A上定义二元关系上定义二元关系R： , R x+y = u+v，求求R导出的划分导出的划分. A A=, , , , , , , , , , , , , , 根据根据 中的中的 x+y = 2, 3, 4, 5, 6, 7, 8 将将A划分成等价类：划分成等价类： A/R=, , , , , , , , , , , , , , 1333设设R是是Z上的模上的模 n 等价关系等价关系, 即即 x y x y(modn),试给出由试给出由R确定的确定的Z的划分的划分 .解解 设除以设除以 n 余数为余数为 r 的整数构成等价类的整数构成等价类 r，则，则 r = kn+r | k Z , r = 0, 1, , n 1 = r | r = 0, 1, , n 1 练习练习3134图图1111练习练习44设偏序集设偏序集 的哈斯图如图所示的哈斯图如图所示. (1) 写出写出A和和R的集合表达式的集合表达式(2) 求该偏序集中的极大元、极小元、最大元、最小元求该偏序集中的极大元、极小元、最大元、最小元解：解：(1) A = a, b, c, d, e R = , , , , , , IA (2) 极大元和最大元是极大元和最大元是a, 极小元极小元是是d, e； 没有最小元没有最小元.abcde135练习练习55设设R是是A上的二元关系，上的二元关系， 设设 S = | c( R R).证明如果证明如果R是等价关系，则是等价关系，则S也是等价关系。也是等价关系。证：证： R是是A上的等价关系上的等价关系. (1) 证证自反自反 任取任取x, x A R x ( R R) S(2) 证证对称对称 任取任取, S c( R R) c ( R R) S (3) 证证传递传递 任取任取, , S S c ( R R) d ( R R) R R S1366设偏序集设偏序集和和，定义，定义A B上二元关系上二元关系T: T xRu ySv 证明证明T为偏序关系为偏序关系.证：证：(1) 自反性自反性 任取任取, A B x A y B xRx ySy T (2) 反对称性反对称性 任取任取, T T xRu ySv uRx vSy (xRu uRx) (ySv vSy) x=u y=v = (3) 传递性传递性 任取任取, T T xRu ySv uRw vSt (xRu uRw) (ySv vSt) xRw ySt T 练习练习6137关系性质的证明方法关系性质的证明方法1. 证明证明R在在A上上自反自反 任取任取x, x A . R 前提前提 推理过程推理过程 结论结论2. 证明证明R在在A上上对称对称 任取任取， R . R 前提前提 推理过程推理过程 结论结论1383. 证明证明R在在A上上反对称反对称 任取任取， R R . x = y 前提前提 推理过程推理过程 结论结论4. 证明证明R在在A上上传递传递 任取任取,， R R . R 前提前提 推理过程推理过程 结论结论关系性质的证明方法关系性质的证明方法1397R,S为为A上的关系，证明上的关系，证明 R S t(R) t(S) 证：证：只需证明对于任意正整数只需证明对于任意正整数n, Rn Sn. 对对n归纳归纳.n=1, 显然为真显然为真.假设对于假设对于n，命题为真，任取，命题为真，任取 Rn+1 Rn R t ( Rn R) t ( Sn S) Sn S Sn+1 练习练习7140数学归纳法（主要用于幂运算）数学归纳法（主要用于幂运算）证明中用到关系运算的定义和公式证明中用到关系运算的定义和公式, 如：如： x domR y( R) y ranR x( R) R R 1 R S t ( R S) R A x A R y R A x (x A R) r(R) = R IA s(R) = R R 1 t(R) = R R2 关系等式或包含式的证明方法关系等式或包含式的证明方法141作业作业q4q13q15q20q25q26q36q46