Bài giảng Quan hệ công chúng - Phần 5: Quan hệ Relations

Nội dung text: Bài giảng Quan hệ công chúng - Phần 5: Quan hệ Relations

1. Relations Phần V 1. Định nghĩa và tính chất 2.Biểu diễn quan hệ Quan hệ 3.Quan hệ tương đương. Đồng dư. Phép tốn số học trên Zn RELATIONS 4.Quan hệ thứ tự. Hasse Diagram 1 2 1. Definitions 1. Definitions Definition. A quan hệ hai ngơi từ tập A đến tập B là tập con Example. A = students; B = courses. của tích Descartess R  A x B. R = {(a, b) | student a is enrolled in class 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 1
2. 1. Definitions 2. Properties of Relations Example. Cho A = {1, 2, 3, 4}, và Định nghĩa. Quan hệ R trên A được gọi là phản xạ R = {(a, b) | a là ước của b} nếu: Khi đĩ (a, a) R với mọi a A R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} 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)} 1 2 3 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 1 2 3 4 5 6 . Quan hệ trên Z phản xạ vì a a với mọi a Z 2. Properties of Relations . Quan hệ > trên Z khơng phản xạ vì 1 > 1 Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu: .Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số a A b A (a R b) (b R a) nguyên a là ước của chính nĩ . Quan hệ R được gọi là phản xứng nếu Chú ý. Quan hệ R trên tập A là phản xạ iff nĩ chứa  a A b A (a R b)  (b R a) (a = b) đường chéo của A × A : Ví dụ. = {(a, a); a A}  Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập 1 A = {1, 2, 3, 4}là đối xứng 2  Quan hệ trên Z khơng đối xứng. 3 Tuy nhiên nĩ phản xứng vì 4 (a b)  (b a) (a = b) 1 2 3 4 7 8 2
3. . Quan hệ“ | ” (“ước số”) trên Z +. khơng đối xứng Tuy nhiên nĩ cĩ tính phản xứng vì 2. Properties of Relations Định nghĩa. Quan hệ R trên A cĩ tính bắc cầu( truyền) (a | b)  (b | a) (a = b) nếu Chú ý. Quan hê R trên A là đối xứng iff nĩ đối xứng nhau a A b A c A (a R b)  (b R c) (a R c) qua đường chéo của A × A. Quan hệ R là phản xứng iff chỉ cĩ các phần tử nằm trên Ví dụ. đường chéo là đối xứng qua của A × A. 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. 4 4 * Quan hệ và “|”trên Z cĩ tính bắc cầu 3 3 (a b)  (b c) (a c) 2 2 * * 1 1 (a | b)  (b | c) (a | c) 1 2 3 4 1 2 3 4 9 10 3. Representing Relations Định nghĩa ChoR 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 Introduction Dịng và cột Matrices u v w tiêu đề cĩ Representing Relations 1 1 1 0 2 0 0 1 thể bỏ qua nếu 3 0 0 1 khơng gây hiểu nhầm. 4 1 0 0 Đây là matrận cấp 4×3 biễu diễn cho quan hệ R 11 12 3
4. Representing Relations 1 if (ai , bj) R mij = 0 if (ai , bj) R Định nghĩa. Cho R là quan hệ từ A = {a1, a2, , am} đến B = {b1, b2, , bn}. Matrận biểu diễn của R là Ví dụ. Cho R là quan hệ từ A = {a1, a2, a3} đến matrận cấp m × n MR = [mij] xác định bởi B = {b1, b2, b3, b4, b5} được biễu diễn bởi matrận b b b b b 0 nếu (a , b ) R 1 2 3 4 5 m = i j ij 0 1 0 0 0 a1 1 nếu (ai , bj) R M 1 0 1 1 0 a R 2 a 1 2 1 0 1 0 1 3 Ví dụ. Nếu R là quan hệ từ 1 0 0 A = {1, 2, 3} đến B = {1, 2} sao Khi đĩ R gồm các cặp: cho a R b nếu a > b. 2 1 0 {(a , b ), (a , b ), (a , b ), (a , b ), (a , b ), (a , b ), (a , b )} Khi đĩ ma trận biểu diễn của R là 3 1 1 1 2 2 1 2 3 2 4 3 1 3 3 3 5 13 14 Representing Relations Representing Relations . Cho R là quan hệ trên tập A, khi đĩ MR là matrận R là đối xứng iff MR is đối xứng vuơng. . R là phản xạ iff tất cả các phần tử trên đường chéo của mij = mji với mọi i, j MR đều bằng1: mii = 1 với mọi i u v w u 1 1 0 u v w v 0 1 1 u 1 0 1 w 0 0 1 v 0 0 1 w 1 1 0 15 16 4
5. Representing Relations 4.Equivalence Relations R is phản xứng iff MR thỏa: Introduction Equivalence Relations m = 0 or m = 0 if i j ij ji Representation of Integers Equivalence Classes u v w Linear Congruences. u 1 0 1 v 0 0 0 w 0 1 1 17 18 Định nghĩa Quan hệ tương đương  Ví dụ: Định nghĩa. Quan hệ R trên tập A được gọi là tương Cho S = {sinh viên của lớp}, gọi đương nếu nĩ cĩ tính chất phản xạ, đối xứng và bắc R = {(a,b): a cĩ cùng họ với b} cầu : Hỏi Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb iff a và b cĩ cùng độ dài. Khi đĩ R là quan hệ tương đương. R phản xạ? Yes Mọi sinh viên cĩ cùng họ Ví dụ. Cho R là quan hệ trên R sao cho aRb iff a – b R đối xứng? Yes thuộc cùng một nguyên. Khi đĩ R là quan hệ tương đương nhĩm R bắc cầu? Yes . 19 20 5
6. Recall that if a and b are integers, then a is said to be divisible by b, or a is a multiple of b, or b is a divisor of Lớp tương đương a, or b divides a if there exists an integer k such that a = kb Example. Let m be a positive integer and R the relation on Z such that aRb if and only if a – b is divisible by m, then R is an equivalence relation Đị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 The relation is clearly reflexive and symmetric. bởi [a]R hoặc [a] là tập Let a, b, c be integers such that a – b and b – c are [a] = {b A| b R a} both divisible by m, then a – c = a – b + b – c is also R divisible by m. Therefore R is transitive This relation is called the congruence modulo m and we write a  b (mod m) instead of aRb 21 22 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ĩ 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 Theorem. Cho R là quan hệ tương đương trên tập A số nguyên a chia hết cho 8. Do đĩ và a, b A, Khi đĩ (i) a R b iff [a]R = [b]R [0]8 ={ , – 16, – 8, 0, 8, 16, } Tương tự (ii) [a]R [b]R iff [a]R  [b]R =  [1]8 = {a | a chia 8 dư 1} = { , – 15, – 7, 1, 9, 17, } 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 24 6
7. Example. Cho m là số nguyên dương, khi đĩ cĩ m lớp Note. Cho {A1, A2, } là phân họach A thành các tập đồng dư modulo m là [0]m , [1]m , , [m – 1]m . con khơng rỗng, rời nhau . Khi đĩ cĩ duy nhất quan hệ Chúng lập thành phân họach của Z thành các tập con tương đương trên A sao cho mỗi Ai là một lớp tương đương. rời nhau. Chú ý rằng Thật vậy với mỗi a, b A, ta đặt a R b iff cĩ tập con Ai [0]m = [m]m = [2m]m = sao cho a, b Ai . [1]m = [m + 1]m = [2m +1]m = Dễ dàng chứng minh rằng R là quan hệ tương đương trên A và [a] = A iff a A R i i [m – 1]m = [2m – 1]m = [3m – 1]m = Mỗi lớp tương đương này được gọi là số nguyên modulo m .Tập hợp các số nguyên modulo m được ký hiệu bởi Z a m A A2 Z = {[0] , [1] , , [m – 1] } 1 A3 m m m m A b 4 A5 25 26 5 Linear Congruences Note. Các phép tĩan “ + ” và “ × “ trên Zm cĩ các tính chất như các phép tĩan trên Z Example. Cho m là số nguyên dương, ta định nghĩa hai phép tĩan “ + ” và “ × “ trên Zm như sau [a ]m + [b]m = [b]m + [a]m [a ] + ([b] + [c ] ) = ([a] + [b] ) + [c] [a ]m + [b]m = [a + b]m m m m m m m [a ] + [0] = [a] [a ]m [b]m = [a b]m m m m [a ]m + [m – a]m = [0]m , Theorem. Các phép tĩan nĩi trên được định nghĩa tốt, Ta viết – [a] = [m – a] i.e. Nếu a  c (mod m) và b  d (mod m), thì m m a + b  c + d (mod m) và a b  c d (mod m) [a ]m [b]m = [b]m [a ]m [a ] ([b] [c ] ) = ([a] [b] ) [c] Example. 7  2 (mod 5) và11  1 (mod 5) .Ta cĩ m m m m m m [a ] [1] = [a] 7 + 11  2 + 1 = 3 (mod 5) m m m 7 × 11  2 × 1 = 2 (mod 5) [a ]m ([b]m + [c ]m) = [a]m [b]m + [a]m [c]m 27 28 7
8. Example. “ Phương trình bậc nhất” trên Zm Mỗi chữ cái sẽ được mã hĩa bằng cách cộng thêm 3 . Chẳng hạn A được mã hĩa bởi chữ cái tương ứng với [x] + [a] = [b] m m m [0] + [3] = [3] , nghĩa là bởi D. với [a] và [b] cho trước, cĩ nghiệm duy nhất: 26 26 26 m m Tương tự B được mã hĩa bởi chữ cái tương ứng với [x]m = [b ]m – [a]m = [b – a]m [1]26 + [3]26 = [4]26, nghĩa là bởi E, cuối cùng Z đựơc mã hĩa bởi chữ cái tương ứng với [25]26 + [3]26 = [2]26 Cho m = 26 ,phương trình [x]26 + [3]26 = [b]26 cĩ nghĩa là bởi C. nghiệm duy nhất với mọi [b] trong Z . 26 26 Bức thư “MEET YOU IN THE PARK” được mã như Do đĩ [x] [x] + [3] là song ánh từ Z vào chính 26 26 26 26 sau nĩ. M E E T Y O U I N T H E P A R K Sử dụng song ánh này chúng ta thu được mã hĩa Caesar: 12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10 Mỗi chữ cái tiếng Anh được thay bởi một phần tử 1 17 23 11 16 22 10 7 18 3 20 13 của Z26: A [0]26 , B [1]26 , , Z [25]26 15 7 7 22 Ta sẽ viết đơn giản: A 0, B 1, , Z 25 P H H W B R X L Q W K H S D U N 29 30 Trước hết chúng ta chọn a khả nghịch trong Z26 i.e. tồn Để giải mã, ta dùng ánh xạ ngược: tại a’ trong Z26 sao cho [x]26 [x]26 – [3]26 = [x – 3]26 [a]26 [a’ ]26 = [a a’ ]26 = [1]26 P H H W tương ứng với 15 7 7 22 –1 Chúng ta viết [a’ ]26 = [a]26 nếu tồn tại . Nghiệm của phương trình Lấy ảnh qua ánh xạ ngược: 12 4 4 19 [a]26 [x]26 = [c]26 Ta thu đươc chữ đã đươc mã –1 là M E E T là [x]26 = [a]26 [c]26 = [a’c]26 Mã hĩa như trên cịn quá đơn giản,dễ dàng bị bẻ khĩa. Chúng ta cũng nĩi nghiệm của phương trình Chúng ta cĩ thể tổng quát mã Caesar bằng cách sử dụng a x  c (mod 26) ánh xạ f : [x]26 [ax + b]26 trong đĩ a và b là các hằng số được chọn sao cho f là song ánh là x  a’c (mod 26) 31 32 8
9. Ánh xạ ngược của f xác định bởi 6. Partial Orderings [x]26 [a’(x – b)]26 Example. Cho a = 7 và b = 3, khi đĩ nghịch đảo của [7]26 là [15]26 vì [7]26 [15]26 = [105]26 = [1]26 Introduction Bây giờ M được mã hĩa như sau Lexicographic Order Hasse Diagrams [12]26 [7 12 + 3]26 = [87]26 = [9]26 Maximal and Minimal Elements nghĩa là được mã hĩa bởi I. Ngược lại I được giải mã như sau Upper Bounds and Lower Bounds Topological Sorting [9]26 [15  (9 – 3) ]26 = [90]26 = [12]26 nghĩa là tương ứng với M. 33 34 Định nghĩa Định nghĩa Example. Cho R là quan hệ trên tập số thực: Definition. Quan hệ R trên tập A là quan hệ thứ tự( thứ tự) nếu a R b iff a b nĩ cĩ tính chất phản xạ, phản xứng và bắc cầu. Hỏi: 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 Yes Is R reflexive? Reflexive: a a Yes Is R transitive? Antisymmetric: (a b)  (b a) (a = b) Is R symmetric? No Is R antisymmetric? Yes Transitive: (a b)  (b c) (a c) 35 36 9
10. Định nghĩa Definition. A relation R on a set A is a partial order if it is reflexive, antisymmetric and transitive. Antisymmetric? Yes? Example.Quan hệ ước số “ | ”trên tập số nguyên dương a | b means b = ka, b | a means a = jb. là quan hệ thứ tự, i.e. (Z+, | ) là poset Then a = jka It follows that j = k = 1, i.e. a = b Reflexive? Yes, x | x since x = 1  x Not a poset. Transitive? Yes? Example. Is (Z, | ) a poset? Antisymmetric? 3|-3, and -3|3, a | b means b = ka, b | c means c = jb. No Then c = j(ka) = jka: a | c but 3 -3. 37 38 Ex. Is (2S,  ), where 2S the set of all subsets of S, a poset? Definition. Các phần tử a và b của poset (S, ) gọi Yes, A poset. là so sánh được nếu a b or b a . Reflexive? Trái lại thì ta nĩi a và b khơng so sánh được. Yes, A  A, A 2S Transitive? Cho (S, ), nếu hai phần tử tùy ý của S đều so sánh A  B, B  C. Does that mean được với nhau thì ta gọi nĩ là tập sắp thứ tự tồn phần. A  C? Ta cũng nĩi rằng là thứ tự tồn phần hay thứ tự tuyến Yes Antisymmetric? tính trên S Example. Quan hệ “ ” trên tập số nguyên dương là thứ A  B, B  A. Does that mean tự tồn phần. A =B? Example. Quan hệ ước số “ | ”trên tập hợp số nguyên Yes dương khơng là thứ tự tịan phần, vì các số 5 và 7 là khơng so sánh được. 39 40 10
11. Thứ tự tự điển Thứ tự tự điển Ex. Trên tập các chuỗi bit cĩ độ dài n ta cĩ thể định Cho (A, ) và (B, ’) là hai tập sắp thứ tự tịan phần. nghĩa thứ tự như sau: Ta định nghĩa thứ tự trên A B như sau : a1a2 an b1b2 bn (a1 , b1) (a2, b2) iff iff ai bi,  i. a1 < a2 or (a1 = a2 and b1 ’ b2) Với thứ tự này thì các chuỗi 0110 và 1000 là khơng Dễ dàng thấy rằng đây là thứ tự tịan phần trên A B so sánh được với nhau .Chúng ta khơng thể nĩi chuỗi Ta gọi nĩ là thứ tự tự điển . nào lớn hơn. Chú ý rằng nếu A và B được sắp tốt bởi và ’ ,tương Trong tin học chúng ta thường sử dụng thứ tự tịan phần ứng thì A B cũng được sắp tốt bởi thứ tự trên các chuỗi bit . Đĩ là thứ tự tự điển. Chúng ta cũng cĩ thể mở rộng định nghĩa trên cho tích Descartess của hữu hạn tập sắp thứ tự tịan phần. 41 42 Thứ tự tự điển Thứ tự tự điển Cho  là một tập hữu hạn (ta gọi là bảng chữ cái). Giả sử là thứ tự tịan phần trên , khi đĩ ta cĩ thể định Tập hợp các chuỗi trên , ký hiệu là * ,xác định nghĩa thứ tự tồn phần trên * như sau. bởi Cho s = a1 a2 am và t = b1 b2 bn là hai chuỗi trên *   *, trong đĩ  là chuỗi rỗng. Khi đĩ s t iff  Nếu x , và w *, thì wx *, trong đĩ wx là kết nối w với x. . Hoặc ai = bi đối với 1 i m ,tức là t = a1 a2 am bm +1 bm +2 bn Example. Chẳng hạn  = {a, b, c}. Thế thì . Hoặc tồn tại k < m sao cho * = {, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc,  ai = bi với 1 i k và aaa, aab, }  ak+1 < bk+1 , nghĩa là s = a1 a2 ak ak +1 ak +2 am t = a1 a2 ak bk +1 bk +2 bn 43 44 11
12.  Chúng ta cĩ thể kiểm tra là thứ tự tịan phần trên * Ta gọi nĩ là thứ tự từ điển trên * Example. Nếu  = {0, 1} với 0 < 1, thì là thứ tự tịan Example. Nếu  là bảng chữ cái tiếng Anh với thứ tự: a < phần trên tập tất cả các chuỗi bit * . 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. For example Ta cĩ  discreet discrete d i s c r e e t  0110 10 e t d i s c r e t e  0110 01100 discreet discreetness d i s c r e e t d i s c r e e t n e s s 45 46 Hasse Diagrams Hasse Diagrams Mỗi poset cĩ thể biễu diễn bởi đồ thị đặc biệt ta gọi . Ta định nghĩa Hasse diagram của poset (S, ) là đồ thị: là biểu đồ Hasse Mỗi phần tử của S được biễu diễn bởi một điểm trên Để định nghĩa biểu đồ Hasse chúng ta cần các khái niệm mặt phẳng . phần tử trội và trội trực tiếp.  Nếu b là trội trực tiếp của a thì vẽ một cung đi từ Definition. Phần tử b trong poset (S, ) đựoc gọi là a đến b . phần tử trội của phần tử a trong S if a b b d Chúng ta cũng nĩi rằng a là được trội bởi b .Phần tử b a b d, a c được gọi là trội trực tiếp của a nếu b là trội của a, và khơng tồn tại trội c sao cho a e a c b, a c b c 47 48 12
13. Hasse Diagrams Example. Biểu đồ Hasse của P({a,b,c}) và biểu đồ Hasse của các chuỗi bit độ dài 3 with thứ tự tự Ex. Biểu đồ Hasse của poset ({1,2,3,4}, ) cĩ thể điển vẽ như sau {a,b,c} 111 4 {b,c} {a,b} {a,c} 011 3 Note. Chúng ta khơng vẽ 110 101 mũi tên với qui ước mỗi {a} 2 {b} {c} cung đều đi từ dưới lên 100 010 001 1 trên  000 They look similar !!! 49 50 ầ ử ố ạ ầ ử ố ể Note. Trong một poset S hữu hạn, phần tử tối đại và Ph n t t i đ i và ph n t t i ti u. phần tử tối tiểu luơn luơn tồn tại. Xét poset cĩ biểu đồ Hasse như dưới đây:  Thật vậy, chúng ta xuất phát từ điêm bất kỳ a0 S.  Mỗi đỉnh màu đỏ là tối đại. Nếu a khơng tối tiểu, khi đĩ tồn tại a a ,  Mỗi đỉnh màu xanh là tối tiểu. 0 1 0 tiếp tục như vậy cho đến khi tìm được phần tử tối tiểu .  Khơng cĩ cung nào xuất phát từ điểm tối đại.  Khơng cĩ cung nào kết thúc ở điểm tối tiểu. Phần tử tối đại tìm được bằng phương pháp tương tự. a0 a1 a 51 2 52 13
14. Example. Tìm phần tử tối đại, tối tiểu của poset Example. Tìm phần tử tối đại, tối tiểu của poset các ({2, 4, 5, 10, 12, 20, 25}, | ) ? chuỗi bit độ dài 3? Solution. Từ biểu đồ Hasse , chúng ta thấy rằng 12, 20, Solution. Từ biểu đồ Hasse , chúng ta thấy rằng 111 là 25 là các phần tử tối đại , cịn 2, 5 là các phần tử tối tiểu phần tử tối đại duy nhất và 000 là phần tử tối tiểu duy nhất . 111 Như vậy phần tử tối đại, tối tiểu của poset cĩ thể khơng 111 là phần tử lớn nhất duy nhất. và 000 là phần tử nhỏ nhất 110 101 011 12 20 theo nghĩa: 10 4 25 000 abc 111 100 010 001 với mọi chuỗi abc 5 2 000 53 54 Chúng ta cĩ định lý Chặn trên , chặn dưới Theorem. Trong một poset hữu hạn, nếu chỉ cĩ duy nhất một phần tử tối đại thì đĩ là phần tử lớn nhất . Definition. Cho (S, ) là poset và A  S . Phần tử Tương tự cho phần tử nhỏ nhất. chặn trên của A là phần tử x S (cĩ thể thuộc A hoặc khơng) sao cho  a A, a x. Proof. Giả sử g là phần tử tối đại duy m nhất. g Phần tử chặn dưới của A là phần tử x S sao cho  a A, x a Lấy a là phần tử bất kỳ, khi đĩ tồn tại Ex. Phần tử chận trên của phần tử tối đại m sao cho a b {g,j} là a. a m a c d Vì g là duy nhất nên m = g , Tại sao khơng phải là b? do đĩ ta cĩ a g l e f j Như vậy g là phần tử lĩn nhất. g h i Chúng minh tương tự cho phần tử nhỏ nhất l 55 56 14
15. Definition. Cho (S, ) là poset và A  S. Chặn trên Chặn trên nhỏ nhất (nếu cĩ ) của A = {a, b} đựơc ký nhỏ nhất của A là phần tử chặn trên x của A sao hiệu bởi a  b cho mọi chặn trên y của A, ta đều cĩ y  x Chặn dưới lớn nhất của A là phần tử chặn dưới x Chặn dưới lớn nhất (nếu cĩ) của A = {a, b} đựoc ký của A sao cho mọi chặn dưới y của A,ta cĩ hiệu bởi a  b y x Ex. Chặn trên nhỏ nhất của {i,j} là d Ex. Chặn dưới chung LN a b của{g,j} là gì? a b Ex. i  j = d c d c d e f j e f j Ex. b  c = f g h i g h i 57 58 Topological Sorting Topological Sorting Consider the problem of getting dressed. Recall that every finite non-empty poset has at least one Precedence constraints are modeled by a poset in which a b minimal element a . if and only if you must put on a before b. 1 shoes belt jacket shoes belt jacket In what order E.g. shirt is will you get socks jeans swter jwlry a minimal socks jeans swter jwlry dressed while element respecting constraints? uwear shirt uwear shirt In other words, we will find a new total order so that a  Now the new set after we remove a1 is still a poset. is a lower bound of b if a b 59 60 15
16. Topological Sorting This process continues until all elements are removed We obtain a new order of the elements satisfying the given constraints:  Let a2 be a minimal of the new poset. a1, a2, , am shoes belt jacket shoes belt jacket E.g. underwear socks jeans swter jwlry socks jeans swter jwlry is a new minimal element uwear shirt uwear shirt  Now every element of this new poset cannot be a The arrangement of the given poset in the new total order a1, a2, compatible with the old proper lower bound of a1 and a2 in the original poset order is called the Topological sorting 61 62 Bài tập Bài tập 1. Khảo sát các tính chất của các quan hệ R sau. Xét 2 . Khảo sát tính chất của các quan hệ sau a) x, y Z, x y xy; xem quan hệ R nào là quan hệ tương đương. Tìm các R b) x, y R, xRy x = y hay x < y + 1. lớp tương đương cho các quan hệ tương đương tương c) x, y R, xRy x = y hay x < y - 1. ứng. d) (x, y); (z, t) Z2, (x, y) (z, t) x z hay (x = z và y a) x, y R, xRy x2 + 2x = y2 + 2y; t); e) (x, y); (z, t) Z2, (x, y) (z, t) x < z hay (x = z và y b) x, y R, xRy x2 + 2x y2 + 2y; t); c) x, y R, xRy x3 – x2y – 3x = y3 – xy2 – 3y; d) x, y R+, xRy x3 – x2y – x = y3 – xy2 – y. 63 64 16
17. Bài tập Bài tập 3 . Xét quan hệ R trên Z định bởi: 4 . Xét tập mẫu tự A = {a, b, c} với n x, y Z, xRy n Z, x = y2 a < b < c và : a) Chứng minh R là một quan hệ tương đương. s1 = ccbac b)Trong số các lớp tương đương 1,2,3,4cĩ bao nhiêu s = abccaa lớp phân biệt ? 2 c) Câu hỏi tương tự như câu hỏi b) cho các lớp. theo thứ tự từ điển. Hỏi cĩ bao nhiêu chuỗi ký tự s gồm 6 ký tự thỏa s2 s s1? 6,7,21,24,25,35,42,48 65 66 Bài tập Bài tập 5. ĐỀ THI NĂM 2006 6 . Đề 2007.Cĩ bao nhiêu dãy bit cĩ độ dài 15  Xét thứ tự “”trên tập P(S)các tập con của tập sao cho 00001 s 011, trong đĩ “ ” là thứ tự S ={1,2,3,4,5}trong đĩ AB nếu A là tập con từ điển. của B.  Tìm một thứ tự tồn phần “ ≤ ”trên P(S) sao cho với A, B trong P(S), nếu AB thì A≤ B. Tổng quát hố cho trường hợp S cĩ n phần tử. 67 68 17