Chương III Quan hệ

1. Định nghĩa: Một quan hệ hai ngôi R trên S ≠  thực chất là 1 tập con R của S2. Tập con này liệt kê các cặp của S2 có quan hệ R. R = { (x,y)  S2 / x R y }  S2 x,y  S: x R y (x,y)  R x ¬R y (x,y)  R 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)} Với quan hệ này ta có:2 R 4,nhưng 2 ¬R 3 2.Cách xác định 1 qhệ 2 ngôi R trên S khác : Cách 1: Liệt kê R như 1 tập con của S Ví dụ: S = Z. Cho qhệ 2 ngôi trên S là: R = {(0,0); (1,3);(-2,-5)(7,-6)} (R là tập con của S2) 2.Cách xác định 1 qhệ 2 ngôi R trên S khác : Cách 2: Nêu ra nội dung của qhệ 2 ngôi Ví dụ: S = Z x,y  S: x R y 3x2 > 2y3 + 1 5 R 3 4 ¬R 3 2.Cách xác định 1 qhệ 2 ngôi R trên S khác : Cách 3: Biểu diễn qhệ 2 ngôi R bằng ma trận vuông nhị phân: Kết quả trả về: 1 nếu x R y 0 nếu x ¬R y Ví dụ: S = { a,b,c,d} và qhệ 2 ngôi R ( trên S) có ma trận như sau: Ví dụ: R = { (a,a);(a,c);(c,a);(c,c);(c,d);(d,b)} 3. Các tính chất: Với R là quan hệ 2 ngôi trên S ≠  3.1: Tính phản xạ: R phản xạ nếu “x  S: x R x “ R không phản xạ nếu: Ví dụ về tính chất phản xạ: S= { 1,2,3} là tập hợp con của T={1,2,3,4} R={(2,2),(1,3),(3,3),(1,1)} là tập hợp con của S2 và T2 R (trên S): R phản xạ vì 2 R 2; 1 R 1; 3 R 3 R ( trên T):R ko phản xạ vì tồn tại 4 thuộc T, 4 ¬R 4 3.Các tính chất: 3.2: Tính đối xứng: R đối xứng nếu: “x,y  S: x R y => y R x và ngược lại. Ví dụ: A={1,2,3}, xét quan hệ trên A R3 = {(1,1), (3,2), (1,3), (3,1), (2,3)} là quan hệ đối xứng R4 = {(2,1), (1,2), (3,2), (1,3), (3,1), (3,3)} là quan hệ không đối xứng 3.Các tính chất: 3.3: Tính phản xứng: R phản xứng nếu x,y  S: x R y và y R x => x = y Hoặc R phản xứng nếu: x,y  S: x ≠ y => x ¬R y và y ¬R x 3.Các tính chất: 3.4: Tính truyền (tính bắc cầu): R truyền nếu x,y,z  S: x R y và y R z => x R z 1.Định nghĩa: Cho (S,R) R gọi là qhệ tương đương nếu R có tính chất: Phản xạ Đối xứng Truyền Kí hiệu :R ≡ ~ Ví dụ: S= { mọi người} x,y  S, ta đặt x ~ y x cùng tuổi với y x  S, x cùng tuổi với x, nghĩa là x ~ x x,y  S, x ~ y => x cùng tuổi với y => y cùng tuổi với x => y ~ x ( tính đối xứng) Tương tự với tính bắc cầu 1.Định nghĩa: Cho (S, ~) và a  S Tìm x  S mà x ~ a Đặt [a] = { x  S / x ~ a} = { a,…} ≠ [a] là tập con của S [a] là lớp tương đương của a xác định bởi quan hệ tương tương ~ 1.2: Sự phân hoạch thành các lớp tương đương: Cho (S,~), qhệ tương đương ~ sẽ phân chia S thành các lớp tương đương rời nhau từng đôi một. Mỗi lớp tương đương có dạng [a] với a nào đó  S. Nếu 2 ptử có qhệ ~ thì chúng thuộc cùng 1 lớp tương đương : x ~ y Nếu 2 ptử không qhệ ~ thì chúng thuộc 2 lớp tương đương rời nhau : x ~ y