Bài giảng "Toán rời rạc - Chương 5: Quan hệ" cung cấp cho người học các kiến thức: Quan hệ hai ngôi, quan hệ tương đương, quan hệ thứ tự. Đây là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn này và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 5 QUAN HỆ lvluyen@ ∼luyen/trr FB: Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@ Chương 5. Quan hệ 14/12/2015 1/39 Nội dung Chương 5. QUAN HỆ 1. Quan hệ hai ngôi 2. Quan hệ tương đương 3. Quan hệ thứ tự lvluyen@ Chương 5. Quan hệ 14/12/2015 2/39 . Quan hệ hai ngôi 1 Định nghĩa 2 Các tính chất của quan hệ lvluyen@ Chương 5. Quan hệ 14/12/2015 3/39 . Định nghĩa Định nghĩa. Một quan hệ hai ngôi từ tập A đến tập B là tập con R của tích Descartes A × B. Quan hệ từ A đến chính nó được gọi là quan hệ hai ngôi (hay quan hệ ) trên A. Ví dụ. Cho A = {0, 1, 2} và B = {a, b}. Khi đó R = {(0, a), (0, b), (1, a), (2, b)} là một quan hệ từ A vào B. Quan hệ này được mô tả bằng lvluyen@ Chương 5. Quan hệ 14/12/2015 4/39 Ví dụ. Cho A = {1, 2, 3, 4}, và R = {(a, b) | a là ước của b}. Khi đó R là một quan hệ trên A. Hãy tìm R? Giải. R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}. Ví dụ. Cho A = {1, 2, 3, 4}. Hỏi ta có thể xây dựng được bao nhiêu qua hệ trên A? Giải. Vì |A| = 4 nên |A × A| = 16. Do mỗi quan hệ trên A là một tập con của |A × A| nên số quan hệ trên A là 216 . Ví dụ.(tự làm) Cho A = {1, 2, 3}. Hãy tìm số quan hệ hai ngôi trên A a) chứa (1, 1). b) có đúng 5 phần tử. c) có ít nhất 7 phần tử. lvluyen@ Chương 5. Quan .
