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 | 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 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) 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 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 . | 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 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) 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 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 ≠ : 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 tính chất: : 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 tính chất: : 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 tính chất: : 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 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
