tailieunhanh - 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! | CHƯƠNG 7 QUAN HỆ Nguyễn Quỳnh Diệp diepnq@ 1 Nguyễn Quỳnh Diệp NỘ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 2 QUAN HỆ VÀ CÁC TÍNH CHẤT Toán rời rạc Nguyễn Quỳnh Diệp 3 QUAN 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 4 QUAN 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 5 QUAN 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 6 QUAN 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 7 QUAN 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 8 CÁ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 R Ví 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 9 CÁ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 10 CÁ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 11 QUAN HỆ N-NGÔI VÀ ỨNG DỤNG Toán rời rạc Nguyễn Quỳnh Diệp 12 QUAN HỆ .