›
›

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

pdf 39 trang hapham 70
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 5: Quan hệ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_5_quan_he.pdf

Nội dung text: Bài giảng Toán rời rạc - Chương 5: Quan hệ

  1. TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 5 QUAN HỆ lvluyen@hcmus.edu.vn ∼luyen/trr FB: fb.com/trr2015 Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 1/39
  2. Nội dung Chương 5. QUAN HỆ 1. Quan hệ hai ngôi 2. Quan hệ tương đương 3. Quan hệ thứ tự lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 2/39
  3. 5.1. Quan hệ hai ngôi 1 Định nghĩa 2 Các tính chất của quan hệ lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 3/39
  4. 5.1.1. Định nghĩa Định nghĩa. Một quan hệ hai ngôi từ tập A đến tập B là tập con R của tích Descartes A × B. Quan hệ từ A đến chính nó được gọi là quan hệ hai ngôi (hay quan hệ ) trên A. Ví dụ. Cho A = {0, 1, 2} và B = {a, b}. Khi đó R = {(0, a), (0, b), (1, a), (2, b)} là một quan hệ từ A vào B. Quan hệ này được mô tả bằng lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 4/39
  5. Ví dụ. Cho A = {1, 2, 3, 4}, và R = {(a, b) | a là ước của b}. Khi đó R là một quan hệ trên A. Hãy tìm R? Giải. R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}. Ví dụ. Cho A = {1, 2, 3, 4}. Hỏi ta có thể xây dựng được bao nhiêu qua hệ trên A? Giải. Vì |A| = 4 nên |A × A| = 16. Do mỗi quan hệ trên A là một tập con của |A × A| nên số quan hệ trên A là 216. Ví dụ.(tự làm) Cho A = {1, 2, 3}. Hãy tìm số quan hệ hai ngôi trên A a) chứa (1, 1). b) có đúng 5 phần tử. c) có ít nhất 7 phần tử. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 5/39
  6. Định nghĩa. Cho R là quan hệ trên A và x, y ∈ A. Ta nói: i) x quan hệ R với y nếu (x, y) ∈ R, ký hiệu xRy. ii) x không quan hệ R với y nếu (x, y) ∈/ R , ký hiệu xRy. Ví dụ. Cho A = {1, 2, 3} và R = {(1, 1), (1, 2), (2, 3), (1, 3)} là một quan hệ trên A. Khi đó 1R1, 1R2, 2R3, 1R3, 2 R 1, 2 R 2, Ví dụ. Cho A = {1, 2, 3, 4, 5, 6, 7, 8}. Một quan hệ R trên A được xác định như sau: xRy ⇔ x − y chia hết cho 4. Ta có: 1R5, 5R1, 7R7, 1 R 2, 3 R 6, lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 6/39
  7. 5.1.2. Các tính chất của Quan hệ Định nghĩa. Cho R là quan hệ trên A. Ta nói i) R phản xạ ⇔ ∀x ∈ A, xRx. ii) R đối xứng ⇔ ∀x, y ∈ A, xRy → yRx. iii) R phản xứng ⇔ ∀x, y ∈ A, xRy ∧ yRx → x = y. iv) R bắc cầu (hay còn gọi là truyền) ⇔ ∀x, y, z ∈ A, xRy ∧ yRz → xRz. Nhận xét. Cho R là quan hệ trên A. Khi đó: i) R không phản xạ ⇔ ∃x ∈ A, x R x. ii) R không đối xứng ⇔ ∃x, y ∈ A, xRy ∧ y R x. iii) R không phản xứng ⇔ ∃x, y ∈ A, xRy ∧ yRx ∧ x 6= y. iv) R không bắc cầu ⇔ ∃x, y, z ∈ A, xRy ∧ yRz ∧ x R z. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 7/39
  8. Ví dụ. Trên tập hợp số nguyên, ta xét những quan hệ sau: R1 = {(a, b) | a ≤ b}, R2 = {(a, b) | a > b}, R3 = {(a, b) | a = b hay a = −b}, R4 = {(a, b) | a = b + 1}, R5 = {(a, b) | a + b ≤ 3}. Hỏi những quan hệ trên có tính chất nào? Ví dụ. Trên tập hợp A = {1, 2, 3, 4}, ta xét những quan hệ sau: R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}, R2 = {(1, 1), (1, 2), (2, 1)}, R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}, R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}, Hỏi những quan hệ trên có tính chất nào? lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 8/39
  9. Ví dụ.(tự làm) Cho S = {1, 2, 3} và quan hệ hai ngôi R = {(2, 2), (1, 3), (3, 3), (1, 2), (1, 1), (2, 1)} trên S. Xét các tính chất phản xạ, đối xứng, phản xứng và bắc cầu của quan hệ R? Ví dụ.(tự làm) Cho S = {1, 2, 3} và R = {(1, 1); (1, 2); (2, 3); (3, 2); (3, 3)} là một quan hệ hai ngôi trên S. Xét các tính chất phản xạ, đối xứng, phản xứng và bắc cầu của R. Ví dụ.(tự làm) Cho S = {1, 2, 3}. Đặt ∀x, y ∈ S, xRy ⇔ 3(x + y) = xy + 9. Liệt kê tất cả (x, y) ∈ S2 thỏa xRy và xét 4 tính chất phản xạ, đối xứng, phản xứng và bắc cầu của R. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 9/39
  10. Ví dụ. Cho R là quan hệ trên Z, được xác định bởi ∀x, y ∈ Z, xRy ⇔ x + y chẵn. Xác định các tính chất của R. Giải. (i) ∀x ∈ Z, vì x + x = 2x chẵn nên xRx. Do đó R phản xạ. (ii) ∀x, y ∈ Z, nếu xRy thì x + y chẵn nên y + x cũng chẵn, nghĩa là yRx. Do đó R đối xứng. (iii) Ta có 1R3 và 3R1, nhưng 1 6= 3. Do đó R không phản xứng. (iv) ∀x, y, z ∈ Z, nếu xRy và yRz thì x + y và y + z chẵn. Mà x + z = (x + y) + (y + z) − 2y, nên x + z cũng là số chẵn, nghĩa là xRz. Do đó R bắc cầu. Vậy R thỏa mãn các tính chất phản xạ, đối xứng và bắc cầu, nhưng không phản xứng. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 10/39
  11. 5.2. Biểu diễn quan hệ bằng ma trận Ví dụ. 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 Dòng và cột tiêu đề có thể bỏ qua nếu không gây hiểu nhầm. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 11/39
  12. Đị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 Ví dụ. Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} sao cho aRb nếu a > b. Khi đó ma trận biểu diễn của R là  0 0  MR =  1 0  1 1 lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 12/39
  13. 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  0 1 0 0 0  MR =  1 0 1 1 0  1 0 1 0 1 Tìm quan hệ R? Đáp án. R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)} Ví dụ.(tự làm) Trên tập A = {1, 2, 3, 4}, cho quan hệ R được định nghĩa như sau xRy ⇔ x chia hết cho y. Tìm ma trận biểu diễn R? lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 13/39
  14. Ví dụ.(tự làm) Trên tập hợp A = {a, b, c}, quan hệ R có ma trận biểu diễn là:  1 0 1  MR =  0 1 1  . 0 0 1 Hãy tìm R? Hỏi. Cho R là một quan hệ trên tập hữu hạn A. Ta có thể nhận xét gì về ma trận biểu diển của R nếu R có tính phản xạ R có tính đối xứng R có tính phản xứng lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 14/39
  15. 5.2. Quan hệ tương đương 1 Định nghĩa 2 Lớp tương đương 3 Quan hệ đồng dư modulo trên Z lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 15/39
  16. 5.3.1. Định nghĩa Ví dụ. Cho Ω = tập hợp sinh viên của lớp này, gọi R = {(a, b) | a cùng họ với b}. Hỏi R có những tính chất nào? Giải. Phản xạ, đối xứng và bắc cầu. Định nghĩa. Cho R là quan hệ trên tập hợp A. Ta nói R là quan hệ tương đương trên A nếu R thỏa mãn các tính chất phản xạ, đối xứng và bắc cầu. Ví dụ. Cho R là quan hệ trên Z, được xác định bởi ∀x, y ∈ Z, xRy ⇔ x + y chẵn. Khi đó R là quan hệ tương đương. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 16/39
  17. 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 S là quan hệ trên tập số thực sao cho aSb nếu a − b là số nguyên. Khi đó S là quan hệ tương đương. Ví dụ.(tự làm) Trên tập hợp số thực, ta xét quan hệ S được định nghĩa như sau: xSy ⇔ x2 + x = y2 + y. Chứng minh S là quan hệ tương đương. Ví dụ.(tự làm) Cho m là một số nguyên dương và quan hệ R trên Z xác định bởi: ∀x, y ∈ Z, xRy ⇔ x − y chia hết cho m. Chứng minh R là quan hệ tương đương. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 17/39
  18. 5.3.2. Lớp tương đương Định nghĩa. Cho R là quan hệ tương đương trên A và x thuộc A. Khi đó, tập hợp tất cả các phần tử trong A có quan hệ với x được gọi là lớp tương đương của x, ký hiệu bởi x hoặc [x]. Vậy x = {y ∈ A | yRx}. Ví dụ.(tự làm) Trên tập hợp A = {−2, −1, 1, 2, 3, 4, 5}. Ta xét quan hệ hai ngôi R như sau: x R y ⇔ x + 3y chẵn. a) Chứng minh R là quan hệ tương đương. b) Tìm các lớp tương đương [1], [2] và [4]. Mệnh đề. Cho R là quan hệ tương đương trên tập hợp A. Khi đó: i) ∀x, y ∈ A, xRy ⇔ x = y. ii) ∀x, y ∈ A, nếu x 6= y thì x ∩ y = ∅. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 18/39
  19. Nhận xét. Dựa vào Mệnh đề trên ta có nếu R là một quan hệ tương đương trên tập hợp A thì ta có thể phân tích A thành hợp của các lớp tương đương rời nhau theo quan hệ R. Sự phân tích đó được gọi là sự phân hoạch tập hợp A thành các lớp tương đương. Ví dụ. Cho Ω = tập hợp sinh viên của lớp này, gọi R = {(a, b) | a cùng họ với b}. Khi đó R là quan hệ tương đương và khi đó Ω được phân hoạch thành các lớp tương đương, mỗi lớp tương đương là tập hợp những bạn sinh viên cùng họ. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 19/39
  20. 5.3.3. Quan hệ đồng dư trên Z Định nghĩa. Cho n là một số nguyên dương và quan hệ R trên Z xác định bởi: ∀x, y ∈ Z, xRy ⇔ x ≡ y (mod n) Khi đó R là một quan hệ tương đương trên Z. Quan hệ này được gọi là quan hệ đồng dư theo modulo n. Với mỗi x ∈ Z, ta có x = {x + kn | k ∈ Z} = {x, x ± n, x ± 2n, x ± 3n, . . .}. Ta đặt Zn = {0, 1, 2, , n − 1}. Ví dụ. Trong Z12, ta có −7 = 5; 28 = 4. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 20/39
  21. Định nghĩa. Trên Zn ta định nghĩa phép toán +, −, × như sau: x + y = x + y. x − y = x − y. x × y = x × y. Nhận xét. Với mọi x ∈ Zn và với mọi m nguyên, ta có m.x = mx. Ví dụ. Trên Z8, ta có −3 = 5; 7 + 6 = 5; 7 × 6 = 2; 5 × 4 = 4; 5 × 7 + 6 = 1 Ví dụ. Trong Z10, tìm nghiệm của phương trình x + 9 = 5 Đáp án. x = 6. Ví dụ. Tìm x biết x − 8 ≡ 11 (mod 14)? Đáp án. Ta có x ≡ 5 (mod 14). Suy ra x = 14k + 5 với k ∈ Z. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 21/39
  22. Phần tử khả nghịch trong Zn Định nghĩa. Phần tử x trong Zn được gọi là khả nghịch nếu tồn tại y ∈ Zn sao cho x × y = 1. Khi đó y được gọi là nghịch đảo của x, ký hiệu y = x−1. Ví dụ. Trong Z9 ta có: 3 không khả nghịch, vì 3 × 3 = 0. 4 khả nghịch và 4−1 = 7, vì 4 × 7 = 1. Mệnh đề. Cho x ∈ Zn, ta có x khả nghịch khi và chỉ khi (x; n) = 1. Ví dụ. Trong Z10, ta có 7 khả nghịch vì (7; 10) = 1 5 khả nghịch vì (5; 10) = 2 lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 22/39
  23. Kiểm tra tính khả nghịch và tìm nghịch đảo của x ∈ Zn Tìm d là ước số chung lớn nhất của x và n. Nếu d = 1 thì dùng thuật chia Euclide để biểu diễn 1 = xp + nq. Khi đó x × p = 1 nên x khả nghịch và x−1 = p. Nếu d > 1 thì x không khả nghịch. Ví dụ.(tự làm) Trong Z9, tìm tất cả các phần tử khả nghịch và tìm phần tử nghịch đảo tương ứng. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 23/39
  24. Ví dụ. Trong Z8, tìm nghiệm của phương trình 3 × x + 7 = 4 (∗) Giải. Phương trình (∗) tương đương 3 × x = 4 − 7 = −3 = 5. Vì (3; 8) = 1 nên 3 khả nghịch. Bằng thuật chia Euclide ta tìm được 3−1 = 3. Suy ra x = 3−1 × 5 = 3 × 5 = 15 = 7. Ví dụ. Giải phương trình 5x − 9 ≡ 7 (mod 12) (∗∗) Giải. Phương trình (∗∗) tương đương với phương trình 5x − 9 = 7 trong Z12 ⇔ 5 × x = 4 Ta có 5−1 = 5. Suy ra x = 5−1 × 4 = 5 × 4 = 20 = 8. Như vậy x = 12k + 8 với k ∈ Z. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 24/39
  25. 5.3. Quan hệ thứ tự 1 Định nghĩa 2 Phần tử trội 3 Biểu đồ Hasse 4 Phần tử cực trị 5 Sắp xếp tôpô lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 25/39
  26. 3.3.1. Định nghĩa ∗ Ví dụ. Trên tập hợp N , ta xét quan hệ xRy ⇔ x chia hết cho y Hỏi R có những tính chất nào? Đáp án. Phản xa, phản xứng, bắc cầu. Định nghĩa. Quan hệ R trên tập hợp A được gọi là quan hệ thứ tự nếu nó thỏa mãn các tính chất phản xạ, phản xứng và bắc cầu. Khi đó (A, R) được gọi là một tập thứ tự. Nếu R là một thứ tự trên tập hợp A thì ta ký hiệu a  b thay cho aRb, và ký hiệu a ≺ b thay cho a  b nhưng a 6= b. Ví dụ. a) (N, ≤) là tập thứ tự. Ta có 1  2, 4 3, 5  5, , ∗ b) Xét (N , | ). Ta có 2  6, 2 3, 3 2, lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 26/39
  27. 3 2 3 2 Ví dụ.(tự làm) ∀x, y ∈ S = R, đặt xRy ⇔ x − x − x = y − y − y. a) Chứng minh R là một quan hệ tương đương trên S. b) Tìm tất cả u, v, w ∈ S sao cho uR0, vR(−1) và wR2. R có phải là một quan hệ thứ tự trên S không ? Ví dụ.(tự làm) ∀x, y ∈ T = {−8, −7, −3, −2, 2, 5, 6, 9}, đặt xRy ⇔ x | y (nghĩa là x là một ước số của y). a) Tìm tất cả x, y ∈ T sao cho xRy. b) Tại sao R không phải là một quan hệ tương đương và cũng không phải là một quan hệ thứ tự trên T ? lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 27/39
  28. 5.3.2. Phần tử trội Định nghĩa. Cho (A, ) là một tập thứ tự và x, y ∈ A. Khi đó: 1 Nếu x  y thì ta nói y là trội của x hoặc x được trội bởi y. 2 Nếu x ≺ y thì ta nói y là trội thật sự của x. 3 Nếu x ≺ y và không tồn tại z ∈ A sao cho x ≺ z ≺ y thì ta nói y là trội trực tiếp của x. Ví dụ. Cho A = {1, 2, 3, 4, 5, 6}. Khi đó: a) Với (A, ≤), ta có các trội của 2 là 2, 3, 4, 5, 6; trội trực tiếp của 2 là 3. b) Với (A, | ), ta có các trội của 2 là 2, 4, 6; trội trực tiếp của 2 là 4 và 6. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 28/39
  29. Biểu đồ Hasse Định nghĩa. Biểu đồ Hasse của tập thứ tự (A, ) là một đồ thị có hướng Các đỉnh tương ứng với các phần tử của A. Các cung có hướng nối từ x đến y nếu y là trội trực tiếp của x. Ví dụ. Ta có biểu đồ Hasse cho tập thứ tự ({1, 2, 3, 4, 6}, | ) là Ví dụ.(tự làm) Cho tập hợp A = {2, 3, 6, 7, 14, 21, 42}. Vẽ biểu đồ . Hasse của tập thứ tự (A, | ) và (A, . ) lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 29/39
  30. Thứ tự toàn phần Định nghĩa. Các phần tử a và b của tập thứ tự (S, ) gọi là so sánh được nếu a  b hay b  a. 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 thứ tự toàn phần. Ta cũng nói rằng  là thứ tự toàn phần trên S. Ngược lại, nó được gọi là tập thứ tự bộ phận (hay còn gọi thứ tự bán phần) Ví dụ. Quan hệ “≤” trên tập số nguyên dương 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 lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 30/39
  31. 5.3.3. Phần tử cực trị Định nghĩa. Cho (A, ) là một tập thứ tự và m ∈ A. Ta nói i) m là phần tử tối đại của A nếu ∀x ∈ A, m  x → m = x. ii) m là phần tử tối tiểu của A nếu ∀x ∈ A, x  m → x = m. iii) m là phần tử lớn nhất của A nếu ∀x ∈ A, x  m. iv) m là phần tử nhỏ nhất của A nếu ∀x ∈ A, m  x. Ví dụ. Từ biểu đồ Hasse của tập thứ tự ({1, 2, 3, 4, 6}, | ) Ta có • 4 và 6 là các phần tử tối đại • 1 là phần tử tối tiểu và cũng là phần tử nhỏ nhất • không tồn tại phần tử lớn nhất. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 31/39
  32. Ví dụ. Tìm phần tử tối đại, tối tiểu, lớn nhất, nhỏ nhất của tập thứ tự ({2, 4, 5, 10, 12, 20, 25}, |) Giải. Phần tử tối đại: 12, 20, 25 Phần tử tối tiểu: 2, 5 Không có phần tử lớn nhất và nhỏ nhất Ví dụ.(tự làm) Cho S = {2, 3, 4, 5, 6, 14, 15, 30, 45}. Đặt ∀x, y ∈ S, xRy ⇔ ∃ k nguyên lẻ, x = ky. Chứng minh R là một quan hệ thứ tự trên S. Vẽ sơ đồ Hasse cho (S, R) và tìm các phần tử tối tiểu, tối đại. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 32/39
  33. Ví dụ.(tự làm) Cho S = {2, 4, 5, 10, 12, 15, 20, 30, 90, 180} và quan hệ thứ tự R trên S như sau : ∀x, y ∈ S, xRy ⇔ x | y (x là ước số của y). Vẽ sơ đồ Hasse và tìm các phần tử nhỏ nhất, lớn nhất, tối tiểu, tối đại của (S, R), nếu có. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 33/39
  34. 5.3.4. Thứ tự từ điển Định nghĩa. Cho Σ là một tập hữu hạn (ta gọi là bảng chữ cái). Tập hợp các chuỗi trên Σ, ký hiệu là Σ∗, xác định bởi λ ∈ Σ∗, trong đó λ là chuỗi rỗng. Nếu x ∈ Σ, và w ∈ Σ∗, thì wx ∈ Σ∗, trong đó wx là kết nối w với x. Ví dụ. Cho Σ = {a, b, c}, khi đó Σ∗ = {λ, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, . . .} Ví dụ. Cho Σ = {0, 1}, khi đó Σ∗ = {λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, } lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 34/39
  35. Định nghĩa. Giả sử  là thứ tự toàn phần trên Σ, khi đó ta có thể định nghĩa thứ tự toàn phần  trên Σ∗ như sau: ∗ Cho s = a1a2 . . . am và t = b1b2 . . . bn là hai chuỗi trên Σ . Khi đó s ≺ t nếu - m < n và ai = bi đối với 1 ≤ i ≤ m, tức là t = a1a2 . . . ambm+1bm+2 . . . bn - hoặc tồn tại k < m sao cho ai = bi với 1 ≤ i ≤ k và ak+1 ≺ bk+1, nghĩa là s = a1a2 . . . akak+1ak+2 . . . am t = a1a2 . . . akbk+1bk+2 . . . bn Chúng ta có thể kiểm tra  là thứ tự toàn phần trên Σ∗. Ta gọi nó là thứ tự từ điển trên Σ∗. lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 35/39
  36. Ví dụ. Nếu Σ là bảng chữ cái tiếng Anh với thứ tự: a ≺ b ≺ ≺ z, thì thứ tự nói trên là thứ tự thông thường giữa các từ trong từ điển. Ví dụ love ≺ lovely; castle ≺ cat Ví dụ. Nếu Σ = {0, 1} với 0 ≺ 1 thì thì  là thứ tự toàn phần trên tập tất cả các chuỗi bit. Ví dụ 10101 ≺ 10101000; 10101 ≺ 11 lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 36/39
  37. 5.3.5. Sắp xếp tôpô Chú ý. Mọi tập thứ tự hữu hạn đều có phần tử tối tiểu shoes belt jacket Ví dụ shirt là socks trousers cravat watch phần tử tối tiểu uwear shirt Sau khi loại bỏ phần tử shirt (a1) tập còn lại vẫn là tập thứ tự 37/39
  38. Gọi a2 là phần tử tối tiểu của tập thứ tự mới. shoes belt jacket underwear socks trousers cravat watch phần tử tối tiểu mới shirt Tiếp tục quá trình này cho đến khi không còn phần tử nào nữa. Và cuối cùng chúng ta sẽ có một sự sắp xếp a1, a2, a3 , am 38/39
  39. shoes belt jacket socks trousers Cravat watch uwear shirt Đây được gọi là sắp xếp tôpô 39/39