Bài giảng Toán rời rạc: Chương 7 - Nguyễn Quỳnh Diệp

Bài giảng Toán rời rạc: Chương 7 Quan hệ cung cấp cho người học những kiến thức như: Quan hệ và các tính chất; Quan hệ n-ngôi và những ứng dụng; Biểu diễn các quan hệ; Bao đóng của các quan hệ. Mời các bạn cùng tham khảo để nắm chi tiết nội dung của bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 7 - Nguyễn Quỳnh DiệpCHƯƠNG 7QUAN HỆNguyễn Quỳnh Diệp diepnq@tlu.edu.vn 1 Nguyễn Quỳnh DiệpNỘI DUNG • Quan hệ và các tính chất • Quan hệ n-ngôi và những ứng dụng • Biểu diễn các quan hệ • Bao đóng của các quan hệ Toán rời rạc Nguyễn Quỳnh Diệp 27.1 QUAN HỆ VÀ CÁC TÍNH CHẤT Toán rời rạc Nguyễn Quỳnh Diệp 3QUAN HỆ• Có nhiều quan hệ giữa các phần tử của các tập hợp• Các mối quan hệ giữa các phần tử được biểu diễn bằng cách dùng một cấu trúc gọi là quan hệ Toán rời rạc Nguyễn Quỳnh Diệp 4QUAN HỆĐịnh nghĩa 1: Cho A và B là hai tập hợp. Một quan hệ hai ngôi từ A đến B là một tập con của A×B - Quan hệ hai ngôi từ A đến B là tập R các cặp được sắp, phần tử đầu thuộc A, phần tử thứ hai thuộc B - Kí hiệu: ??? để chỉ (a,b)  R ??? để chỉ (a,b)  R Toán rời rạc Nguyễn Quỳnh Diệp 5QUAN HỆVí dụ: - A : tập các sinh viên - B : tập các môn học - R : quan hệ bao gồm các cặp (a,b) với a  A , bB Sinh viên Môn học Quan hệ Tuấn Toán rời rạc (Tuấn, Toán rời rạc) Tuấn Vật lý (Tuấn, Vật lý) Hoa Toán rời rạc (Hoa, Toán rời rạc) Nga Mác (Hoa, Mác) Toán rời rạc Nguyễn Quỳnh Diệp 6QUAN HỆĐịnh nghĩa 2: Một quan hệ trên tập A là quan hệ từ A tới A- Quan hệ trên tập A là một tập con của A × A Toán rời rạc Nguyễn Quỳnh Diệp 7QUAN HỆVí dụ: - A = {1, 2, 3, 4} - R = {(a,b) | a là ước của b} Khi đó: R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)} Toán rời rạc Nguyễn Quỳnh Diệp 8CÁC TÍNH CHẤT CỦA QUAN HỆĐịnh nghĩa 3: Quan hệ R trên tập A được gọi là có tính phản xạ nếu (a,a)  RVí dụ: Xét các quan hệ sau trên tập {1, 2, 3, 4} quan hệ nào có tính phản xạ? Toán rời rạc Nguyễn Quỳnh Diệp 9CÁC TÍNH CHẤT CỦA QUAN HỆĐịnh nghĩa 4: Quan hệ R trên tập A được gọi là có tính đối xứng : nếu (a,b)  R thì (b, a)  R Quan hệ R trên tập A được gọi là phản đối xứng nếu (a, b)  R và (b, a)  R thì a = b Ví dụ: Toán rời rạc Nguyễn Quỳnh Diệp 10CÁC TÍNH CHẤT CỦA QUAN HỆĐịnh nghĩa 5: Quan hệ R trên tập A được gọi là có tính bắc cầu: nếu (a,b)  R và (b, c)  R thì (a, c)  R Ví dụ: - Quan hệ R = {(2,1) , (3,1) , (3, 2) , (4, 1) , (4, 2) , (4, 3)} Trên tập A ={1, 2, 3, 4} có tính bắc cầu Toán rời rạc Nguyễn Quỳnh Diệp 117.2 QUAN HỆ N-NGÔI VÀ ỨNG DỤNG Toán rời rạc Nguyễn Quỳnh Diệp 12QUAN HỆ n-NGÔIĐịnh nghĩa 1: Cho A1, A2, … , An là các tập hợp. Một quan hệ n-ngôi trên các tập này là một tập con của A1 × A2 … × An - A1, A2, … , An gọi là miền của quan hệ - n gọi là bậc của quan hệ Ví dụ: - Quan hệ R gồm bộ 5 (A, N, S, D, T) - Trong đó: A: hãng hàng không - N: Số chuyến bay - S: nơi xuất phát - D: nơi đến - T: thời gian xuất phát Toán rời rạc Nguyễn Quỳnh Diệp 13CƠ SỞ DỮ LIỆU• Một cơ sở dữ liệu gồm các bản ghi như một quan hệ n-ngôi. Ví dụ: Tên Mã sinh viên Ngành học Điểm trung bình Ackermand 2342234 Tin học 3,88 Adams 8773324 Vật lí 3,45 Chou 9834532 Tin học 3,49 Goodfriend 1093434 Toán 3,45 Rao 7673387 Toán 3,90 Stevens 9835345 Tâm lí học 2,99 Toán rời rạc Nguyễn Quỳnh Diệp 14CÁC PHÉP TOÁN TRÊN QUAN HỆ n-NGÔIPhép chọn Giả sử R là một quan hệ n-ngôi và C là điều kiện mà các phần tử trong R có thể thỏa mãn. Khi đó phép chọn Sc ánh xạ quan hệ n- ngôi R tới quan hệ n-ngôi gồm tất cả các bộ n-thành phần của R thỏa mãn điều kiện C đó. Ví dụ: Quan hệ nào được tạo thành khi dùng phép chiếu P1,4 lên quan hệ: (sinh viên, mã sinh viên, ngành học, điểm trung bình) Toán rời rạc Nguyễn Quỳnh Diệp 15CÁC PHÉP TOÁN TRÊN QUAN HỆ n-NGÔIPhép chiếu Phép chiếu ??? ?? ?? ánh xạ bộ n-phần tử (a1, a2, … , an) tới bộ m-phần tử (??? , ??? , ??? ), trong đó m≤ n Ví dụ: - Tìm các bản ghi có ngành học là Tin học - Sử dụng phép chọn Sc với C là điều kiện Ngành học = “Tin học” Toán rời rạc Nguyễn Quỳnh Diệp 16CÁC PHÉP TOÁN TRÊN QUAN ...