集合論與圖論：第6講 關(guān)系表示與關(guān)系性質(zhì)

第6講關(guān)系表示與關(guān)系性質(zhì)內(nèi)容提要關(guān)系運算性質(zhì)(續(xù))關(guān)系矩陣,關(guān)系圖自反,反自反,對稱,反對稱,傳遞2023/1/111《集合論與圖論》第6講關(guān)系基本運算的性質(zhì)(續(xù))定理6~定理9定理6:設(shè)R1,R2,R3是集合,則(1)R1○(R2R3)=(R1○R2)(R1○R3)

(2)(R1R2)○R3=(R1○R3)(R2○R3)

(3)R1○(R2R3)

(R1○R2)(R1○R3)

(4)(R1R2)○R3

(R1○R3)(R2○R3)2023/1/112《集合論與圖論》第6講定理6(證明(1))(1)R1○(R2R3)=(R1○R2)(R1○R3)證明:<x,y>,<x,y>R1○(R2R3)z(x(R2R3)zzR1y)z((xR2zxR3z)zR1y)z((xR2zzR1y)(xR3zzR1y))z(xR2zzR1y)z(xR3zzR1y)x(R1○R2)yx(R1○R3)yx((R1○R2)(R1○R3))y<x,y>(R1○R2)(R1○R3)2023/1/113《集合論與圖論》第6講定理6(證明(3))(3)R1○(R2R3)

(R1○R2)(R1○R3)證明:<x,y>,<x,y>R1○(R2R3)z(x(R2R3)zzR1y)z((xR2zxR3z)zR1y)z((xR2zzR1y)(xR3zzR1y))z(xR2zzR1y)z(xR3zzR1y)x(R1○R2)yx(R1○R3)yx((R1○R2)(R1○R3))y<x,y>(R1○R2)(R1○R3).#2023/1/114《集合論與圖論》第6講定理6(討論(3))(3)R1○(R2R3)

(R1○R2)(R1○R3)反例(說明=不成立):設(shè)R1={<b,d>,<c,d>},R2={<a,b>},R3={<a,c>}.則R1○(R2R3)=R1○=,

R1○R2={<a,d>},R1○R3={<a,d>},(R1○R2)(R1○R3)={<a,d>}.#abcd2023/1/115《集合論與圖論》第6講定理7定理7:設(shè)F,G為二集合,則(F○G)-1=G-1○F-1.GG-1FF-12023/1/116《集合論與圖論》第6講定理7(證明)(F○G)-1=G-1○F-1證明:<x,y>,<x,y>(F○G)-1

<y,x>(F○G)z(yGzzFx)z(zG-1yxF-1z)z((xF-1zzG-1y)<x,y>G-1○F-1.#xyz2023/1/117《集合論與圖論》第6講定理8定理8:設(shè)R,S,A,B,A,為集合,A,則(1)R(AB)=(RA)(RB);(2)R∪A=∪{RA|AA};(3)R(AB)=(RA)(RB);(4)R∩A=∩{RA|AA};(5)(R○S)A=R○(SA).2023/1/118《集合論與圖論》第6講定理8(證明(2))(2)R∪A

=∪{RA|AA};證明:<x,y>,x(R∪A)yxRyx∪AxRyA(AAxA)A(xRyxAAA)A(x(RA)yAA)x(∪{RA|AA})y.R∪A=∪{RA|AA}2023/1/119《集合論與圖論》第6講定理8(證明(4))(4)R∩A=∩{RA|AA};(A)證明:<x,y>,x(R∩A)yxRyx∩A(0xRy)x∩A(A(AA)xRy)x∩AA(AAxRy)A(AAxA)A((AAxRy)(AAxA))A(AA((xRy)xA))A(AA)x(RA)y)A(AAx(RA)y)x(∩{RA|AA})y.R∩A=∩{RA|AA}2023/1/1110《集合論與圖論》第6講定理8(證明(5))(5)(R○S)A=R○(SA)證明:<x,y>,x((R○S)A)y

x(R○S)yxAz(xSzzRy)xAz(xSzzRyxA)z((xSzxA)zRy)z(x(SA)zzRy)x(R○(SA))y.R∪A=∪{RA|AA}.#2023/1/1111《集合論與圖論》第6講定理9定理9:設(shè)R,S,A,B,A,為集合,A,則(1)R[AB]=R[A]R[B];(2)R[∪A]

