tailieunhanh - Bài giảng môn Toán rời rạc - Chương 6: Quan hệ

Bài giảng môn Toán rời rạc - Chương 6: Quan hệ, cung cấp những kiến thức như định nghĩa; các tính chất của quan hệ; Biểu diễn quan hệ hai ngôi; quan hệ tương đương; quan hệ thứ tự. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC Chương 6 QUAN HỆ Toán Rời Rạc Chương 6. Quan hệ O c 2020 LVL 1 43 Nội dung Chương 6. QUAN HỆ 1. Quan hệ hai ngôi 2. Quan hệ tương đương 3. Quan hệ thứ tự Toán Rời Rạc Chương 6. Quan hệ O c 2020 LVL 2 43 . Quan hệ hai ngôi 1 Định nghĩa 2 Các tính chất của quan hệ 3 Biểu diễn quan hệ Toán Rời Rạc Chương 6. Quan hệ O c 2020 LVL 3 43 . Đị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. 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 Định nghĩa. Một quan hệ trên tập hợp A là một quan hệ hai ngôi từ A đến chính nó. Toán Rời Rạc Chương 6. Quan hệ O c 2020 LVL 4 43 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ụ. tự làm Trên tập hợp số nguyên ta xét những quan hệ sau R1 a b a b R2 a b a gt b R3 a b a b hay a b R4 a b a b 1 R5 a b a b 3 . Quan hệ nào chứa cặp 1 1 1 2 2 1 1 1 and 2 2 Ví dụ. Cho A 1 2 3 4 . Hỏi ta có thể xây dựng được bao nhiêu quan hệ trên A Mở rộng kết quả cho trường hợp A có n phần tử. Toán Rời Rạc Chương 6. Quan hệ Oc 2020 LVL 5 43 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 . 2 Trong trường hợp A n số quan hệ trên A là 2n . 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ó đúng 5 phần tử và chứa 1 1 d có ít nhất 7 phần tử. Đáp án. a 28 5 b C9 4 c C8 7 8 9 d C9 C9 C9 Định nghĩa. Cho R là quan hệ trên A và x y A. Ta nói i x quan hệ R với y nếu x y R ký hiệu xRy. ii x không quan hệ R với y nếu x y R ký hiệu x amp hay xRy . Ry amp Toán Rời Rạc Chương 6. Quan hệ O c 2020 LVL 6 43 Ví dụ. Cho A 1 2 3 và R 1 1 1 2 2 3 1 3 là một quan hệ trên A. Khi đó R R 1R1 1R2 2R3 1R3 2 1 2 2 . . . Ví dụ. Cho A 1 2 3 4 5 6 7 8 . Một quan hệ R trên A được xác định như sau xRy x y chia hết cho 4. Ta có R R 1R5 5R1 7R7 1 2 3 6 . . . Toán Rời Rạc Chương 6.