Bổ túc toán  (Page 2/3)

Thí dụ 1.4 : { 1, 2, 3, 4 } = { 2, 1, 4, 3 } nhưng { 1, 2, 3, 4 }  { 2, 1, 3, 5 }

Tập hợp tất cả các tập hợp con của tập A được gọi là tập lũy thừa (power set) của A và xác định bởi 2A.

Thí dụ 1.5 : Giả sử A = { 1, 2, 3 }

Thì 2A = { , {1 }, {2 }, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} }

Các phép toán trên tập hợp

Các toán tử cơ bản trên tập hợp bao gồm các toán tử một ngôi (unary) và hai ngôi (binary) như sau :

1) Phép phần bù (complement) : A' = {x  x  A }

2) Phép hợp (union) : A  B = {x  x A hoặc x B}

3) Phép giao (intersection) : A  B = {x  x A và x B}

4) Phép trừ (difference) : A \ B = {x  x A nhưng x B}

5) Tích Đecac : A  B = {(a,b)  a A và bB}

Thí dụ 1.6 : Cho A = {1, 2} và B = {2, 3}

Ta có : A  B = {1, 2, 3}

A  B = {2}

A \ B = {1}

A  B = {(1, 2 ), (1, 3), (2, 2), (2, 3)}

2A = {, {1}, {2}, {1, 2}}

Lưu ý : Nếu A và B lần lượt có số phần tử là n và m thì tập hợp A  B có n  m phần tử và tập 2A có 2n phần tử.

Quan hệ (relations)

Cho hai tập hợp A và B. Một quan hệ hai ngôi R giữa A và B là tập hợp chứa tất cả các tập hợp con của A  B mà thành phần thứ nhất A được gọi là miền xác định (domain) của R, còn B gọi là miền giá trị (range) của R (có thể trùng với miền xác định). Chúng ta sẽ thường dùng quan hệ hai ngôi mà miền xác định và miền giá trị cùng thuộc một tập hợp S nào đó. Trong trường hợp này, ta gọi đây là một quan hệ trên S. Nếu R là một quan hệ và (a,b) là một cặp trong R thì ta viết aRb.

Thí dụ 1.7 : Cho S = { 0, 1, 2, 3}

. Quan hệ "thứ tự nhỏ hơn" trên S được xác định bởi tập :

L = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}

. Quan hệ "bằng" trên S được xác định bởi tập :

E = {(0, 0), (1, 1), (2, 2), (3, 3)}

. Quan hệ "chẵn lẻ" trên S được xác định bởi tập :

P = {(0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)}

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}