Bài viết này sẽ cung cấp cho bạn một cái nhìn toàn diện về khái niệm quan hệ trong toán học rời rạc. Chúng ta sẽ đi sâu vào định nghĩa chính thức, các tính chất quan trọng như tính phản xạ, đối xứng, và bắc cầu. Bên cạnh đó, bài viết cũng sẽ trình bày các phép toán trên quan hệ (hợp, giao, bù) và khái niệm bao đóng. Với những kiến thức này, bạn sẽ có thể tự tin giải quyết các bài toán liên quan đến quan hệ một cách hiệu quả.
Trong cuộc sống hàng ngày, chúng ta thường xuyên bắt gặp các mối liên hệ giữa các đối tượng. Ví dụ, mối quan hệ "là cha của" giữa những người, mối quan hệ "được thuê bởi" giữa nhân viên và công ty, hay mối quan hệ "chia hết cho" giữa các số nguyên. Trong toán học rời rạc, chúng ta mô hình hóa những mối liên hệ này một cách chặt chẽ hơn.
Một cách hình thức, cho hai tập hợp A và B. Một quan hệ nhị phân từ A đến B là một tập con của tích Descartes A × B. Nói cách khác, một quan hệ R chỉ đơn giản là một tập hợp các cặp có thứ tự. Chúng ta viết a R b để chỉ (a, b) ∈ R và a ∦ b để chỉ (a, b) ∉ R. Khi (a, b) ∈ R, ta nói rằng "a có quan hệ với b theo R".
Ví dụ, cho A là tập hợp sinh viên tại một trường đại học và B là tập hợp các khóa học tại trường đó. Cho R là quan hệ "đăng ký vào", sao cho (a, b) ∈ R (tức là a R b) nếu sinh viên a đăng ký vào khóa học b.
Lưu ý rằng bạn có thể coi tất cả các hàm như quan hệ (trong đó đầu vào có quan hệ với đầu ra), nhưng không phải ngược lại (vì một phần tử duy nhất có thể liên quan đến nhiều phần tử khác).
Đôi khi, quan hệ là giữa một tập hợp A và chính nó: một tập con của A × A. Trong trường hợp này, ta nói quan hệ là trên tập hợp A.
Để hiểu rõ hơn về khái niệm quan hệ, hãy xem xét một vài ví dụ sau:
Các quan hệ có thể có một số tính chất giúp phân loại chúng. Dưới đây là một số tính chất quan trọng:
Một quan hệ R trên một tập hợp A là phản xạ nếu (a, a) ∈ R cho tất cả a ∈ A. Ví dụ, nếu A = {1, 2, 3, 4}, thì R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 1), (4, 4)} là phản xạ. Quan hệ "chia hết" cũng là phản xạ vì a = 1 * a cho bất kỳ số nguyên a.
Một quan hệ R trên một tập hợp A được gọi là đối xứng nếu (a, b) ∈ R → (b, a) ∈ R cho tất cả a, b ∈ A.
Một quan hệ R trên một tập hợp A được gọi là phản đối xứng nếu ((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b) cho tất cả a, b ∈ A.
Lưu ý: Tính đối xứng và phản đối xứng không loại trừ lẫn nhau: một quan hệ có thể có một, cả hai hoặc không có tính chất nào.
Một quan hệ R trên một tập hợp A được gọi là bắc cầu nếu, đối với tất cả a, b, c ∈ A, ((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R. Ví dụ, các quan hệ sau đây trên Z đều có tính bắc cầu: {(a, b) | a ≤ b}, {(a, b) | a > b}, {(a, b) | a = b hoặc a = -b}, {(a, b) | a = b}. Quan hệ "chia hết" cũng có tính bắc cầu.
Vì quan hệ là các tập hợp, chúng có thể được kết hợp theo cùng cách mà các tập hợp có thể được kết hợp.
Các phép toán tập hợp như hợp (∪), giao (∩), và hiệu (\) có thể được áp dụng cho các quan hệ. Ví dụ, nếu R1 = {(a, b) | a < b} và R2 = {(a, b) | a > b} là các quan hệ được xác định trên R, thì R1 ∪ R2 = {(a, b) | a ≠ b}.
Cho R là một quan hệ từ tập hợp A đến tập hợp B. Cho S là một quan hệ từ tập hợp B đến tập hợp C. Hợp thành của R và S là quan hệ bao gồm các cặp có thứ tự (a, c) trong đó a ∈ A, c ∈ C và tồn tại một phần tử b ∈ B sao cho (a, b) ∈ R và (b, c) ∈ S. Ta viết S ∘ R để biểu thị quan hệ này.
Đôi khi một quan hệ không có một số tính chất mà chúng ta muốn nó có: ví dụ, tính phản xạ, đối xứng hoặc bắc cầu. Vậy làm cách nào để thêm các phần tử vào quan hệ của chúng ta để đảm bảo tính chất đó? Lý tưởng nhất là chúng ta muốn thêm càng ít phần tử mới càng tốt để bảo toàn "ý nghĩa" của quan hệ ban đầu.
Cho một quan hệ R trên một tập hợp A. Bao đóng phản xạ của R là R ∪ Δ, trong đó Δ = {(a, a) | a ∈ A}. Ví dụ, bao đóng phản xạ của R = {(a, b) | a < b} trên tập hợp các số nguyên là quan hệ R ∪ Δ = {(a, b) | a ≤ b}.
Cho một quan hệ R. Bao đóng đối xứng của R là R ∪ R-1, trong đó R-1 = {(b, a) | (a, b) ∈ R}. Ví dụ, bao đóng đối xứng của R = {(a, b) | a < b} trên tập hợp các số nguyên là quan hệ R ∪ R-1 = {(a, b) | a ≠ b}.
Bao đóng bắc cầu của R trên một tập hợp A là R ∪ R2 ∪ R3 ∪ ⋯ ∪ R|A|, trong đó Rk là kết quả của việc hợp thành R với chính nó k lần. Tính chất bắc cầu có thể được hiểu theo phép hợp thành: một quan hệ R trên một tập hợp A là bắc cầu nếu và chỉ nếu Rn ⊆ R cho n ≥ 1.
Hiểu rõ về quan hệ, các tính chất và phép toán trên quan hệ là rất quan trọng trong toán học rời rạc. Những kiến thức này không chỉ giúp bạn giải quyết các bài toán cụ thể mà còn cung cấp nền tảng vững chắc cho việc học tập các chủ đề nâng cao hơn trong khoa học máy tính và toán học.
Bài viết liên quan