第二二元关系ppt课件

1、第二章 二元关系2-1 有序对与卡氏积2-2 二元关系2-3 关系矩阵和关系图2-4 关系的性质2-5 二元关系的幂运算2-6 关系的闭包2-7 等价关系和划分2-8 序关系2-1 有序对与卡氏积1. 有序对(序偶)的概念2. 卡氏(笛卡儿)积3. 笛卡儿积的性质1、序偶的概念定义定义2.1 2.1 称称a,a,ba,a,b为由元素为由元素a a、b b构成的有序构成的有序对或序偶，记作对或序偶，记作。其中。其中a a称为有序对的第一个称为有序对的第一个元素，元素，b b称为第二个元素，且称为第二个元素，且a a，b b可以一样。可以一样。许多事物是成对出现的，而且这种成对出现的事物，具有一定

2、的顺序。例如：上、下；左、右；34；平面上的坐标等。普通地说，由两个具有固定次序的客体组成，来表达两个客体之间的关系。注：有序对可以看作是具有两个元素的集合，与普通集合不同的是有序对具有确定的次序。定理定理2.1 =2.1 =，当且仅当，当且仅当a=c,b=da=c,b=d。引理引理1 x,a=x,b1 x,a=x,b，当且仅当，当且仅当a=ba=b。引理引理2 2 设设A,BA,B是非空的集族，假设是非空的集族，假设A=B,A=B,那么那么(1)A=B ; (2) A=B(1)A=B ; (2) A=B推论推论 a ab b时，时， 引理1的证明nx,a=x,bx,a=x,b当且仅当当且仅当

3、 a=ba=b。n证明：证明：a=b a=b x,a=x,b x,a=x,bnx=a, x,a=x,bx=a, x,a=x,ba,a=a,ba,a=a,bn a=a,b a=a,b b=a b=anx xa, aa, ax,a=x,bx,a=x,b a=b a=bn x,a=x,b x,a=x,b a=b a=b# #引理2的证明引理引理2 2 设设A,BA,B是非空的集族，假设是非空的集族，假设A=B,A=B,那么那么(1)A=B ; (2) A=B(1)A=B ; (2) A=B证明证明: (1): (1)x,x,x xA A z(zz(zA Ax xz)z)z(zz(zB Bx xz)z

4、)x xBB A = B A = B(2) (2) x,x,x xAAz(zz(zA Ax xz)z)z(zz(zB Bx xz)z)x xBB A = B A = B# #定理证明n=，当且仅当，当且仅当a=c,b=da=c,b=d。n证明：证明：=a,a,b=c,c,da,a,b=c,c,dna,a,b= c,c,da,a,b= c,c,da,b=c,da,b=c,dna,a,b=c,c,d a,a,b=c,c,d a,a,b= a,a,b= c,c,dc,c,da=c a=c a=c a=cn(a,b=c,d)(a,b=c,d)(a=c) (a=c) b=d b=dn = = a=c,b

5、=d a=c,b=d。 # #推论证明n 推论: ab n证明: (反证) =a=b,与ab矛盾. #序偶的概念可推行到三元组、四元组、序偶的概念可推行到三元组、四元组、 n n元组元组: : 有序三元组有序三元组(ordered triple)(ordered triple)表示序偶表示序偶,z;,z; 有序四元组有序四元组表示序偶表示序偶,w;,w; 有序有序n n元组元组表示序偶表示序偶x1,x2,xn-,xn 1,xn 定义定义2.2 2.2 一个有序一个有序n(nn(n2)2)元组是一个有序对，它的元组是一个有序对，它的第一个元素为有序的第一个元素为有序的(n-1)(n-1)元组元组

