Chương 3 : Quan hệ hai ngôi | Tài liệu Cấu Trúc Rời Rạc

Quan hệ hai ngôi R trên tập A được gọi là quan hệ tương đương nếu nó có các tính chất phản xạ, đối xứng và bắc cầu. Tài liệu giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao.

Môn:
Thông tin:
42 trang 4 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Chương 3 : Quan hệ hai ngôi | Tài liệu Cấu Trúc Rời Rạc

Quan hệ hai ngôi R trên tập A được gọi là quan hệ tương đương nếu nó có các tính chất phản xạ, đối xứng và bắc cầu. Tài liệu giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao.

127 64 lượt tải Tải xuống
Chương 3: Quan hệ hai ngôi
Nguyễn Minh T
Trường Đại học Công nghệ Thông tin
Ngày 5 tháng 4 năm 2023
3.1 Quan hệ hai ngôi các tính chất
Định nghĩa 3.1
Một quan hệ hai ngôi (quan hệ) R từ tập A đến tập B tập con của
tích Descartess R A × B.
Ta viết aRb thay cho (a, b) R; nếu (a, b) ∈ R thì ta viết aRb.
Quan hệ hai ngôi từ A đến A được gọi quan hệ hai ngôi trên A.
dụ 3.2 Cho A = {1, 2, 3, 4} R, S các quan hệ (hai ngôi) trên A
xác định bởi
a. R = {(a, b) A
2
| a ước của b}.
b. S = {(a, b) A
2
| a b}.
c. T = {(a, b) A
2
| a + b
.
.
. 3}.
Khi đó
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
S = ...........................................................................................................
T = ...........................................................................................................
Định nghĩa 3.3 (Tính phản xạ) Quan hệ hai ngôi R trên tập A tính
phản xạ nếu chỉ nếu
a A, aRa.
dụ 3.4 Trên tập A = {1, 2, 3, 4}, xét các quan hệ hai ngôi
Quan hệ R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)} không
tính phản xạ (3, 3) ∈ R.
Quan hệ S = {(1, 1), (1, 2), (1, 4), (2, 2), (3, 3), (4, 1), (4, 4)} tính
phản xạ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dụ 3.5
Quan hệ trên tập Z tính phản xạ . . . . . . . . . . . . . . . . . . . . . . . . . .
Quan hệ < trên tập Z không tính phản xạ . . . . . . . . . . . . . . . . . . . .
Quan hệ "là ước" trên tập các số nguyên dương Z
+
tính phản xạ
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.6 (Tính đối xứng) Quan hệ hai ngôi R trên tập A tính
đối xứng nếu chỉ nếu
x, y A, xRy yRx
dụ 3.7
Quan hệ R = {(1, 1), (1, 2), (2, 1)} trên tập A = {1, 2, 3, 4} tính
đối xứng.
Quan hệ trên tập Z không tính đối xứng . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Quan hệ "là ước" trên tập các số nguyên dương Z
+
không tính
đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.8 (Tính phản đối xứng) Quan hệ hai ngôi R trên tập A
tính chất phản đối xứng nếu chỉ nếu
x, y A, (xRy yRx) x = y.
dụ 3.9
Quan hệ R = {(1, 1), (1, 2), (2, 1)} trên tập A = {1, 2, 3, 4} tính
phản đối xứng.
Quan hệ trên tập Z tính phản đối xứng . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Quan hệ "là ước" trên tập các số nguyên dương Z
+
tính phản đối
xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.10 (Tính bắc cầu) Quan hệ hai ngôi R trên tập A tính
bắc cầu nếu chỉ nếu
x, y, z A, (xRy yRz) xRz
dụ 3.11
Quan hệ R = {(1, 1), (1, 2), (2, 1), (2, 2), (1, 3), (2, 3)} trên tập
A = {1, 2, 3, 4} tính bắc cầu.
Quan hệ trên tập Z tính bắc cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Quan hệ "là ước" trên tập các số nguyên dương Z
+
tính phản đối
xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dụ 3.12 Cho A = {1, 2, 3, 4} R một quan hệ trên A như sau
R = {(a, b) A
2
| a + b số lẻ}.
Xác định các phần tử các tính chất của R.
Giải. Dạng định nghĩa của R
R = {(1, 2), (1, 4), (2, 1), (2, 3), (3, 2), (3, 4), (4, 1), (4, 3)}
Ta thấy
R không tính phản xạ (1, 1) ∈ R
R tính đối xứng với mọi a, b A nếu "a + b số lẻ" thì "b + a
số lẻ."
R không tính phản đối xứng (1, 2) R (2, 1) R nhưng
1 = 2.
R không tính bắc cầu (1, 2) R (2, 3) R nhưng (1, 3) ∈ R.
3.2 Biểu diễn quan hệ hai ngôi
Định nghĩa 3.13 Cho R một quan hệ từ A = {a
1
, a
2
, . . . , a
m
} đến
B = {b
1
, b
2
, . . . , b
n
}. Ma trận biểu diễn của R M
R
= [m
ij
]
m×n
trong đó
m
ij
=
(
1 nếu (a
i
, b
j
) R
0 nếu (a
i
, b
j
) ∈ R
dụ 3.14 Cho R một quan hệ từ A = {a, b, c} đến B = {s, t, u, v}
như sau
R = {(a, s), (a, v), (b, v), (c, t), (c, u), (c, v)}.
Ma trận biểu diễn của R
1 0 0 1
0 0 0 1
0 1 1 1
Nhận xét.
Cho R một quan hệ trên tập A. Khi đó M
R
ma trận vuông.
Quan hệ R tính phản xạ khi chỉ khi tất cả các phần tử trên
đường chéo của M
R
đều bằng 1, tức m
ii
= 1 với mọi i.
Quan hệ R tính đối xứng khi chỉ khi M
R
ma trận đối xứng.
Quan hệ R tính phản đối xứng khi chỉ khi m
ij
= 0 hoặc
m
ij
= 0 với mọi i = j.
dụ 3.15 Giả sử quan hệ R được biểu diễn bởi ma trận
M
R
=
1 1 0
1 1 1
0 1 1
Quan hệ R tính phản xạ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Quan hệ R tính đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Quan hệ R ............. tính phản đối xứng . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.16 Một đồ thị hướng (digraph) bao gồm một tập hợp V
các đỉnh (hoặc các nút) cùng với một tập hợp E các cặp phần tử thứ
tự của V được gọi các cạnh (hoặc các cung). Đỉnh a gọi đỉnh đầu
của cạnh (a, b), đỉnh b gọi đỉnh cuối của cạnh y.
Một cạnh của dạng (a, a) được biểu diễn bằng một cung từ đỉnh a
quay lại chính nó. Một cạnh như vậy được gọi một vòng (loop).
Một quan hệ hai ngôi R trên một tập hữu hạn A thể được biểu
diễn bởi một đồ thị hướng trong đó các phần tử của A các đỉnh,
các cặp (a, b) R các cạnh từ a đến b.
dụ 3.17 Cho A = {a, b, c, d} quan hệ hai ngôi R trên A như sau
R = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}
Đồ thị biểu diễn quan hệ R như sau
a
b
c
d
Nhận xét:
Quan hệ hai ngôi R tính phản xạ khi chỉ khi các đỉnh của đồ thị
hướng đều vòng.
Quan hệ hai ngôi R tính phản xạ khi chỉ khi mỗi cạnh giữa các
đỉnh phân biệt đều cạnh theo hướng ngược lại.
Quan hệ hai ngôi R tính phản đối xứng khi chỉ khi không tồn
tại các cạnh hướng ngược nhau giữa hai đỉnh.
Quan hệ hai ngôi R tính bắc cầu khi chỉ khi nếu một cạnh
từ đỉnh x đến đỉnh y cạnh từ đỉnh y đến đỉnh z thì một cạnh từ
đỉnh x đến đỉnh z.
dụ 3.18 Xét các tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu
của các quan hệ hai ngôi sau:
a
b
c
R tính phản xạ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
R không tính đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
R không tính phản đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
R không tính bắc cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dụ 3.19 Cho A = {a, b, c, d} quan hệ hai ngôi
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (b, d), (d, d)}
R tính phản xạ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
R không tính đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
R không tính phản đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
R không tính bắc cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dụ 3.20 Xét các tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu
của các quan hệ hai ngôi sau:
a. x, y Z, xRy x = y
2
b. Cho A = {a, b, c, d, e}
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Giải. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Quan hệ tương đương
Định nghĩa 3.21 Quan hệ hai ngôi R trên tập A được gọi quan hệ
tương đương nếu các tính chất phản xạ, đối xứng bắc cầu.
dụ 3.22 Cho A = {1, 2, 3, 4} R một quan hệ trên A như sau
R = {(a, b) A
2
| a + b số chẵn}.
Khi đó R một quan hệ tương đương.
Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dụ 3.23 Cho R một quan hệ trên Z như sau
a, b Z, aRb a b
.
.
. 5
Khi đó R một quan hệ tương đương. Quan hệ R được gọi quan hệ
đồng modulo 5.
Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.24 Cho R một quan hệ tương đương trên tập A
a A.
Lớp tương đương của a, hiệu [a]
R
hoặc
a, tập hợp
{x A | xRa}.
Mỗi phần tử x [a]
R
được gọi một phần tử đại diện của lớp
tương đương [a]
R
.
Tập thương của A theo quan hệ R, hiệu A/R, tập tất cả
các lớp tương đương của các phần tử thuộc A, nghĩa
A/R = {[a]
R
| a A}.
dụ 3.25 Xét R quan hệ đồng theo modulo 5 trên tập Z.
Lớp tương đương của 0, 1
[0]
R
= {. . . , 10, 5, 0, 5, 10, . . .}
[1]
R
= {. . . , 9, 4, 1, 6, 11, . . .}
Ta [0]
R
= [5]
R
= [10]
R
[1]
R
= [6]
R
= [11]
R
Định 3.26 Cho R một quan hệ tương đương trên tập A x, y A.
Các điều sau đây tương đương
1. xRy
2. [x]
R
= [y]
R
3. [x]
R
[y]
R
=
Nhận xét. Các lớp tương đương trên A tạo nên một phân hoạch trên A,
nghĩa chúng chia tập A thành các tập con rời nhau.
dụ 3.27 Quan hệ R quan hệ đồng theo modulo 5 trên tập số
nguyên Z phân hoạch Z thành 5 tập con [0]
R
, [1]
R
, [2]
R
, [3]
R
, [4]
R
.
Nhận xét. Ngược lại, cho {A
1
, A
2
, . . .} một phân hoạch của A gồm
các tập con không rỗng, rời nhau. Khi đó duy nhất quan hệ tương
đương trên A sao cho mỗi A
i
một lớp tương đương.
Thật vậy, với mỗi a, b A, ta đặt aRb nếu tập con A
i
sao cho
a, b A
i
.
Dễ dàng chứng minh rằng R quan hệ tương đương trên A [a]
R
= A
i
nếu a A
i
.
dụ 3.28 Cho R một quan hệ hai ngôi trên tập số thực R như sau
x, y R, xRy x + x
3
= y + y
3
.
a. Chứng minh R một quan hệ tương đương.
b. Tìm các lớp tương đương của 1, 0, 1 tìm tập thương.
Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dụ 3.29 Cho R một quan hệ hai ngôi trên tập A = {−1, 0, 1, 2, 3, 4}
như sau
x, y A, xRy 4x y
.
.
. 3.
a. Chứng minh R một quan hệ tương đương.
b. Tìm các lớp tương đương của 1, 0, 1 tìm tập thương.
Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
| 1/42

