QUAN HỆ
Giảng viên: ThS. Hồ Văn Ngọc
CHƯƠNG
2
Nội dung
Giới thiệu Quan hệ
Các tính chất của quan hệ.
Quan hệ tương đương.
Quan hệ thứ tự.
Quan hệ toàn phần
1. Giới thiệu Quan hệ
Tập hợp: có thể hiểu tổng quát là một sự tụ tập của một số hữu hạn hay vô hạn các đối tượng nào đó.
Các đối tượng này được gọi là các phần tử của tập hợp
Ký hiệu:
Tập hợp: Dùng chữ cái HOA: A, B, C, ...
Phần tử của tập hợp: Dùng chữ cái thường:
a, b, x, y, ...
1. Giới thiệu Quan hệ
Nếu a là 1 phần tử của tập hợp A thì ta viết a  A. Ngược lại viết a  A
Ví dụ về tập hợp:
A = {x  N | x là số nguyên tố}
B = {x  Z | x2 < 15}
C = {-2, -1, 0, 1, 2}
Nếu tập A có n phần tử,
ta ký hiệu: |A| = n

1. Giới thiệu Quan hệ
Tập hợp con:
Tập hợp A là một tập con (hay tập hợp con) của tập hợp B nếu A "được chứa" trong B.
Nếu A và B là các tập hợp và mọi phần tử của A cũng là phần tử của B, thì:
A là tập con của B (hay A chứa trong B),
ký hiệu A  B
B là tập cha của A (hay B chứa A),
ký hiệu B  A
A  B  {a| a  A  a  B}
1. Giới thiệu Quan hệ
Tập hợp rỗng: kí hiệu là  , là tập hợp không chứa phần tử nào
Tích Descartes (Đề-các) của hai tập hợp A và B, ký hiệu là A×B, là một tập hợp chứa tất cả các bộ có dạng (a, b) với a là một phần tử của A và b là một phần tử của B.

AxB = {(a,b)| a  A, b  B}
Nếu tập |A| = n và |B| = m thì
|AxB| = n x m

1. Giới thiệu Quan hệ
Ví dụ:
Nếu: A = {1,2}; B = {p,q,r} thì:
A×B = {(1,p),(1,q),(1,r),(2,p),(2,q),(2,r)}
và:
B×A = {(p,1),(q,1),(r,1),(p,2),(q,2),(r,2)}
1. Giới thiệu Quan hệ
Định nghĩa:
Một quan hệ giữa tập A và tập B là một tập con  của tích Descartes AxB.
Nếu (a,b)  , ta viết: ab
Quan hệ từ A đến A (chính nó) gọi là quan hệ trên A

1. Giới thiệu Quan hệ
Ví dụ: Một cách biểu diễn quan hệ:


1. Giới thiệu Quan hệ
Ví dụ: A = tập sinh viên; B = tập lớp học.
R = {(a, b) | sinh viên a học lớp b}


1. Giới thiệu Quan hệ
Ví dụ. Cho A = {1, 2, 3, 4}, và
R = {(a, b) | aA, bA, a là ước của b}
Khi đó:
R = {(1, 1), (1, 2), (1, 3), (1, 4),
(2, 2), (2, 4), (3, 3), (4,4)}

Biểu diễn:
2. Các tính chất của quan hệ
Tính phản xạ:
Quan hệ R trên A được gọi là phản xạ nếu: a  A, a R a
Ví dụ: Xét tập A = {1, 2, 3, 4}
với quan hệ ước số :
R = {(a, b) | aA, bA, a là ước của b}
R1 = {(1, 1), (1, 2), (1, 3), (1, 4),
(2, 2), (2, 4), (3, 3), (4,4)}
R1 phản xạ vì: (1,1)  R1, (2,2)  R1,
(3,3)  R1, (4,4)  R1
2. Các tính chất của quan hệ
Ví dụ: Cho tập A = {1, 2, 3, 4},
Xét 2 quan hệ sau:

R1 = {(1,1), (1,2), (2,1),
(2, 2), (3, 4), (4, 1), (4, 4)}
không phản xạ vì (3, 3)  R1

R2 = {(1,1), (1,2), (1,4),
(2, 2), (3, 3), (4, 1), (4, 4)}
phản xạ vì (1,1), (2,2), (3,3), (4,4)  R2
2. Các tính chất của quan hệ
Ví dụ:
Quan hệ “” trên Z phản xạ vì a  a
với mọi a Z

Quan hệ “>” trên Z không phản xạ
vì 1 1

2. Các tính chất của quan hệ
Tính đối xứng:
Quan hệ R trên A được gọi là đối xứng nếu: aA, bA, a R b  b R a
Ví dụ:
+ Quan hệ R1 = {(1,1), (1,2), (2,1)}
trên tập A = {1, 2, 3, 4} là đối xứng
+ Quan hệ "" trên Z không đối xứng
2. Các tính chất của quan hệ
Tính phản xứng:
Một quan hệ R trên tập A được gọi là phản xứng nếu:
x, y  A, (x R y)  (y R x)  x = y