6、，第二个元素为第二个元素为anan，记为，记为。即。即,an = ,an = 定理定理2.2 = 2.2 = 当且当且仅当仅当ai=bi, i=1,2, n. ai=bi, i=1,2, n. 有序n元组注：注：n元组有严厉的集合定义，但我们关注的是有序对及元组有严厉的集合定义，但我们关注的是有序对及有序有序n元组的次序性，不过多讨论他们的集合表示。元组的次序性，不过多讨论他们的集合表示。2、卡氏积(Cartesian product)n定义2.3 设A、B为集合，称由A中元素为第一个元素，B中元素为第二个元素的一切有序对组成的集合为A与B的卡氏积(笛卡儿积),记作AB,即AB=|xAyB 。

7、 例1 设A =a,b， B =1，2，3, 求AB， BA。解：AB=,。 BA=,。 由此例可知，笛卡儿积不满足交换律。#3、笛卡儿积的性质设设A、B、C为恣意集合，那么笛卡儿积的运算有如下性质：为恣意集合，那么笛卡儿积的运算有如下性质：1A=，A=2不适宜交换律：不适宜交换律：AB BA当当A B A B时时3不适宜结合律：不适宜结合律：(AB)C A(BC)当当A B C 时时4分配律：分配律：A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 后四个式子按集合相等的概念可以证明。后四个式子按集合相等的概念可以证明。笛

8、卡儿积的性质例 证明(B C)A=(BA) (CA) 证:在集合(BC)A中任取，那么 (BC)A x(BC)yA (xBxC)yA xByAxCyA (xByA)(xCyA) (BA)(CA) (BA)(CA)(BC)A=(BA)(CA)。#(卡氏积图示)3、笛卡儿积的性质(续1)5假设假设C ,那么那么 AB (AC BC) (CA CB)证证: 证证, 任取任取 AC，有，有 AC xAyC xByC BC因此，因此， AC BC。证证, 假设假设A= , 那么那么AB. 假设假设A ,C , AC BC, 取取yC ，那么有，那么有xA xAyC 已设已设yC ，故，故yC 为真为真

9、AC BC xByC xB因此，因此， AB类似可证：类似可证： AB (CA CB)。 #6设设A、B、C、D为恣意非空集合，那么为恣意非空集合，那么 (AB CD) AC BD 证明与性质证明与性质5的证明方法类似，从略的证明方法类似，从略3、笛卡儿积的性质(续2)例 证明(A-B)C=(AC)-(BC)。证：证：(A-B)C x(A-B)yC xAxB yC (x AyC xB) (xAyC yC) (x AyC) (xByC) (x AyC) (xByC) (x AyC)(xByC) ACBC (AC)-(BC)所以，所以，(A-B)C=(AC)-(BC)。#n维卡氏积n定义2.4 设

10、A1,A2,An为n个集合(n2)，称集合n|x1A1x2A2 xnAn n为n维卡氏积，记作A1 A2An ，当A1=A2=An=A时，记A生成的n维卡氏积为Ann设A1,A2,An均为有穷集合，并设|Ai|=ni, i=1,2,n，那么 |A1 A2An|=n1 n2 nnn性质：例如nAB(CD)=(ABC)(ABD)nABC= A= B= C= .2.2 二元关系 事物之间存在着各式各样的关系，例如，三名学生A、B、C选修、四门课，设A选和，B选，C选和，那么，学生选课的对应关系可记作 ： R=,这个序偶的集合R反映了学生集合S=A,B,C与课程集合T=,之间的关系。关系的概念关系的运