Preview text:

Chương 3: Quan hệ hai ngôi Nguyễn Minh Trí
Trường Đại học Công nghệ Thông tin Ngày 5 tháng 4 năm 2023
3.1 Quan hệ hai ngôi và các tính chất Định nghĩa 3.1
• Một quan hệ hai ngôi (quan hệ) R từ tập A đến tập B là tập con của tích Descartess R ⊂ A × B.
• Ta viết aRb thay cho (a, b) ∈ R; nếu (a, b) ̸∈ R thì ta viết aRb.
• Quan hệ hai ngôi từ A đến A được gọi là quan hệ hai ngôi trên A.
Ví dụ 3.2 Cho A = {1, 2, 3, 4} và R, S là các quan hệ (hai ngôi) trên A xác định bởi
a. R = {(a, b) ∈ A2 | a là ước của b}.
b. S = {(a, b) ∈ A2 | a ≤ b}. .
c. T = {(a, b) ∈ A2 | a + b .. 3}. Khi đó
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
S = ...........................................................................................................
T = ...........................................................................................................
Định nghĩa 3.3 (Tính phản xạ) Quan hệ hai ngôi R trên tập A có tính
phản xạ nếu và chỉ nếu ∀a ∈ A, aRa.
Ví dụ 3.4 Trên tập A = {1, 2, 3, 4}, xét các quan hệ hai ngôi
• Quan hệ R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)} không có
tính phản xạ vì (3, 3) ̸∈ R.
• Quan hệ S = {(1, 1), (1, 2), (1, 4), (2, 2), (3, 3), (4, 1), (4, 4)} có tính
phản xạ vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ví dụ 3.5
• Quan hệ ≤ trên tập Z có tính phản xạ vì . . . . . . . . . . . . . . . . . . . . . . . . . .
• Quan hệ < trên tập Z không có tính phản xạ vì . . . . . . . . . . . . . . . . . . . .
• Quan hệ "là ước" trên tập các số nguyên dương Z+ có tính phản xạ
vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.6 (Tính đối xứng) Quan hệ hai ngôi R trên tập A có tính
đối xứng nếu và chỉ nếu ∀x, y ∈ A, xRy ⇒ yRx Ví dụ 3.7
• Quan hệ R = {(1, 1), (1, 2), (2, 1)} trên tập A = {1, 2, 3, 4} có tính đối xứng.
• Quan hệ ≤ trên tập Z không có tính đối xứng vì . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Quan hệ "là ước" trên tập các số nguyên dương Z+ không có tính
đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.8 (Tính phản đối xứng) Quan hệ hai ngôi R trên tập A có
tính chất phản đối xứng nếu và chỉ nếu
∀x, y ∈ A, (xRy ∧ yRx) ⇒ x = y. Ví dụ 3.9
• Quan hệ R = {(1, 1), (1, 2), (2, 1)} trên tập A = {1, 2, 3, 4} có tính phản đối xứng.
• Quan hệ ≤ trên tập Z có tính phản đối xứng vì . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Quan hệ "là ước" trên tập các số nguyên dương Z+ có tính phản đối
xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.10 (Tính bắc cầu) Quan hệ hai ngôi R trên tập A có tính
bắc cầu nếu và chỉ nếu
∀x, y, z ∈ A, (xRy ∧ yRz) ⇒ xRz Ví dụ 3.11
• Quan hệ R = {(1, 1), (1, 2), (2, 1), (2, 2), (1, 3), (2, 3)} trên tập
A = {1, 2, 3, 4} có tính bắc cầu.
• Quan hệ ≤ trên tập Z có tính bắc cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Quan hệ "là ước" trên tập các số nguyên dương Z+ có tính phản đối
xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ 3.12 Cho A = {1, 2, 3, 4} và R là một quan hệ trên A như sau
R = {(a, b) ∈ A2 | a + b là số lẻ}.
Xác định các phần tử và các tính chất của R.
Giải. Dạng định nghĩa của R là
R = {(1, 2), (1, 4), (2, 1), (2, 3), (3, 2), (3, 4), (4, 1), (4, 3)} Ta thấy
• R không có tính phản xạ vì (1, 1) ̸∈ R
• R có tính đối xứng vì với mọi a, b ∈ A nếu "a + b là số lẻ" thì "b + a là số lẻ."
• R không có tính phản đối xứng vì (1, 2) ∈ R và (2, 1) ∈ R nhưng 1 ̸= 2.
• R không có tính bắc cầu vì (1, 2) ∈ R và (2, 3) ∈ R nhưng (1, 3) ̸∈ R.
3.2 Biểu diễn quan hệ hai ngôi
Định nghĩa 3.13 Cho R là một quan hệ từ A = {a1, a2, . . . , am} đến
B = {b1, b2, . . . , bn}. Ma trận biểu diễn của R là MR = [mij]m×n trong đó (1 nếu (a m i, bj ) ∈ R ij = 0 nếu (ai, bj) ̸∈ R
Ví dụ 3.14 Cho R là một quan hệ từ A = {a, b, c} đến B = {s, t, u, v} như sau
R = {(a, s), (a, v), (b, v), (c, t), (c, u), (c, v)}.
Ma trận biểu diễn của R là 1 0 0 1 0 0 0 1   0 1 1 1 Nhận xét.
• Cho R là một quan hệ trên tập A. Khi đó MR là ma trận vuông.
• Quan hệ R có tính phản xạ khi và chỉ khi tất cả các phần tử trên
đường chéo của MR đều bằng 1, tức là mii = 1 với mọi i.
• Quan hệ R có tính đối xứng khi và chỉ khi MR là ma trận đối xứng.
• Quan hệ R có tính phản đối xứng khi và chỉ khi mij = 0 hoặc mij = 0 với mọi i ̸= j.
Ví dụ 3.15 Giả sử quan hệ R được biểu diễn bởi ma trận 1 1 0 MR = 1 1 1   0 1 1
• Quan hệ R có tính phản xạ vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Quan hệ R có tính đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Quan hệ R ............. tính phản đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.16 Một đồ thị có hướng (digraph) bao gồm một tập hợp V
các đỉnh (hoặc các nút) cùng với một tập hợp E các cặp phần tử có thứ
tự của V được gọi là các cạnh (hoặc các cung). Đỉnh a gọi là đỉnh đầu
của cạnh (a, b), đỉnh b gọi là đỉnh cuối của cạnh này.
• Một cạnh của dạng (a, a) được biểu diễn bằng một cung từ đỉnh a
quay lại chính nó. Một cạnh như vậy được gọi là một vòng (loop).
• Một quan hệ hai ngôi R trên một tập hữu hạn A có thể được biểu
diễn bởi một đồ thị có hướng trong đó các phần tử của A là các đỉnh,
các cặp (a, b) ∈ R là các cạnh từ a đến b.
Ví dụ 3.17 Cho A = {a, b, c, d} và quan hệ hai ngôi R trên A như sau
R = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}
Đồ thị biểu diễn quan hệ R như sau c d a b Nhận xét:
• Quan hệ hai ngôi R có tính phản xạ khi và chỉ khi các đỉnh của đồ thị có hướng đều có vòng.
• Quan hệ hai ngôi R có tính phản xạ khi và chỉ khi mỗi cạnh giữa các
đỉnh phân biệt đều có cạnh theo hướng ngược lại.
• Quan hệ hai ngôi R có tính phản đối xứng khi và chỉ khi không tồn
tại các cạnh có hướng ngược nhau giữa hai đỉnh.
• Quan hệ hai ngôi R có tính bắc cầu khi và chỉ khi nếu có một cạnh
từ đỉnh x đến đỉnh y và cạnh từ đỉnh y đến đỉnh z thì có một cạnh từ đỉnh x đến đỉnh z.
Ví dụ 3.18 Xét các tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu
của các quan hệ hai ngôi sau: c a b
• R có tính phản xạ vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• R không có tính đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• R không có tính phản đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• R không có tính bắc cầu vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ 3.19 Cho A = {a, b, c, d} và quan hệ hai ngôi
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (b, d), (d, d)}
• R có tính phản xạ vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• R không có tính đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• R không có tính phản đối xứng vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• R không có tính bắc cầu vì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ 3.20 Xét các tính chất phản xạ, đối xứng, phản đối xứng, bắc cầu
của các quan hệ hai ngôi sau:
a. ∀x, y ∈ Z, xRy ⇔ x = y2 b. Cho A = {a, b, c, d, e} và
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Giải. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Quan hệ tương đương
Định nghĩa 3.21 Quan hệ hai ngôi R trên tập A được gọi là quan hệ
tương đương nếu nó có các tính chất phản xạ, đối xứng và bắc cầu.
Ví dụ 3.22 Cho A = {1, 2, 3, 4} và R là một quan hệ trên A như sau
R = {(a, b) ∈ A2 | a + b là số chẵn}.
Khi đó R là một quan hệ tương đương. Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ 3.23 Cho R là một quan hệ trên Z như sau . ∀a, b ∈ . Z, aRb ⇔ a − b . 5
Khi đó R là một quan hệ tương đương. Quan hệ R được gọi là quan hệ đồng dư modulo 5. Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Định nghĩa 3.24 Cho R là một quan hệ tương đương trên tập A và a ∈ A.
• Lớp tương đương của a, kí hiệu [a]R hoặc a, là tập hợp {x ∈ A | xRa}.
• Mỗi phần tử x ∈ [a]R được gọi là một phần tử đại diện của lớp tương đương [a]R.
• Tập thương của A theo quan hệ R, ký hiệu là A/R, là tập tất cả
các lớp tương đương của các phần tử thuộc A, nghĩa là A/R = {[a]R | a ∈ A}.
Ví dụ 3.25 Xét R là quan hệ đồng dư theo modulo 5 trên tập Z.
• Lớp tương đương của 0, 1
[0]R = {. . . , −10, −5, 0, 5, 10, . . .}
[1]R = {. . . , −9, −4, 1, 6, 11, . . .}
• Ta có [0]R = [5]R = [10]R và [1]R = [6]R = [11]R
Định lý 3.26 Cho R là một quan hệ tương đương trên tập A và x, y ∈ A.
Các điều sau đây là tương đương 1. xRy 2. [x]R = [y]R 3. [x]R ∩ [y]R ̸= ∅
Nhận xét. Các lớp tương đương trên A tạo nên một phân hoạch trên A,
nghĩa là chúng chia tập A thành các tập con rời nhau.
Ví dụ 3.27 Quan hệ R là quan hệ đồng dư theo modulo 5 trên tập số
nguyên Z phân hoạch Z thành 5 tập con [0]R, [1]R, [2]R, [3]R, [4]R.
Nhận xét. Ngược lại, cho {A1, A2, . . .} là một phân hoạch của A gồm
các tập con không rỗng, rời nhau. Khi đó có duy nhất quan hệ tương
đương trên A sao cho mỗi Ai là một lớp tương đương.
Thật vậy, với mỗi a, b ∈ A, ta đặt aRb nếu có tập con Ai sao cho a, b ∈ Ai.
Dễ dàng chứng minh rằng R là quan hệ tương đương trên A và [a]R = Ai nếu a ∈ Ai.
Ví dụ 3.28 Cho R là một quan hệ hai ngôi trên tập số thực R như sau
∀x, y ∈ R, xRy ⇔ x + x3 = y + y3.
a. Chứng minh R là một quan hệ tương đương.
b. Tìm các lớp tương đương của −1, 0, 1 và tìm tập thương. Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ 3.29 Cho R là một quan hệ hai ngôi trên tập A = {−1, 0, 1, 2, 3, 4} như sau .
∀x, y ∈ A, xRy ⇔ 4x − y .. 3.
a. Chứng minh R là một quan hệ tương đương.
b. Tìm các lớp tương đương của −1, 0, 1 và tìm tập thương. Giải.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .