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ự. . | TOÁN RỜI RẠC (Discrete Mathematics) Chương 3 Quan hệ (Relations) 1. Một số khái niệm cơ bản Định nghĩa : Quan hệ R (2 ngôi) giữa 2 tập hợp A và B là một tập con của A B. Một quan hệ giữa A và A gọi là một quan hệ trên A Nếu (a,b) R, ta viết aRb. Ví dụ : A=Tập các quận-huyện. B=Tập các tỉnh-TP Quan hệ R “Quận/Huyện thuộc tỉnh” giữa 2 tập A và B là tập của A B: 1. Một số khái niệm cơ bản Chắng hạn: R={(Long Khánh,Đồng Nai),(Gò Vấp, Tp. HCM), (Bình Chánh, ),(Long Thành, Đồng Nai)} Quan hệ này có thể trình bày ở dạng bảng: Quận-Huyện Tỉnh-TP Long Khánh Đồng Nai Gò Vấp Bình Chánh Long Thành Đồng Nai 1. Một số khái niệm cơ bản Ví dụ : Cho 2 tập hợp A={các sinh viên} và B={các môn học}, Chẳng hạn: A={sv1, sv2, sv3, sv4} B={Toán RR, LTM1, PPsố, Triết} Xét quan hệ R ” Đăng ký môn học” giữa A và B được định nghĩa: x Ay B, xRy “sinh viên x có đăng ký môn học y” Nếu sv2 đăng ký môn PPSố, thì: (sv2, PPSố) R Nếu sv1 đăng ký môn Toán RR, thì: (sv1,toán RR) R Nếu sv1 không đăng ký môn Triết, thì: (sv1,Triết) R , 1. Một số khái niệm cơ bản Ví dụ : Trên tập L ={các đường thẳng trong mặt phẳng} Xét quan hệ R ”Song song” được định nghĩa bởi: L1,L2 L , L1 R L2 L1//L2 Ví dụ : Trên tập S là tập các đa giác trong mặt phẳng. Quan hệ R ”đồng dạng” được định nghĩa như sau: a,b S, a R b “a và b đồng dạng” Ví dụ : Trên tập số nguyên Z, cho trước số n>1. Xét quan hệ: a R b a – b chia hết cho n a và b có cùng số dư khi chia cho n 1. Một số khái niệm cơ bản Quan hệ này gọi là quan hệ đồng dư modulo n. Kí hiệu a b (mod n). Ví dụ như: 1 8(mod 7); 3 11(mod 8), Có thể biễu diễn quan hệ 2 ngôi bằng biểu đồ: Ví dụ : Cho A={4,5,6},B={1,2,3} và R={(4,1),(4,2),(5,2),(6,3)} 4 1 5 2 6 3 Hoặc 4 5 6 1 2 3 A B R A B 1. Một số khái niệm cơ bản Ví dụ : Cho tập A={2,4,6} và B={a,b,c,d} Có bao nhiêu quan hệ khác nhau có thể có giữa A và B? Có bao nhiêu quan hệ có chứa cặp (2,b)? Có bao nhiêu . | TOÁN RỜI RẠC (Discrete Mathematics) Chương 3 Quan hệ (Relations) 1. Một số khái niệm cơ bản Định nghĩa : Quan hệ R (2 ngôi) giữa 2 tập hợp A và B là một tập con của A B. Một quan hệ giữa A và A gọi là một quan hệ trên A Nếu (a,b) R, ta viết aRb. Ví dụ : A=Tập các quận-huyện. B=Tập các tỉnh-TP Quan hệ R “Quận/Huyện thuộc tỉnh” giữa 2 tập A và B là tập của A B: 1. Một số khái niệm cơ bản Chắng hạn: R={(Long Khánh,Đồng Nai),(Gò Vấp, Tp. HCM), (Bình Chánh, ),(Long Thành, Đồng Nai)} Quan hệ này có thể trình bày ở dạng bảng: Quận-Huyện Tỉnh-TP Long Khánh Đồng Nai Gò Vấp Bình Chánh Long Thành Đồng Nai 1. Một số khái niệm cơ bản Ví dụ : Cho 2 tập hợp A={các sinh viên} và B={các môn học}, Chẳng hạn: A={sv1, sv2, sv3, sv4} B={Toán RR, LTM1, PPsố, Triết} Xét quan hệ R ” Đăng ký môn học” giữa A và B được định nghĩa: x Ay B, xRy “sinh viên x có đăng ký môn học y” Nếu sv2 đăng ký môn PPSố, thì: (sv2, PPSố) R Nếu sv1 đăng ký môn Toán RR, thì:
