七章二元关系.ppt

《七章二元关系.ppt》由会员分享，可在线阅读，更多相关《七章二元关系.ppt（141页珍藏版）》请在三一办公上搜索。

1、第七章:二元关系,主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系本章与后面各章的关系是函数的基础是图论的基础,第七章:二元关系,第一节：有序对与笛卡儿积,引言,关系是数学中最重要的概念之一父子关系、师生关系等于、大于、小于关系直线的平行、垂直关系在计算机科学中有广泛应用人工智能程序设计数据库管理关系数据库,7.1 有序对与笛卡儿积,有序对（序偶）：由两个元素x，y(允许x=y)按给定顺序排列组成的二元组合符号化：x为第一元素，y为第二元素例：平面直角坐标系中的一个点的坐标1,3和3,1是表示平面上两个不同的点=当且仅当x=u，y=v如果xy，

2、那么x，yy，x,7.1 有序对与笛卡儿积,例：已知=，求x,y解：根据有序对等式定义，只需求解方程式 x+2=5 和 2x+y=4 得到：x=3,y=-2,7.1 有序对与笛卡儿积,笛卡尔积AB：集合A中元素为第一元素，集合B中元素为第二元素的有序对集AB=xA yB例：设集合A=a，b，c，B=0，1，求AB，BA，(AB)(BA)AB=，BA=，(AB)(BA)=,7.1 有序对与笛卡儿积,例：设集合A=1，2，求P(A)A解：P(A)=，1，2，1，2P(A)A=，,7.1 有序对与笛卡儿积,说明：如A，B均是有限集，A=m,B=n，则必有AB=mn,7.1 有序对与笛卡儿积,笛卡儿积

3、的性质：对于任意集合A，A=，A=一般不满足交换律，当A，B，AB时，AB BA一般不满足结合律，即当A，B，C均非空时，(AB)CA(BC),7.1 有序对与笛卡儿积,笛卡儿积的性质（续）：对任意三个集合A，B，C有（1）A(BC)=(AB)(AC)（2）A(BC)=(AB)(AC)（3）(BC)A=(BA)(CA)（4）(BC)A=(BA)(CA)（5）A C B D ABCD,7.1 有序对与笛卡儿积,证明：对任意三个集合A，B，C有 A(BC)=(AB)(AC)证明：A(BC)xA yBC xA(yB yC)(xA yB)(xA yC)AB AC(AB)(AC),7.1 有序对与笛卡儿

4、积,例：设A，B，C，D是任意集合，判断下列命题是否正确？ABAC BC不正确。取A，BC，AB=AC=A-(BC)=(A-B)(A-C)不正确。取A=B=1，C=2，A-(BC)=1-=1 而(A-B)(A-C)=1=,7.1 有序对与笛卡儿积,例：设A，B，C，D是任意集合，判断下列命题是否正确？A=B，C=D ACBD 正确。存在集合A使得A AA正确。取A=时，AAA,第七章:二元关系,第二节：二元关系,7.2 二元关系,关系是指事物之间（个体之间）的相互联系二元关系R：满足下列条件之一的集合集合非空，且它的元素都是有序对集合为空集定义：A，B是集合，AB的子集叫做从A到B的一个二元关

5、系例：A=0，1，B=1，2，3R1=，R2=R3=,7.2 二元关系,几类特殊关系：全域关系EAAA恒等关系IA|xA 空关系,7.2 二元关系,例：A=0,1,2EA=,恒等关系IA=,7.2 二元关系,包含关系A是一个集合,定义P(A)上的一个关系R=uP(A)，vP(A)，且uvA=a，b，P(A)=，a，b，AR=，例：A=2，3，4，5，6R=a是b的倍数R=，,7.2 二元关系,关系表示方法枚举法（直观法、列举法）xRy表示特定的序偶x，y R谓词公式表示法（暗含法）关系矩阵表示法关系图表示法,7.2 二元关系,关系表示方法枚举法（直观法、列举法）xRy表示特定的序偶x，y R谓

