Bài giảng Toán rời rạc - Chương 3: Quan hệ (Relations)

Chương 3 của bài giảng Toán rời rạc trình bày các nội dung liên quan đến quan hệ (Relations) như: Một số khái niệm cơ bản, một số tính chất của quan hệ, biểu diễn quan hệ bằng ma trận, quan hệ tương đương, quan hệ thứ tự. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - Chương 3: Quan hệ (Relations) TOÁNRỜIRẠC(DiscreteMathematics) Chương3Quanhệ(Relations)1.Mộtsốkháiniệmcơbản1.1Địnhnghĩa1.1: QuanhệR(2ngôi)giữa2tậphợpAvàBlàmộttậpcon củaA B.MộtquanhệgiữaAvàAgọilàmộtquanhệ trênA Nếu(a,b) R,taviếtaRb.Vídụ1.1: A=Tậpcácquậnhuyện. B=TậpcáctỉnhTP QuanhệR “Quận/Huyệnthuộctỉnh”giữa2tậpAvàB làtậpcủaA B:1.Mộtsốkháiniệmcơbản Chắnghạn:R={(LongKhánh,ĐồngNai),(GòVấp,Tp.HCM), (BìnhChánh,Tp.HCM),(LongThành,ĐồngNai)} Quanhệnàycóthểtrìnhbàyởdạngbảng: QuậnHuyện TỉnhTP LongKhánh ĐồngNai GòVấp Tp.HCM BìnhChánh Tp.HCM LongThành ĐồngNai1.MộtsốkháiniệmcơbảnVídụ1.2:Cho2tậphợpA={cácsinhviên}vàB={cácmôn học},Chẳnghạn: A={sv1,sv2,sv3,sv4} B={ToánRR,LTM1,PPsố,Triết} XétquanhệR ”Đăngkýmônhọc”giữaAvàBđược địnhnghĩa: x Ay B,xRy “sinhviênxcóđăngkýmônhọcy”  Nếusv2đăngkýmônPPSố,thì:(sv2,PPSố) R  Nếusv1đăngkýmônToánRR,thì:(sv1,toánRR) R  Nếusv1khôngđăngkýmônTriết,thì:(sv1,Triết) R  ,…1.Mộtsốkháiniệmcơbản Vídụ1.3:TrêntậpL ={cácđườngthẳngtrongmặt phẳng}XétquanhệR ”Songsong”đượcđịnhnghĩabởi: L L1,L2 ,L1 RL 2 L1//L2 Vídụ1.4:TrêntậpSlàtậpcácđagiáctrongmặtphẳng. QuanhệR ”đồngdạng”đượcđịnhnghĩanhưsau: a,b S,aRb “avàbđồngdạng” Vídụ1.5:TrêntậpsốnguyênZ,chotrướcsốn>1.Xét quanhệ: aRb a–bchiahếtchon avàbcócùngsốdưkhichiachon1.Mộtsốkháiniệmcơbản Quanhệnàygọilàquanhệđồngdưmodulon.Kíhiệua b(modn).Ví dụnhư:1 8(mod7);3 11(mod8),… Cóthểbiễudiễnquanhệ2ngôibằngbiểuđồ: Vídụ1.6:ChoA={4,5,6},B={1,2,3}vàR={(4,1),(4,2),(5,2),(6,3)} B A B 3 R Hoặc 4 1 2 5 2 1 6 3 4 5 6 A1.MộtsốkháiniệmcơbảnVídụ1.7:ChotậpA={2,4,6}vàB={a,b,c,d}a) CóbaonhiêuquanhệkhácnhaucóthểcógiữaAvàB?b) Cóbaonhiêuquanhệcóchứacặp(2,b)?c) Cóbaonhiêuquanhệkhôngchứacặp(2,a)và(4,b)?Giải:a) Tacó|A B|=|A| |B|=3 4=12 SốtậpconkhácnhaucủaA Blà212. MàmỗitậpconcủaA Blàmộtquanhệ.vậysốquan hệkhácnhaucóthểcógiữaAvàBlà2121b)Sốquanhệcóchứacặp(2,b)?1.Mộtsốkháiniệmcơbảnb)GọiXlàmộtquanhệthoảđiềuđiệnđãcho(nghĩalàX cóchưáítnhấtlà1cặp(2,b)).Xcódạng: X={(2,b)} YvớiY A B\{(2,b)} Có1cáchchọntập{(2,b)} Mỗicáchchọn{(2,b)}có2|A B\{(2,b)}|=211. Theonguyênlýnhân,sốquanhệXcóthểtìmđượclà 1 211=211.c)TínhsốquanhệgiữaAvàBkhôngchứa(1,a)và(3,b)? (bàitập)d)Cóbaonhiêuquanhệcóđúng5cặp(a,b)vớia Avà b B?(bàitập):…..1.Mộtsốkháiniệmcơbản(tt)1.2.Địnhnghĩa1.2:MộtquanhệRcónngôitrêncáctậpA1,A2, …,AnlàmộttậpconA1 A2 … An.CáctậpA1,A2,…,An gọilàcácmiềncủaR. Vídụ1.8:ChoA1:Tậpchuyếncáctàu,A2:Tậpcácnhàga A3={0,1,2,…23}:Giờtrongngày A4={0,1,2,…59}:Phúttronggiờ XétquanhệR(4ngôi)gồmcácbộcódạng(x,y,z,t)chobiết lịchtàuđếntạimỗiga,vớix:sốhiệutàu,y:ga,z:giờ,t: phút.NếutàuS1đếngaNhatranglúc13h30,thì: (S1,NhaTrang,13,30) R NếutàuS3đếngaSàigònlúc4h30thì (S3,SaìGòn,4,30) RMộtsốkháiniệmcơbản(tt) NếutàuS1đếngaTuyHòalúc17h45thì: (S1,TuyHòa,17,45) R NếutàuLH2đếngaBìnhĐịnhlúc4h00thì: (LH2,BìnhĐịnh,4,0) R Cóthểbốtrícácphầntửcủaquanhệởdạngbảng: Số Ga Giờ Phút Mỗidònglà Tàu mộtbộcủaR S1 NhaTrang 13 30 S3 SàiGòn 4 40 S1 TuyHòa 17 45 LH2 BìnhĐịnh 4 001.Mộtsốkháiniệmcơbản(tt)1.3.Địnhnghĩa1.3: ChotrướccáctậpA1,A2,…,An.Ánhxạchiếulêncác thànhphầnthứi1,i2,…,im(m n)đượcđịnhnghĩa: i1 ,i2 ,...,im :A1 A 2 ... A n A i1 A i2 ... A im (a1 a 2 ... an )  (ai1 ai2 ... aim ) Khiđó,vớiRlàmộtquanhệtrênA1,A2,…,An,thì: i1 ,i2 ,...,im (R) Gọilàquanhệchiếu1.Mộtsốkháiniệmcơbản(tt) Vídụ1.9:ChoA1={Sốhiệucácchuyếntàu};A2={cácga}; A3={Giờđến}={0,1,2,…,23};A4={phút}={0,1,2,…,59} vàquanhệR=“Lịchtàu”giữaA1,A2,A3.Nếuchỉmuốnbiết danhsáchcáctàuvàgađến(khôngcầnquantâmđếnthời SoTau ,Ga (R) điểm),taxétquanh ệchiếu: SoTau ,Ga (R) R S ố Ga Giờ Phút S ố Ga Tàu TàuS1 NhaTrang 13 30 S1 NhaTrangS3 SàiGòn 4 40 S3 SàiGònS1 TuyHòa 17 45 S1 TuyHòaLH2 BìnhĐịnh 4 00 LH2 BìnhĐịnh2.Mộtsốtínhchấtcủaquanhệ: MộtquanhệRtrênAcóthểcócáctínhchấtsauđây: a)Tínhphảnxạ(reflexivity): R ...