七章二元关系ppt课件

1、1第七章第七章: 二元关系二元关系q主要内容主要内容q有序对与笛卡儿积有序对与笛卡儿积q二元关系的定义与表示法二元关系的定义与表示法q关系的运算关系的运算q关系的性质关系的性质q关系的闭包关系的闭包q等价关系与划分等价关系与划分q偏序关系偏序关系q本章与后面各章的关系本章与后面各章的关系q是函数的根底是函数的根底q是图论的根底是图论的根底2第七章第七章: 二元关系二元关系 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积3引言引言q关系是数学中最重要的概念之一关系是数学中最重要的概念之一q父子关系、师生关系父子关系、师生关系q等于、大于、小于关系等于、大于、小于关系q直线的平行、垂直关系直线的

2、平行、垂直关系q在计算机科学中有广泛运用在计算机科学中有广泛运用q人工智能人工智能q程序设计程序设计q数据库管理数据库管理关系数据库关系数据库47.1 有序对与笛卡儿积有序对与笛卡儿积q有序对序偶：由两个元素有序对序偶：由两个元素x x，y(y(允许允许x=y)x=y)按给定顺序陈列组成的二元组合按给定顺序陈列组成的二元组合q符号化：符号化：xyqx x为第一元素，为第一元素，y y为第二元素为第二元素q例：平面直角坐标系中的一个点的坐标例：平面直角坐标系中的一个点的坐标q1,31,3和和3,13,1是表示平面上两个不同的点是表示平面上两个不同的点qx = = v当且仅当当且仅当x=u x=u

3、 ，y=vy=vq假设假设x xy y，那么，那么x x，y yy y ，x x57.1 有序对与笛卡儿积有序对与笛卡儿积q例：知例：知=，求，求x,yx,yq解：根据有序对等式定义，只需求解方程式解：根据有序对等式定义，只需求解方程式q x+2=5 x+2=5 和和 2x+y=4 2x+y=4q 得到：得到： x=3, y=-2 x=3, y=-267.1 有序对与笛卡儿积有序对与笛卡儿积77.1 有序对与笛卡儿积有序对与笛卡儿积q例：设集合例：设集合A=1A=1，22，求，求P(A)P(A)A Aq解：解：qP(A)=P(A)=，11，22，11，22qP(A)P(A)A A q=1， 2

4、，11，12，21，22， 1 1，1287.1 有序对与笛卡儿积有序对与笛卡儿积97.1 有序对与笛卡儿积有序对与笛卡儿积q笛卡儿积的性质：笛卡儿积的性质：q对于恣意集合对于恣意集合A，A=，A=q普通不满足交换律，当普通不满足交换律，当A，B，AB时时，q AB BAq普通不满足结合律，即当普通不满足结合律，即当A，B，C均非空时，均非空时，(AB)CA(BC)107.1 有序对与笛卡儿积有序对与笛卡儿积q笛卡儿积的性质续：笛卡儿积的性质续：q对恣意三个集合对恣意三个集合A，B，C有有q 1A(BC)=(AB) (AC)q 2A(BC)=(AB)(AC)q 3(BC)A=(BA) (CA)

5、q 4(BC)A=(BA)(CA)q 5A C B D ABCD117.1 有序对与笛卡儿积有序对与笛卡儿积q证明：证明：q对恣意三个集合对恣意三个集合A，B，C有有q A(BC)=(AB) (AC)q证明：证明： A(BC) q xA yBCq xA (yB yC)q (xA yB) (xA yC)q AB ACq (AB) (AC)127.1 有序对与笛卡儿积有序对与笛卡儿积q例：设例：设A，B，C，D是恣意集合，判别以下命是恣意集合，判别以下命题能否正确？题能否正确？qABAC BCq不正确。取不正确。取A，BC，AB=AC=qA-(BC)=(A-B) (A-C)q不正确。取不正确。取A

6、=B=1，C=2，q A-(BC)=1-=1q 而而(A-B) (A-C)=1=137.1 有序对与笛卡儿积有序对与笛卡儿积q例：设例：设A，B，C，D是恣意集合，判别以下命是恣意集合，判别以下命题能否正确？题能否正确？qA=B，C=D ACBD q正确。正确。q存在集合存在集合A使得使得A AAq正确。取正确。取A=时，时，AAA14第七章第七章: 二元关系二元关系 第二节：二元关系第二节：二元关系 157.2 二元关系二元关系q关系是指事物之间个体之间的相互联络关系是指事物之间个体之间的相互联络q二元关系二元关系R R：满足以下条件之一的集合：满足以下条件之一的集合q集合非空，且它的元素都

7、是有序对集合非空，且它的元素都是有序对q集合为空集集合为空集q定义：定义：A A，B B是集合，是集合，A AB B的子集叫做从的子集叫做从A A到到B B的的一个二元关系一个二元关系q例：例：A=0A=0，11，B=1B=1，2 2，33qR1=R1=，R2=R2=qR3=R3=167.2 二元关系二元关系q几类特殊关系：几类特殊关系：q全域关系全域关系EAEAA AA Aq恒等关系恒等关系IAIAx|xA x|xA q空关系空关系177.2 二元关系二元关系q例：例： A=0,1,2 A=0,1,2qEA=,EA=,q , ,q恒等关系恒等关系IA =,IA =,187.2 二元关系二元关