6、词公式表示法（暗含法）关系矩阵表示法关系图表示法,7.2 二元关系,关系矩阵表示法设集合A=a1,am,B=b1,bn,R是A到B的关系,则R的关系矩阵是一个mn阶的矩阵 MR=(rij)mn其中rij=1,当R ri j=0,当R如果R是A上的关系时,则其关系矩阵是一个方阵,7.2 二元关系,例：A=a,b,c,d,B=x,y,z,A=4，B=3,R=,则MR是43的矩阵,1 0 1MR=0 1 0 0 0 1 0 1 0,其中r13=1表示R,而r23=0,表示R,7.2 二元关系,关系表示方法枚举法（直观法、列举法）xRy表示特定的序偶x，y R谓词公式表示法（暗含法）关系矩阵表示法关系

7、图表示法,7.2 二元关系,关系图：A=a1,am，B=b1,bn结点：m+n个空心点分别表示a1,am和b1,bn有向边：如果R,则由结点ai向结点bj通一条有向弧,箭头指向bj自回路：R,则画一条以ai到自身的一条有向弧这样形成的图称为关系R的关系图,7.2 二元关系,例：A=2,3,4,5,6(1)R1=a是b的倍数(2)R2=(a-b)2A,第七章:二元关系,第三节：关系的运算,7.3 关系的运算,二元关系的定义域和值域定义域：值域：例X=1,2,3,4,5,6,Y=a,b,c,d,e,fR=,domR=1,2,3,4ranR=a,b,c,d,7.3 关系的运算,二元关系的逆关系R-1

8、就是将R中的所有有序对的两个元素交换次序成为R-1，故|R|=|R-1|说明R-1 的关系矩阵是R的关系矩阵的转置，即 MR-1=(MR)TR-1的关系图就是将R的关系图中的弧改变方向即可以,7.3 关系的运算,例：R=，R-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,7.3 关系的运算,例：R=，R-1=，,7.3 关系的运算,关系的右复合例A=1,2,3,4,5,B=3,4,5,C=1,2,3R=|x+y=6=,S=y-z=2=,RS=,7.3 关系的运算,例（续）,从而RS的