=∪{R[A]|AA};(3)R[AB]R[A]R[B];(4)R[∩A]

∩{R[A]|AA};(5)R[A]-R[B]R[A-B];(6)(R○S)[A]=R[S[A]].2023/1/1112《集合論與圖論》第6講定理9(證明(2))(2)R[∪A]=∪{R[A]|AA};證明:y,yR[∪A]

x(xRyx∪A)x(xRyA(AAxA)A(AAx(xRyxA))A(AAyR[A])y∪{R[A]|AA}.R∪A=∪{RA|AA}.2023/1/1113《集合論與圖論》第6講定理9(證明(4))(4)R[∩A]

∩{R[A]|AA};證明:y,yR[∩A]

x(xRyx∩A)x(xRyA(AAxA))xA(xRy(AAxA))Ax(xRy(AAxA))(*)Ax(AA(xRyxA))(**)A(AAx(xRyxA))A(AAyR[A])y∩{R[A]|AA}.R[∩A]

∩{R[A]|AA}.2023/1/1114《集合論與圖論》第6講定理9(證明(4),續(xù))(*)xA(xRy(AAxA))Ax(xRy(AAxA))(**)

Ax(xRy(AAxA))Ax(AA(xRyxA))容易證明:(*)xyB(x,y)yxB(x,y)(**)

p(qr)q(pr)2023/1/1115《集合論與圖論》第6講定理9(證明(4),續(xù))(*)xyB(x,y)yxB(x,y)證明:在任何解釋下,若左1,則右1.2023/1/1116《集合論與圖論》第6講定理9(證明(4),續(xù))(**)

p(qr)q(pr)證明1:(p(qr))(q(pr))是永真式真值表,等值演算證明2:(反證)設(shè)“左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,矛盾!#2023/1/1117《集合論與圖論》第6講定理9(證明(5))(5)R[A]-R[B]R[A-B];證明:y,yR[A]-R[B]

yR[A]yR[B]x(xRyxA)x(xRyxB)x(xRyxA)x(xRyxB)x(xRyxA)x(xRyxB)x(xRyxAxB)x(xRyxA-B)yR[A-B].R[A]-R[B]R[A-B].2023/1/1118《集合論與圖論》第6講定理9(證明(5),續(xù))x(xRyxA)x(xRyxB)x(xRyxAxB)前提:x(xRyxA),x(xRyxB)結(jié)論:x(xRyxAxB)證明:(1)x(xRyxA),前提引入(2)cRycA,(1)EI

(3)x(xRyxB),前提引入(4)cRycB,(3)UI2023/1/1119《集合論與圖論》第6講定理9(證明(5),續(xù))前提:x(xRyxA),x(xRyxB)結(jié)論:x(xRyxAxB)證明:(1)

x(xRyxA),前提引入

(2)cRycA,(1)EI

(3)x(xRyxB),前提引入

(4)cRycB,(3)UI

(5)cRy,

(2)化簡(6)cB,(4)(5)假言推理2023/1/1120《集合論與圖論》第6講定理9(證明(5),續(xù))證明:(1)x(xRyxA),前提引入

(2)cRycA,(1)EI

(3)x(xRyxB),前提引入(4)cRycB,(3)UI

(5)cRy,(2)化簡

(6)cB,(4)(5)假言推理

(7)

cRycAcB,(2)(6)合取

(8)x(xRyxAxB)(7)EG.#2023/1/1121《集合論與圖論》第6講定理9(證明(6))(6)(R○S)[A]=R[S[A]].證明:y,y(R○S)[A]x(x(R○S)yxA)x(z(xSzzRy)xA)z(zRyx(xSzxA))z(zRyzS[A])yR[S[A]].(R○S)[A]=R[S[A]].#2023/1/1122《集合論與圖論》第6講定理9(討論)討論:當R為單根關(guān)系時,(3)(4)(5)中等號成立.(3)R[AB]R[A]R[B];(4)R[∩A]

∩{R[A]|AA};(5)R[A]-R[B]R[A-B];2023/1/1123《集合論與圖論》第6講關(guān)系表示法關(guān)系的表示方法:集合關(guān)系矩陣關(guān)系圖2023/1/1124《集合論與圖論》第6講關(guān)系矩陣(matrix)設(shè)A={a1,a2,…,an},RAA,則R的關(guān)系矩陣

M(R)=(rij)nn,其中例如,A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},則#2023/1/1125《集合論與圖論》第6講關(guān)系矩陣的性質(zhì)R的集合表達式與R的關(guān)系矩陣可以唯一相互確定M(R-1)=(M(R))T.(T表示矩陣轉(zhuǎn)置)M(R1○R2)=M(R2)M(R1).(表示這樣的矩陣“乘法”,其中加法使用邏輯,乘法使用邏輯.)2023/1/1126《集合論與圖論》第6講例題4例題4:設(shè)A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},用M(R1),M(R2)確定M(R1-1),M(R2-2),M(R1○R1),M(R1○R2),M(R2○R1),從而求出它們的集合表達式.2023/1/1127《集合論與圖論》第6講例題4(解)R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},解:R1-1={<a,a>,<a,b>,<b,a>,<c,b>}R2-1={<b,a>,<c,a>,<c,b>}2023/1/1128《集合論與圖論》第6講例題4(解,續(xù))R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},解(續(xù)):R1○R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.2023/1/1129《集合論與圖論》第6講例題4(解,續(xù))R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},解(續(xù)):

