Bài giảng Toán rời rạc: Chương 4 - Quan hệ bao gồm những nội dung về quan hệ 2 ngôi; cách xác định một quan hệ; các tính chất của quan hệ 2 ngôi; biểu diễn quan hệ 2 ngôi dưới dạng ma trận; quan hệ tương đương; lớp tương đương và tập hợp thương và một số nội dung khác. | Quan hệ Quan hệ 2 ngôi Cho một tập hợp X khác rỗng. Một quan hệ 2 ngôi trên X là một tập hợp con R của X2. Cho 2 phần tử x và y của X, ta nói x có quan hệ R với y khi và chỉ khi (x,y) R, và viết là x R y x R y (x,y) R Khi x không có quan hệ R với y, ta viết: Ví dụ Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳn. (R = { (x,y) Z2 : x-y = 2k với k Z } ) ∀x, y ∈ R, xRy ⇔ |x| = |y| ∀x, y ∈ Q, xRy ⇔ x ≤ y ∀x, y ∈ Z, xRy ⇔ a – b chia hết cho n x ≡ y (mod n). Quan hệ Người ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB. Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An. Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là một bộ n (a1, a2, . . ., an) với ai Ai (i=1, , n). Xác định một quan hệ Liệt kê: liệt kê tất cả các cặp hay bộ phần tử có quan hệ R (tức là thuộc R) Nêu tính chất đặc trưng cho quan hệ R, tức là tính chất hay tiêu chuẩn để xác định các phần tử thuộc R hay không Các tính chất của quan hệ 2 ngôi Giả sử R là một quan hệ 2 ngôi trên một tập hợp X Ta nói quan hệ R có tính phản xạ (reflexive) nếu và chỉ nếu x R x với mọi x X. Ta nói quan hệ R có tính đối xứng (symmetric) nếu và chỉ nếu x R y y R x với mọi x,y X Ta nói quan hệ R có tính phản xứng (antisymmetric) nếu và chỉ nếu (x R y và y R x) x = y với mọi x,y X. Ta nói quan hệ R có tính truyền hay bắc cầu (transitive) nếu và chỉ nếu (x R y và y R z) x R z với mọi x,y,z X Ví dụ Quan hệ trên tập hợp các số thực Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ | Quan hệ Quan hệ 2 ngôi Cho một tập hợp X khác rỗng. Một quan hệ 2 ngôi trên X là một tập hợp con R của X2. Cho 2 phần tử x và y của X, ta nói x có quan hệ R với y khi và chỉ khi (x,y) R, và viết là x R y x R y (x,y) R Khi x không có quan hệ R với y, ta viết: Ví dụ Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳn. (R = { (x,y) Z2 : x-y = 2k với k Z } ) ∀x, y ∈ R, xRy ⇔ |x| = |y| ∀x, y ∈ Q, xRy ⇔ x ≤ y ∀x, y ∈ Z, xRy ⇔ a – b chia hết cho n x ≡ y (mod n). Quan hệ Người ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB. Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An. Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là một bộ
