《[企业管理]集合83805305.ppt》由会员分享，可在线阅读，更多相关《[企业管理]集合83805305.ppt（162页珍藏版）》请在三一办公上搜索。
1、第二篇 集合论,主要包括如下内容：集合论初步 二元关系 函数,基本概念,1.集合与元素集合：是一些确定的、可以区分的事物汇集在一起组成的一个整体。用大写的英文字母表示。元素：集合中的每个事物，称之为元素。用小写英文字母表示：表示元素与集合的属于关系。,2.有限集合与无限集合 有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。无限集合：元素是无限个的集合。,3.集合的表示方法 列举法（外延表示法）：将集合中的元素一一列出，写在大括号内。描述法（谓词法）：用句子(或谓词公式)描述元素的属性。A=x|P(x),其中P(x)是谓词公式，如果论域内个体a使得P(a)为真，则aA，
2、否则aA。,4.说明集合中的元素间次序是无关紧要的，但是必须是可以区分的。对集合中的元素无任何限制.常用的几个集合符号的约定：自然数集合N=0,1,2,3,整数集合Z，实数集合R，有理数集合Q.,集合中的元素也可以是集合，下面的集合的含义不同：如 a：张书记 a:党支部(只有一个书记)a：分党委(只有一个支部)a：党委(只有一个分党委)a：市党委(只有一个党委)（5）对一个集合来说，任一事物或者是它的元素或者不是它的元素，二者必居其一而不可兼而有之，且结论是确定的。,集合实例,B=9，8，8，7=9，8，7=7，8，9D=x|x B（除7、8、9外的一切事物）F=7，8，9（FB）A=年青人罗
3、素悖论：一个村子里的理发师说，我给而且只给自己不给自己理发的人理发。,集合间的关系,一.被包含关系(子集)1.定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。文氏图表示如右下图。谓词定义：ABx(xAxB),2.性质：有自反性，对任何集合A有AA。有传递性，对任何集合A、B、C，有AB且 BC，则AC。有反对称性，对任何集合A、B，有AB且 BA，则A=B。例：判断下列各式的正确性。aa,b，aa,b，a,ba,b,a,a,ba,b,a,二.相等关系 定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。谓词定义：A=Bx(
4、xAxB)定理：A=B，当且仅当AB且 BA。证明：A=Bx(xA xB)x(xAxB)(xBxA)x(xAxB)x(xBxA)AB BA,2.性质有自反性，对任何集合A，有A=A。有传递性，对任何集合A、B、C，如果有A=B且 B=C，则A=C。有对称性，对任何集合A、B，如果有A=B，则B=A。,三.真被包含关系(真子集)1.定义：A、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。谓词定义：ABA BABx(xAxB)x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(x(xAxB)x(xAxB)(x(xAxB)x(xBxA)x(xAxB)x
5、(xBxA),2.性质 对任何集合A、B、C，如果有AB且 BC，则AC。练习题：设A=a,a,a,b,a,b,c判断下面命题的真值。aA(a A)cA aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b,c(cA)(a),特殊集合,一.全集 E 定义：包含所讨论的所有集合的集合，称之为全集，记作E。文氏图如右图。E=x|P(x)P(x)性质：对于任何集合A，都有AE。,二.空集,定义：不含任何元素的集合，称之为空集，记作。=x|x x性质：1.对于如何集合A，都有A。因为x(xxA)为永真式，所以A。2.空集是唯一的。,三.集合的幂集定义:A是集合，由A的所有子集构成
6、的集合，称之为A的幂集。记作P(A)或2A。P(A)=B|BA例如，A P(A)a a,b 结论：对任意集合A，因为A，AA，所以有P(A),AP(A)。,集合的运算,一.交运算1.定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记作AB。谓词定义：AB=x|xAxBxAB xAxB,2.性质幂等律 对任何集合A，有AA=A。交换律 对任何集合A、B，有AB=BA。结合律 对任何集合A、B、C，有(AB)C=A(BC)。同一律 对任何集合A，有AE=A。零律 对任何集合A，有A=。AB AB=A。,证明：AB=A x(xAB xA)x(xAB xA)(xA xAB
7、)x(xABxA)(xAxAB)x(xAxB)xA)(xA(xAxB)x(xAxB)xA)(xA(xAxB)x(T(T(xA xB)x(xA xB)x(xAxB)AB,二.并运算1.定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作AB谓词定义：AB=x|xAxBxAB xAxB2.性质幂等律 对任何集合A，有AA=A。交换律 对任何集合A、B，有AB=BA。结合律 对任何集合A、B、C，有(AB)C=A(BC)。,同一律 对任何集合A，有A=A。零律 对任何集合A，有AE=E。分配律 对任何集合A、B、C，有 A(BC)=(AB)(AC)。A(BC)=(AB)
8、(AC)。吸收律 对任何集合A、B，有 A(AB)=A A(AB)=A。证明 A(AB)=(AE)(AB)(同一)=A(EB)(分配)=AE=A(零律)(同一)AB AB=B。,三.差运算-(相对补集)1.定义：A、B是集合，由属于A，而不属于B的元素构成的集合,称之为A与B的差集,或B对A的相对补集，记作A-B。谓词定义：A-B=x|xAx BxA-B xAxB2.性质设A、B、C是任意集合，则A-=A-A=A-A=A-BA AB A-B=A-B=AAB=,四.绝对补集 1.定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作A。实际上A=E-A。谓词定义：A=E-A=x|x
9、Ex A=x|x Ax A xA2.性质设A、B、C是任意集合，则 E=E(A)=A AA=AA=E A-B=AB,(AB)=AB(AB)=AB 证明：任取x(AB)x(AB)xAB(xAxB)(xAxB)xAxB xAB(AB)=AB AB B A证明：AB x(xAxB)x(xBxA)x(x Bx A)B A,集合恒等式与命题演算等价式的比较,命题演算 集合运算对象 命题A、B 集合A、B T E F 运算符 AB AB AB AB A A关系 A=B A=B AB AB 定律 定律,五.对称差1.定义：A、B是集合,由属于A而不属于B，或者属于B而不属于A的元素构成的集合,称之为A与B的
10、对称差,记作AB。谓词定义：AB=(A-B)(B-A)=x|(xAxB)(xBxA)AB=(AB)-(AB),2.性质 交换律 对任何集合A、B，有AB=BA。结合律 对任何集合A、B、C，有(AB)C=A(BC)。同一律 对任何集合A，有A=A。对任何集合A，有AA=。,习题,(1)判断下面命题的真值：a)如果AB，BC，则 A C。b)如果AB，BC，则 AC。c)如果AB，BC，则 AC。d)如果AB，BC，则 AC。e)如果AB及BC，则AC。f)如果AB，BC，则 AC。(2)设A=，B=P(P(A)a）是否有B？B？b）是否有B？B？c）是否有B？B？,（1）已知AB=AC，是否必
11、须B=C？（2）已知AB=AC，是否必须B=C？（3）已知AB=AC，是否必须B=C？,有限集合的基数集合中元素的个数,(1)|P(A)|=2|A|(2)|AB|A|+|B|(3)|AB|min|A|,|B|(4)|A-B|A|-|B|(5)|A B|=|A|+|B|-2|AB|问题:(2)、(3)、(4)等号成立的条件是什么？,序偶与集合的笛卡尔积,一.序偶与有序n元组1.定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作；称x、y分别为序偶的第一，第二元素。注意，序偶与集合x,y不同：序偶：元素x和y有次序；集合x,y：元素x和y的次序是无关紧要的。,2.定义：设，是两个序
12、偶，如果 x=u和y=v，则称和相等，记作=.3.定义:有序3元组是一个序偶,其第一个元素也是个序偶。有序3元组,c可以简记成。但不是有序3元组。4.定义:有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,记作,xn。且可以简记成。5.定义：=(x1=y1)(x2=y2)(xn=yn),集合的笛卡尔积,例如“斗兽棋”的16颗棋子，可看成是由两种颜色的集合A和8种动物的集合B组成的 A=红,蓝 B=象,狮,虎,豹,狼,狗,猫,鼠每个棋子可以看成一个序偶，斗兽棋可记成集合AB：,1.定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作AB
13、，即 AB=|xAyB 例1 设A=0,1，B=a,b，求AB，BA，AA。解：AB=BA=AA=可见 ABBA所以，集合的笛卡尔积运算不满足交换律,也不满足结合律。,2.性质 1)如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=mn.2)A=B=,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)所以式成立。,4)若C,则 AB(ACBC)(CACB).证明:必要性：
14、设AB，求证 ACBC任取AC xAyC xByC(因AB)BC 所以,ACBC.充分性：已知C 取C中元素y,任取 xAxAyC AC BC(由ACBC)xByC xB 所以,AB.所以 AB(ACBC),5)设A、B、C、D为非空集合，则 ABCDACBD.证明:首先,由ABCD 证明ACBD.任取xA，任取yB，所以 xAyBABCD(由ABCD)xCyD 所以,ACBD.其次,由AC，BD.证明ABCD任取AB AB xAyB xCyD(由AC，BD)CD 所以,ABCD 证毕.,6)约定(A1A2)An-1)An)=A1A2An 特别 AAA=An 3.应用1)令A1=x|x是学号
15、A2=x|x是姓名 A3=男,女 A4=x|x是出生日期 A5=x|x是班级 A6=x|x是籍贯 则A1A2A3 A4A5 A6中一个元素：这就是学生档案数据库的一条信息，所以学生的档案就是A1A2A3 A4A5 A6的一个子集。,n 个,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 的一个子集。,优先权,一元运算
16、符(A,P(A)优先于二元运算符(,)优先于集合关系符(=,)优先于一元联结词()优先于二元联结词(,)优先于逻辑关系符(,)括号内的优先于括号外的！,关系及其表示法 基本概念1.关系的定义定义1:设A、是集合，如果AB，则称R是一个从A到B的二元关系。如果 RAA，则称R是A上的二元关系。二元关系简称为关系。定义2:任何序偶的集合，都称之为一个二元关系。如:R=,R xRy 也称之为x与y有关系。R xRy 也称之为x与y没有关系。,关系的表示,列举法：A=0，1 B=a，b R1=,(A到B的关系）R2=,(A上的关系）描述法：A=1，2，3Dx=|xAyAx整除yLx=|xAyAxy,2
17、.关系的定义域与值域定义域(domain)：设RAB，称集合 dom R=x|y(R)为R的定义域。值域(range)：设RAB，称集合 ran R=y|x(R)为R的值域。关系的域(fild)：fid R=dom R ran R.结论：dom R A，ran R B。R=,dom R=ran R=,三.关系的另两种表示法,1.有向图法：RAB（A、B非空、有限），用两组小圆圈(称为 结点)分别表示A和B的元素，当R时，从x到y引一条有向弧(边)（由x指向y）。这样得到的图形称为R的关系图。如RAA,即R是集合A中关系时,用一组小圆圈表示A中的元素，若R,则从x到x画一条有向环(自回路)。,例
18、 设A=1,2,3,4,B=a,b,c，R3 AB，R3=,则R3的关系图如下：例 设A=1,2,3,4,R4 AA，R4=,则R4的关系图如右上图。,R3:,4.矩阵表示法：,非空有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。设A=a1,a2,am，B=b1,b2,bn是个有限集，RAB，定义R的mn阶矩阵 MR=(rij)mn，其中 rij=称MR为关系R的关系矩阵。,例 设A=1,2,3,4,B=a,b,c，R3 AB，R3=,例 设A=1,2,3,4,R4 AA，R4=,则 MR3=MR4=,四.三个特殊关系,1.空关系：因为AB，(或AA)，所以也是一个从A
19、到B(或A上)的关系，称之为空关系。2.全域关系：AA本身也是一个A上的关系，称之为A上的全域关系，记为EA，即 EA=|xAyA。3.A上的恒等关系IA：IAAA，且IA=|xA称之为A 上的恒等关系。,3.A上的恒等关系IA：IAAA，且IA=|xA称之为A 上的恒等关系。IA的关系距阵为单位距阵。例如A=1,2,3,则IA=,A上的、全域关系及IA的关系图及矩阵如下：,五.关系的集合运算,由于关系就是集合，所以集合的、和运算对关系也适用。例如，A是学生集合，R是A上的同乡关系，S是A上的同姓关系，则RS：或同乡或同姓关系RS：既同乡又同姓关系R S：同乡而不同姓关系RS：同乡而不同姓,或
20、同姓而不同乡关系R：不是同乡关系,这里R=(AA)R,关系的性质,本节中所讨论的关系都是集合A中的关系。关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。,一.自反性,定义:设R是集合A中的关系，如果对于任意xA都有R(xRx)，则称R是A中自反关系。即 R是A中自反的x(xAxRx)从关系图看自反性:每个结点都有环。从关系矩阵看自反性：主对角线都为1。,令A=1,2,3,给定A上八个关系如下：,二.反自反性,定义：设R是集合A中的关系，如果对于任意的xA都有R，则称R为A中的反自反关系。即R是A中反自反的x(xAR)从关系图看反自反性:每个结点都无环。从关系矩阵看反自反性：主对角
21、线都为0。,三.对称性,定义:R是集合A中关系,对任何x,yA,如果有xRy,必有yRx,则称R为A中的对称关系。R是A上对称的xy(xAyAxRy)yRx)从关系图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。从关系矩阵看对称性：以主对角线为对称的矩阵。,四.反对称性,定义:设R为集合A中关系,对任何x,yA,如果有xRy,和yRx,就有x=y,则称R为A中反对称关系。R是A上反对称的xy(xAyAxRyyRx)x=y)xy(xAyAxyxRy)y x)由R的关系图看反对称性：两个不同的结点之间最多有一条边。从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。
22、,五.传递性,定义:R是A中关系，对任何x,y,zA,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。即R在A上传递xyz(xAyAzAxRyyRz)xRz)从关系图和关系矩阵中不易看清是否有传递性。,例如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)(2
23、R11R1)2R1)(2R11R2)2R2)(2R22R1)2R1)(2R22R2)2R2)(FF)F)(FT)T)(TF)F)(TF)T)(FF)F)(FT)F)(FF)F)(FF)F)T,三个特殊关系具有的性质,非空集合A上的空关系：非空集合A上的全域关系：非空集合A上的恒等关系：,本节要求：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)xR
24、z),关系矩阵,关系图,性质 判定:,下面归纳以上八个关系的性质：Y-有 N-无,1。,2。,。,1。,2。,。,1。,2。,。,1。,2。,。,3,3,3,3,R2,R1,R3,R4,自反性 反自反性 对称性 反对称性 传递性,R1 Y N N Y Y,R2 N Y N Y N,R3 Y N Y N Y,R4 Y N Y Y Y,例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
25、-y)=-3n=3(-n),因-nI,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+nI,所以xRz,所以R传递。,关系的复合,复合关系的定义：设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RS。定义为：RS=|xXzZy(yY RS)规定：R=R=。,2.复合关系的计算方法 A=1,2,3 B=1,2,3.4 C=1,2,3,4,5RAB SBC枚举法R=,S=,则 RS=,R=,S=,有向图法关系矩阵法令A=a1,a2,am B=b1,b2,b
26、n C=c1,c2,ct RAB SBC,c11=(a11b11)(a12b21).(a1nbn1)=(a1kbk1)(其中是逻辑乘,是逻辑加)00=0,01=10=11=1 00=01=10=0,11=1cij=(ai1b1j)(ai2b2j).(ainbnj)=(aikbkj)(1im,1jt),例：已知 R=,AA S=,AA求：RS，SR，RR，SS，(RS)R，R(SR),三.性质1.满足结合律:RAB SBC TCD 则 R(ST)=(RS)T 由于ST是B到D的关系，所以R(ST)是A到D的关系。(RS)是A到C的关系，所以(RS)T是A到D的关系。,证明：任取R(S T)b(b
27、BR S T)b(bBRc(cCST)bc(bBR(cCST)cb(cC(bBRST)c(cCb(bBRS)T)c(cCR ST)(R S)T,所以,可以用下图形象表示:,2.R是从A到B的关系，则 R IB=IA R=R令A=1,2,3,B=a,b,c,d,4.关系的乘幂 令R是A上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即 R R=R2，R2 R=R R2=R3，一般地 R0=IA，Rm Rn=Rm+n(Rm)n=Rmn(m,n为非负整数),逆关系,一.定义 R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作R-1
28、，或RC。RC=|R RC R二.计算方法 1.R=,RC=,2.RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。3.RC的矩阵 M=(MR)T 即为R矩阵的转置。如 三.性质令R、S都是从X到Y的关系，则 1.(RC)C=R 2.(RS)C=RCSC，(RS)C=RCSC。3.dom RC=ran R,ran RC=dom R。4.(R-S)C=RC-SC。,R-1,1 0 1,5.RS RC SC。证明：充分性，已知RC SC，则任取RRC SC S RS 必要性，已知R S，则任取RC RS SC RCSC 6.(R)C=RC证明:任取(R)C RR RC RC(R)C=RC,7
29、.令R是从X到Y的关系，S是Y到 Z的关系，则(R S)C=SC RC。证明：任取(R S)CR Sy(yYRS)y(yYSCRC)SC RC 所以(RS)C=SC RC,8.R是A上关系，则R是对称的，当且仅当 RC=R,证明：充分性，已知 RC=R 任取x,yA 设R,则RC,而RC=R 所以有R，所以R对称。必要性，已知R 对称，先证RCR，任取RC,则R,因R对称，所以有R，所以RCR。再证R RC，任取R,因R对称，所以有R，则RC,所以RRC。最后得RC=R。,9.R是A上关系，则R是反对称的，当且仅当 RRC IA。,证明：充分性，已知RRC IA，任取x,yA 设R 且R，RR
30、RRC，RRC IA(因RRC IA)x=y 所以R反对称。必要性，已知R反对称，任取RRC RRCRRC RRx=y(因R反对称)IA 所以RRC IA。,10.R是A上关系，则R是传递的，当且仅当 RR R。,证明：必要性，对任意的RR a(aAR R)因为R传递，有R，所以RRR。充分性，对任意的a、b、cA，若R R，则由合成运算的定义，有 R R，由RRR，有 R，所以R传递。,11.R是A上关系，则R是自反的，当且仅当 IA R。,证明：必要性由于R是自反的，所以，对任意的aA，有 R，而IA=|aA，所以IA R。充分性由于IA=|aA且IA R所以任意的aA，有 R，因此R自反
31、。,一些相关结论,定理1 设R1、R2是A上的自反关系，则R1C、R1R2、R1R2也是A上的自反关系。定理2 设R1、R2是A上的对称关系，则R1C、R1R2、R1R2也是A上的对称关系。证明：对任意的，若 R1R2 R1 R2 R1 R2 R1R2 所以R1R2是A上的对称关系。证明2：因为R1、R2是A上的对称关系，所以有 R1=R1C、R2=R2C，而（R1R2）C=R1C R2C=R1R2所以R1R2是A上的对称关系。,定理3 设R1、R2是A上的传递关系，则R1C、R1R2也是A上的传递关系。,证明：对任意的,，若 R1 R2 R1 R2 R1 R2 R1 R2 R1 R2（R1、
32、R2传递）R1 R2所以R1 R2在A上传递。,定理4 设R1、R2是A上的反对称关系，则R1C、R1R2也是A上的反对称关系。,证明：对任意的 R1 R2,且xy R1 R2 R1 R2由于R1、R2是反对称的，且xy,所以有 R1 R2 即 R1 R2所以R1 R2在A上反对称。,关系的闭包运算,设R是A上的关系，有时希望给R增加一些有序对，构成新关系R，使得R具有自反性、或对称性、或传递性，但不希望R太大，即希望增加的有序对尽量少，这就是闭包的思想。,二.闭包的定义：,给定 A中关系R,若A上另一个关系R，满足：RR；R是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称
33、、传递)的关系R,如果RR,就有RR。则称R是R的自反(对称、传递)闭包。记作r(R)、(s(R)、t(R)(reflexive、symmetric、transitive),三.计算方法定理1.给定 A中关系R,则 r(R)=RIA。证明：令R=RIA,显然R是自反的和RR。下面证明R是“最小的”：如果有A上自反关系R且RR,由于R是自反的，有IAR,所以 RIAR,即RR。所以R就是R的自反闭包。即r(R)=RIA。,定理2.给定 A中关系R,则 s(R)=RRC。,证明：(1)显然R RRC(2)对 RRC,有R RC即RC R所以 RRC，即RRC是对称的。（3）设R是对称的，且R R，
34、对任意的 RRCR RC若 R，则 R（R R）若 RC，有 R，即 R，由于R对称，所以 R，所以RRC R。所以s(R)=RRC,定理3.给定 A中关系R,则 t(R)=RR2R3.。,证明：令R=RR2R3.,显然有 RR；证R是传递的：任取x,y,zA,设有R R,由R定义得必存在整数i,j使得Ri,Rj,根据关系的复合得Ri+j,又因Ri+j R,所以R,R传递。,定理3.给定 A中关系R,则 t(R)=RR2R3.。,（令R=RR2R3.,）证R是“最小的”：如果有A上传递关系R”且 RR”,（证出R R）。任取R,则由R定义得必存在整数i,使得Ri,根据关系的复合得A中必存在i-
35、1个元素e1,e2,.,ei-1，使得RR.R。因RR”,有R”R”.R”。由于R”传递，所以有R”。RR”。综上所述，R就是R的传递闭包，即 t(R)=RR2R3=Ri,例:A=1,2,3 A中关系R,S,T,如下：R=,S=,T=,求t(R)，t()，t(),定理4.给定 A中关系R,如果A是有限集合，|A|=n,则 t(R)=RR2.Rn。,证明：令R=RR2R3.,R=RR2.Rn，显然有RR。下面证明RR：任取R,由R定义得必存在最小的正整数p 使得RP,(下面证明Pn)如果Pn,根据关系的复合得A中必存在p-1个元素e1,e2,.,ep-1，使得 RR.R。令x=e0，y=eP 因
36、为|A|=n，所以，存在正整数t，q，0tR.R且R.R所以，Rk，其中，k=t+p-qR，即R=R。,求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,则转到步骤，否则停止。下面举例，令X=1,2,3,4,X中关系R图如右图所示。运行该算法求t(R)的矩阵：,i=1(i-列,j-行)A4,1=1 1行+4行4行i
37、=2 A1,2=1,1行+2行1行 A2,2=1,2行+2行2行 A不变 A4,2=1,4行+2行4行,4行全1,A不变i=3 A1,3=1,1行+3行1行,3行全0,A不变 A2,3=1,2行+3行2行,3行全0,A不变 A4,3=1,4行+3行4行,3行全0,A不变i=4 A1,4=1,1行+4行1行 A4,4=1,4行+4行4行 A不变,最后 A=Mt(R),A=MR=,A的初值:,四.性质,定理5.R是A上关系，则R是自反的，当且仅当 r(R)=R.R是对称的，当且仅当 s(R)=R.R是传递的，当且仅当 t(R)=R.,四.性质,定理6.R是A上关系，则R是自反的，则s(R)和t(R
38、)也自反。R是对称的，则r(R)和t(R)也对称。R是传递的，则r(R)也传递。证明:因为R自反,所以IA R,由于s(R)=RRC t(R)=RR2R3，所以IA s(R)IA t(R)s(R)、t(R)自反,R是对称的，则r(R)和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)也对称。,(R2)-1=(R R)-1=R-1 R-1=(R-1)2,R是传递的，则r(R)也传递。,证明：因为R传递，所以，R2R。又r(R)=R IA,所以(r(R)2
39、=r(R)r(R)=(RIA)(RIA)=(RR)(RIA)(IAR)(IA IA)=R2RR IA R IA=r(R)所以，r(R)是传递的。,四.性质,定理7：设R1、R2是A上关系，如果R1R2，则 r(R1)r(R2)s(R1)s(R2)t(R1)t(R2)证明 r(R1)=IAR1IAR2=r(R2)(或证 由定义R2r(R2)，由于R1R2，有R1r(R2)，因为r(R2)是自反的，所以，由闭包定义，得r(R1)r(R2)。),定理.R1和R2是A上关系，求证 a)r(R1R2)=r(R1)r(R2),b)s(R1R2)=s(R1)s(R2),c)t(R1)t(R2)t(R1R2)
40、,证明：a)r(R1R2)=(R1R2)IA=(R1IA)(R2IA)=r(R1)r(R2),b)s(R1R2)=(R1R2)(R1R2)C=(R1R2)(R1)C(R2)C=(R1(R1)C)(R2(R2)C)=s(R1)s(R2),c)因 R1(R1R2)且R2(R1R2)，得 t(R1)t(R1R2),t(R2)t(R1R2)，所以有 t(R1)t(R2)t(R1R2)。,四.性质,定理9：设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)
41、IA=s(R)IA=rs(R),练习：给定A中关系R如图所示：分别画出r(R)、s(R)、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R)、ts(R)的图。,归纳：关系性质证明方法,设R是A上关系，一.证明R的自反性：方法1 用自反定义证：任取 xA,证出R.方法2 用恒等关系IA证：证出IA R.方法3 用自反闭包证：证出r(R)=R,即RIA=R.二.证明R的反自反性：方法1 用反自反定义证：任取 xA,证出R.三.证明R的对称性：方法1 用对称定义证：任取 x,yA,设R,证出 R.方法2 用求逆关系证：证出 RC=R.方法3 用对称闭包证：证出 s(R)=R,即RR
42、C=R.,四.证明R的反对称性：方法1 用定义1证：任取 x,yA,设R,R.证出 x=y。方法2用定义2证：任取 x,yA,xy,设R,证出R.方法3 用定理证：证出 RRC IA.五.证明R的传递性：方法1 用传递定义证：任取 x,y,zA,设R,R,证出 R.方法2 用传递闭包证：证出 t(R)=R,即 RR2R3.=R.方法3用定理证：证出,例 R和S都A上是自反、对称、传递的，求证RS也是自反、对称和传递的。证明：一.证明RS的自反性方法1 用自反定义证：任取 xA,(证出RS)因R和S都自反，所以有R，S，于是有RS，所以RS也自反。方法2 用恒等关系IA证：(证出IA RS)因R
43、和S都自反，所以 IA R，IA S，所以 IA RS所以RS也自反。方法3 用自反闭包证：(证出r(RS)=RS,即(RS)IA=RS)因R和S都自反，所以r(R)=R,r(S)=S,r(RS)=(RS)IA=(RIA)(SIA)=r(R)r(S)=RS所以RS也自反。,二.证明RS的对称性：方法1 用对称定义证：任取 x,yA,设RS,(证出 RS.)则R，S，因为R和S对称，所以有R，S，于是RS。RS对称。方法2 用求逆关系证：(证出(RS)C=RS.)因为R和S对称，所以有RC=R，SC=S，而(RS)C=RCSC=RS，RS对称。方法3 用对称闭包证：(证出 s(RS)=RS,即(
44、RS)(RS)C=RS.)因为R和S对称，所以s(R)=R,s(S)=Ss(RS)=(RS)(RS)C=(RS)(RCSC)=(RRC)(RSC)(SSC)(SRC)=(s(R)(RSC)(s(S)(SRC)=(R(RSC)(S(SRC)=RS(吸收律)RS对称。,五.证明RS的传递性：方法1 用传递定义证：任取 x,y,zA,设RS,RS,(证出RS)RSRS RSRS(RR)(S S)RS（因为R、S传递）RS 所以RS传递。方法2 用传递闭包证：证出 t(RS)=RS,即(RS)(RS)2(RS)3.=RS.方法3用定理证：证出用方法2、方法3证明此题的传递性有很大难度。R(ST)(RS
45、)(RT),练习：）R和S都是A上关系，a)R和S都自反，则 是否自反。b)R和S都反自反，则 是否反自反。c)R和S都对称，则 是否对称。d)R和S都传递，则 是否传递。）S是上关系，证明若是自反和传递，则=S。其逆为真吗？3）设R是集合A上的一个自反关系,求证：R是对称和传递的，当且仅当 和在R中,则有也在R中。,例.R和S都是A上等价关系,下面哪个是A上等价关系?证明或举反例说明.a)RS b)RS c)-R(即AA-R)d)R-S e)R2 f)r(R-S)解.a)c)d)f)不是.请看反例:,集合的划分与覆盖,一.定义 设X是一个非空集合,A=A1,A2,.,An,Ai AiX(i=
46、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,3划分,一定是覆盖；但覆盖,不一定是划分。,二.最小划分与最大划分最小划分：划分块最少的划分。即只有一个划分块的划分，这个划分块就是X本身。最大划分：划分块最多的划分。即每个划分块里只有一个元素的划分。,等价关系与等价类,一.等价关系1.定义:设R是A上关系,若R是自反
47、的、对称的和传递的，则称R是A中的等价关系。若a,bA，且aRb，则称a与b等价。例：集合A=1,2,3,4,5,6,7,R是A上的模3同余关系，即R=|x-y可被3整除,2.等价关系的关系图 1)完全关系(全域关系AA)图，下面分别是当A中只有1、2、3个元素时的完全关系图。2）.等价关系的关系图:等价关系R的关系图由若干个独立子图构成，每个独立子图都是完全关系图。,A=1,2,3，下面是A中关系，判断那些关系是等价关系,思考题：A=1,2,3,可构造多少个A中不同的等价关系？可以根据等价关系有向图的特点来考虑。如果等价关系R中有 a)三个独立子图的情形，则()个等价关系。b)二个独立子图的
48、情形，则()个等价关系。c)一个独立子图的情形，则()个等价关系。一共有()个中不同的等价关系。,二.等价类,1.定义：R是A上的等价关系，aA,由a确定的集合aR:aR=x|xAR称集合aR为由a生成的R等价类。简称a等价类。可见 xaR R,不同的等价类个数=独立子图个数。上述三个等价关系各有几个等价类？说出对应的各个等价类。,3.等价类性质,R是A上等价关系，任意a,b,cA aR，且aR A。aRbR=，当且仅当 R。证明:设R，假设aRbR,则存在xaRbR，xaRxbR,R,R,由R对称得R又由R传递得R,产生矛盾。若aRbR=,而R,由等价类定义得baR,又因为bRb,所以bbR
49、，所以baRbR，产生矛盾。,3.等价类性质,aR=bR 当且仅当 R。证明：若R，则任何xaR，有R，由对称性得R，再由传递性得R,xbR，所以aRbR。类似可证bRaR。aR=bR。如果aR=bR，由于有aRa,所以aaR，又由于aR=bR，有abR，所以有R，由对称性得R.,三.商集,从算术角度看：1用4除,每份1/4,这就是“商”,于是:1=1/4+1/4+1/4+1/4 从集合角度看：,商集的定义,定义：R是A上等价关系，由R的所有等价类构成的集合称之为A关于R的商集。记作A/R。即 A/R=aR|aA。,定理:集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R.证明：由
50、等价类性质可得：1)对任意的a A，aR，且aRA.2)设aR,bR是A/R的两个不同元素，有 aRbR=；所以，只需要证明 3)aA aR=A。显然aA aR A，由对任意的aA，有aaR aA aR，所以有A aA aR，因此，aA aR A。综上所述，商集A/R是A的一个划分。,四.由划分确定等价关系,例如，X=1,2,3,4,A=1,2,3,4,A是X的一个划分，求X上一个等价关系R，使得X/R=A。,定理:集合X的一个划分可以确定X上的一个等价关系。证明：假设A=A1,A2,.,An是X的一个划分，如下构造X 上的一个等价关系R:R=A12A22,An2 其中Ai2=AiAi，(i=
