Các tính chất của quan hệ

Ta gọi một quan hệ R trên tập S là:

Phản xạ (reflexive) : nếu aRa là đúng ∀a ∈ S

Đối xứng (symmetric) : nếu aRb thì bRa

Bắc cầu (transitive) : nếu aRb và bRc thì aRc

Thí dụ 1.8 :

. L không là quan hệ phản xạ trên S vì (0, 0) ∉ L, nhưng E và P là 2 quan hệ mang tính phản xạ.

. L không là quan hệ đối xứng trên S vì (0, 1) ∈ L nhưng (1, 0) ∉ L, tuy nhiên cả E và P đều mang tính đối xứng.

. Cả L, E và P đều là các quan hệ mang tính bắc cầu, nhưng X = {(1, 0),(0, 3)} thì không vì (1, 3) ∉ X.

Quan hệ tương đương

Một quan hệ R trên tập S có đủ các tính chất phản xạ, đối xứng và bắt cầu được gọi là quan hệ tương đương.

Thí dụ 1.9 : E và P là các quan hệ tương đương, còn L và X không là các quan hệ tương đương trên S.

Một tính chất quan trọng của quan hệ tương đương là nếu R là quan hệ tương đương trên tập S thì R phân hoạch tập S thành các lớp tương đương (equivalence class) Si không rỗng và rời nhau, tức là S = S1 S2 ... và với mọi i ≠ j ta có :

+ Si Sj =

+ Với mỗi a,b cùng thuộc Si thì aRb là đúng.

+ Với mỗi a ∈ Si và b ∈ Sj thì aRb là sai.

Lưu ý rằng số lớp tương đương có thể là vô hạn. Vậy nếu R là quan hệ tương trên S và a ∈ S, ta có :

Si = [a] = {b S | aRb}

Thí dụ 1.10 :

. E có 4 lớp tương đương khác nhau: [0] = {0}, [1] = {1}, [2] = {2} và [3] = {3}

. P có 2 lớp tương đương khác nhau: [0] = [2] = {0, 2} và [1] = [3] = {1, 3}

Bao đóng của quan hệ

Giả sử P là tập hợp một số tính chất của các quan hệ, bao đóng P (P - closure) của một quan hệ R trên tập S là quan hệ nhỏ nhất có chứa tất cả các cặp của R thoả mãn các tính chất trong P.

Bao đóng bắc cầu R+ của R được xác định như sau :

i) Nếu (a,b) thuộc R thì (a,b) thuộc R⁺.

ii) Nếu (a,b) thuộc R⁺ và (b,c) cũng thuộc R thì (a,c) thuộc R⁺.

iii) Không còn gì thêm trong R⁺.

Bao đóng phản xạ và bắc cầu R* của R được xác định như sau :

R^* = R⁺ {(a, a) | a ∈ S}

Thí dụ 1.11 : Cho quan hệ R = {(1, 2), (2, 2), (2, 3)} trên tập hợp S = {1, 2, 3}

Khi đó ta có :

R⁺ = {(1, 2), (2, 2), (2, 3), (1, 3)}

R^* = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}