tailieunhanh - Bài giảng Toán rời rạc: Bài 8 - Vũ Thương Huyền

Bài giảng Toán rời rạc: Bài 8 - Vũ Thương Huyền cung cấp cho học viên các kiến thức về quan hệ; khái niệm quan hệ và các tính chất; quan hệ n-ngôi và những ứng dụng; các phép toán trên quan hệ n-ngôi; 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 chi tiết nội dung bài giảng! | BÀI 8 QUAN HỆ Vũ Thương Huyền huyenvt@ 1 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 huyenvt@ 2 QUAN HỆ VÀ CÁC TÍNH CHẤT Toán rời rạc huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 11 QUAN HỆ N-NGÔI VÀ ỨNG DỤNG Toán rời rạc huyenvt@ 12 QUAN HỆ n-NGÔI Định