9、关系图,7.3 关系的运算,例：A=a,b,c,d,eR=,S=,RS=,SR=,RR=,SS=注意：RSSR,7.3 关系的运算,定义：R是二元关系，A是集合R在A上的限制 A在R下的像,A,RA,7.3 关系的运算,例：R=,求：,7.3 关系的运算,优先顺序：逆运算优先于其他运算关系运算优先于集合运算没有规定优先权的运算以括号决定运算顺序,7.3 关系的运算,定理：设F是任意的关系，则(F-1)-1=FdomF-1=ranF,ranF-1=domF,7.3 关系的运算,定理：设F，G，H是任意的关系(FG)H=F(GH)(FG)-1=G-1F-1证明：(FG)-1 FG t(F G)t(

10、G-1 F-1)G-1F-1,7.3 关系的运算,例R=,S=,RS=,(RS)-1=,R-1=,S-1=,S-1R-1=,7.3 关系的运算,定理:设R为A上关系，则 RIAIARR定理:R(ST)=RSRTR(ST)RSRT(ST)X=SXTX(ST)XSXTX,7.3 关系的运算,证明 R(ST)=RSRT R(ST)y(RST)y(R(ST)y(RS)(RT)y(RS)y(RT)RS RT RSRT,7.3 关系的运算,证明 R(ST)RSRT R(ST)t(RST)t(RST)t(RS)(RT)t(RS)t(RT)RSRT RSRT,7.3 关系的运算,定理:R(AB)=RARBRA

11、B=RARBR(AB)=RARBRAB RARB,7.3 关系的运算,定理:RAB RARB证明：yRAB x(RxAB)x(RxAxB)x(RxA)(R xB)x(RxA)x(R xB)yRAyRB yRARB,7.3 关系的运算,R的n次幂记为RnR0=ARn+1=RnR定理:设R是集合A上的关系，m,nNRmRn=Rm+n(Rm)n=Rmn证明思路：使用归纳法并利用复合关系的结合律,7.3 关系的运算,例R=,R0=,R1=RR2=,R3=R2R=,R4=R3R=,R5=R4R=,7.3 关系的运算,从关系图来看关系的n次幂 R：1 2 3 4 5R2就是所有在R中通过二条弧连接的点，则

12、在R2这两点间直接有条弧。1 2 3 4 5R3,R4,7.3 关系的运算,定理：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,7.3 关系的运算,定理：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,7.3 关系的运算,证

13、明：对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+i,7.3 关系的运算,定理：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,7.3 关系的运算,证明：若qt，则RqS。若qt，则存在自然数k，i使得 q=s+kp+i其中0 ip

14、-1，所以 Rq=Rs+kp+i=Rs+i由于0 ip-1 s+i s+p-1=s+t-s-1=t-1,第七章:二元关系,第四节：关系的性质,7.4 关系的性质,自反性aA，有R，则R为A上的自反关系反自反性aA，有 R，R为A上的反自反关系例 A=a,b,cR1=,R2=,R3=,7.4 关系的性质,例：R是I+上的整除关系，则R具有自反性证明：xI+，x能整除x，R，R具有自反性例：R是I上的同余关系，则R具有自反性证明：xI，(x-x)/k=0I,x与x同余RR具有自反性其它，关系，均是自反关系,7.4 关系的性质,例：N上的互质关系是反自反关系证明：xN，x与x是不互质的，R，R具有反

15、自反关系实数上的,关系,均是反自反关系,7.4 关系的性质,关系矩阵的特点？自反关系的关系矩阵的对角元素均为1反自反关系的关系矩阵的对角元素均为0关系图的特点？自反关系的关系图中每个顶点都有环反自反关系的关系图中每个顶点都没有环定理：R是A上的关系，则：R是自反关系的充要条件是IARR是反自反关系的充要条件是RIA=,7.4 关系的性质,对称关系Ra,bA,如果R,则必有R 例R1,R1是对称的R2,R2是对称的R3,R3不是对称的,7.4 关系的性质,关系矩阵特点？对称关系的关系矩阵是对称矩阵关系图特点？如果两个顶点之间有边，一定是一对方向相反的边（无单边）定理：R在A上对称当且仅当R=R-

16、1证明：必要性RRR-1充分性RR-1R,7.4 关系的性质,反对称关系Ra,bA,如果R且R,则必有aba,bA,如果ab,R,则必有R例:Aa,b,cR,S,T,R,S是反对称的,T不是反对称的,7.4 关系的性质,例:实数集合上关系是反对称关系x,y实数集,如xy,且xy,则yx不成立例：,关系,均是反对称关系反对称关系矩阵和关系图特点？若rij=1，且ij，则rji=0如果两个顶点之间有边，一定是一条有向边（无双向边）定理：R在A上反对称当且仅当RR-1 IA,7.4 关系的性质,传递关系a,b,cA,如果R,R,必有R例R1,是传递关系R2,是传递关系R3,不是传递关系,7.4 关系

17、的性质,例:整除关系DI是I上的传递关系x,y,zI,如DI,DI,即x能整除y,且y能整除z,则必有x能整除z,DI例:P(A)上的包含关系具有传递性若uv,vw,则必有uw例:实数集上的关系具有传递性若xy,yz必有xz,7.4 关系的性质,传递关系关系图特点？如果结点a能通过有向弧组成的有向路径通向结点x,则a必须有有向弧直接指向x,否则R就不是传递的例：R=,定理：R在A上传递当且仅当RR R,7.4 关系的性质,自 反：反自反：对 称：反对称：传 递：,7.4 关系的性质,设A是集合，R1和R2是A上的关系若R1，R2是自反和对称的，则R1R2也是自反的和对称的若R1和R2是传递的，

18、则R1R2也是传递的,7.4 关系的性质,设A是集合，R1和R2是A上的关系若R1，R2是自反的和对称的，则R1R2也是自反的和对称的证明：R1，R2是自反的 IA R1，IA R2所以IA R1R2R1，R2是对称的 R1=R1-1和R2=R2-1所以(R1R2)-1=R1-1R2-1=R1R2,7.4 关系的性质,例：X=1,2,3，判断关系的性质R1=,R2=,反对称,反自反反对称可传递,7.4 关系的性质,R3=,R4=Ex 自反，对称，可传递的,自反，对称，反对称，可传递的,7.4 关系的性质,X=1,2,3,R5=反自反的，对称的，反对称的，可传递的若X=，X上的空关系自反的，反自

19、反的，对称的，反对称的，可传递的,第七章:二元关系,第五节：关系的闭包,7.5 关系的闭包,定义：R是非空集合A上的关系,若A上另外有一个关系R满足如下三条：R是自反的(对称的，传递的）RRA上任何一个满足以上两条的关系R”，均有RR”，称关系R为R的自反(对称,传递)闭包,记作r(R)(s(R),t(R),7.5 关系的闭包,解释R是在R的基础上添加有序对添加元素的目的是使R具有自反性(对称性,传递性)添加后使之具有自反性(对称性,传递性)的所有关系中R是最小的一个,7.5 关系的闭包,例A=a,b,c，R=,自反闭包r(R),对称闭包s(R),传递闭包t(R),7.5 关系的闭包,定理：R

20、是非空集合A上的关系,则r(R)=RA证明:RRA，RA是自反的设R”满足RR”,R”是自反的RA则R或A 如R,由RR”知R”如A,由R”的自反性知R”均有R”RAR”,7.5 关系的闭包,定理:设R是非空集A的关系,则s(R)=RR-1 证明:RRR-1满足定义第2条RR-1RR-1R-1RRR-1 RR-1是对称的,7.5 关系的闭包,如RR”,且R”是对称的RR-1R或R-1如R,由RR”,则R”如R-1,则R,则R”因R”对称R”,RR-1R”满足定义第3条,7.5 关系的闭包,例:设A=1,2,3,A上的关系R如图,求r(R),s(R)解:R=,r(R)=RA=,s(R)=RR-1

21、=,7.5 关系的闭包,定理:设R是非空集合A上的关系,则t(R)=R1R2 证明：首先证明R1R2 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)R1R2即证R1R2传递推论:设A是非空有限集，R是集合A上的二元关系，则存在正整数n，使得t(R)=RR2 Rn,7.5 关系的闭包,例 A=a,b,c,dR=,S=,求t(R),t(S)解:R2=,R3=t(R)=R,S2=,S3=,S4=t(S)=S,7.5 关系的闭包,给定关系R，r(R)，s(R)，t(R)的关系矩阵分别为M

22、，Mr，Ms，Mt，那么：Mr=M+EMs=M+MMt=M+M2+M3+,7.5 关系的闭包,关系图分别为G，Gr，Gs，Gt，那么：考察G的每个顶点，如果没有环就加上一个环，最终得到的是Gr考察G的每一条边，如果有一条从xi到xj的单向边，则在G中加一条xj到xi的反方向边，最终得到Gs考察G的每个顶点xi，找出从xi出发的所有2步，3步，n步长的路径。设路径的终点为xj1，xj2，xjk。如果没有从xi到xjl的边，就加上这条边，最终得到Gt,7.5 关系的闭包,定理：设A是一集合，R是A上的二元关系，则有：R是自反的当且仅当r(R)RR是对称的当且仅当s(R)RR是可传递的当且仅当t(R

23、)RR是自反的当且仅当r(R)R证明：Rr(R)。由自反闭包定义，r(R)R。,7.5 关系的闭包,定理：设A是集合，R1和R2是A上的二元关系，R1R2，则有：r(R1)r(R2)s(R1)s(R2)t(R1)t(R2)r(R1)r(R2)证明：r(R1)=R1A，r(R2)=R2A,7.5 关系的闭包,定理：设X是一集合，R是X上的二元关系，则有：若R是自反的，则s(R),t(R)也自反若R是对称的，则r(R),t(R)也对称若R是可传递的，则r(R)也可传递,7.5 关系的闭包,定理：设X是一集合，R是X上的二元关系，则有：若R是对称的，则t(R)也对称证明：归纳法证明若R是对称，则Rn

24、也对称n=1，显然成立假设Rn对称，对任意 Rn+1 t(RnR)t(RnR)RRn Rn+1,7.5 关系的闭包,定理：设X是一集合，R是X上的二元关系，则有：若R是对称的，则t(R)也对称证明：RRn Rn+1 任取，有 t(R)n(Rn)n(Rn)t(R),7.5 关系的闭包,若R是传递的，s(R)不一定是传递的反例：R=,，R是传递的 s(R)=,s(R)不是传递的,第七章:二元关系,第六节：等价关系与划分,7.6 等价关系与划分,等价关系：非空集合A上的关系，满足：自反的对称的可传递的例实数(或I、N集上)集合上的“=”关系全集上集合的相等关系命题集合上的命题等价关系,7.6 等价关

25、系与划分,例：设A=1,2,3,4,5,6,7R=|x,yA(x-y)可被3整除试证明R是等价关系解：(1)R=，,7.6 等价关系与划分,(2)R的关系矩阵,R满足自反、对称和可传递的,7.6 等价关系与划分,等价类：设R是非空A集合上的等价关系，对于任何xA，令：xR=y|yA xRyxR是由xA生成的R等价类x为等价类xR的表示元素,7.6 等价关系与划分,讨论等价类xR是一个集合，xR A(xR是A的子集)xR中的元素是在A中，所有与x具有等价关系R的元素所组成的集合在等价关系中的关系图中，一个最大连通子图中的点就是一个等价类,7.6 等价关系与划分,例：A=a,b,c,dR=，aR=

26、a,b=bR cR=c,d=dR,7.6 等价关系与划分,例：设A=NR=|xAyA(x-y)可被3整除等价类0R=0，3，6，9 1R=1，4，7，10 2R=2，5，8，11,7.6 等价关系与划分,定理 设A是一个集合，R是A上的等价关系，xRy当且仅当x=y证明：充分性，因为xx=y,即xy，所以xRy。必要性，已知xRy，考虑x的任意元素z，有zRx。根据R的传递性，有zRy，因此zy。证明xy。类似可证明yx，所以x=y,7.6 等价关系与划分,定理：设A是一个集合，R是A上的等价关系，对于所有x,yA，或者x=y，或者 x y=证明：只需证明如果xRy，则xy=反证法：假设xy，

27、则zxy R R R(矛盾!),7.6 等价关系与划分,定理：设R是集合A上的等价关系，则 A=x|xA证明：首先易证x|xA A 其次，对任意yA yA yy yA yx|xA 所以：A x|xA,7.6 等价关系与划分,商集：R是A上的等价关系，R的所有等价类构成的集合记为A/R：xR|x A例：A为全班同学的集合，|A|=n，(nN)按指纹的相同关系R1是一个等价关系A/R1=x1R1,xnR1 同姓关系R2是一等价关系A/R2=张，李，,7.6 等价关系与划分,划分：给定一非空集合A，A的一个划分为非空子集族S=A1,A2,Am，满足：Sxy(x,ySxyxy=)A1A2 Am=A,7

28、.6 等价关系与划分,例：A=a,b,c,下列哪些Ai为A的一个划分？A1=a,b,c A2=a,c,bA3=a,a,b,cA4=a,b,c,A5=a,a,b,c,7.6 等价关系与划分,等价关系与划分有一一对应关系划分到等价关系转化：A是一非空集合，S是A的一个划分，下述关系必定是一个等价关系R=|x,y A x,y在S的同一划分等价关系到划分的转化：设A是非空集合，R是A上的等价关系。R的商集是A的划分,7.6 等价关系与划分,例：A=a,b,c,d,eS=a,b,c,d,e 对应划分S的等价关系为 R=a,ba,bccd,ed,e=,第七章:二元关系,第七节：偏序关系,7.7 偏序关系,

29、次序在现实生活中常见：小于，包含等研究序理论的动机：研究一般次序关系推导出一般序关系的性质这些关系可以应用于所有特定的序关系,7.7 偏序关系,偏序关系R(记作)自反性:aA，有R反对称性:a,bR,如果R且R,则必有ab传递性:a,b,cA,如果R,R,必有R例:偏序关系Aa,b,cR,7.7 偏序关系,例：A是非零自然数集,是A上的整除关系。aA,a能整除a 具有自反性a,bA,如a能整除b,且b能整除a,则ab 具有反对称性 a,b,cA,如a能整除b,b能整除c,则a能整除c,具有传递性是A上的偏序关系,7.7 偏序关系,小于：ababab可比：a与b可比 abba可比不同于等于例：A

30、=1，2，3，是A上的整除关系1，3可比全序关系R：R是A上的偏序关系,满足：a,bA,a与b可比 例：实数上的,关系是全序关系,7.7 偏序关系,哈斯图得名于德国数学家Helmut Hasse用来表示有限偏序集的一种数学图表偏序集：,7.7 偏序关系,覆盖：，b覆盖a如果 ab，不存在cA，acb哈斯图思路：所有结点的自回路均省略省略所有弧上的箭头,适当排列A中元素的位置,如ab,则a画在b的下方如ab,bc,则必有ac,a到b有边,b到c有边,则a到c的无向弧省略条件2，3等于说如果b覆盖a,则画一条从a到b的弧线，否则不画,7.7 偏序关系,例：画出下列偏序集的哈斯图。R整除=,7.7

31、偏序关系,例：A=a,b,c,包含关系R是P(A)上的偏序关系,哈斯图如下:P(A)=,a,b,c,a,b,a,c,b,c,a,b,c,7.7 偏序关系,最小(大)元：设是偏序集,集合BA最大元bB：aB,均有ab最小元bB：aB,均有ba说明如果A的子集B存在最大(小)元素,则最大(小)元素是唯一的最大(小)元可能不存在,7.7 偏序关系,例:A1,2,3,4,5,6,R是整除关系,哈斯图为,A中不存在最大元,7.7 偏序关系,极大(小)元：设是偏序集,BA极大元bB：aB,如ba,则ab不存在aB，ba极小元bB：aB,如ab,则ab不存在aB，ab说明极大元未必是最大元极大元未必是唯一的

32、如果B是有限集,则B必存在极大元最大元就是极大元,7.7 偏序关系,例：下列哈斯图表示的偏序集是否有最大(小)元？是否有极大(小)元？,7.7 偏序关系,上(下)界：设是偏序集,BA,aAB的上界a：对每个bB,有baB的下界a：对每个bB,有ab说明上下界不一定唯一,7.7 偏序关系,例：,A=2,3,6,12,24,36 B:2,3,2,3,6,6,12,6,12,24,36,7.7 偏序关系,上(下)确界：设是偏序集,BA最小上界：C=b|b为B的上界的最小元最大下界：D=b|b为B的下界的最大元说明B的最小元一定是B的下界，同时也是B的最大下界；B的最大元一定是B的上界，同时也是B的最

33、小上界最小上界或最大下界可能不存在若存在最小上界或最大下界，是唯一的,7.7 偏序关系,例:A，R整除,A=2,3,6,12,24,36 B:2,3,2,3,6,6,12,6,12,24,36,7.7 偏序关系,拓扑排序：给定一个非空有限的偏序集合，构造出一个全序集合，使得每当ab有ab，方法如下：选取A的极小元a，使a是列表表示中的第一个元素对子集A-a重复这一过程，每次一个新的极小元素被找到，它在的列表表示中成为下一个元素重复这一过程，直到A的元素被抽完,7.7 偏序关系,例：求下列偏序集对应的全序集,1,2,3,4,6,8,12,24,1,3,2,6,4,8,12,24,第七章 习题课,

34、有序对：由两个元素x，y按给定顺序排列组成的二元组合笛卡儿积：集合A中元素为第一元素，集合B中元素为第二元素的有序对集二元关系R：满足下列条件之一的集合：集合非空，且它的元素都是有序对集合为空集从A到B的关系：A，B是集合，AB的任何子集所定义的二元关系A上的关系：A=B空关系，全域关系，恒等关系，包含关系关系的表示法：集合表达式、关系矩阵、关系图,第七章 习题课,关系的八种运算：定义域：值域：域：逆：右复合：限制：像：幂：R0=A；Rn+1=RnR,第七章 习题课,关系运算的五种性质:,自 反：反自反：对 称：反对称：传 递：,第七章 习题课,关系的三种闭包：自反闭包：r(R)=RA对称闭包

35、：s(R)=RR-1 传递闭包：t(R)=R1R2,第七章 习题课,A上的等价关系：自反的；对称的；可传递的等价类：xR=y|yA xRy商集：R的所有等价类构成的集合，记为A/R：xR|x A划分：A的非空子集族S=A1,A2,Am，满足：Sxy(x,ySxyxy=)A1A2 Am=AA上的偏序关系与偏序集,基本要求,熟练掌握关系的三种表示法 能够判定关系的性质，以及等价关系、偏序关系掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念计算AB,dom R,ranR,fldR,R1,RS,Rn,r(R),s(R),t(R)求等价类和商集A/R给定A的划分，求出 所

36、对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系,练习1,1设A=1,2,3,R=|x,yA且x+2y 6，S=,求:(1)R的集合表达式(2)R1(3)dom R,ran R,fld R(4)RS,R3(5)r(R),s(R),t(R),解答,(1)R=,(2)R1=,(3)domR=1,2,3,ranR=1,2,fldR=1,2,3(4)RS=,R3=,(5)r(R)=,s(R)=,t(R)=,练习2,2设A=1,2,3,4，在AA上定义二元关系R：,R x+y=

37、u+v，求R导出的划分.,AA=,根据 中的 x+y=2,3,4,5,6,7,8 将A划分成等价类：A/R=,3设R是Z上的模 n 等价关系,即 xy x y(modn),试给出由R确定的Z的划分.,解 设除以 n 余数为 r 的整数构成等价类 r，则 r=kn+r|kZ,r=0,1,n1=r|r=0,1,n1,练习3,图11,练习4,4设偏序集 的哈斯图如图所示.(1)写出A和R的集合表达式(2)求该偏序集中的极大元、极小元、最大元、最小元,解：(1)A=a,b,c,d,e R=,IA(2)极大元和最大元是a,极小元是d,e；没有最小元.,练习5,5设R是A上的二元关系，设 S=|c(RR)

38、.证明如果R是等价关系，则S也是等价关系。,证：R是A上的等价关系.(1)证自反 任取x,xA R x(RR)S(2)证对称 任取,S c(RR)c(RR)S(3)证传递 任取,S S c(RR)d(RR)R R S,6设偏序集和，定义AB上二元关系T:T xRu ySv 证明T为偏序关系.,证：(1)自反性 任取,AB xAyB xRxySy T(2)反对称性 任取,TT xRu ySv uRx vSy(xRu uRx)(ySv vSy)x=u y=v=(3)传递性 任取,TT xRu ySv uRw vSt(xRu uRw)(ySv vSt)xRw ySt T,练习6,关系性质的证明方法,

39、1.证明R在A上自反 任取x,xA.R 前提 推理过程 结论2.证明R在A上对称 任取，R.R 前提 推理过程 结论,3.证明R在A上反对称 任取，RR.x=y 前提 推理过程 结论4.证明R在A上传递 任取,，RR.R 前提 推理过程 结论,关系性质的证明方法,7R,S为A上的关系，证明 RS 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,练习7,数学归纳法（主要用于幂运算）证明中用到关系运算的定义和公式,如：xdomR y(R)yranR x(R)R R1 R S t(RS)RA xA R yRA x(xA R)r(R)=RIA s(R)=RR1 t(R)=RR2,关系等式或包含式的证明方法,作业,413152025263646,