Nội dung

Relations Phần V 1. Định nghĩa và tính chất 2.Biểu diễn quan hệ 3.Quan hệ tương đương. Đồng dư. Phép toán số học trên Zn 4.Quan hệ thứ tự. Hasse Diagram Quan hệ RELATIONS 2 1 1. Definitions 1. Definitions Definition. A quan hệ hai ngôi từ tập A đến tập B là tập con của tích Descartess 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 Example. A = students; B = courses. R = {(a, b) | student a is enrolled in class b} 4 1 1. Definitions 2. Properties of Relations Đị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 Example. 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 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 5 2. Properties of Relations  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 Đị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) Quan hệ“ | ” (“ước số”) trên Z là phản xạ vì mọi số + nguyên a là ước của chính nó . Chú ý. Quan hệ R trên tập A là phản xạ iff nó chứa đường chéo của A × A :  = {(a, a); a  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. 1 2 3 Tuy nhiên nó phản xứng vì (a  b)  (b  a)  (a = b) 4 1 2 3 4 6 7 8 2  Quan hệ“ | ” (“ước số”) trên Z +. không đối xứng 2. Properties of Relations Tuy nhiên nó có tính phản xứng vì (a | b)  (b | a)  (a = b) Chú ý. Quan hê R trên A là đối xứng iff nó đối xứng nhau qua đường chéo  của A × A. Định nghĩa. Quan hệ R trên A có tính bắc cầu( truyền) nếu a  A b  A c  A (a R b)  (b R c)  (a R c) Quan hệ R là phản xứng iff chỉ có các phần tử nằm trên đường chéo là đối xứng qua  của A × A. 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 4 4 3 3 2 2 1 * 1 1 2 3 4 1 2 3 (a  b)  (b  c)  (a  c) * * 4 (a | b)  (b | c)  (a | c) 9 10 Định nghĩa 3. Representing Relations 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 Matrices Representing Relations 1 2 3 4 u 1 0 0 1 v 1 0 0 0 w 0 1 1 0 Dòng và cột tiêu đề có thể bỏ qua nếu không gây hiểu nhầm. Đây là matrận cấp 4×3 biễu diễn cho quan hệ R 11 12 3 Representing Relations mij = Đị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à matrận cấp m × n MR = [mij] xác định bởi mij = b1 b2 b3 b4 b5 0 1 0 0 0  M R  1 0 1 1 0 1 0 1 0 1 1 nếu (ai , bj)  R 1 2 3 1 0 1 1 2 0 0 1 {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)} 13 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 MR đều bằng1: mii = 1 với mọi i u v w v 1 1 0 14 Representing Relations  Cho R là quan hệ trên tập A, khi đó MR là matrận u 1 0 0 a1 a2 a3 Khi đó R gồm các cặp: Representing Relations  0 if (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 matrận 0 nếu (ai , bj)  R 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à 1 if (ai , bj)  R w 0 1 1 u v w 15 với mọi i, j mij = mji u 1 0 1 v 0 0 1 w 1 1 0 16 4 Representing Relations 4.Equivalence Relations R is phản xứng iff MR thỏa: Introduction Equivalence Relations Representation of Integers Equivalence Classes Linear Congruences. mij = 0 or mji = 0 if i  j u v w u 1 0 0 v 0 0 1 w 1 0 1 17 Định nghĩa 18 Quan hệ tương đương 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ạ? Yes R đối xứng? Yes R bắc cầu? Yes Đị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 iff a và b có cùng độ dài. Khi đó R là quan hệ tương đương. Mọi sinh viên Ví dụ. Cho R là quan hệ trên R sao cho aRb iff a – b nguyên. Khi đó R là quan hệ tương đương có cùng họ thuộc cùng một nhóm. 19 20 5 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 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 The relation is clearly reflexive and symmetric. Let a, b, c be integers such that a – b and b – c are both divisible by m, then a – c = a – b + b – c is also 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 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, … } 23 Lớp tương đương Đị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} 22 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ó Theorem. Cho R là quan hệ tương đương trên tập A và a, b  A, Khi đó (i) a R b iff [a]R = [b]R (ii) [a]R  [b]R iff [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. 24 6 Note. 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. Thật vậy với mỗi a, b  A, ta đặt a R b iff có tập con Ai sao cho a, b  Ai . Dễ dàng chứng minh rằng R là quan hệ tương đương trên A và [a]R = Ai iff a  Ai a A2 A1 A4 A3 A5 Example. Cho m là số nguyên dương, khi đó có m lớp đồng dư modulo m là [0]m , [1]m , …, [m – 1]m . Chúng lập thành phân họach của Z thành các tập con rời nhau. Chú ý rằng [0]m = [m]m = [2m]m = … [1]m = [m + 1]m = [2m +1]m = … ………………………………… [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 Zm Zm = {[0]m , [1]m , …, [m – 1]m} b 25 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 ]m + ([b]m + [c ]m) = ([a]m + [b]m) + [c]m [a ]m + [0]m = [a]m [a ]m + [m – a]m = [0]m , Ta viết – [a]m = [m – a]m [a ]m + [b]m = [a + b]m [a ]m [b]m = [a b]m Theorem. Các phép tóan nói trên được định nghĩa tốt, i.e. Nếu a  c (mod m) và b  d (mod m), thì a + b  c + d (mod m) và a b  c d (mod m) Example. 7  2 (mod 5) và11  1 (mod 5) .Ta có 7 + 11  2 + 1 = 3 (mod 5) 7 × 11  2 × 1 = 2 (mod 5) 26 [a ]m [b]m = [b]m [a ]m [a ]m ([b]m [c ]m) = ([a]m [b]m) [c]m [a ]m [1]m = [a]m [a ]m ([b]m + [c ]m) = [a]m [b]m + [a]m [c]m 27 28 7 Example. “ Phương trình bậc nhất” trên Zm [x]m + [a]m = [b]m với [a]m và [b]m cho trước, có nghiệm duy nhất: [x]m = [b ]m – [a]m = [b – a]m Cho m = 26 ,phương trình [x]26 + [3]26 = [b]26 có nghiệm duy nhất với mọi [b]26 trong Z26 . Do đó [x]26  [x]26 + [3]26 là song ánh từ Z26 vào chính nó . Sử dụng song ánh này chúng ta thu được mã hóa Caesar: Mỗi chữ cái tiếng Anh được thay bởi một phần tử của Z26: A  [0]26 , B  [1]26 , …, Z  [25]26 Ta sẽ viết đơn giản: A  0, B  1, …, Z  25 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 [0]26 + [3]26 = [3]26, nghĩa là bởi D. Tương tự B được mã hóa bởi chữ cái tương ứng với [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 nghĩa là bởi C. Bức thư “MEET YOU IN THE PARK” được mã như sau MEET YOU IN THE PAR K 12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10 15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13 P HHW B R X L Q WKH SD U N 29 Trước hết chúng ta chọn a khả nghịch trong Z26 i.e. tồn tại a’ trong Z26 sao cho Để giải mã, ta dùng ánh xạ ngược: [x]26  [x]26 – [3]26 = [x – 3]26 P H H W tương ứng với 15 7 7 22 Lấy ảnh qua ánh xạ ngược: Ta thu đươc chữ đã đươc mã là 12 4 4 19 30 [a]26 [a’ ]26 = [a a’ ]26 = [1]26 Chúng ta viết [a’ ]26 = [a]26–1 nếu tồn tại . Nghiệm của phương trình [a]26 [x]26 = [c]26 MEET là Mã hóa như trên còn quá đơn giản,dễ dàng bị bẻ khóa. Chúng ta có thể tổng quát mã Caesar bằng cách sử dụng á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 31 [x]26 = [a]26–1 [c]26 = [a’c]26 Chúng ta cũng nói nghiệm của phương trình a x  c (mod 26) là x  a’c (mod 26) 32 8 Á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 Bây giờ M được mã hóa như sau [12]26  [7 12 + 3]26 = [87]26 = [9]26 nghĩa là được mã hóa bởi I. Ngược lại I được giải mã như sau [9]26  [15  (9 – 3) ]26 = [90]26 = [12]26 Introduction Lexicographic Order Hasse Diagrams Maximal and Minimal Elements Upper Bounds and Lower Bounds Topological Sorting nghĩa là tương ứng với M. 33 Định nghĩa 34 Định nghĩa Example. Cho R là quan hệ trên tập số thực: a R b iff a  b Hỏi: Is R reflexive? Yes Is R transitive? Yes Is R symmetric? No Is R antisymmetric? Definition. 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 Reflexive: a  a Antisymmetric: (a  b)  (b  a)  (a = b) Transitive: (a  b)  (b  c)  (a  c) Yes 35 36 9 Định nghĩa Definition. A relation R on a set A is a partial order if it is reflexive, antisymmetric and transitive. Antisymmetric? a | b means b = ka, b | a means a = jb. Then a = jka It follows that j = k = 1, i.e. a = b Example.Quan hệ ước số “ | ”trên tập số nguyên dương là quan hệ thứ tự, i.e. (Z+, | ) là poset Yes, x | x since x = 1  x Reflexive? Transitive? Yes? Not a poset. Example. Is (Z, | ) a poset? Yes? Antisymmetric? a | b means b = ka, b | c means c = jb. Then c = j(ka) = jka: a | c No 3|-3, and -3|3, but 3  -3. 37 Ex. Is (2S,  ), where 2S the set of all subsets of S, a poset? Reflexive? Transitive? Antisymmetric? Yes, A poset. Yes, A  A, A 38 Definition. Các phần tử a và b của poset (S,  ) gọi là so sánh được nếu a  b or b  a . Trái lại thì ta nói a và b không so sánh được. 2S 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. A  B, B  C. Does that mean A  C? Ta cũng nói rằng  là thứ tự toàn phần hay thứ tự tuyến tính trên S Example. Quan hệ “ ” trên tập số nguyên dương là thứ tự toàn phần. Yes A  B, B  A. Does that mean A =B? Yes 39 Example. Quan hệ ước số “ | ”trên tập hợp số nguyên 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. 40 10