8、系q包含关系包含关系qA是一个集合是一个集合,定义定义P(A)上的一个关系上的一个关系qR =uP(A)，vP(A)，且，且uvqA=a，b，P(A)= ，a，b，AqR=，q例：例： A=2，3，4，5，6qR=a是是b的倍数的倍数qR= ，197.2 二元关系二元关系q 关系表示方法关系表示方法q 枚举法直观法、列举法枚举法直观法、列举法q xRyxRy表示特定的序偶表示特定的序偶x x，y y R Rq 谓词公式表示法暗含法谓词公式表示法暗含法q 关系矩阵表示法关系矩阵表示法q 关系图表示法关系图表示法207.2 二元关系二元关系q 关系表示方法关系表示方法q 枚举法直观法、列举法枚举法

9、直观法、列举法q xRyxRy表示特定的序偶表示特定的序偶x x，y y R Rq 谓词公式表示法暗含法谓词公式表示法暗含法q 关系矩阵表示法关系矩阵表示法q 关系图表示法关系图表示法217.2 二元关系二元关系q 关系矩阵表示法关系矩阵表示法q 设集合设集合A=a1,am,B=b1,bn,RA=a1,am,B=b1,bn,R是是A A到到B B的关系的关系, ,那么那么R R的关系矩阵是一个的关系矩阵是一个m mn n阶的矩阶的矩阵阵q MR=(rij)m MR=(rij)mn nq 其中其中rij =1,rij =1,当当R Rq ri j =0, ri j =0,当当R Rq 假设假设R

10、 R是是A A上的关系时上的关系时, ,那么其关系矩阵是一个那么其关系矩阵是一个方阵方阵227.2 二元关系二元关系例：例：A=a,b,c,d,B=x,y,z,A=4，B=3,R=,那么那么MR是是43的矩阵的矩阵 1 0 1 1 0 1MR = 0 1 0MR = 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0其中其中r13=1表示表示R,而而r23=0,表示表示R237.2 二元关系二元关系q 关系表示方法关系表示方法q 枚举法直观法、列举法枚举法直观法、列举法q xRyxRy表示特定的序偶表示特定的序偶x x，y y R Rq 谓词公式表示法暗含法谓词公式表示法暗含法q 关系

11、矩阵表示法关系矩阵表示法q 关系图表示法关系图表示法247.2 二元关系二元关系q 关系图：关系图：A=a1,am，B=b1,bnq 结点：结点：m+n个空心点分别表示个空心点分别表示a1,am和和b1,bnq 有向边：假设有向边：假设R,那么由结点那么由结点ai向结向结点点bj通一条有向弧通一条有向弧,箭头指向箭头指向bjq 自回路：自回路：R,那么画一条以那么画一条以ai到本身的到本身的一条有向弧一条有向弧q 这样构成的图称为关系这样构成的图称为关系R的关系图的关系图257.2 二元关系二元关系q 例：例：A=2,3,4,5,6q (1)R1=a是是b的倍数的倍数q (2)R2=(a-b)

