北大离散数学ppt课件

1、第5讲 二元关系的基本概念北京大学,内容提要 1. 有序对与卡氏积 2. 二元关系 3. 二元关系的基本运算,1,有序对与卡氏积,有序对(有序二元组) 有序三元组, 有序n元组 卡氏积 卡氏积性质,2,有序对(ordered pair),有序对: = a, a,b 其中, a是第一元素, b是第二元素. 也记作(a,b) 定理1: = a=cb=d 推论: ab ,3,有序对(引理1),引理1: x,a=x,b a=b 证明: () 显然. () 分两种情况. (1) x=a. x,a=x,b a,a=a,b a=a,b a=b. (2) xa. ax,a=x,b a=b. #,4,有序对(引

2、理2),引理2: 若A=B , 则 (1) A=B (2) A=B 证明: (1) x, xA z(zA xz) z(zB xz) xB. (2) x, xA z( zA xz ) z( zB xz ) xB. #,5,有序对(定理1),定理1: = a=cb=d 证明: () 显然. () 由引理2, = a,a,b=c,c,d a,a,b=c,c,da,b=c,d. 又 a,a,b=c,c,d a,a,b=c,c,d a=c a=c. 再由引理1, 得b=d. #,6,有序对(推论),推论: ab 证明: (反证) =a=b, 与ab矛盾. #,7,有序三元组(ordered triple

3、),有序三元组: =,c 有序n(2)元组: =,an 定理2: = ai = bi, i =1,2,n. #,8,卡氏积(Cartesian product),卡氏积: AB=|xAyB. 例: A=,a, B=1,2,3. AB=,. BA=,. AA= , , , . BB= , , . #,9,卡氏积的性质,非交换: AB BA (除非 A=B A= B=) 非结合: (AB)C A(BC) (除非 A= B= C=) 分配律: A(BC) = (AB)(AC)等 其他: AB= A=B=等,10,卡氏积非交换性,非交换: AB BA (除非 A=B A= B=) 反例: A=1, B

4、=2. AB=, BA=.,11,卡氏积非结合性,非结合: (AB)C A(BC) (除非 A= B= C=) 反例: A=B=C=1. (AB)C=,1, A(BC)=.,12,卡氏积分配律,1. A(BC) = (AB)(AC) 2. A(BC) = (AB)(AC) 3. (BC)A = (BA)(CA) 4. (BC)A = (BA)(CA),13,卡氏积分配律(证明1),A(BC) = (AB)(AC). 证明: , A(BC) xAy(BC) xA(yByC) (xAyB)(xAyC) (AB)(AC) (AB)(AC) A(BC) = (AB)(AC). #,14,例题1,例题1

5、: 设A,B,C,D是任意集合, (1) AB= A= B= (2) 若A, 则 ABAC BC. (3) AC BD ABCD, 并且当(A=B=)(AB)时, ABCD ACBD.,15,卡氏积图示,A,B,C,A(BC) = (AB)(AC),ACBDABCD,B,A,C,D,16,例题1(证明(2),(2) 若A, 则ABAC BC. 证明: () 若 B=, 则 BC. 设 B, 由A, 设xA. y, yBAB AC xAyC yC. BC,17,例题1(证明(2),续),(2) 若A, 则ABACBC. 证明(续): ()若B=,则AB=AC. 设 B. , AB xAyB xA

6、yC AC ABAC. # 讨论: 在()中不需要条件 A.,18,n维卡氏积,n维卡氏积: A1A2An = | x1A1x2A2xnAn An = AAA |Ai|=ni ,i =1,2,n |A1A2An| = n1n2nn. n维卡氏积性质与2维卡氏积类似.,19,n维卡氏积(性质),非交换: ABCBCA (要求A,B,C均非空,且互不相等) 非结合: (非2元运算) 分配律: 例如 AB(CD)=(ABC)(ABD) 其他: 如 ABC=A=B=C=.,20,二元关系,n元关系 二元关系 A到B的二元关系 A上的二元关系 一些特殊关系,21,n元关系(n-ary relation)

7、,n元关系: 是集合, 其元素全是有序n元组. 例1: F1=, , F1是4元关系. 例2: F2=, F2是3元关系. #,22,二元关系(binary relation),2元关系(简称关系): 是集合,其元素全是有序对. 例3: R1=, R1是2元关系. 例4: R2=, R2是2元关系. 例5: A=,a,1 A不是关系. #,23,二元关系的记号,设F是二元关系, 则 F x与y具有F关系 xFy 对比: xFy (中缀(infix)记号) F(x,y) (前缀(prefix)记号) F (后缀(suffix)记号) 例如: 2.,24,A到B的二元关系,A到B的二元关系: 是A

8、B的任意子集. R是A到B的二元关系 RAB RP(AB) 若|A|=m,|B|=n, 则|AB|=mn, 故 |P(AB)|=2mn 即A到B不同的二元关系共有2mn个,25,A到B的二元关系(举例),例: 设 A=a1,a2, B=b, 则A到B的二元关系共有4个: R1=, R2=, R3=, R4=,. B到A的二元关系也有4个: R5=, R6=, R7=, R8=,. #,26,A上的二元关系,A上的二元关系: 是AA的任意子集 R是A上的二元关系 RAA RP(AA) 若|A|=m, 则|AA|=m2, 故 |P(AA)|= 即A上不同的二元关系共有 个,27,A上的二元关系(例

9、1),例1: 设 A=a1,a2, 则A上的二元关系共有16个: R1 = , R2 = , R3 = , R4 = , R5 = ,28,A上的二元关系(例1,续1),R6 = , , R7 = , , R8 = , , R9 = , , R10 = , , R11 = , ,29,A上的二元关系(例1,续2),R12 = , R13 = , R14 = , , R15 = , R16 = ,. #,30,A上的二元关系(例2),例2: 设 B=b, 则B上的二元关系共有2个: R1=, R2=. # 例3: 设 C=a,b,c, 则C上的2元关系共有29=512个! #,31,一些特殊关系

