Giáo trình Toán-Tin - Bài 2: Quan hệ

Nội dung text: Giáo trình Toán-Tin - Bài 2: Quan hệ

1. 2 1. Định nghĩa và tính chất 2. Biểu diễn quan hệ 3. Quan hệ tương đương. Đồng dư 4. Quan hệ thứ tự.
2. 3 Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Descartes R  A x B. Chúng ta sẽ 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. 4 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}
4. 5 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)} 1 2 3 4 1 2 3 4
5. Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu: (a, a) R với mọi a 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 6
6. . 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 7
7. 8 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)
8. 9 Định nghĩa. Quan hệ R trên A có tính bắc cầu nếu a A b A 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à “|”trên Z có tính bắc cầu (a b)  (b c) (a c) (a | b)  (b | c) (a | c)
9. 10 1. Ma trận 2. Biểu diễn Quan hệ
10. 11 Cho R là quan hệ từ A = {1,2,3,4} đến B = {u,v,w}: R = {(1,u),(1,v),(2,w),(3,w),(4,u)}. Khi đó R có thể biễu diễn như sau u v w 1 1 1 0 2 0 0 1 3 0 0 1 4 1 0 0 Đây là ma trận cấp 4×3 biễu diễn cho quan hệ R
11. Đị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 m × n MR = [mij] xác định bởi 0 nếu (ai , bj) R mij = 1 nếu (ai , bj) R 1 2 Ví dụ. Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} sao cho a R b 1 0 0 nếu a > b. 2 1 0 Khi đó ma trận biểu diễn của R là 3 1 1 12
12. 13 Biểu diễn Quan hệ 1 nếu (ai , bj) R mij = 0 nếu (ai , bj) R Ví dụ. Cho R là quan hệ từ A = {a1, a2, a3} đến B = {b1, b2, b3, b4, b5} được biễu diễn bởi ma trận b1 b2 b3 b4 b5 a1 0 1 0 0 0 a2 M 1 0 1 1 0 R a3 1 0 1 0 1 Khi đó R gồm các cặp: {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}
13. 14 . Cho 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 của MR đều bằng1: mii = 1 với mọi i u v w u 1 1 0 v 0 1 1 w 0 0 1
14. 15 R là đối xứng nếu MR là đối xứng mij = mji u v w u 1 0 1 v 0 0 1 w 1 1 0
15. 16 R là phản xứng nếu MR thỏa: mij = 0 hoặc mji = 0 nếu i j u v w u 1 0 1 v 0 0 0 w 0 1 1
16. 17 1. Giới thiệu 2. Quan hệ tương đương 3. Biểu diễn số nguyên 4. Lớp tương đương
17. 18 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?
18. Đị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 19
19. Cho a và b là hai số nguyên. A được gọi là ước của b hay b chia hết cho nếu tồn tại số nguyên k sao a = kb 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 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à chúng ta viết a  b (mod m) thay vì aRb 20
20. 21 Định nghĩa. 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}
21. 22 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, }
22. 23 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.
23. Định nghĩa. Quan hệ R trên tập A là quan hệ thứ tự (thứ tự) nếu nó có tính chất phản xạ, phản xứng và bắc cầu. Người ta thường ký hiệu quan hệ thứ tự bởi Cặp (A, ) đựợc gọi là tập sắp thứ tự hay poset Phản xạ: a a Phản xứng: (a b)  (b a) (a = b) Bắc cầu: (a b)  (b c) (a c)
24. Giả sử A1, A2, ,An là n tập hợp. Quan hệ n- ngôi xác định trên các tập A1, A2, An là một tập con của tích Descartes A1xA2xA3x An. Hay R  A1 x A2 x A3 x x An. Ví dụ : A=A1=A2=A3={1, 2, 3, 4} và quan hệ (a, b, c) R A1x A2x A3 sao cho a<b<c thì R={(1,2,3), (1,3,4),(2,3,4)} và (3,1,2) Company Logo