R1○R2

={<a,a>,<a,c>}.2023/1/1130《集合論與圖論》第6講例題4(解,續(xù))R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},解(續(xù)):

R2○R1

={<a,b>,<a,c>,<b,b>,<b,c>}.#2023/1/1131《集合論與圖論》第6講關(guān)系圖(graph)設(shè)A={a1,a2,…,an},RAA,則A中元素以“○”表示(稱為頂點),R中元素以“”表示(稱為有向邊);若xiRxj,則從頂點xi向頂點xj引有向邊<xi,xj>,這樣得到的圖稱為R的關(guān)系圖G(R).例如,A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},則abcabcG(R1)G(R2)2023/1/1132《集合論與圖論》第6講關(guān)系圖(舉例)R1-1={<a,a>,<a,b>,<b,a>,<c,b>}R2-1={<b,a>,<c,a>,<c,b>}abcG(R2-1

)cG(R1-1)ab2023/1/1133《集合論與圖論》第6講關(guān)系圖(舉例,續(xù))R1○R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.R1○R2

={<a,a>,<a,c>}.R2○R1

={<a,b>,<a,c>,<b,b>,<b,c>}.

abcG(R1○R2)cG(R1○R1)abcG(R2○R1)ab2023/1/1134《集合論與圖論》第6講關(guān)系矩陣,關(guān)系圖(討論)當A中元素標定次序后,RAA的關(guān)系圖G(R)與R的集合表達式可以唯一互相確定R的集合表達式,關(guān)系矩陣,關(guān)系圖三者均可以唯一互相確定對于RAB,|A|=n,|B|=m,關(guān)系矩陣M(R)是nm階的,關(guān)系圖G(R)中的邊都是從A中元素指向B中元素的.2023/1/1135《集合論與圖論》第6講關(guān)系性質(zhì)自反性(reflexivity)反自反性(irreflexivity)對稱性(symmetry)反對稱性(antisymmetry)傳遞性(transitivity)2023/1/1136《集合論與圖論》第6講自反性(reflexivity)設(shè)RAA,說R是自反的(reflexive),如果x(xAxRx).R是非自反的x(xAxRx)定理10:R是自反的IAR

R-1是自反的M(R)主對角線上的元素全為1G(R)的每個頂點處均有環(huán).#2023/1/1137《集合論與圖論》第6講自反性(舉例)2023/1/1138《集合論與圖論》第6講反自反性(irreflexivity)設(shè)RAA,說R是反自反的(irreflexive),如果x(xAxRx).R是非反自反的x(xAxRx)定理11:R是反自反的IAR=