10、,空关系 恒等关系 全域关系 整除关系 小于等于关系, 包含关系, 真包含关系,32,特殊关系,设A是任意集合, 则可以定义A上的: 空关系: 恒等关系: IA = | xA 全域关系: EA = AA = | xA yA,33,特殊关系(续),设AZ, 则可以定义A上的: 整除关系: DA = | xA yA x|y 例: A=1,2,3,4,5,6, 则 DA= , , ,. #,34,特殊关系(续),设AR, 则可以定义A上的: 小于等于(less than or equal to)关系: LEA = | xA yA xy 小于(less than)关系, LA = | xA yA xy

11、 大于等于(greater than or equal to)关系 大于(great than)关系,35,特殊关系(续),设A为任意集合, 则可以定义P(A)上的: 包含关系: A = | xA yA xy 真包含关系: A = | xA yA xy ,36,与二元关系有关的概念,定义域, 值域, 域 逆, 合成(复合) 限制, 象 单根, 单值,37,定义域,值域,域,对任意集合R, 可以定义: 定义域(domain) : dom R = x | y(xRy) 值域(range): ran R = y | x(xRy) 域(field): fld R = dom R ran R,38,定义

12、域,值域,域图示,A,B,dom R,ran R,39,定义域,值域,域(举例),例: R1=a,b, R2=a,b, R3=,. 当a,b不是有序对时, R1和R2不是关系. dom R1=, ran R1=, fld R1= dom R2=c,e, ran R2=d,f, fld R2=c,d,e,f dom R3=1,3,5, ran R3=2,4,6, fld R3=1,2,3,4,5,6. #,40,逆, 合成(复合),对任意集合F,G, 可以定义: 逆(inverse) : F-1 = | yFx 合成(复合)(composite): FG = | z( xGz zFy ) ,x,

13、z,y,G,F,41,关于合成,顺序合成(右合成): FG = | z( xFz zGy ) 逆序合成(左合成): FG = | z( xGz zFy ) ,42,限制,象,对任意集合F,A, 可以定义: 限制(restriction): FA = | xFy xA 象(image): FA = ran(FA) FA = y | x(xA xRy) ,43,单根,单值,对任意集合F, 可以定义: 单根(single rooted): F是单根的 y( yran F !x( xdom F xFy ) ) (yran F)(!xdom F)(xFy) 单值(single valued): F是单值

14、的 x( xdom F !y( yran F xFy ) ) (xdom F)(!yran F)(xFy),44,例题2,例2: 设 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) Fa, Fa, Fa,a, F-1a. (4) Fa, Fa,a, F-1a, F-1a.,45,例题2(解(1),已知: A=a,b,c,d, B=a,b, R= , , 求: (1) A-1, B-1,R-1. 解: (1) A-1 = , B-1 = , R-1 = ,.,46,例题

15、2(解(2),已知: B=a,b, R= , , G= , . 求: (2) BR-1, GB, GR, RG. 解: (2) BR-1=, GB=, GR=, RG=.,47,例题2(解(3),已知: F= , , , 求: (3) Fa, Fa, Fa,a, F-1a. 解: (3) Fa = , , Fa = , Fa,a = F, F-1a= .,48,例题2(解(4),已知: F= , , , 求: (4) Fa, Fa,a, F-1a, F-1a. 解: (4) Fa = b, a , Fa,a = b, a, a,a , F-1a = , F-1a = a . #,49,例题3,

16、设 R= | x,yZ y=|x| , A= 0, 1, 2, B= 0, -1, -2 求: (1) RAB 和 RARB; (2) RA-RB 和 RA-B. 解: (1) RAB=R0=0, RARB=0,1,20,1,2=0,1,2; (2) RA-RB=0,1,2-0,1,2= , RA-B=R1,2=1,2. #,50,定理3,定理3: 设F,G是任意集合, 则 (1) dom(FG) = domF domG (2) ran(FG) = ranF ranG (3) dom(FG) domF domG (4) ran(FG) ranF ranG (5) domF-domG dom(F

17、-G) (6) ran F-ranG ran(F-G),51,定理3(证明(1),(1) dom(FG) = domF domG 证明: (1) x, xdom(FG) y( x(FG)y ) y(xFy xGy) y(xFy)y(xGy) xdomF xdomG x domF domG dom(FG) = domF domG.,52,定理3(证明(4),(4) ran(FG) ranF ranG 证明: (4) x, xran(FG) y( y(FG)x ) y(yFx yGx) y(yFx) y(yGx) xranF xranG x ranF ranG ran(F G) ranF ranG

18、.,53,定理3(证明(5),(5) domF-domG dom(F-G) 证明: (5) x, xdomF-domG xdomF xdomG y(xFy)y(xGy) y(xFy)y(xGy) y( x(F-G)y ) x dom(F-G) domF-domG dom(F-G). #,54,定理4,定理4: 设F是任意集合, 则 (1) domF-1 = ranF; (2) ranF-1 = domF; (3) (F-1)-1 F, 当F是关系时, 等号成立.,55,定理4(证明(1),(1) domF-1 = ranF; 证明: (1) x, xdomF-1 y(xF-1 y) y(yFx) xranF domF-1 = ranF. (2)可类似证明.,56,定理4(证明(3),(3) (F-1)-1