离散数学二元关系.ppt

2023/5/24,1,第四章 二元关系,主要内容：关系的概念及表示方法 关系的性质 关系的运算:关系的复合，求逆关系，关系的闭包。三种关系:等价关系，相容关系，次序关系。,2023/5/24,2,一、序偶与有序n元组1.定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作；称x、y分别为序偶的第一，第二元素。注意，序偶与集合x,y不同：序偶：元素x和y有次序；集合x,y：元素x和y的次序无关紧要。,4-1 序偶与集合的笛卡尔积,2023/5/24,3,2.定义：设，是两个序偶，如果x=u和y=v则称和相等，记作=。3.定义：有序3元组是一个序偶,其第一个元素也是个序偶。有序3元组,c可以简记成，但不是有序3元组。,2023/5/24,4,4.定义：有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,记作,xn。且可以简记成。5.定义=(x1=y1)(x2=y2)(xn=yn),2023/5/24,5,例如“斗兽棋”的16颗棋子，,设：A=红,蓝 B=象,狮,虎,豹,狼,狗,猫,鼠每个棋子可以看成一个序偶，斗兽棋可记成集合AB：,2023/5/24,6,1.定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作AB，即 AB=|xAyB 例1 设A=0,1，B=a,b，求AB，BA，AA。解：AB=,BA=,AA=,可见 ABBA所以，集合的笛卡尔积运算不满足交换律。,2023/5/24,7,另外(AB)C=,c|AB cC A(BC)=|aA BC,因 不是有序三元组,所以(AB)CA(BC)。故也不满足结合律。,2.性质 1)如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=mn。证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。2)A=B=,2023/5/24,8,3)对和满足分配律。设A,B,C是任意集合，则 A(BC)=(AB)(AC)；A(BC)=(AB)(AC)；(AB)C=(AC)(BC)；(AB)C=(AC)(BC)；证明：任取A(BC)xA yBC xA(yByC)(xA yB)(xAyC)ABAC(AB)(AC)所以式成立。（其余可以类似证明）,2023/5/24,9,4)若C,则 AB(ACBC)(CACB)证明：充分性：设AB，求证 ACBC 任取AC xAyC xByC(因AB)BC 所以,ACBC。必要性：若C,由ACBC 求证 AB 取C中元素y,任取 xA xAyC AC BC(由ACBC)xByC xB 所以,AB。所以 AB(ACBC)类似可以证明 AB(CACB)。,2023/5/24,10,5)设A、B、C、D为非空集合，则 ABCDACBD证明：首先,由ABCD 证明ACBD 任取xA，任取yB，所以 xAyBAB CD(由ABCD)xCyD 所以,ACBD。其次,由AC，BD 证明ABCD 任取AB xAyB xCyD(由AC，BD)CD 所以,ABCD 证毕。,2023/5/24,11,6)约定(A1A2)An-1)An)=A1A2An 特别 AAA=An 设R是实数集合，则R2表示笛卡尔坐标平面，R3表示三维空间，Rn表示n维空间。3.应用 1)令A1=x|x是学号 A2=x|x是姓名 A3=男,女 A4=x|x是出生日期 A5=x|x是班级 A6=x|x是籍贯 则A1A2A3 A4A5 A6中一个元素：这就是学生档案数据库的一条信息，所以学生的档案就是A1A2A3 A4A5 A6的一个子集。,2023/5/24,12,2)令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z 是英文字母表 一个英文单词可以看成有序n元组：如 at=,boy=,data=,computer=于是可以说：atA2,boyA3,dataA4,computerA8,所以英文词典中的单词集合可以看成是 AA2An 的一个子集。作业 P105,2023/5/24,13,4-2 关系及其表示法,相关 按照某种规则，确认了二个对象或多个对象之间有关系，称这二个对象或多个对象是相关的。,例1：大写英文字母与五单位代码的对应关系R1:令=A,B,C,D,Z=30,23,16,22,21是五单位代码集合=11000,10011,01110,10010,10001R1=,.,2023/5/24,14,例2：令=1,2,3,4,A中元素间的关系R2：R2=,AA,关系的定义定义1:设A、是集合，如果AB，则称R是一个从A到B的二元关系。如果 RAA，则称R是A上的二元关系。二元关系简称为关系。定义2:任何序偶的集合，都称之为一个二元关系。如:R=,基本概念,2023/5/24,15,R xRy 也称之为x与y有关系。,R xRy 也称之为x与y没有关系。,例3.R是实数集合，R上的几个熟知的关系,从例3中可以看出关系是序偶(点)的集合(构成线、面)。,2023/5/24,16,关系的定义域与值域定义域(domain)：设RAB，由所有R的第一个元素组成的集合，称为R的定义域。记作dom R，即 dom R=x|y(R)值域(range)：设RAB，由所有R的第二个元素组成的集合，称为R的值域。记作ran R，即 ran R=y|x(R)令：R1=,dom R1=1,2,3,4 ran R1=1,2,3,4,2023/5/24,17,枚举法：即将关系中所有序偶一一列举出，写在大括号内。如R=,。谓词公式法：即用谓词公式表示序偶的第一元素与第二元素间的关系。例如 R=|xR时，从x到y引一条有向弧(边)。这样得到的图形称为R的关系图。,关系的表示方法,2023/5/24,18,例 设A=1,2,3,4,B=a,b,c,R1 AB,R2 AA，R1=,R2=,R1、R2的关系图如下：,2023/5/24,19,矩阵表示法：设A=a1,a2,am，B=b1,b2,bn是个有限集，RAB，定义R的mn阶矩阵 MR=(rij)mn，其中,例：R1=,R2=,2023/5/24,20,空关系：因为AB，(或AA)，所以也是一个从A到B(或A上)的关系，称之为空关系。即无任何元素的关系，它的关系图中只有结点,无任何边；它的矩阵中全是0。完全关系(全域关系)：AB(或AA)本身也是一个从A到B(或A上)的关系，称之为完全关系。即含有全部序偶的关系。它的矩阵中全是1。,三个特殊关系,2023/5/24,21,A上的恒等关系IA：IAAA,且IA=|xA为A上的恒等关系。例如 A=1,2,3,则IA=,A上的、完全关系及IA的关系图及矩阵如下：,2023/5/24,22,由于关系就是集合，所以集合的、-、和运算对关系也适用。例如 A是学生集合，R是A上的同乡关系，S是A上的同姓关系，则RS：或同乡或同姓关系RS：既同乡又同姓关系R-S：同乡而不同姓关系RS：同乡而不同姓,或同姓而不同乡关系 R：不是同乡关系,这里R=(AA)-R作业 P109、c)d),关系的集合运算,2023/5/24,23,本节中所讨论的关系都是集合A中的关系。关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。一.自反性定义:设R是集合A中的关系，如果对于任意xA都有R(xRx)，则称R是A中自反关系。即 R是A中自反的关系x(xAxRx)例如：在实数集合中,“”是自反关系，因为，对任意实数x，有x x.,4-3 关系的性质,2023/5/24,24,从关系有向图看自反性:每个结点都有环。从关系矩阵看自反性：主对角线都为1。,令A=1,2,3，确定以下八个关系中哪些是自反的？,2023/5/24,25,二.反自反性定义：设R是集合A中的关系，如果对于任意的xA都有R，则称R为A中的反自反关系。即 R是A中反自反的x(xAR)从关系有向图看反自反性:每个结点都无环。从关系矩阵看反自反性：主对角线都为0。如 实数的大于关系，父子关系是反自反的。注意：一个不是自反的关系，不一定就是反自反 的，如前边R6、R7非自反,也非反自反。,2023/5/24,26,R2、R5、R8、均是反自反关系。,观察下图：,2023/5/24,27,三.对称性定义:R是集合A中关系,若对任何x,yA,如果有xRy,必有yRx,则称R为A中的对称关系。R是A上对称的 xy(xAyAxRy)yRx)从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。从关系矩阵看对称性：以主对角线为对称的矩阵。例 邻居关系和朋友关系是对称关系。,2023/5/24,28,R3、R4、R6、R8均是对称关系。,2023/5/24,29,四.反对称性定义:设R为集合A中关系,若对任何x,yA,如果有xRy,和yRx,就有x=y,则称R为A中反对称关系。,由R的关系图看反对称性：两个不同的结点之间最多有一条边。从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。另外对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒等关系。,2023/5/24,30,上面R1、R2、R4、R5、R8均是反对称关系。R4、R8既是对称也是反对称的。,2023/5/24,31,五.传递性定义:R是A中关系，对任何x,y,zA,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。即R在A上传递xyz(xAyAzAxRyyRz)xRz)例 实数集中的、，集合、是传递的。从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T，即是传递的。即若R与R有一个是F时(即定义的前件为假)，R是传递的。,例如 A=1,2,下面A中关系R是传递的。通过带量词的公式在论域展开式说明R在A上传递,xyz(xAyAzAxRyyRz)xRz)xyz(xRyyRz)xRz)(为了简单做些删改)yz(1RyyRz)1Rz)yz(2RyyRz)2Rz)(z(1R11Rz)1Rz)z(1R22Rz)1Rz)(z(2R11Rz)2Rz)(z(2R22Rz)2Rz)(1R11R1)1R1)(1R11R2)1R2)(1R22R1)1R1)(1R22R2)1R2)(2R11R1)2R1)(2R11R2)2R2)(2R22R1)2R1)(2R22R2)2R2)(FF)F)(FT)T)(TF)F)(TF)T)(FF)F)(FT)F)(FF)F)(FF)F)T,2023/5/24,33,以上R1、R3、R4、R5、R8均是传递的关系。,本节要求：1.准确掌握这五个性质的定义。2.熟练掌握五个性质的判断和证明。R是A中自反的x(xAxRx)R是A中反自反的x(xAR)R是A上对称的xy(xAyAxRy)yRx)R是A上反对称的xy(xAyAxRyyRx)x=y)xy(xAyAxyxRy)y x)R在A上传递xyz(xAyAzAxRyyRz)xRz)注意 性质表达式的前件为F时此表达式为T，即R是满足此性质的。(自反和反自反性除外),2023/5/24,35,2023/5/24,36,下面归纳这八个关系的性质：Y-有 N-无,2023/5/24,37,2023/5/24,38,练习1:令I是整数集合，I上关系R定义为：R=|x-y可被3整除，求证R是自反、对称和传递的。证明：自反性：任取xI,因 x-x=0,0可被3整除,所以有R,故R自反。对称性：任取x,yI,设R,由R定义得 x-y可被3整除,即x-y=3n(nI)，y-x=-(x-y)=-3n=3(-n),-nN R,R是对称的。传递性:任取x,y,zI,设xRy,yRz,由R定义得 x-y=3m,y-z=3n(m.nI)x-z=(x-y)+(y-z)=3m+3n=3(m+n),m+nN 所以xRz,所以R传递。证毕,2023/5/24,39,练习2：设R是集合A上的一个自反关系,求证：R是对称和传递的，当且仅当和 在R中,则有也在R中。证明：必要性 已知R是对称和传递的。设R 又R，(要证出 R)因R对称的故R,又已知R 由传递 性得R。所以有如果和在R 中,则有也在R中。充分性 已知任意 a,b,cA，如和在 R中,则有也在R中。,2023/5/24,40,先证R对称 任取 a,bA 设R，(要证出 R)因R是自反的,所以R，由R且R，根据已知条件得R，所以R是对称的。再证R传递 任取 a,b,cA 设R，R。(要证出R)由R是对称的,得R，由R且R，根据已知条件得R，所以R是传递的。作业 第113页、,2023/5/24,41,4-4 关系的复合,下面介绍由两个关系生成一种新的关系，即关系的复合运算。例如，有3个人a,b,c，A=a,b,c，R是A上兄妹关系，S是A上母子关系，RS即a是b的哥哥,b是a的妹妹;b是c的母亲，c是b的儿子。则a和c间就是舅舅和外甥的关系,记作 RS,称它是R和S的复合关系。,2023/5/24,42,1.定义:设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RS。定义为：RS=|xXzZ y(yY RS)显然，RS 是从X到Z的关系。2.复合关系的计算方法(俗称过河拆桥法)A=1,2,3 B=1,2,3.4 C=1,2,3,4,5RAB SBC枚举法R=,S=,则 RS=,2023/5/24,43,有向图法,关系矩阵法令A=a1,a2,am B=b1,b2,bn C=c1,c2,ct RAB SBC,2023/5/24,44,2023/5/24,45,谓词公式法设I是实数集合，R和S都是I上的关系，定义如下：R=|y=x2+3x S=|y=2x+3,所以 RS=|y=2x2+6x+3,三.性质 关系复合运算不满足交换律，但是1.满足结合律:RAB SBC TCD 则,2023/5/24,46,b(bBR(S T)b(bBRc(cCST)bc(bBR(cCST)cb(cC(bBRST)c(cCb(bBRS)T)c(cC(R S)T),所以,可以用下图形象表示:,证明：任取,2023/5/24,47,2.RAB SBC TBC,证明 任取R(ST)b(bBRST)b(bBR(ST)b(bBRS)(bBRT)b(bBRS)b(bBRT)R SR T(R S)(R T)所以R(ST)=(R S)(R T),2023/5/24,48,证明 任取R(ST)b(bBRST)b(bBR(ST)b(bBRS)(bBRT)b(bBRS)b(bBRT)R S R T(R S)(R T)所以 R(ST)(R S)(R T)x(A(x)B(x)xA(x)xB(x),2023/5/24,49,3.R是从A到B的关系，则,验证:,令A=1,2,3,B=a,b,c,d,从这两个图看出它们的复合都等于R。,2023/5/24,50,4.关系的乘幂 令R是A上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即,例如R是A上关系，如上图所示,可见R2,表明在R图上有从a到c有两条边的路径:abc;R3,表明在R图上有从a到d有三条边的路径:abcd。.如果Rk,表明在R图上有从x到y有k条边(长为k)的路径(x,yA)。,有,(m,n为非负整数),2023/5/24,51,4-5 逆关系,一.定义 R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作RC，或 R-1。RC=|R RC R二.计算方法 1.R=,RC=,2023/5/24,52,2.RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。3.RC的矩阵 M=(MR)T 即为R矩阵的转置。如,三.性质令R、S都是从X到Y的关系，则 1.(RC)C=R 2.(RS)C=RCSC。3.(RS)C=RCSC。4.(RS)C=RCSC。,2023/5/24,53,证明1：任取(RS)C，则(RS)C RS RS RCSC RCSC所以(RS)C=RCSC，其它类似可证。5.RS RC SC。证明：充分性，已知RC SC，则任取RRC SC S RS 必要性，已知R S，则任取RC R S SC RCSC,2023/5/24,54,6.(R)C=RC证明:任取(R)C RR RC RC(R)C=RC,7.令R是从X到Y的关系，S是Y到 Z的关系，则(R S)C=SC RC。(注意RC SC)证明：任取(R S)CR Sy(yYRS)y(yYSCRC)SC RC 所以(R S)C=SC RC,2023/5/24,55,8.R是A上关系，则 R是对称的，当且仅当 RC=R R是反对称的，当且仅当 RRC IA。证明：充分性，已知 RC=R(证出R对称)任取x,yA 设R,则RC,而RC=R 所以有R，所以R对称。必要性，已知R 对称，(证出RC=R)先证RCR，任取RC,则R,因R对称所以有R，所以RCR。再证R RC，任取R,因R对称，所以有R，则RC,所以RRC。最后得RC=R。,2023/5/24,56,证明 充分性，已知RRC IA，(证出R反对称)任取x,yA 设R 且R，RRRRC，RRC IA(因RRC IA)x=y 所以R反对称。必要性，已知R反对称，(证出RRC IA)任取RRC RRCRRC RRx=y(因R反对称)IA 所以RRC IA。,作业：第118页a)b)、,2023/5/24,57,4-6 关系的闭包运算,关系的闭包是通过关系的复合和求逆构成的一个新的关系。这里要介绍关系的自反闭包、对称闭包和传递闭包。,一.例子 给定 A中关系R，如图所示，求A上另一个关系R，使得它是包含R的“最小的”(序偶尽量少)具有自反(对称、传递)性的关系。这个R就是R的自反(对称、传递)闭包。,2023/5/24,58,这三个关系图分别是R的自反、对称、传递闭包。,二.定义：给定 A中关系R,若A上另一个关系R，满足：RR；R是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称、传递)的关系R,如果RR,就有RR。则称R是R的自反(对称、传递)闭包。记作r(R)、s(R)、t(R)(reflexive、symmetric、transitive),2023/5/24,59,三.计算方法定理1.给定 A中关系R,则 r(R)=RIA。证明：令R=RIA,显然R是自反的和R R，下面证明R是“最小的”：如果有A上自反关系R且R R,又IA R,所以 RIA R,即R R。所以R就是R的自反闭包。即r(R)=RIA。定理2.给定 A中关系R,则 s(R)=RRC。证明方法与1.类似。定理3.给定 A中关系R,则 t(R)=RR2R3.。证明：令R=RR2R3.,显然有 R R；,2023/5/24,60,证R是传递的：任取x,y,zA,设有 R R,由R定义得必存在整数i,j使得Ri,Rj,根据关系的复合得Ri+j,又因Ri+j R,所以 R,R传递。证R是“最小的”：如果有A上传递关系R且RR,（证出R R）任取 R,则由R定义得必存在整数i,使得Ri,根据关系的复合得A中必存在i-1个元素e1,e2,.,ei-1，使得(见49页)RR.R。因RR,有 R R.R。由于R传递，所以有 R。R R。综上所述，R就是R的传递闭包，即 t(R)=RR2R3=Ri,2023/5/24,61,用上述公式计算t(R)，要计算R的无穷大次幂,好象无法实现似的。其实则不然，请看下例:A=1,2,3 A中关系R1,R2,R3,如下：R1=,R2=,R3=,R12=,R13=R14=所以 t(R1)=R1 R12 R13=R1 R22=,R23=,R23=IA,R24=R2.t(R2)=R2 R22 R23R32=,R33=R32 t(R3)=R3R32,2023/5/24,62,定理4.给定 A中关系R,如果A是有限集合，|A|=n则 t(R)=RR2.Rn。证明：令R=RR2R3.,R=RR2.Rn显然有R R,下面证明R R：任取 R,由R定义得必存在最小的正整数i 使得Ri,(下面证明in)如果in,根据关系的复合得A中必存在i-1个元素e1,e2,.,ei-1，使得 RR.R。上述元素序列:x=e0,e1,e2,.,ei-1,y=ei中共有i+1个元素，i+1n,而A 中只有n个元素，所以上述元素中至少有两个相同，设ej=ek(jk)，于是R的关系图中会有下面这些边：,2023/5/24,63,从此图中删去回路中k-j(k-j1)条边后得Ri-(k-j)，i-(k-j)R,于是 R R。最后得 R=R，所以 t(R)=RR2.Rn 定理证毕。,2023/5/24,64,求t(R)的矩阵Warshall算法：|X|=n,RXX,令MR=A R2的矩阵为A2，Rk的矩阵为Ak.于是t(R)的矩阵记作MR+=A+A2+Ak+(+是逻辑加)置新矩阵 A:=MR;置 i=1;对所有 j,如果Aj,i=1,则对k=1,2,n Aj,k:=Aj,k+Ai,k;/*第j行+第i行,送回第j行*/i加1;如果in,则转到步骤，否则停止。,2023/5/24,65,举例，令X=1,2,3,4,X中关系R图如右图所示。运行该算法求t(R)的矩阵：,A=MR=,i=1(i-列,j-行)A4,1=1 L1+L4L4,最后 A=Mt(R),i=2 A1,2=1 A2,2=1 A4,2=1 L1+L2L1 L2+L2L2 L4+L2L4,i=3 A1,3=1,A2,3=1,A4,3=1 L1+L3L1 L2+L3L2 L4+L3L4,i=4 A1,4=1 A4,4=1 L1+L4L1 L4+L4L4,2023/5/24,66,四.性质定理5.R是A上关系，则 R是自反的，当且仅当 r(R)=R.R是对称的，当且仅当 s(R)=R.R是传递的，当且仅当 t(R)=R.定理6.R是A上关系，则 R是自反的，则s(R)和t(R)也自反。R是对称的，则r(R)和t(R)也对称。R是传递的，则r(R)也传递。证明:因为R自反,由定理5得r(R)=R,即RIA=R,r(s(R)=s(R)IA=(RRC)IA=(RIA)RC=r(R)RC=RRC=s(R)s(R)自反,2023/5/24,67,类似可以证明t(R)也自反。证明.证明t(R)对称:(t(R)C=(RR2.Rn.)C=RC(R2)C.(Rn)C.=RC(RC)2.(RC)n.=RR2.Rn.(R对称，RC=R)=t(R)所以t(R)也对称。类似可以证明r(R)也对称。证明.证明r(R)传递:先用归纳法证明下面结论:(RIA)i=IARR2.Ri i=1时 RIA=IAR 结论成立。假设ik 时结论成立，即(RIA)k=IARR2.Rk,2023/5/24,68,当i=k+1时(RIA)k+1=(RIA)k(RIA)=(IARR2.Rk）(IAR)=(IARR2.Rk)(RR2.Rk+1)=IARR2.RkRk+1所以结论(RIA)i=IARR2.Ri成立.t(r(R)=t(RIA)=(RIA)(RIA)2(RIA)3.=(IAR)(IARR2)(IARR2R3).=IARR2R3.=IAt(R)=IAR(R传递t(R)=R)=r(R)所以r(R)也传递。,2023/5/24,69,定理7：设R1、R2是A上关系，如果R1R2，则 r(R1)r(R2)s(R1)s(R2)t(R1)t(R2)证明 r(R1)=IAR1IAR2=r(R2)，类似可证。定理8：设R是A上关系，则 sr(R)=rs(R)tr(R)=rt(R)st(R)ts(R)证明：sr(R)=r(R)(r(R)c=(RIA)(RIA)c=(RIA)(RcIAc)=RIARcIA=(RRc)IA=s(R)IA=rs(R)的证明用前边证明的结论：(RIA)k=IARR2.Rk可证，这里从略。,2023/5/24,70,因 Rs(R)由定理7得 t(R)ts(R)st(R)sts(R)因s(R)对称，有定理6得ts(R)也对称，由定理5得sts(R)=ts(R)所以有st(R)ts(R)。证明完毕。,练习：给定A中关系R如图所示：分别画出r(R)、s(R)、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R)、ts(R)的图。,2023/5/24,72,本节重点掌握闭包的定义、计算方法和性质。作业：P127、,2023/5/24,73,4-7 集合的划分与覆盖,一.定义 设X是一个非空集合,A=A1,A2,.,An,Ai AiX(i=1,2,.,n),如果满足A1A2.An=X(i=1,2,.,n)则称A为集合X的覆盖。设A=A1,A2,.,An是X一个覆盖,且AiAj=(ij,1i,jn)则称A是X的划分,每个Ai均称为这个划分的一个划分类。例 X=1,2,3,A1=1,2,3,A2=1,2,3,A3=1,2,3,A4=1,2,2,3,A5=1,3A1,A2,A3,A4 是覆盖。A1,A2,A3也是划分。划分一定是覆盖；但覆盖不一定是划分。,2023/5/24,74,二.最小划分与最大划分最小划分：划分块最少的划分。即只有一个划分块的划分，这个划分块就是X本身。如A1=1,2,3。最大划分：划分块最多的划分。即每个划分块里只有一个元素的划分。如A2=1,2,3。A1,A2,A3是一种划分,其中A1是最小划分,A2是最大划分。,2023/5/24,75,三.交叉划分 例 X是东大学生集合,A和B都是X的划分：A=M,W,MX,WX,M=男生,W=女生B=L,N,LX,NX,L=辽宁人,N=非辽宁人,C=LM,LW,NM,NW,称C是X的交叉划分。,2023/5/24,76,定义：若A=A1,A2,.,Am与B=B1,B2,.,Bn都是集合X的划分,则其中所有的AiBj,组成的集合C,称为C是A与B两种划分的交叉划分。证明:在C中任取元素,AiBjX(AiX,BjX)(A1B1)(A1B2).(A1Bn)(A2B1)(A2Bn).(AmB1)(AmB2).(AmBn)=(A1(B1B2B3.Bn)(A2(B1B2B3.Bn).(Am(B1B2B3.Bn)=(A1A2A3.Am)(B1B2B3.Bn)=XX=X,2023/5/24,77,再验证C中任意两个元素不相交：在C中任取两个不同元素AiBh和AjBk,考察(AiBh)(AjBk)(i=j和h=k不同时成立)=(AiAj)(BhBk)ij,hk(AiAj)(BhBk)=Ai=ij,hk(AiAj)(BhBk)=ij,h=k(AiAj)(BhBk)=Bh=综上所述，C是X的划分。作业：第130页(1),2023/5/24,78,一.等价关系1.定义:设R是A上关系,若R是自反的、对称的和传递的，则称R是A中的等价关系。若a,bA，且aRb，则称a与b等价。例子，集合A=1,2,3,4,5,6,7,R是A上的模3同余关系，即R=|x-y可被3整除(或x/3与y/3的余数相同)即R x(mod 3)=y(mod3),4-8 等价关系与等价类,2023/5/24,79,上例中的关系为：R=,2.等价关系的有向图 1)完全关系(全域关系AA)图，下面分别是当A中只有1、2、3个元素时的完全关系图。,A=1,A=1,2,A=1,2,3,2023/5/24,80,2.等价关系的有向图模3同余关系R的图：从关系图可看出R是自反、对称、传递的关系，所以R是等价关系。,等价关系R的有向图可能由若干个独立子图(R图的一部分)构成的，每个独立子图都是完全关系图。上述关系R图就是由三个独立的完全图构成的。下面给出八个关系如图所示，根据等价关系有向图的特点，判断哪些是等价关系。,2023/5/24,81,下面是A=1,2,3中关系：,2023/5/24,82,思考题：A=1,2,3,可构造多少个A中不同的等价关系？可以根据等价关系有向图的特点来考虑。如果等价关系R中有 a)三个独立子图的情形，则()个等价关系。b)二个独立子图的情形，则()个等价关系。c)一个独立子图的情形，则()个等价关系。一共有()个中不同的等价关系。,2023/5/24,83,二.等价类,1.定义：R是A上的等价关系，aA,由a确定的集合aR:aR=x|xAR称集合aR为由a形成的R等价类。简称a等价类。可见 xaR R上例，A=1,2,3,4,5,6,7,R是A上的模3同余关系，1R=1,4,7=4R=7R-余数为1的等价类 2R=2,5=5R-余数为2的等价类 3R=3,6=6R-余数为0的等价类思考题：此例为什么只有三个等价类？,2023/5/24,84,2.由等价关系图求等价类：R图中每个独立子图上的结点，构成一个等价类。不同的等价类个数=独立子图个数。,上述三个等价关系各有几个等价类？说出对应的各个等价类。,2023/5/24,85,3.等价类性质 R是A上等价关系，任意a,b,cA 同一个等价类中的元素，彼此有等价关系R。即任意x,yaR，必有R 证明：任取x,yaR，由等价类定义得R,R,由R对称得R，又由R传递得R。,2023/5/24,86,aRbR=，当且仅当 R。证明:设R，假设aRbR,则存在xaRbR，xaRxbR,R,R,由R对称得R又由R传递得R,产生矛盾。若aRbR=,而R,由等价类定义得baR,又因为bRb,所以bbR，所以baRbR，产生矛盾。,2023/5/24,87,aR=bR 当且仅当 R。证明：若R，则任何xaR，有R，由对称性得R，再由传递性得R,xbR，所以aRbR。类似可证bRaR。aR=bR。如果aR=bR，由于有aRa,所以aaR，abR，所以有R，由对称性得R。.A中任何元素a,a必属于且仅属于一个等价类。证明：A中任何元素a,由于有aRa,所以aaR，如果 abR，所以有R.由性质得：aR=bR。,2023/5/24,88,.任意两个等价类 aR、bR，要么aR=bR，要么aRbR=。(因为要么R，要么R。).R的所有等价类构成的集合是A的一个划分。(由性质即得。)(这个划分称之为商集)性质（4）说明了覆盖性，性质（5）说明了不相交性,2023/5/24,89,三.商集,定义：R是A上等价关系，由R的所有等价类构成的集合称之为A关于R的商集。记作A/R。即 A/R=aR|aA,例如A=1,2,3,4,5,6,7,R上模3同余关系，则 A/R=1R,2R,3R=1.4.7,2,5,3,6,2023/5/24,90,练习:X=1,2,3,X上关系R1、R2、R3，如上图所示。X/R1=1R1,2R1,3R1=1,2,3 X/R2=1R2,2R2=1,2,3 X/R3=1R3=1,2,3,2023/5/24,91,定理:集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。证明：由等价类性质可得：1)A/R中任意元素aR，有aRA。2)设aR,bR是A/R的两个不同元素，有aRbR=3)因为A中每个元素都属于一个等价类，所以所有等价类的并集必等于A。所以商集A/R是A的一个划分。定理：设R1和R2是非空集合A上的等价关系，则 A/R1=A/R2 当且仅当 R1=R2。(这个定理显然成立。),2023/5/24,92,四.由划分确定等价关系,例如，X=1,2,3,4,A=1,2,3,4,A是X的一个划分，求X上一个等价关系R，使得X/R=A。显然由图可得：R=1,223242。,一般地A=A1,A2,An是X的一个划分，则构造一个X中的等价关系R，使得X/R=A。R=A12A22,An2 其中Ai=Ai2Ai2，下面证明R是X中的等价关系。,定理:集合X的一个划分可以确定X上的一个等价关系。证明：假设A=A1,A2,.,An是X的一个划分，如下构造X 上的一个等价关系R:RA12A22An2，其中Ai2=Ai2Ai2，1)证R自反：任取aX，因为A是X的划分，必存在 AiA使aAi,于是AiAi,又AiAi R 有aRa。2)证R对称：任取a,bX,设aRb，必存在AiA使得AiAi,于是a,bAi,bRa,R是对称的。3)证R传递：任取a,b,cX,设aRb，bRc,必存在AiA使得AiAi,AiAi,于是a,b,cAi,所以AiAi，又AiAi R有aRc 所以R传递。最后得R是集合X中的等价关系。,2023/5/24,94,本节重点：等价关系概念、证明。等价类概念、性质。求商集。作业：P134、,2023/5/24,95,4-9 相容关系,定义:给定集合X上的关系r,若r是自反的、对称的,则r是A上相容关系。例子：X 是由一些英文单词构成的集合。X=fly,any,able,key,book,pump,fit,X上关系r:r=|X,X且与含有相同字母,2023/5/24,96,r的有向图：看出有自反、对称性。而不传递。,相容关系的简化图和简化矩阵,图的简化：不画环；两条对称边用一条无向直线代替。,矩阵的简化：因为r的矩阵是对称阵且主对角线全是1，用下三角矩阵(不含主对角线)代替r的矩阵。,令x1=fly,x2=any,x3=able,x4=key,x5=book,x6=pump,x7=fit,X=x1,x2,x3,x4,x5,x6,x7,r的简化图为：,2023/5/24,98,相容类及最大相容类,定义：设r是集合X上的相容关系,CX,如果对于C中任意元素x,y有r,称C是r的一个相容类。上例中x1,x2,x3,x4,x1,x2,x3,x2,x3,x4,x1,x2,x4,x3,x4,x5,x1,x3,x4,x1,x2,x3,x4,x1,x7,x6 都是相容类。上述相容类中，有些相容类间有真包含关系。,定义：设r是集合X上的相容关系，C是r的一个相容类，如果C不能被其它相容类所真包含，则称C是一个最大相容类。也可以说，C是一个相容类，如果C中加入任意一个新元素，就不再是相容类，C就是一个最大相容类。x1,x2,x3,x4,x3,x4,x5,x1,x7,x6都是最大相容类。,2023/5/24,99,从简化图找最大相容类：-找最大完全多边形。即：含有结点最多的多边形中，每个结点都与其它结点相联结。,在相容关系简化图中，每个最大完全多边形的结点集合构成一个最大相容类。上例中最大相容类x1,x2,x3,x4,x3,x4,x5,x1,x7,x6分别对应最大完全四、三、一、零边形。,2023/5/24,100,给定X上相容关系r,如图所示,r的最大相容类：x1,x2,x5,x2,x3,x5,x3,x4,x5,x1,x4,x5,完全覆盖：定义：r是X中的相容关系，由r的所有最大相容类为元素构成的集合，称之为X的完全覆盖。记作Cr(X)。Cr(X)=x1,x2,x3,x4,x3,x4,x5,x1,x7,x6 Cr(X)=x1,x2,x5,x2,x3,x5,x3,x4,x5,x1,x4,x5,作业 P139(2),2023/5/24,101,4-10 次序关系,一.偏序(半序)关系(partial order relation),定义：R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称是偏序集。例如数值的、关系和集合的都是偏序关系。用符号“”表示任意偏序关系，但要注意“”不一定是“小于或等于”的含义。,例1 A=1,2,4,6,是A中的整除关系，其关系图如右图，显然是自反、反对称和传递的，即它是个偏序。,2023/5/24,102,注：（1）用矩阵表示半序关系，不能明显看到二元关系的特征。（2）用简化的关系图表示较适合。,简化的关系图：(1)自反性：每个顶点都有自回路，省去。(2)反对称性：两个顶点间只可能有一个箭头从左右，或从下上的方向从小到大安置顶点，可省略箭头。(3)传递性：由于有(a,b)，(b,c)R 则(a,c)R 故只画(a,b)，(b,c)对应的边,省略边(a,c)。,2023/5/24,103,定义：Hasse图 设是上的一个半序关系，如果ab，则将画在下面，且不，使ac，cb，则，间用直线连接。并符合简化的关系图的绘制，称这