Chương
Chương
2
2
2.2 Quan hệ tương đương
2.3 Quan hệ thứ tự
2.1 Định nghĩa
QUAN HỆ HAI NGÔI
2.1 ĐỊNH NGHĨA
a) Tích đề-các:
 Tích đề-các của hai tập A&B là tập:
},/),{( BbAabaBA




}/), ,{(
2121 iinn
AaaaaAAA 
 Tích đề-các của các tập A
1
, A
2
, …, A
n
là tập:
Ví dụ:
Cho 2 tập: A = {1; 2; 3}, B = {a, b}
AB = {(1; a), (1; b), (2; a), (2; b), (3; a), (3; b)}
BA = {(a; 1), (a; 2), (b; 1), (b; 2), (c; 1), (c; 2)}
AA = A

Cho 2 tập A = {a
1
, a
2
, …, a
n
}, B = {b
1
, b
2
, …, b
n
}
Ma trận biểu diễn quan hệ giữa A&B, kí hiệu:
M
R
= (m
ij
)
mxn






ji
ji
ij
bRakhi0

Quan hệ R gọi quan hệ tương đương nếu nó có tính
phản xạ, đối xứng và bắc cầu.
Ví dụ
Chứng minh quan hệ đồng dư “mod n” là quan hệ
tương đương
a, b  z, aRb  (a – b) chia hết cho n
HD
 Tính phản xạ:
aRan0a)(aZ,a






bRana)(b
na)(bnb)(aaRbZ,ba,










 Tính đối xứng:
 R có tính phản xạ
 R có tính đối xứng

, …/A
i
 A}
Thỏa các điều kiện sau:
AAAAii
jiAAi
n
ji






,.
21

 Cho R là một quan hệ tương đương trên tập A
và xA. Lớp tương đương chứa x là tập hợp các
phần tử của A có quan hệ với x, kí hiệu:
A/aRx}{a)x(hay[x] 
Và
}/{ AxxS 
là một phân hoạch của A.
 Ghi chú: Tập hợp các lớp tương đương S của A
gọi là tập thương của A.
Ví dụ
Cho f(x) = x
2
+ 2x. Trên tập số thực R, xét quan hệ

2.3 QUAN HỆ THỨ TỰ
Quan hệ R gọi quan hệ thứ tự nếu nó có tính phản
xạ, phản đối xứng và bắc cầu.
Ví dụ
Chứng tỏ các quan hệ sau là quan hệ thứ tự:
1. Trên tập số thực R, xét quan hệ “” thông thường:
a, b  R, aRb  a  b
2. Trên tập N*, xét quan hệ chia hết sau:
a, b N*, aRb  “b chia hết cho a”
HD
1. Ta kiểm tra các tính chất sau:
 Tính đối xứng:
a N*, a  a  aRa  R có tính phản xạ
 Tính phản đối xứng:
a, b N*, aRb & bRa  a  b & b  a
 a = b  R có tính phản đối xứng
 Tính bắc cầu:
a, b, c N*, aRb & bRc  a  b & b  c
 a  c  R có tính bắc cầu
Vậy R là một quan hệ thứ tự