Ví dụ:
+ Quan hệ “” là phản xứng
+ Quan hệ đồng nhất “” là phản xứng
+ Quan hệ song song “” là phản xứng

2. Các tính chất của quan hệ
Tính bắc cầu:
Quan hệ R trên A có tính bắc cầu (truyền) nếu a, b, cA, (a R b)  (b R c)  (a R c)
Ví dụ:
+ 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ệ "" và quan hệ ước số ("|") trên Z có tính bắc cầu
3. Biểu diễn quan hệ
Định nghĩa:
Cho R là quan hệ từ A = {a1, a2, ..., am} đến B = {b1, b2, ..., bn}
Ma trận biểu diễn của R là ma trận cấp mxn được xác định như sau:




3. Biểu diễn quan hệ
Ví dụ:
Cho R là quan hệ từ A = {1,2,3,4} đến
B = {u,v,w} như sau:
R = {(1,u),(1,v),(2,w),(3,w),(4,u)}.

Ta có: |A| = 4; |B| = 3
Khi đó R có thể biễu diễn
như một ma trận 4x3 :

3. Biểu diễn quan hệ
Ví dụ:
Nếu R là quan hệ từ A = {1, 2, 3} đến
B = {1, 2} sao cho a R b nếu a > b.
Khi đó ma trận biểu diễn của R là

3. Biểu diễn quan hệ
Nhận xét:
Nếu R là quan hệ trên tập A, khi đó MR là ma trận vuông
R là phản xạ nếu tất cả các phần tử trên đường chéo chính của MR đều bằng 1 (mii = 1 i)
R là đối xứng nếu MR đối xứng qua đường chéo chính

4. Quan hệ tương đương
Xét ví dụ:
Cho S = {sinh viên của lớp}
Gọi R = {(a,b)| a có cùng họ với b}

Hỏi:
R phản xạ?

R đối xứng?

R bắc cầu?

YES
YES
YES
4. Quan hệ tương đương
Định nghĩa:
Quan hệ R trên tập A được gọi là tương
đương nếu nó có tính chất:
- Phản xạ
- Đối xứng
- Bắc cầu

4. Quan hệ tương đương
Ví dụ:
Quan hệ R trên các chuỗi ký tự xác định bởi a R b nếu a và b có cùng độ dài.
Khi đó R là quan hệ tương đương

Cho R là quan hệ trên tập số thực sao cho a R b nếu a – b là số nguyên.
Khi đó R là quan hệ tương đương
4. Quan hệ tương đương
Lớp tương đương:
Cho R là quan hệ tương đương trên A và
phần tử a  A.
Lớp tương đương chứa a được ký hiệu
bởi [a]R hoặc [a] là tập
[a]R = {b  A | b R a}

4. Quan hệ tương đương
Ví dụ:
Tìm các lớp tương đương modulo 8 chứa 0 và modulo 8 chứa 1?

Giải:
- Lớp tương đương modulo 8 chứa 0 gồm tất cả các số nguyên a chia hết cho 8.
Ta có: [0]8 = {..., -16, -8, 0, 8, 16, ...}
- Lớp tương đương modulo 8 chứa 1 gồm tất cả các số nguyên a chia 8 dư 1.
Ta có: [1]8 = {..., -15, -7, 1, 9, 17, ...}
5. Quan hệ thứ tự
Xét ví dụ:
Cho R là quan hệ trên tập số thực:
a R b nếu a  b
Hỏi:
+ R phản xạ ?
+ R phản xứng ?
+ R đối xứng ?
+ R bắc cầu ?

YES
YES
NO
YES
5. Quan hệ thứ tự
Định nghĩa:
Quan hệ R trên tập A là quan hệ thứ tự nếu nó có tính chất:
- Phản xạ
- Phản xứng
- Bắc cầu
Khi đó, ta nói A là một tập hợp sắp thứ tự
Ký hiệu: Cặp (A, )
5. Quan hệ thứ tự
Ví dụ:
+ (R, ) là một tập hợp có thư tự.
+ (Z, |) là một tập hợp có thư tự. (|: ước)

6. Quan hệ toàn phần
Định nghĩa:
Các phần tử a và b của cặp (S, ) gọi là so sánh được nếu a b hay b a

Định nghĩa:
Cho (S, ), nếu hai phần tử tùy ý của S đều so sánh được với nhau thì ta gọi nó là tập sắp thứ tự toàn phần

Ta cũng nói rằng là thứ tự toàn phần hay thứ tự tuyến tính trên S
6. Quan hệ toàn phần
Ví dụ:
Quan hệ “” trên tập số nguyên dương Z+ là thứ tự toàn phần

Quan hệ ước số “|” trên tập hợp số nguyên dương không là thứ tự toàn phần, vì các số 5 và 7 là không so
sánh được.
Add your company slogan