Bài giảng "Cấu trúc rời rạc - Chương 3: Quan hệ" cung cấp cho người học các kiến thức về quan hệ hai ngôi trên một tập hợp và các tính chất, biểu diễn quan hệ hai ngôi, quan hệ tương đương, lớp tương đương, sự phân hoạch thành các lớp tương đương. . | . Quan hệ hai ngôi trên một tập hợp và các tính chất. Biểu diễn quan hệ hai ngôi. . Quan hệ tương đương. Lớp tương đương. Sự phân hoạch thành các lớp tương đương. . Quan hệ thứ tự. Thứ tự toàn phần và bán phần. Biểu đồ Hasse. Phần tử min và max. Các phần tử tối tiểu và tối đại. Chương 3. Quan hệ Quan hệ hai ngôi R = { (a1, b1), (a1, b3), (a3, b3) } Định nghĩa: Cho hai tập A, B. Ta gọi tập R là một quan hệ hai ngôi từ A đến B nếu R A x B. Nếu (a, b) R thì ta nói a có quan hệ R với b và ký hiệu a R b; ngược lại nếu (a, b) R thì ta kí hiệu Khi A = B, ta gọi R là một quan hệ hai ngôi trên A. a1 a2 a3 b1 b2 b3 A B Ví dụ: Ā 1. Định nghĩa. Ví dụ: Cho A = {1, 2, 3, 4}, R là một quan hệ (hai ngôi) trên A và R = {(a, b) A | a là ước của b}. Khi đó R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} Quan hệ hai ngôi 2. Các tính chất của quan hệ. Định nghĩa: Giả sử R là một quan hệ hai ngôi trên tập A. (a) Ta nói quan hệ R có tính phản xạ nếu và chỉ nếu a R a , a 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 Quan hệ hai ngôi 2. Các tính chất của quan hệ Ví dụ: - Quan hệ ≤ trên Z phản xạ vì a ≤ a, a Z. - Quan hệ > trên Z không phản xạ vì 1 không lớn hơn 1. - Quan hệ “ | ” (“ước số”) trên Z+ là phản xạ vì mọi số nguyên dương a là ước của chính nó. Quan hệ hai ngôi 2. Các tính chất của quan hệ. Định nghĩa: Giả sử R là một quan hệ hai ngôi trên tập A. (b) Ta nói quan hệ R có tính đối xứng nếu và chỉ nếu a R b b R a , a, b A. (c) Ta nói quan hệ R có tính phản xứng nếu và chỉ nếu (a R b b R a) a = b , a, b A. 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). - Quan hệ“ | ” (“ước số”) trên Z+ không đối xứng, | . Quan hệ hai ngôi trên một tập hợp và các tính chất. Biểu diễn quan hệ hai ngôi. . Quan hệ tương đương. Lớp tương đương. Sự phân hoạch thành các lớp tương đương. . Quan hệ thứ tự. Thứ tự toàn phần và bán phần. Biểu đồ Hasse. Phần tử min và max. Các phần tử tối tiểu và tối đại. Chương 3. Quan hệ Quan hệ hai ngôi R = { (a1, b1), (a1, b3), (a3, b3) } Định nghĩa: Cho hai tập A, B. Ta gọi tập R là một quan hệ hai ngôi từ A đến B nếu R A x B. Nếu (a, b) R thì ta nói a có quan hệ R với b và ký hiệu a R b; ngược lại nếu (a, b) R thì ta kí hiệu Khi A = B, ta gọi R là một quan hệ hai ngôi trên A. a1 a2 a3 b1 b2 b3 A B Ví dụ: Ā 1. Định nghĩa. Ví dụ: Cho A = {1, 2, 3, 4}, R là một quan hệ (hai ngôi) trên A và R = {(a, b) A | a là ước của b}. Khi đó R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} Quan hệ hai ngôi 2. Các tính chất của quan hệ. Định nghĩa: Giả sử R là một quan hệ hai ngôi trên tập A. (a) Ta nói quan hệ R có tính phản xạ nếu và chỉ .
