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
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng 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ạ:
a. R phản xạ nếu “∀x ∈ S: x R x “
b. 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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