11、算定理定义定义2.5 2.5 假设集合假设集合F F中的全体元素均为有序的中的全体元素均为有序的n(nn(n2)2)元组，那么称元组，那么称F F为为n n元关系。当元关系。当n=2n=2时，称时，称F F为二元关系为二元关系, ,简称为关系。简称为关系。对于二元关系对于二元关系F F，假设，假设 F F，记作，记作 xFyxFy表示方法：表示方法：( (中缀，前缀，后缀中缀，前缀，后缀规定空集规定空集为为n n元空关系，简称空关系元空关系，简称空关系n元关系续n例1: F1=,F1是4元关系. # n例2:F2=, F2是3元关系. #n例3:R1=, R1是2元关系. # n例4:R2=,

12、 R2是2元关系. # n例5:A=,a,1, A不是关系. #关系的概念(续1)定义2.6 设A和B是两个恣意集合，卡氏积AB的任一子集R称为A到B的二元关系。RABRP(AB)假设|A|=m,|B|=n, 那么|AB|=mn, 故|P(AB)|=2mn即A到B不同的二元关系共有2mn个关系举例例 设A=1，2，3，4，求A上的小于等于关系LA解：LA=|x,yAxy = , , , , , #关系举例n设A=a1,a2, B=b,n那么A到B的二元关系共有4个:nR1=, R2=, R3=,nR4=,. nB到A的二元关系也有4个:nR5= , R6=, R7=,nR8=,. # A上的二

13、元关系A上的二元关系: 是AA的恣意子集R是A上的二元关系RAARP(AA) 例 设集合A有n个元素,问A上能够的二元关系有多少个？解：集合A上的二元关系与AA的子集个数一样。假设|A|=n，那么|AA|=n2, AA的子集个数就有2的n2次方个。所以A上不同的二元关系有2的n2次方个。 例如，集合A=a,b上的二元关系有16个关系的概念(续4)关系的概念(续3)求：集合求：集合A=a,bA=a,b上的上的1616个二元关系。个二元关系。R1= R1= ( (空关系空关系) ;) ;R2=, R3=, R4=, R5=;R2=, R3=, R4=, R5=;R6= , (R6= , (恒等关系

14、恒等关系IA)IA)，R7=, R8=,R7=, R8=,R 9 = , , R 1 0 = , , R 9 = , , R 1 0 = , , R11=,;R11=,;R12=, R13=,R12=, R13=,R14=, R15=,;R14=, R15=,;R16= , (R16= , (全域关系全域关系EA) EA) 。几种特殊的关系称称EA= ( EA= ( x x A A y y A) =AA) =AA A 是是A A上的全域关系。上的全域关系。称称IA= ( IA= ( x x A) A) 是是A A上的恒等关系。上的恒等关系。假设假设A A是实数集或其子集，是实数集或其子集，称称

15、DA= (DA= (x x A A y y A A x|y) x|y) 是是A A上的整除关系。上的整除关系。称称LA= (LA= (x x A A y y A A x xy) y) 是是A A上的小于等上的小于等于关系。于关系。假设假设A A为恣意的集合为恣意的集合称称A= (A= (x xA A y yA A x x y) y) 是是P(A)P(A)上的包含上的包含关系。关系。称称A= (A= (x xA A y yA A x x y) y) 是是P(A)P(A)上的真包上的真包含关系含关系整除关系举例例: A=1,2,3,4,5,6, 那么DA=, , , , , , , ,.#二元关系

16、相关概念n 定义域, 值域, 域n 逆, 合成(复合)n 限制, 象n 单根, 单值关系相关的概念定义2.7 设R为任一集合，称domR = xy (R) 为R的定义域，称ranR = yx (R) 为R的值域， 称fldR = domR ranR为R的域。例：设R1=a,b,R2=a,b, R3=,解：当a,b不是有序对时, R1和R2不是关系.由定义得domR1=, ranR1=, fldR1=,domR2=c,e,ranR2=d,f,fldR2=c,e,d,f,domR3=1,3,5,ranR3=2,4,6,fldR3=1,2,3,4,5,6#关系的运算定义2.8 设F,G,A为3个集合

17、，F的逆(inverse):称F-1=|F(2) F与G的合成或复合(composite): FG=|z(G F)GxzyFn留意n(1) 当R中无有序对时，domR,ranR,fldR均为n(2) FG的合成为逆序合成限制和像FA=|FxA为为F在在A上的限制上的限制(restriction)FA=ran(FA)为为A在在F下的像下的像FA=y|x(xA xRy) 单根假设对于恣意的假设对于恣意的yranF,独一地存在着独一地存在着xdomF, 使得使得F，那么称，那么称F是单根是单根(single rooted)的的y( yran F !x( xdomF xFy) )(yran F)(!x

18、domF)(xFy) !表示表示“存在独一的存在独一的单值(single valued)n假设对于恣意的xdomF,独一地存在着yranF，使得F，那么称F是单值的n x( xdomF !y( yran F xFy) (xdomF)(!yran F)(xFy)举例设A=a,b,c,d, B=a,b, R=, F=, , G=,，求(1) A-1,B-1,R-1. (2) BR-1, GB, GR, RG. (3) F a, F a, F a,a, F-1 a.(4) Fa, Fa,a, F-1a, F-1a解:(1) A-1=, B-1=,R-1=,.(2) BR-1=, GB=, GR=,

19、RG=.(3) F a=,F a=, F a,a=F, F-1 a=.(4) Fa=b,a, Fa,a=b,a,a,a, F-1a= , F-1a=a#n定理2.3 定义域和值域相关的定理n定理2.4逆的定义域和值域相关定理n定理2.5合成的结合律n定理2.6合成相关的分配律n定理2.7逆合成定理n定理2.8限制相关的定理n定理2.9像相关的定理定理定理2.3 设设F,G为二集合，那么为二集合，那么dom(FG) = domFdomG; ran(FG) = ranFranG; dom(FG) domFdomG;ran(FG) ranFranG; domFdomG dom(F G);ranFra

20、nG ran(F G).定理2.3的证明证：dom(FG) = domFdomG证明：x, xdom(FG)y( FG)y( F)(G)y( F) y(G)xdom(F) xdom(G)x (dom(F) dom(G) dom(FG) = domFdomG#证：ran(FG) ranFranG证明：y, yran(FG)x( FG)x(FG)x(F)x(G)(P7)yran(F)yran(G)y(ranF ranG) ran(FG) ranFranG#定理2.3的证明(续)证：domFdomG dom(F G)证明：x, x(domF-domG)(xdomF)(xdomG)y(F)z(G) y

21、(F-G)x dom(F-G) domFdomG dom(F G)定理2.3的证明(续)逆的定义域和值域相关定理定理2.4 设F为任一集合，那么domF-1=ranF;ranF-1=domF;(F-1)-1F,当F为关系时，等号成立定理2.4(1)的证明(1) 证明: x, xdomF-1yF-1yFxranFdomF-1=ranF#定理2.4(3)的证明(3) (F-1)-1F, 当F是关系时, 等号成立.证明: (1) 设F是关系, 那么,(F-1)-1 x(F-1)-1y yF-1xxFy.这时(F-1)-1= F. 当F不是关系时,(F-1)-1F, 例如, 设F=,a, 那么F-1=

22、, (F-1)-1= F(F-1)-1F. #合成运算的结合律定理定理2.5 设设R1,R2,R3为三个集合，那么为三个集合，那么(R1 R2)R3 = R1(R2R3)证明：证明： , (R1 R2)R3 z(R3(R1 R2)z(R3 t(R2 R1)z t(R3R2 R1)t(z (R3R2 R1)t(R2 R3 R1) R1 (R2 R3)(R1 R2)R3 = R1(R2R3)#xyztR3R2R1合成运算的分配律定理定理2.6设设R1,R2,R3为三个集合，那么为三个集合，那么R1(R2 R3)=R1R2 R1R3;(R1R2)R3 =R1R3R2R3;R1(R2R3) R1R2 R1R3;(R1R2)R3 R1R3 R2R3.分配律的证明R1(R2 R3)=R1R2 R1R3证明： , R1(R2 R3)z(R2 R3)R1)z(R2R3)R1)z(R2 R1) (R3R1)z(R2 R1) z(R3R1) R1R2 R1R3(R1R2 R1R3) R1(R2 R3)=R1R2 R1R3#分配律的证明(续)R1(R2R3) R1R2 R1R3证明：, R1(R2R3)z(R2R3)R1)z(R2 R3)R1)z(R2 R1) (R3R1)z(R2 R1)