《集合论与图论：第6讲 关系表示与关系性质》由会员分享，可在线阅读，更多相关《集合论与图论：第6讲 关系表示与关系性质（63页珍藏版）》请在金锄头文库上搜索。
1、第6讲 关系表示与关系性质内容提要关系运算性质(续)关系矩阵, 关系图自反, 反自反, 对称, 反对称, 传递2024/7/271集合论与图论第6讲关系基本运算的性质(续)定理6定理9定理6: 设R1,R2,R3是集合,则 (1) R1(R2R3) = (R1R2)(R1R3) (2) (R1R2)R3 = (R1R3)(R2R3) (3) R1(R2R3) (R1R2)(R1R3) (4) (R1R2)R3 (R1R3)(R2R3)2024/7/272集合论与图论第6讲定理6(证明(1) (1) R1(R2R3) = (R1R2)(R1R3)证明: , R1(R2R3)z(x(R2R3)zz
2、R1y)z(xR2zxR3z)zR1y)z(xR2zzR1y)(xR3zzR1y)z(xR2zzR1y)z(xR3zzR1y)x(R1R2)yx(R1R3)yx(R1R2)(R1R3)y(R1R2)(R1R3)2024/7/273集合论与图论第6讲定理6(证明(3) (3) R1(R2R3) (R1R2)(R1R3)证明: , R1(R2R3)z(x(R2R3)zzR1y)z(xR2zxR3z)zR1y)z(xR2zzR1y)(xR3zzR1y)z(xR2zzR1y)z(xR3zzR1y)x(R1R2)yx(R1R3)yx(R1R2)(R1R3)y(R1R2)(R1R3). #2024/7/2
3、74集合论与图论第6讲定理6(讨论(3)(3) R1(R2R3) (R1R2)(R1R3)反例(说明=不成立): 设 R1=, R2=, R3=. 则R1(R2R3) = R1 = , R1R2=, R1R3=, (R1R2)(R1R3)=. #abcd2024/7/275集合论与图论第6讲定理7定理7: 设F,G为二集合, 则(FG)-1 = G-1F-1.GG-1FF-12024/7/276集合论与图论第6讲定理7(证明)(FG)-1 = G-1F-1证明: , (FG)-1 (FG) z(yGzzFx)z(zG-1yxF-1z) z(xF-1zzG-1y) G-1F-1. #xyz202
4、4/7/277集合论与图论第6讲定理8定理8: 设R,S,A,B,A,为集合,A,则 (1) R(AB) = (RA)(RB); (2) RA = RA | AA; (3) R(AB) = (RA)(RB); (4) RA = RA | AA; (5) (RS)A = R(SA).2024/7/278集合论与图论第6讲定理8(证明(2)(2) RA = RA | AA;证明: , x(RA)y xRyxA xRy A( AA xA ) A( xRy xA AA ) A( x(RA)y AA ) x( RA | AA )y. RA = RA | AA2024/7/279集合论与图论第6讲定理8(
5、证明(4)(4) RA = RA | AA; (A)证明:, x(RA)y xRyxA(0xRy)xA (A(AA)xRy)xAA(AAxRy)A(AAxA)A(AAxRy)(AAxA)A(AA(xRy) xA)A(AA)x(RA)y)A(AAx(RA)y) x( RA | AA )y. RA = RA | AA2024/7/2710集合论与图论第6讲定理8(证明(5) (5) (RS)A = R(SA)证明: , x(RS)A)y x(RS)y xA z(xSzzRy ) xA z(xSzzRy xA) z(xSzxA) zRy ) z( x(SA)z zRy ) x(R(SA)y. RA
6、= RA | AA. #2024/7/2711集合论与图论第6讲定理9定理9: 设R,S,A,B,A,为集合,A,则 (1) RAB = RARB; (2) RA = RA | AA ; (3) RAB RARB; (4) RA RA | AA; (5) RA-RB RA-B; (6) (RS)A = RSA.2024/7/2712集合论与图论第6讲定理9(证明(2)(2) RA = RA | AA ;证明: y, yRA x(xRyxA) x( xRy A( AA xA) A( AA x( xRy xA ) ) A(AAyRA) y RA | AA . RA = RA | AA. 2024/
7、7/2713集合论与图论第6讲定理9(证明(4)(4) RA RA | AA; 证明: y, yRA x(xRyxA) x(xRyA(AAxA)xA(xRy(AAxA)Ax(xRy(AAxA) (*)Ax(AA(xRyxA) (*)A(AAx(xRyxA)A(AAyRA)y RA | AA .RA RA | AA. 2024/7/2714集合论与图论第6讲定理9(证明(4),续)(*) xA(xRy(AAxA)Ax(xRy(AAxA)(*) Ax(xRy(AAxA)Ax(AA(xRyxA)容易证明: (*) xyB(x,y) yxB(x,y)(*) p(qr) q(pr)2024/7/2715
8、集合论与图论第6讲定理9(证明(4),续)(*) xyB(x,y) yxB(x,y)证明: 在任何解释下, 若左1, 则右1.2024/7/2716集合论与图论第6讲定理9(证明(4),续)(*) p(qr) q(pr)证明1: (p(qr)(q(pr)是永真式 真值表, 等值演算证明2: (反证) 设“左1”且“右0”即p(qr)1且q(pr)0. 由p(qr)1得p=1, qr=1;由q(pr)0得q=1, pr=0; 所以r=0, qr=0, 矛盾! #2024/7/2717集合论与图论第6讲定理9(证明(5)(5) RA-RB RA-B;证明: y, yRA-RB yRAyRB x(x
9、RyxA) x(xRyxB) x(xRyxA) x(xRyxB) x(xRyxA) x(xRyxB) x(xRyxAxB) x(xRyxA-B) yRA-B. RA-RB RA-B. 2024/7/2718集合论与图论第6讲定理9(证明(5),续) x(xRyxA) x(xRyxB) x(xRyxAxB)前提: x(xRyxA), x(xRyxB)结论: x(xRyxAxB)证明: (1) x(xRyxA), 前提引入 (2) cRycA, (1)EI (3) x(xRyxB), 前提引入 (4) cRycB, (3)UI2024/7/2719集合论与图论第6讲定理9(证明(5),续)前提:
10、x(xRyxA), x(xRyxB)结论: x(xRyxAxB)证明: (1) x(xRyxA), 前提引入 (2) cRycA, (1)EI (3) x(xRyxB), 前提引入 (4) cRycB, (3)UI (5) cRy, (2)化简 (6) cB, (4)(5)假言推理2024/7/2720集合论与图论第6讲定理9(证明(5),续)证明: (1) x(xRyxA), 前提引入 (2) cRycA, (1)EI (3) x(xRyxB), 前提引入 (4) cRycB, (3)UI (5) cRy, (2)化简 (6) cB, (4)(5)假言推理 (7) cRycAcB, (2)(
11、6)合取 (8) x(xRyxAxB) (7)EG. #2024/7/2721集合论与图论第6讲定理9(证明(6)(6) (RS)A = RSA.证明:y, y(RS)A x( x(RS)y xA ) x( z( xSz zRy ) xA ) z( zRy x( xSz xA ) ) z( zRy zSA) y RSA. (RS)A = RSA. #2024/7/2722集合论与图论第6讲定理9(讨论)讨论: 当R为单根关系时, (3)(4)(5)中等号成立. (3) RAB RARB; (4) RA RA | AA; (5) RA-RB RA-B;2024/7/2723集合论与图论第6讲关系
12、表示法关系的表示方法:集合关系矩阵关系图2024/7/2724集合论与图论第6讲关系矩阵(matrix)设 A=a1,a2,an, RAA, 则R的关系矩阵 M(R)=(rij)nn, 其中例如, A=a,b,c, R1=,R2=, 则 #2024/7/2725集合论与图论第6讲关系矩阵的性质R的集合表达式与R的关系矩阵可以唯一相互确定M(R-1) = (M(R)T. (T表示矩阵转置)M(R1R2) = M(R2)M(R1). (表示这样的矩阵“乘法”, 其中加法使用逻辑, 乘法使用逻辑. )2024/7/2726集合论与图论第6讲例题4例题4: 设 A=a,b,c, R1=, R2=, 用
13、M(R1), M(R2)确定M(R1-1), M(R2-2), M(R1R1), M(R1R2), M(R2R1), 从而求出它们的集合表达式.2024/7/2727集合论与图论第6讲例题4(解)R1=, R2=, 解: R1-1 = , R2-1 = ,2024/7/2728集合论与图论第6讲例题4(解,续)R1=, R2=, 解(续): R1R1 = ,.2024/7/2729集合论与图论第6讲例题4(解,续)R1=, R2=, 解(续): R1R2 = ,.2024/7/2730集合论与图论第6讲例题4(解,续)R1=, R2=, 解(续): R2R1 = ,. #2024/7/2731
14、集合论与图论第6讲关系图(graph)设 A=a1,a2,an, RAA, 则A中元素以“”表示(称为顶点), R中元素以“”表示(称为有向边); 若xiRxj, 则从顶点xi向顶点xj引有向边, 这样得到的图称为R的关系图 G(R).例如, A=a,b,c, R1=,R2=, 则abcabcG(R1)G(R2)2024/7/2732集合论与图论第6讲关系图(举例)R1-1 = ,R2-1 = ,abcG(R2-1 )cG(R1-1)ab2024/7/2733集合论与图论第6讲关系图(举例,续)R1R1 = ,.R1R2 = ,.R2R1 = ,. abcG(R1 R2 )cG(R1 R1)a
15、bcG(R2 R1)ab2024/7/2734集合论与图论第6讲关系矩阵,关系图(讨论)当A中元素标定次序后, RAA的关系图G(R)与R的集合表达式可以唯一互相确定R的集合表达式,关系矩阵,关系图三者均可以唯一互相确定对于RAB, |A|=n,|B|=m,关系矩阵M(R)是nm阶的,关系图G(R)中的边都是从A中元素指向B中元素的.2024/7/2735集合论与图论第6讲关系性质自反性(reflexivity)反自反性(irreflexivity) 对称性(symmetry)反对称性(antisymmetry)传递性(transitivity)2024/7/2736集合论与图论第6讲自反性(
16、reflexivity)设RAA, 说R是自反的(reflexive),如果x( xA xRx ).R是非自反的 x( xA xRx)定理10: R是自反的 IAR R-1是自反的 M( R )主对角线上的元素全为1 G( R )的每个顶点处均有环. #2024/7/2737集合论与图论第6讲自反性(举例)2024/7/2738集合论与图论第6讲反自反性(irreflexivity)设RAA, 说R是反自反的(irreflexive), 如果x(xA xRx).R是非反自反的 x( xA xRx)定理11: R是反自反的 IAR= R-1是反自反的 M( R )主对角线上的元素全为0 G( R
17、 )的每个顶点处均无环. #2024/7/2739集合论与图论第6讲反自反性(举例)2024/7/2740集合论与图论第6讲自反,自反性(分类)自反反自反非自反, 非反自反自反且反自反 ?上的空关系2024/7/2741集合论与图论第6讲对称性(symmetry)设RAA, 说R是对称的(symmetric),如果xy(xAyAxRyyRx).R非对称 xy(xAyAxRyyRx)定理12: R是对称的 R-1=R R-1是对称的 M( R )是对称的 G( R )的任何两个顶点之间若有边, 则必有两条方向相反的有向边. #2024/7/2742集合论与图论第6讲对称性(举例)2024/7/2
18、743集合论与图论第6讲反对称性(antisymmetry)设RAA, 说R是反对称的(antisymmetric),若xy(xAyAxRyyRxx=y).R非反对称xy(xAyAxRyyRxxy)定理13: R是反对称的 R-1 RIA R-1是反对称的 在M( R )中, ij(ijrij=1rji=0) 在G( R )中, xixj(ij), 若有有向边, 则必没有. #2024/7/2744集合论与图论第6讲反对称性(举例)2024/7/2745集合论与图论第6讲对称,反对称(分类)对称反对称非对称, 非反对称对称且反对称 ?2024/7/2746集合论与图论第6讲传递性(transi
19、tivity)设RAA, 说R是传递的(transitive), 如果xyz(xAyAzAxRyyRzxRz).R非传递xyz(xAyAzAxRyyRzxRz)定理14: R是传递的 RRR R-1是传递的 在M(RR)中, ij, 若rij=1,则M( R )中相应的元素rij=1. 在G( R )中, xixjxk, 若有有向边, 则必有有向边. #2024/7/2747集合论与图论第6讲传递性(举例)2024/7/2748集合论与图论第6讲传递(分类)非传递传递2024/7/2749集合论与图论第6讲举例在 N = 0,1,2, 上:=|xNyNxy自反,反对称,传递=|xNyNxy自反
20、,反对称,传递=|xNyNx=|xNyNxy反自反,反对称,传递|=|xNyNx|y反对称,传递(0|0)IN=|xNyNx=y自反,对称,反对称,传递EN=|xNyN=NN自反,对称,传递. #2024/7/2750集合论与图论第6讲例5例5: A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,2024/7/2751集合论与图论第6讲例5(续)R1=,反对称,传递R2=,反对称G(R1)acbG(R2)acb2024/7/2752集合论与图论第6讲例5(续)R3=,自反,对称,传递R4=,对称G(R3)acbG(R4)acb2024/7/2753集合论与图论第6讲例5(续)R5=
21、,自反,反对称,传递R6=,. #G(R5)acbG(R6)acb2024/7/2754集合论与图论第6讲关系运算是否保持关系性质定理15: 设R1,R2AA都具有某种性质.自反 反自反 对称 反对称 传递R1-1, R2-1(4)R1R2R1R2(2)(5)R1R2 , R2R1(1)R1-R2 , R2-R1(3)R1,R2(3)2024/7/2755集合论与图论第6讲定理15(证明(1)(1) R1,R2自反 R1R2自反.证明:x, xA xR2x xR1x xR1R2x R1,R2自反 R1R2自反. #2024/7/2756集合论与图论第6讲定理15(证明(2)(2) R1,R2反
22、自反 R1R2反自反.证明: (反证) 若R1R2非反自反, 则 xA, x(R1R2)x xR1x xR2x 与R1,R2反自反矛盾! R1,R2反自反 R1R2反自反. #2024/7/2757集合论与图论第6讲定理15(证明(3)(3) R1,R2对称 R1-R2对称.证明:x,yA, x(R1-R2)y xR1y xR2y yR1x yR2x y(R1-R2)x R1,R2对称 R1-R2对称. #2024/7/2758集合论与图论第6讲定理15(证明(3)(3) R1对称 R1对称.证明: x,yA, x(R1)y x(EA-R1)y xEAy xR1y yEAx yR1x y(EA
23、-R1)x y(R1)x R1对称 R1对称. #2024/7/2759集合论与图论第6讲定理15(证明(4)(4) R1反对称 R1-1反对称.证明: (反证) 若R1-1非反对称, 则 x,yA, xR1-1y yR1-1x xy yR1x xR1y xy 与R1反对称矛盾! R1反对称 R1-1反对称. #2024/7/2760集合论与图论第6讲定理15(证明(5)(5) R1,R2传递 R1R2传递.证明:x,y,zA, x(R1R2)y y(R1R2)z xR1y xR2y yR1z yR2z xR1y yR1z xR2y yR2z xR1z xR2z x(R1R2)z R1,R2传递 R1R2传递. #2024/7/2761集合论与图论第6讲总结关系矩阵, 关系图自反, 反自反, 对称, 反对称, 传递2024/7/2762集合论与图论第6讲作业(#4)p81, 习题二, 15, 16, 17, 22, 23下周一(3月3日)交作业#1,#2,#3,#42024/7/2763集合论与图论第6讲