R-1是反自反的M(R)主對角線上的元素全為0G(R)的每個頂點處均無環(huán).#2023/1/1139《集合論與圖論》第6講反自反性(舉例)2023/1/1140《集合論與圖論》第6講自反,自反性(分類)自反反自反非自反,非反自反自反且反自反?上的空關(guān)系2023/1/1141《集合論與圖論》第6講對稱性(symmetry)設(shè)RAA,說R是對稱的(symmetric),如果xy(xAyAxRyyRx).R非對稱xy(xAyAxRyyRx)定理12:R是對稱的R-1=R

R-1是對稱的M(R)是對稱的G(R)的任何兩個頂點之間若有邊,則必有兩條方向相反的有向邊.#2023/1/1142《集合論與圖論》第6講對稱性(舉例)2023/1/1143《集合論與圖論》第6講反對稱性(antisymmetry)設(shè)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),若有有向邊<xi,xj>,則必沒有<xj,xi>.#2023/1/1144《集合論與圖論》第6講反對稱性(舉例)2023/1/1145《集合論與圖論》第6講對稱,反對稱(分類)對稱反對稱非對稱,非反對稱對稱且反對稱?2023/1/1146《集合論與圖論》第6講傳遞性(transitivity)設(shè)RAA,說R是傳遞的(transitive),如果xyz(xAyAzAxRyyRzxRz).R非傳遞xyz(xAyAzAxRyyRzxRz)定理14:R是傳遞的

R○RRR-1是傳遞的在M(R○R)中,ij,

若rij’=1,則M(R)中相應(yīng)的元素rij=1.

在G(R)中,xixjxk,若有有向邊<xi,xj>,<xj,xk>,

則必有有向邊<xi,xk>.#2023/1/1147《集合論與圖論》第6講傳遞性(舉例)2023/1/1148《集合論與圖論》第6講傳遞(分類)非傳遞傳遞2023/1/1149《集合論與圖論》第6講舉例在N={0,1,2,…}上:={<x,y>|xNyNxy}自反,反對稱,傳遞={<x,y>|xNyNxy}自反,反對稱,傳遞<={<x,y>|xNyNx<y}反自反,反對稱,傳遞>={<x,y>|xNyNx>y}反自反,反對稱,傳遞|={<x,y>|xNyNx|y}反對稱,傳遞(0|0)IN={<x,y>|xNyNx=y}自反,對稱,反對稱,傳遞EN={<x,y>|xNyN}=NN自反,對稱,傳遞.#2023/1/1150《集合論與圖論》第6講例5例5:A={a,b,c}R1={<a,a>,<a,b>,<b,c>,<a,c>},R2={<a,a>,<a,b>,<b,c>,<c,a>},R3={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>},R4={<a,a>,<a,b>,<b,a>,<c,c>},R5={<a,a>,<a,b>,<b,b>,<c,c>},R6={<a,b>,<b,a>,<b,c>,<a,a>},2023/1/1151《集合論與圖論》第6講例5(續(xù))R1={<a,a>,<a,b>,<b,c>,<a,c>}反對稱,傳遞R2={<a,a>,<a,b>,<b,c>,<c,a>}反對稱G(R1)acbG(R2)acb2023/1/1152《集合論與圖論》第6講例5(續(xù))R3={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>}自反,對稱,傳遞R4={<a,a>,<a,b>,<b,a>,<c,c>}對稱G(R3)acbG(R4)acb2023/1/1153《集合論與圖論》第6講例5(續(xù))R5={<a,a>,<a,b>,<b,b>,<c,c>}自反,反對稱,傳遞R6={<a,b>,<b,a>,<b,c>,<a,a>}.#G(R5)acbG(R6)acb2023/1/1154《集合論與圖論》第6講關(guān)系運算是否保持關(guān)系性質(zhì)定理15:設(shè)R1,R2AA都具有某種性質(zhì).自反反自反對稱反對稱傳遞R1-1,

R2-1(4)R1R2R1R2(2)(5)R1○R2,

R2○R1(1)R1-R2,

R2-R1(3)~R1,~R2(3‘)2023/1/1155《集合論與圖論》第6講定理15(證明(1))(1)R1,R2自反R1○R2自反.證明:x,xA

xR2xxR1x

xR1○R2xR1,R2自反R1○R2自反.#2023/1/1156《集合論與圖論》第6講定理15(證明(2))(2)R1,R2反自反R1R2反自反.證明:(反證)若R1○R2非反自反,則

xA