Bài giảng Chương III: Quan hệ

Một quan hệ hai ngôi R trên S ≠  thực chất là 1 tập con R của S2. Tập con này liệt kê các cặp của S2 có quan hệ R.R = { (x,y)  S2 / x R y }  S2x,y  S: x R y (x,y)  Rx ¬R y (x,y)  R
Nội dung trích xuất từ tài liệu:
Bài giảng Chương III: Quan hệ1.Địnhnghĩa:MộtquanhệhaingôiRtrênS≠∅thực chấtlà1tậpconRcủaS2.Tậpconnàyliệtkêcác cặpcủaS2cóquanhệR. R={(x,y)∈S2/xRy} ∈S2∀x,y∈S: xRy(x,y)∈R x¬Ry(x,y)∉R Ví dụ: Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} Với quan hệ này ta có:2 R 4,nhưng 2 ¬R 32.Cáchxácđịnh1qhệ2ngôiRtrênSkhác∅:Cách1:LiệtkêRnhư1tậpconcủaSVídụ:S=Z.Choqhệ2ngôitrênSlà:R={(0,0);(1,3);(2,5)(7,6)} (RlàtậpconcủaS2)2.Cáchxácđịnh1qhệ2ngôiRtrênSkhác∅:Cách2:Nêuranộidungcủaqhệ2ngôiVídụ:S=Z∀x,y∈S:xRy3x2>2y3+1 5R3 4¬R 32.Cáchxácđịnh1qhệ2ngôiRtrênSkhác∅:Cách3:Biểudiễnqhệ2ngôiRbằngmatrậnvuông nhịphân:Kếtquảtrảvề: 1nếuxRy 0nếux ¬RyVídụ:S={a,b,c,d}vàqhệ2ngôiR(trênS)cóma trậnnhưsau:Vídụ:R={(a,a);(a,c);(c,a);(c,c);(c,d);(d,b)}3.Cáctínhchất: VớiRlàquanhệ2ngôitrênS≠∅3.1:Tínhphảnxạ:a. Rphảnxạnếu“∀x∈S: xRx“b. Rkhôngphảnxạnếu: Vídụvềtínhchấtphảnxạ:S={1,2,3}làtậphợpconcủaT={1,2,3,4}R={(2,2),(1,3),(3,3),(1,1)}làtậphợpconcủaS2vàT2R(trênS):Rphảnxạvì2R2;1R1;3R3R(trênT):Rkophảnxạvìtồntại4thuộcT,4¬R43.Cáctínhchất:3.2:Tínhđốixứng:Rđốixứngnếu:“∀x,y∈S: xRy=>yRxvà ngượclại.Vídụ:A={1,2,3},xétquanhệtrênA R3={(1,1),(3,2),(1,3),(3,1),(2,3)}làquanhệđối xứng R4={(2,1),(1,2),(3,2),(1,3),(3,1),(3,3)}làquan hệkhôngđốixứng3.Cáctínhchất:3.3:Tínhphảnxứng:Rphảnxứngnếu ∀x,y∈S:xRyvàyRx=>x=yHoặcRphảnxứngnếu: ∀x,y∈S:x≠y=>x¬Ryvày¬Rx3.Cáctínhchất:3.4:Tínhtruyền(tínhbắccầu):Rtruyềnnếu ∀x,y,z∈S:xRyvàyRz=>xRz1.Địnhnghĩa:Cho(S,R)RgọilàqhệtươngđươngnếuRcótínhchất: Phảnxạ Đốixứng TruyềnKíhiệu:R≡~Vídụ:S={mọingười}∀x,y∈S,tađặtx~yxcùngtuổivớiy∀x∈S,xcùngtuổivớix,nghĩalàx~x∀x,y∈S,x~y=>xcùngtuổivớiy=>ycùngtuổi vớix=>y~x(tínhđốixứng)Tươngtựvớitínhbắccầu1.Địnhnghĩa:Cho(S,~)vàa∈STìmx∈Smàx~aĐặt[a]={x∈S/x~a}={a,…}∅ ≠[a]làtậpconcủaS[a]làlớptươngđươngcủaaxácđịnhbởiquanhệ tươngtương~1.2:Sựphânhoạchthànhcáclớptươngđương:Cho(S,~),qhệtươngđương~sẽphânchiaSthànhcác lớp tương đương rời nhau từng đôi một. Mỗi lớp tươngđươngcódạng[a]vớianàođó∈S.Nếu2ptửcóqhệ~thìchúngthuộccùng1lớptương đương:x~yNếu 2 ptử không qhệ ~ thì chúng thuộc 2 lớp tương đươngrờinhau:x~y