›
›

Bài giảng Toán rời rạc - Chương 4: Quan hệ

Download
TOÁN RỜI RẠC  
Chương 4: QUAN HỆ  
GV: NGUYỄN LÊ MINH  
Bộ môn Công nghệ thông tin  
Nội dung  
Định nghĩa và tính chất  
Biểu diễn quan hệ  
Quan hệ tương đương – Đồng dư  
Quan hệ thứ tự - Biểu đồ Hass  
Bài tập  
2
Định nghĩa  
Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích  
Descart R A x B. Được viết a R b thay cho (a, b) R.  
Quan hệ từ A đến chính nó được gọi là quan hệ trên A  
R = { (a1, b1), (a1, b3), (a3, b3) }  
3
Định nghĩa  
Ví dụ. A = tập sinh viên; B = các lớp học.  
R = {(a, b) | sinh viên a học lớp b}  
3
Định nghĩa  
Ví dụ. Cho A = {1, 2, 3, 4}, và  
R = {(a, b) | a là ước của b}  
Khi đó  
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)}  
3
2
2
1
1
4
3
4
3
Các tính chất của quan hệ  
Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu:  
a A, a R a  
Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ:  
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  
3
Các tính chất của quan hệ  
.Quan hệ trên Z phản xạ vì a a với mọi aZ  
.Quan hệ > trên Z không phản xạ vì 1 > 1  
.Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa  
đường chéo của A × A :  
4
3
= {(a, a); a A}  
2
1
3
2
4
1
3
Các tính chất của quan hệ  
Định nghĩa. 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)  
Quan hệ R được gọi là phản xứng nếu  
a A b A (a R b) (b R a) (a = b)  
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.  
Tuy nhiên nó phản xứng vì  
(a b) (b a) (a = b)  
3
Các tính chất của quan hệ  
Chú ý. Quan hệ R trên A là đối xứng nếu nó đối xứng nhau  
qua đường chéo của A × A.  
Quan hệ R là phản xứng nếu chỉ có các phần tử nằm trên  
đường chéo là đối xứng qua của A × A.  
3
Các tính chất của quan hệ  
4
4
*
3
2
3
2
*
*
1
1
1
2
3
4
1
2
3
4
3
Các tính chất của quan hệ  
Định nghĩa. 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.  
3
Tóm lại  
R phản xạ : aRa  
R đối xứng: aRb bRa  
R phản xứng: aRb và bRa a=b  
R bắc cầu: aRb và bRc aRc  
3
Quan hệ tương đương  
Ví dụ.  
Xét quan hệ trên tập {1,2,3,4}  
Các quan hệ sau, quan hệ nào là phản xạ, đối xứng, bắc cầu  
3
Quan hệ tương đương  
Ví dụ.  
Xét quan hệ sau trên tập số nguyên  
Quan hệ nào là phản xạ, đối xứng, bắc cầu ?  
3
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 và bắc cầu :  
Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu  
a và b có cùng độ dài. Khi đó R là quan hệ tương đương.  
Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b  
nguyên. Khi đó R là quan hệ tương đương  
3
Quan hệ tương đương  
Cho a và b là hai số nguyên. a được gọi là ước của b hay b  
chia hết cho a nếu tồn tại số nguyên k sao cho b = ka  
Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z sao  
cho aRb nếu a – b chia hết cho m, khi đó R là quan hệ  
tương đương.  
- Rõ ràng quan hệ này có tính phản xạ và đối xứng.  
- Cho a, b, c sao cho a – b và b – c chia hết cho m, khi đó a  
– c = a – b + b – c cũng chia hết cho m. Suy ra R có tính chất  
bắc cầu.  
- Quan hệ này được gọi là đồng dư modulo m và được viết  
viết  
a b (mod m)  
thay vì aRb  
3
Lớp tương đương  
Định nghĩa. Cho R là quan hệ tương đương trên A và phần  
tử x A . Lớp tương đương chứa x được ký hiệu bởi [x]R  
hoặc [x] là tập hợp con  
[x]R = {b A| x R a}  
3
Lớp tương đương  
Ví dụ. Tìm các lớp tương đương modulo 8 chứa 0 và 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. Do đó  
[0]8 ={ …, – 16, – 8, 0, 8, 16, … }  
Tương tự  
[1]8 = {a | a chia 8 dư 1}  
= { …, – 15, – 7, 1, 9, 17, … }  
3
Lớp tương đương  
Chú ý. Trong ví dụ cuối, các lớp tương đương [0]8 và [1]8 là  
rời nhau.  
Tổng quát, chúng ta có  
Định lý. Cho R là quan hệ tương đương trên tập A và  
a, b A, Khi đó  
(i) a R b nếu [a]R = [b]R  
(ii) [a]R [b]R nếu [a]R [b]R =   
Chú ý. Các lớp tương đương theo một quan hệ tương  
đương trên A tạo nên một phân họach trên A, nghĩa là chúng  
chia tập A thành các tập con rời nhau.  
3
Lớp tương đương  
Chú ý. Cho {A1, A2, … } là phân họach A thành 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.  
a
A2  
A1  
A3  
b
A4  
A5  
3
Tải về để xem bản đầy đủ
pdf 43 trang Mãnh Khiết 12/01/2024 18040 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 4: Quan hệ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_4_quan_he.pdf