Bài giảng Toán rời rạc - Chương 3: Quan hệ (Phạm Thế Bảo) có nội dung trình bày các kiến thức về định nghĩa và tính chất của quan hệ; biểu diễn quan hệ; quan hệ tương đương, đồng dư; quan hệ thứ tự, biểu đồ Hass, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LOGO3 Chương TOÁN RỜI RẠC Phạm Thế Bảo email ptbao@ ptbao TRR Chương 3 QUAN HỆ 3 I. Quan hệ 1. Định nghĩa và tính chất 2. Biểu diễn quan hệ 3. Quan hệ tương đương. Đồng dư 4. Quan hệ thứ tự biểu đồ Hass 4 1. Định nghĩa Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Đề các R A x B. Chúng ta sẽ viết a R b thay cho a b R. Quan hệ từ A đến chính nó được gọi là quan hệ trên A R a1 b1 a1 b3 a3 b3 5 1. Định nghĩa Ví dụ. A tập sinh viên B các lớp học. R a b sinh viên a học lớp b 6 1. Định nghĩa Ví dụ. Cho A 1 2 3 4 và 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 1 2 3 4 1 2 3 4 2. Các tính chất của Quan hệ Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu a A a R a Ví dụ. Trên tập A 1 2 3 4 quan hệ R1 1 1 1 2 2 1 2 2 3 4 4 1 4 4 không phản xạ vì 3 3 R1 R2 1 1 1 2 1 4 2 2 3 3 4 1 4 4 phản xạ vì 1 1 2 2 3 3 4 4 R2 7 Quan hệ trên Z phản xạ vì a a với mọi a Z Quan hệ gt trên Z không phản xạ vì 1 gt 1 Quan hệ ước số trên Z là phản xạ vì mọi số nguyên a là ước của chính nó . Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa đường chéo của A A a a a A 4 3 2 1 1 2 3 4 8 9 2. Các tính chất của Quan hệ Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu a A b A a R b b R a Quan hệ R được gọi là phản xứng nếu a A b A a R b b R a a b Ví dụ. Quan hệ R1 1 1 1 2 2 1 trên tập A 1 2 3 4 là đối xứng Quan hệ trên Z không đối xứng. Tuy nhiên nó phản xứng vì a b b a a b 10 2. Các tính chất của Quan hệ Quan hệ ước số trên Z . không đối xứng Tuy nhiên nó có tính phản xứng vì a b b a a b Chú ý. Quan hệ R trên A là đối xứng nếu nó đối xứng nhau qua đường chéo của A A. Quan hệ R là phản xứng nếu chỉ có các phần tử nằm trên đường chéo là đối xứng qua của A A. 4 4 3 3 2 2 1 1 1 2 3 4 1 2 3 4 11 2. Các tính chất của Quan hệ Định nghĩa. Quan hệ R trên A có tính bắc cầu truyền nếu a b c A a R b b R c a R c Ví dụ. Quan hệ R 1 1 1 2 2 1 2 2 1 3 2 3 trên tập A 1 2 3 4 có tính bắc cầu. Quan hệ và trên Z có tính bắc cầu a b b c a c a b b