12、2A 536425364226第七章第七章: 二元关系二元关系 第三节：关系的运算第三节：关系的运算277.3 关系的运算关系的运算q二元关系的定义域和值域二元关系的定义域和值域q定义域：定义域：q值域：值域：q例例qX=1,2,3,4,5,6,Y=a,b,c,d,e,fX=1,2,3,4,5,6,Y=a,b,c,d,e,fqR=,R=,qdomR=1,2,3,4domR=1,2,3,4qranR=a,b,c,dranR=a,b,c,d),(|RyxyxdomR),(|RyxxyranR287.3 关系的运算关系的运算q二元关系的逆关系二元关系的逆关系qR-1R-1就是将就是将R R中的一切有

13、序对的两个元素交换次中的一切有序对的两个元素交换次序成为序成为R-1 R-1 ，故，故|R|=| R-1 | |R|=| R-1 | q阐明阐明qR-1 R-1 的关系矩阵是的关系矩阵是R R的关系矩阵的转置，即的关系矩阵的转置，即 MR-1=(MR)TMR-1=(MR)TqR-1R-1的关系图就是将的关系图就是将R R的关系图中的弧改动方向的关系图中的弧改动方向即可以即可以,|,1RxyyxR297.3 关系的运算关系的运算q例：例：qR=，qR-1=， q 1 0 0 1 1 0 1 0q 0 0 0 1 0 0 1 0 q MR= 1 1 0 0 MR-1=MRT= 0 0 0 1 q

14、0 0 1 0 1 1 0 0 307.3 关系的运算关系的运算q例：例：qR=，qR-1=， dbcabcadR的关系图R-1的关系图317.3 关系的运算关系的运算q 关系的右复合关系的右复合q 例例q A=1,2,3,4,5,B=3,4,5,C=1,2,3q R=|x+y=6q =,q S=y-z=2 q =,q RS=,),(|,GytFtxtyxGFo327.3 关系的运算关系的运算q 例续例续5435432132154321321从而从而RS的关系图的关系图337.3 关系的运算关系的运算q 例：例： A=a,b,c,d,eq R=,q S=,q RS=,q SR=,q RR=,q

15、 SS=q 留意：留意：RSSR 347.3 关系的运算关系的运算q 定义：定义：R是二元关系，是二元关系，A是集合是集合q R在在A上的限制上的限制q q A在在R下的像下的像,|RAx yxRyxA )(ARranARARA357.3 关系的运算关系的运算q例：R = , , , , , 求：q R 1R 2,3R R 1R2,3R367.3 关系的运算关系的运算q优先顺序：优先顺序：q逆运算优先于其他运算逆运算优先于其他运算q关系运算优先于集合运算关系运算优先于集合运算q没有规定优先权的运算以括号决议运算顺序没有规定优先权的运算以括号决议运算顺序377.3 关系的运算关系的运算q 定理：

16、设定理：设F是恣意的关系，那么是恣意的关系，那么q (F-1)-1=Fq domF-1 =ranF, ranF-1 =domF387.3 关系的运算关系的运算q 定理：设定理：设F，G，H是恣意的关系是恣意的关系q (FG)H = F(GH)q (FG)-1 =G-1F-1q 证明：证明： (FG)-1 q FGq t(F G)q t(G-1 F-1)q G-1F-1397.3 关系的运算关系的运算q 例例q R=,q S=,q RS=, ,q (RS)-1=, ,q R-1=, ,q S-1=, q S-1R-1=, ,407.3 关系的运算关系的运算q 定理定理: 设设R为为A上关系，那么

17、上关系，那么q RIAIARRq 定理定理:q R(ST)=RSRTq R(ST)RSRTq (ST)X=SXTXq (ST)XSXTX417.3 关系的运算关系的运算q 证明证明 R(ST)=RSRTq R(ST)q y(RST)q y(R(ST)q y(RS) (RT)q y(RS) y(RT)q RS RTq RSRT427.3 关系的运算关系的运算q证明证明 R(ST)RSRTq R(ST) t (RST)q t (RST) t (RS)q (RT) t (RS)q t (RT)q RSRT RSRT437.3 关系的运算关系的运算q 定理定理:q R (AB) = R AR Bq R

18、AB = RARBq R (AB) = R AR Bq RAB RARB447.3 关系的运算关系的运算q 定理定理: RAB RARBq 证明：证明：yRAB q x(RxAB)q x(RxAxB)q x(RxA)(R xB)q x(RxA) x(R xB)q yRAyRB q yRARB457.3 关系的运算关系的运算q R的的n次幂次幂q记为记为Rnq R0 =Aq Rn+1=RnRq定理定理: 设设R是集合是集合A上的关系，上的关系，m,nNq RmRn=Rm+nq (Rm)n=Rmnq证明思绪：运用归纳法并利用复合关系的结证明思绪：运用归纳法并利用复合关系的结合律合律467.3 关系

19、的运算关系的运算q 例例R=,q R0= ,q R1=Rq R2=,q R3=R2Rq =,q R4=R3Rq =,q R5=R4Rq =,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，那么，那么q 对一切的对一切的k0，那么，那么R

20、s+k=Rt+kq 对一切的对一切的k,i0 ，那么有，那么有Rs+kp+i=Rs+iq p=t-sq 设设S=R0,R1,R2,Rt-1，那么，那么R的每的每一次幂都是一次幂都是S的元素，即对恣意的元素，即对恣意qN, RqS 497.3 关系的运算关系的运算q 定理：定理：R是是A上的二元关系，假设存在自然数上的二元关系，假设存在自然数s和和t，且，且st，使，使Rs=Rtq 对一切的对一切的k0，那么，那么Rs+k=Rt+kq 对一切的对一切的k,i0 ，那么有，那么有Rs+kp+i=Rs+iq p=t-sq 设设S=R0,R1,R2,Rt-1，那么，那么R的每的每一次幂是一次幂是S的元

21、素，即对恣意的元素，即对恣意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+iRp=Rs+iRp =Rs+p+i =Rs+t-s+i =Rt+i=Rs+i517.3 关系的运算关系的运算q 定理：定理：R是是A上的二元关系，假设存在自然数上的二元关系，假设存在自然数s和和t，且，且st，使，使Rs=Rtq 对一切的对一切的k0，那么，那么Rs+k=Rt+kq 对一切的对一切的k,i0

22、，那么有，那么有Rs+kp+i=Rs+iq p=t-sq 设设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 = s+t-s-1=t-153第七章第七章: 二元关系二元关系 第四节：关系的性质第四节：关系的性质547.4 关系的性质关系的性质q自反性自反性qaA，

23、有，有R，那么，那么R为为A上的自反关系上的自反关系q反自反性反自反性qaA，有，有 R，R为为A上的反自反关系上的反自反关系q例例 A=a,b,cqR1=,qR2=,qR3=,557.4 关系的性质关系的性质q例：例：R是是I+上的整除关系，那么上的整除关系，那么R具有自反性具有自反性q证明：证明：xI+，x能整除能整除x，qR，R具有自反性具有自反性q例：例：R是是I上的同余关系，那么上的同余关系，那么R具有自反性具有自反性q证明：证明：xI，(x-x)/k=0I, qx与与x同余同余RR具有自反性具有自反性q其它其它，关系，均是自反关系关系，均是自反关系567.4 关系的性质关系的性质q

24、例：例：N上的互质关系是反自反关系上的互质关系是反自反关系q证明：证明：xN，x与与x是不互质的，是不互质的，q R，R具有反自反关系具有反自反关系q实数上的实数上的,关系关系,均是反自反关系均是反自反关系577.4 关系的性质关系的性质q关系矩阵的特点？关系矩阵的特点？q自反关系的关系矩阵的对角元素均为自反关系的关系矩阵的对角元素均为1q反自反关系的关系矩阵的对角元素均为反自反关系的关系矩阵的对角元素均为0q关系图的特点？关系图的特点？q自反关系的关系图中每个顶点都有环自反关系的关系图中每个顶点都有环q反自反关系的关系图中每个顶点都没有环反自反关系的关系图中每个顶点都没有环q定理：定理：R是

25、是A上的关系，那么：上的关系，那么：qR是自反关系的充要条件是是自反关系的充要条件是IARqR是反自反关系的充要条件是是反自反关系的充要条件是RIA=587.4 关系的性质关系的性质q对称关系对称关系Rqa,bA,假设假设R,那么必有那么必有R q例例qR1,qR1是对称的是对称的qR2,qR2是对称的是对称的qR3,qR3不是对称的不是对称的 597.4 关系的性质关系的性质q关系矩阵特点？关系矩阵特点？q对称关系的关系矩阵是对称矩阵对称关系的关系矩阵是对称矩阵q关系图特点？关系图特点？q假设两个顶点之间有边，一定是一对方向相反假设两个顶点之间有边，一定是一对方向相反的边无单边的边无单边q定

26、理：定理： R在在A上对称当且仅当上对称当且仅当R=R-1q证明：必要性证明：必要性qRRR-1q充分性充分性qRR-1R607.4 关系的性质关系的性质q反对称关系反对称关系Rqa,bA,假设假设R且且R,那那么必有么必有abqa,bA,假设假设ab,R,那么必有那么必有Rq例例: Aa,b,cqR,qS,qT,qR,S是反对称的是反对称的,T不是反对称的不是反对称的617.4 关系的性质关系的性质q例例: 实数集合上实数集合上关系是反对称关系关系是反对称关系qx,y实数集实数集,如如xy,且且xy,那么那么yx不不成立成立q例：例：,关系关系,均是反对称关系均是反对称关系q反对称关系矩阵和

27、关系图特点？反对称关系矩阵和关系图特点？q假设假设rij=1，且，且ij， 那么那么rji=0q假设两个顶点之间有边，一定是一条有向边假设两个顶点之间有边，一定是一条有向边无双向边无双向边q定理：定理： R在在A上反对称当且仅当上反对称当且仅当RR-1 IA627.4 关系的性质关系的性质q传送关系传送关系qa,b,cA,假设假设R,R, 必有必有Rq例例qR1,q是传送关系是传送关系qR2,q是传送关系是传送关系qR3,q不是传送关系不是传送关系637.4 关系的性质关系的性质q例例:整除关系整除关系DI是是I上的传送关系上的传送关系qx,y,zI,如如DI,DI,即即x能整除能整除y,且且

28、y能整除能整除z,那那么必有么必有x能整除能整除z, DIq例例:P(A)上的包含关系上的包含关系具有传送性具有传送性q假设假设uv,vw,那么必有那么必有uwq例例:实数集上的实数集上的关系具有传送性关系具有传送性q假设假设xy,yz必有必有xz647.4 关系的性质关系的性质q传送关系关系图特点？传送关系关系图特点？q假设结点假设结点a能经过有向弧组成的有向途径通向能经过有向弧组成的有向途径通向结点结点x,那么那么a必需有有向弧直接指向必需有有向弧直接指向x,否那么否那么R就不是传送的就不是传送的q例：例：R=,q定理：定理：R在在A上传送当且仅当上传送当且仅当RR Rdcba657.4

29、关系的性质关系的性质自自 反：反：反自反：反自反： 对对 称：称：反对称：反对称：传传 递：递： )(xRxXxx xRx)Xx(x )(yRxxRyXyXxyx )(yxyRxxRyXyXxyx )(xRzyRzxRyXzXyXxzyx 667.4 关系的性质关系的性质q 设设A是集合，是集合，R1和和R2是是A上的关系上的关系q 假设假设R1，R2是自反和对称的，那么是自反和对称的，那么R1R2也是自反的和对称的也是自反的和对称的q 假设假设R1和和R2是传送的，那么是传送的，那么R1R2也是传也是传送的送的677.4 关系的性质关系的性质q 设设A是集合，是集合，R1和和R2是是A上的关

30、系上的关系q 假设假设R1，R2是自反的和对称的，那么是自反的和对称的，那么R1R2也是自反也是自反q 的和对称的的和对称的q 证明：证明：R1，R2是自反的是自反的 IA R1，IA R2q 所以所以IA R1R2q R1，R2是对称的是对称的 R1=R1-1和和R2=R2-1q 所以所以(R1R2)-1=R1-1R2-1= R1R2687.4 关系的性质关系的性质q例：例： X=1,2,3，判别关系的性质，判别关系的性质qR1=,n R2=, n反对称反对称n反自反反自反n反对称反对称n可传送可传送697.4 关系的性质关系的性质qR3=,qR4= Ex q自反，对称，可传送的自反，对称，

31、可传送的 n自反，对称，反对称，可传送的自反，对称，反对称，可传送的707.4 关系的性质关系的性质qX=1,2,3, R5= q反自反的，对称的，反对称的，可传送的反自反的，对称的，反对称的，可传送的q假设假设X= ，X上的空关系上的空关系q自反的，反自反的，对称的，反对称的，可传自反的，反自反的，对称的，反对称的，可传送的送的71第七章第七章: 二元关系二元关系 第五节：关系的闭包第五节：关系的闭包727.5 关系的闭包关系的闭包q定义：定义：R是非空集合是非空集合A上的关系上的关系,假设假设A上另外上另外有一个关系有一个关系R满足如下三条：满足如下三条：qR是自反的是自反的(对称的，传送

32、的对称的，传送的qRRqA上任何一个满足以上两条的关系上任何一个满足以上两条的关系R，均有，均有RR，q称关系称关系R为为R的自反的自反(对称对称,传送传送)闭包闭包,记作记作r(R) (s(R),t(R)737.5 关系的闭包关系的闭包q解释解释qR是在是在R的根底上添加有序对的根底上添加有序对q添加元素的目的是使添加元素的目的是使R具有自反性具有自反性(对称性对称性,传传送性送性)q添加后使之具有自反性添加后使之具有自反性(对称性对称性,传送性传送性)的一的一切关系中切关系中R是最小的一个是最小的一个747.5 关系的闭包关系的闭包q例例A=a,b,c，R=,q自反闭包自反闭包r(R)q,

33、q对称闭包对称闭包s(R)q,q传送闭包传送闭包t(R)q,r(R)r(R)a b ccbaacbcbabac757.5 关系的闭包关系的闭包q定理：定理：R是非空集合是非空集合A上的关系上的关系,那么那么qr(R)=RAq证明证明: RRA，RA是自反的是自反的q设设R满足满足RR,R是自反的是自反的qRAq那么那么R或或A q如如R,由由RR知知Rq如如A,由由R的自反性知的自反性知Rq均有均有RqRAR 767.5 关系的闭包关系的闭包q定理定理: 设设R是非空集是非空集A的关系的关系,那么那么qs(R)=RR-1 q证明证明:qRRR-1满足定义第满足定义第2条条qRR-1qRR-1q

34、R-1RqRR-1 qRR-1是对称的是对称的777.5 关系的闭包关系的闭包v如如RR,且且R是对称的是对称的vRR-1vR或或R-1v如如R,由由RR,那么那么Rv如如R-1,那么那么R,那么那么Rv因因R对称对称vR,RR-1Rv满足定义第满足定义第3条条787.5 关系的闭包关系的闭包q例例:设设A=1,2,3,A上的关系上的关系R如图如图,求求r(R),s(R)q解解:R=,qr(R)= RA q=,qs(R)= RR-1 q=, 1 2 3797.5 关系的闭包关系的闭包定理: 设R是非空集合A上的关系, 那么t(R)= R1R2 证明：首先证明R1R2 t(R)，运用归纳法。n=

35、1，显然R1= R t(R)假设Rk t(R)，对恣意有 Rk+1 =Rk R1 t(Rk R1) t(t(R) t(R) t(R)其次， t(R) R1R2即证R1R2传送推论: 设A是非空有限集，R是集合A上的二元关系，那么存在正整数n，使得t(R)=RR2 Rn807.5 关系的闭包关系的闭包q例例 A=a,b,c,dqR=,qS=,求求t(R),t(S)q解解:R2=,R3=qt(R)=R,qS2=,S3=,S4=qt(S)=S, a b c dR a b c d S817.5 关系的闭包关系的闭包q给定关系给定关系R，r(R)，s(R)，t(R)的关系矩阵的关系矩阵分别为分别为M，M

36、r，Ms，Mt，那么：，那么：qMr=M+EqMs=M+MqMt=M+M2+M3+827.5 关系的闭包关系的闭包q关系图分别为关系图分别为G，Gr，Gs，Gt，那么：，那么：q调查调查G的每个顶点，假设没有环就加上一个的每个顶点，假设没有环就加上一个环，最终得到的是环，最终得到的是Grq调查调查G的每一条边，假设有一条从的每一条边，假设有一条从xi到到xj的的单向边，那么在单向边，那么在G中加一条中加一条xj到到xi的反方向的反方向边，最终得到边，最终得到Gsq调查调查G的每个顶点的每个顶点xi，找出从，找出从xi出发的一切出发的一切2步，步，3步，步，n步长的途径。设途径的终点步长的途径。

37、设途径的终点为为xj1， xj2， ， xjk。假设没有从。假设没有从xi到到xjl的边，就加上这条边，最终得到的边，就加上这条边，最终得到Gt837.5 关系的闭包关系的闭包q定理：设定理：设A是一集合，是一集合，R是是A上的二元关系，上的二元关系，那么有：那么有：qR是自反的当且仅当是自反的当且仅当r(R)RqR是对称的当且仅当是对称的当且仅当s(R)RqR是可传送的当且仅当是可传送的当且仅当t(R)RqR是自反的当且仅当是自反的当且仅当r(R)Rq证明：证明：Rr(R)。由自反闭包定义，。由自反闭包定义，r(R)R。847.5 关系的闭包关系的闭包q定理：设定理：设A是集合，是集合，R1

38、和和R2是是A上的二元关上的二元关系，系，R1R2，那么有：，那么有：qr(R1)r(R2)qs(R1)s(R2)qt(R1)t(R2)qr(R1)r(R2)q证明：证明： r(R1)=R1A ，r(R2)=R2A857.5 关系的闭包关系的闭包q定理：设定理：设X是一集合，是一集合，R是是X上的二元关系，上的二元关系，那么有：那么有：q假设假设R是自反的，那么是自反的，那么s(R),t(R)也自反也自反q假设假设R是对称的，那么是对称的，那么r(R),t(R)也对称也对称q假设假设R是可传送的，那么是可传送的，那么r(R)也可传送也可传送867.5 关系的闭包关系的闭包q定理：设定理：设X是

39、一集合，是一集合，R是是X上的二元关系，上的二元关系，那么有：那么有：q假设假设R是对称的，那么是对称的，那么t(R)也对称也对称q证明：归纳法证明假设证明：归纳法证明假设R是对称，那么是对称，那么Rn也对也对称称qn=1，显然成立，显然成立q假设假设Rn对称，对恣意对称，对恣意q Rn+1q t(RnR)q t(RnR)q RRn Rn+1 877.5 关系的闭包关系的闭包q定理：设定理：设X是一集合，是一集合，R是是X上的二元关系，上的二元关系，那么有：那么有：q假设假设R是对称的，那么是对称的，那么t(R)也对称也对称q证明：证明：RRn Rn+1 q任取任取，有，有q t(R)q n(

40、Rn)q n(Rn)q t(R)887.5 关系的闭包关系的闭包q假设假设R是传送的，是传送的，s(R)不一定是传送的不一定是传送的q反例：反例：R=,，qR是传送的是传送的q s(R)=,q s(R)不是传送的不是传送的89第七章第七章: 二元关系二元关系q q 第六节：等价关系与划分第六节：等价关系与划分907.6 等价关系与划分等价关系与划分q等价关系：非空集合等价关系：非空集合A上的关系，满足：上的关系，满足：q自反的自反的q对称的对称的q可传送的可传送的q例例q实数实数(或或I、N集上集上)集合上的集合上的“=关系关系q选集上集合的相等关系选集上集合的相等关系q命题集合上的命题等价关

41、系命题集合上的命题等价关系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集合上的等价关系，对集合上的等价关系，对于任何于任何xA，令：，令：qxR =y|yA

42、xRyqxR是由是由xA生成的生成的R等价类等价类qx为等价类为等价类xR的表示元素的表示元素947.6 等价关系与划分等价关系与划分q讨论讨论q等价类等价类xR是一个集合，是一个集合，xR A (xR是是A的子集的子集)qxR中的元素是在中的元素是在A中，一切与中，一切与x具有等价关具有等价关系系R的元素所组成的集合的元素所组成的集合q在等价关系中的关系图中，一个最大连通子图在等价关系中的关系图中，一个最大连通子图中的点就是一个等价类中的点就是一个等价类957.6 等价关系与划分等价关系与划分q例：例：qA=a,b,c,dqR=，qaR =a,b= bR qcR =c,d= dR967.6

43、等价关系与划分等价关系与划分q例：设例：设A=NqR=|xAyA(x-y)可被可被3整整除除q等价类等价类q0R =0，3，6，9 q1R =1，4，7，10 q2R=2，5，8，11977.6 等价关系与划分等价关系与划分q定理定理 设设A是一个集合，是一个集合，R是是A上的等价关系，上的等价关系，xRy当且仅当当且仅当x=yq证明：证明：q充分性，由于充分性，由于xx=y,即即xy ，所以，所以xRy。q必要性，知必要性，知xRy，思索，思索x的恣意元素的恣意元素z，有，有zRx。根据。根据R的传送性，有的传送性，有zRy，因此，因此zy。证明。证明xy。类似可证明。类似可证明yx ，所，

44、所以以x=y987.6 等价关系与划分等价关系与划分q定理：设定理：设A是一个集合，是一个集合，R是是A上的等价关系，上的等价关系，q对于一切对于一切x,yA，或者，或者x=y，或者，或者 x y=q证明：只需证明假设证明：只需证明假设xRy，那么，那么xy=q反证法：假设反证法：假设xy，那么，那么zxyq R Rq R (矛盾矛盾!)997.6 等价关系与划分等价关系与划分q定理：设定理：设R是集合是集合A上的等价关系，那么上的等价关系，那么q A=x | xAq证明：首先易证证明：首先易证x | xA Aq 其次，对恣意其次，对恣意yAq yA yy yAq yx | xAq 所以：所以

45、： A x | xA1007.6 等价关系与划分等价关系与划分q商集：商集：R是是A上的等价关系，上的等价关系，qR的一切等价类构成的集合的一切等价类构成的集合q记为记为A/R：xR | x Aq例：例：A为全班同窗的集合，为全班同窗的集合，|A|=n，(nN)q按指纹的一样关系按指纹的一样关系R1是一个等价关系是一个等价关系qA/R1=x1R1,xnR1 q同姓关系同姓关系R2是一等价关系是一等价关系qA/ R2 =张张，李李，1017.6 等价关系与划分等价关系与划分q 划分：给定一非空集合划分：给定一非空集合A，A的一个划分为非的一个划分为非空子集族空子集族S=A1, A2, Am，满足

46、：，满足：q Sq xy(x, ySxyxy=)q A1A2 Am= A1027.6 等价关系与划分等价关系与划分q例：例：A=a,b,c,以下哪些以下哪些Ai为为A的一个划分？的一个划分？qA1=a,b,c qA2=a,c,bqA3=a,a,b,cqA4=a,b,c, qA5=a,a,b,c1037.6 等价关系与划分等价关系与划分q等价关系与划分有一一对应关系等价关系与划分有一一对应关系q划分到等价关系转化：划分到等价关系转化：A是一非空集合，是一非空集合，S是是A的一个划分，下述关系必定是一个等价关系的一个划分，下述关系必定是一个等价关系qR= | x, y A x,y在在S的同一划的同

47、一划分分q等价关系到划分的转化：设等价关系到划分的转化：设A是非空集合，是非空集合，R是是A上的等价关系。上的等价关系。R的商集是的商集是A的划分的划分1047.6 等价关系与划分等价关系与划分q例：例：A =a,b,c,d,eqS=a,b,c,d,eq 对应划分对应划分S的等价关系为的等价关系为 qR=a,ba,bccd,ed,e=,105第七章第七章: 二元关系二元关系q 第七节：偏序关系第七节：偏序关系1067.7 偏序关系偏序关系q次序在现实生活中常见：次序在现实生活中常见：q小于，包含等小于，包含等q研讨序实际的动机：研讨序实际的动机：q研讨普通次序关系研讨普通次序关系q推导出普通序

48、关系的性质推导出普通序关系的性质q这些关系可以运用于一切特定的序关系这些关系可以运用于一切特定的序关系1077.7 偏序关系偏序关系q偏序关系偏序关系R (记作记作 )q自反性自反性: aA，有，有Rq反对称性反对称性: a,bR,假设假设R且且R,那么必有那么必有abq传送性传送性: a,b,cA,假设假设R,R, 必有必有Rq例例:偏序关系偏序关系qAa,b,cqR, ,abc1087.7 偏序关系偏序关系q 例：例：A是非零自然数集是非零自然数集, 是是A上的整除关系上的整除关系。q aA, a能整除能整除a q 具有自反性具有自反性q a,bA,如如a能整除能整除b,且且b能整除能整除

49、a,那么那么abq 具有反对称性具有反对称性 q a,b,cA,如如a能整除能整除b,b能整除能整除c,那么那么a能能整除整除c, q 具有传送性具有传送性q 是是A上的偏序关系上的偏序关系1097.7 偏序关系偏序关系q小于小于 ：a ba babq可比：可比：a与与b可比可比 a bb aq可比不同于等于可比不同于等于q例：例：A=1，2，3， 是是A上的整除关系上的整除关系q1，3可比可比q全序关系全序关系R：R是是A上的偏序关系上的偏序关系, 满足：满足：qa,bA, a与与b可比可比 q例：实数上的例：实数上的,关系是全序关系关系是全序关系1107.7 偏序关系偏序关系q哈斯图哈斯图

50、q得名于德国数学家得名于德国数学家Helmut Hasseq用来表示有限偏序集的一种数学图表用来表示有限偏序集的一种数学图表q偏序集：偏序集：1117.7 偏序关系偏序关系q 覆盖：覆盖：，b覆盖覆盖a假设假设q a b，不存在，不存在cA，a c bq 哈斯图思绪：哈斯图思绪：q 一切结点的自回路均省略一切结点的自回路均省略q 省略一切弧上的箭头省略一切弧上的箭头,适当陈列适当陈列A中元素的位中元素的位置置,如如a b,那么那么a画在画在b的下方的下方q 如如a b,b c,那么必有那么必有a c, a到到b有边有边, b到到c有边有边,那么那么a到到c的无向弧省略的无向弧省略q 条件条件2

51、，3等于说假设等于说假设b覆盖覆盖a,那么画一条从那么画一条从a到到b的弧线，否那么不画的弧线，否那么不画1127.7 偏序关系偏序关系q例：画出以下偏序集的哈斯图。例：画出以下偏序集的哈斯图。qqR整除整除=,1253461137.7 偏序关系偏序关系q例：例：A=a,b,c,包含关系包含关系R是是P(A)上的偏上的偏序关系序关系,哈斯图如下哈斯图如下:qP(A)=,a,b,c,a,b,a,c,b,c,a,b,c aaa,ba,bbba,b,ca,b,cb,cb,ccca,ca,c1147.7 偏序关系偏序关系q最小最小(大大)元：设元：设是偏序集是偏序集,集合集合BAq最大元最大元bB：a

52、B,均有均有a bq最小元最小元bB：aB,均有均有b aq阐明阐明q假设假设A的子集的子集B存在最大存在最大(小小)元素元素,那么最大那么最大(小小)元素是独一的元素是独一的q最大最大(小小)元能够不存在元能够不存在1157.7 偏序关系偏序关系例例:A1,2,3,4,5,6,R是整除关系是整除关系,哈斯图为哈斯图为125346 A中不存在最大元中不存在最大元1167.7 偏序关系偏序关系q极大极大(小小)元：设元：设是偏序集是偏序集,BAq极大元极大元bB：aB,如如b a,那么那么abq不存在不存在aB，b aq极小元极小元bB：aB,如如a b,那么那么abq不存在不存在aB，a bq

53、阐明阐明q极大元未必是最大元极大元未必是最大元q极大元未必是独一的极大元未必是独一的q假设假设B是有限集是有限集,那么那么B必存在极大元必存在极大元q最大元就是极大元最大元就是极大元1253461177.7 偏序关系偏序关系q例：以下哈斯图表示的偏序集能否有最大例：以下哈斯图表示的偏序集能否有最大(小小)元？能否有极大元？能否有极大(小小)元？元？ aaa,ba,bbba,b,ca,b,cb,cb,ccca,ca,c1187.7 偏序关系偏序关系q上上(下下)界：设界：设是偏序集是偏序集, BA, aAqB的上界的上界a：对每个：对每个bB,有有b aqB的下界的下界a：对每个：对每个bB,有

54、有a bq阐明阐明q上下界不一定独一上下界不一定独一1197.7 偏序关系偏序关系q例：例：, A=2,3,6,12,24,36q 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上上(下下)确界：设确界：设是偏序集是偏序集, BAq最小上界：最小上界：C=b|b为为B的上界的上界的最小元的最小元q最大下界：最大下界：D=b|

55、b为为B的下界的下界的最大元的最大元q阐明阐明qB的最小元一定是的最小元一定是B的下界，同时也是的下界，同时也是B的最大下的最大下界；界；B的最大元一定是的最大元一定是B的上界，同时也是的上界，同时也是B的最的最小上界小上界q最小上界或最大下界能够不存在最小上界或最大下界能够不存在q假设存在最小上界或最大下界，是独一的假设存在最小上界或最大下界，是独一的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 1

56、2126 6 6 6,1212,2424,3636 6 6 1227.7 偏序关系偏序关系q拓扑排序：给定一个非空有限的偏序集合拓扑排序：给定一个非空有限的偏序集合，构造出一个全序集合，构造出一个全序集合 ，使得每当使得每当a b有有a b，方法如下：，方法如下：q选取选取A的极小元的极小元a，使，使a是是列表表示列表表示中的第一个元素中的第一个元素q对子集对子集A-a反复这一过程，每次一个新的反复这一过程，每次一个新的极小元素被找到，它在极小元素被找到，它在的列表表示中的列表表示中成为下一个元素成为下一个元素q反复这一过程，直到反复这一过程，直到A的元素被抽完的元素被抽完1237.7 偏序关

57、系偏序关系q例：求以下偏序集对应的全序集例：求以下偏序集对应的全序集 1 12 23 34 46 68 812122424 1 13 32 26 64 48 812122424124第七章第七章 习题课习题课 l 有序对：有序对：l 由两个元素由两个元素x，y按给定顺序陈列组成的二元组合按给定顺序陈列组成的二元组合l 笛卡儿积：笛卡儿积：l 集合集合A中元素为第一元素，集合中元素为第一元素，集合B中元素为第二元素的有序对集中元素为第二元素的有序对集l 二元关系二元关系R：l 满足以下条件之一的集合：满足以下条件之一的集合：l 集合非空，且它的元素都是有序对集合非空，且它的元素都是有序对l 集合

58、为空集集合为空集l 从从A到到B的关系：的关系：l A，B是集合，是集合，AB的任何子集所定义的二元关系的任何子集所定义的二元关系l A上的关系：上的关系：l A=Bl 空关系，全域关系，恒等关系，包含关系空关系，全域关系，恒等关系，包含关系l 关系的表示法：关系的表示法：l 集合表达式、关系矩阵、关系图集合表达式、关系矩阵、关系图125第七章第七章 习题课习题课l 关系的八种运算：l 定义域：l 值域：l 域：l 逆：l 右复合：l 限制：l 像：l 幂：l R0 =A；Rn+1=RnRfldRdomRranR),(|RyxyxdomR),(|RyxxyranR,|,1RxyyxR),(|,

59、GytFtxtyxGFo,|RAx yxRyxA )(ARranAR126第七章第七章 习题课习题课l 关系运算的五种性质关系运算的五种性质: u自自 反：反：u反自反：反自反： u对对 称：称：u反对称：反对称：u传传 递：递： )(xRxXxx xRx)Xx(x )(yRxxRyXyXxyx )(yxyRxxRyXyXxyx )(xRzyRzxRyXzXyXxzyx 127第七章第七章 习题课习题课l 关系的三种闭包：关系的三种闭包：l 自反闭包：自反闭包：l r(R)=RAl 对称闭包：对称闭包：l s(R)=RR-1 l 传送闭包：传送闭包：l t(R)= R1R2 128第七章第七章

60、 习题课习题课l A上的等价关系：上的等价关系：l自反的；对称的；可传送的自反的；对称的；可传送的l等价类：等价类：l xR =y|yA xRyl商集：商集：l R的一切等价类构成的集合，的一切等价类构成的集合，l记为记为A/R：xR | x Al划分：划分：l A的非空子集族的非空子集族S=A1, A2, Am，满足：，满足：lSlxy(x, ySxyxy=)l A1A2 Am= Al A上的偏序关系与偏序集上的偏序关系与偏序集129根本要求根本要求l 熟练掌握关系的三种表示法熟练掌握关系的三种表示法 l 可以断定关系的性质，以及等价关系、偏序关系可以断定关系的性质，以及等价关系、偏序关系l