Chương quan hệ

I-Quan hệ hai ngôi: 1.Định nghĩa: 1.1-Tích đề các:  Tích đề-các của hai tập A&B là tập: - Tích đề-các của các tập A1, A2, …, An là tập: Ví dụ: Cho 2 tập: A = {1; 2; 3}, B = {a, b, c} AB = {(1; a), (1; b),(1,c), (2; a), (2; b), (2; c), (3; a), (3; b), (3; c),} BA = {(a; 1), (a; 2), (a; 3), (b; 1), (b; 2), (b; 3), (c; 1), (c; 2), (c; 3),} BA = {(a; 1), (a; 2), (a; 3), (b; 1), (b; 2), (b; 3), (c; 1), (c; 2), (c; 3),} 1.2 –Định nghĩa: Quan hệ hai ngôi R giữa tập A và tập B là tập con của tích đề-các AB. + Nếu A = B ta nói R là quan hệ (hai ngôi) trên A Ví dụ Xét quan hệ hai ngôi R trên N như sau: “ a, b  N, aRb  (a + b) là số chẵn” Hãy kiểm tra các tính phản xạ, đối xứng, bắc cầu, phản đối xứng của quan hệ R c) Ma trận biểu diễn quan hệ: Cho 2 tập A = {a1, a2, …, am}, B = {b1, b2, …, bn} Ma trận biểu diễn quan hệ giữa A&B, kí hiệu: MR = (mij)mxn Sắp xếp các phần tử của A&B theo một trật tự nào đó lần lượt trên một hàng ngang & hàng dọc, khi đó: Ví dụ: Cho A = {1; 3; 7; 9}, B = {1; 21; 28} Xét quan hệ hai ngôi R giữa A&B sau: aRb  “a là ước của b” Một ma trận biểu diễn quan hệ trên: II-Quan Hệ Tương Đương I.Quan hệ tương đương: 1.ĐỊNH NGHĨA: Quan hệ R trên A được gọi là quan hệ tương đương nếu có đủ 3 tính chất : phản xạ, đối xứng và bắt cầu. Ví dụ 1: các quan hệ “=, ≡, // “ là quan hệ tương đương. Ví dụ 2:các quan hệ “ “ không phải là quan hệ tương đương vì không có tính đối xứng. Ví dụ 3: trên tập hợp các mệnh đề thì quan hệ “tương đương logic” là một quan hệ tương đương. Ví dụ 4: trên tập A = { 1,2,3 } thì R = {(1,1),(2,2),(3,3)} là quan hệ tương đương. R còn là quan hệ tương đương có ít phần tử nhất. T = {(1,1),(2,2),(3,3),(1,2),(2,1)} là quan hệ tương đương. Dễ nhận thấy: + (1,1),(2,2),(3,3) có tính phản xạ + (1,2),(2,1) có tính đối xứng + (1,2),(2,1),(2,2) có tính bắc cầu => T là quan hệ tương đương H = {(1,1),(2,2),(3,3),(2,3)} không là quan hệ tương đương vì không đối xứng. K = {(1,1),(2,1),(1,2),(2,1) } không là quan hệ tương đương vì không có tính phản xạ. Ví dụ 5:trên tập số nguyên Z cho quan hệ hai ngôi f.Xác định như sau:x ϵ Z , y ϵ Z, (x;y) ϵ f 7.x^2 - 9.x = 7y^2 - 9y.f có phải là quan hệ tương đương không? + 7x² - 9x = 7x² - 9x với mọi x ϵ Z => (x,x) ϵ f; vậy f có tính phản xạ (1*) + 7x²-9x ϵ Z với mọi x ϵ Z, mà trong Z có tính bắc cầu với quan hệ '='tức là m = n và n = k (m,n,k ϵ Z) => m = kgiả sử (x,y) ϵ f và (y,z) ϵ f: ta có: 7x² - 9x = 7y² - 9y và 7y² - 9y = 7z² - 9z=> 7x² - 9x = 7z² - 9z => (x,z) ϵ f => f có tính bắc cầu (2*) +7x²-9x và 7y²-9y đều thuộc Z (với x,y ϵ Z)nên từ 7x²-9x = 7y²-9y => 7y²-9y = 7x²-9xvậy: nếu (x,y) ϵ f thì (y,x) ϵ f => f có tính đối xứng (3*)f có đủ 3 tính chất (1*), (2*), (3*) nên là quan hệ tương đương trong Z II. Lớp Tương đương: Cho R là quan hệ tương đương trên A. tập con của A gồm các phần tử tương đương với x A gọi là lớp tương đương chứa x. thường kí hiệu tương đương x là [x] hay . Theo đó, Ví Dụ 1: trên tập A = {1,2,3} thì T = {(1,1),(2,2),(3,3),(1,2),(2,1) } là quan hệ tương đương. Vì: + (1,1),(2,2),(3,3) có tính phản xạ + (1,2),(2,1) có tính đối xứng + (1,2),(2,1),(2,2) có tính bắc cầu => T là quan hệ tương đương Ta có: [1] = {1,2} = [2] [3] = {3,3} => Có 2 lớp tương đương Ví dụ 2: Trên tập Z các số nguyên xét quan hệ =(mod3) như sau: x,y∈Z, x=y(mod3) ⇔ x và y có cùng số dư khi chia cho 3. Dễ chứng minh được đây là quan hệ tương đương trên Z. Ta được: [0] = {….,-6,-3,0,3,6,….} [1] = {…..,-4.-1,1,4,……} [2] = {…...,-5,-2,2,5,……} Tính chất: Giả sử R là một quan hệ tương đương trên A. Khi ấy (i). ∀x∈A ⇒ x∈[x] (ii). ∀x,y∈A, xRy ⇔ [x] =[y] (iii). Hai lớp tương đương [x], [y] sao cho [x]∩[y]≠∅ thì trùng nhau. III. Sự phân hoạch thành lớp tương đương: Cho quan hệ R tương đương trên A. Ta có: 1) Các lớp tương đương của R sẽ lập nên một phân hoạch của A 2) Với một phân hoạch,sẽ tồn tại một quan hệ tương đương R tương ứng 3) Hai phần tử có quan hệ tương đương sẽ cùng thuộc một lớp tương đương,hai phần tử không quan hệ tương đương sẽ thuộc hai lớp tương đương khác nhau 4) Trong mỗi lớp tương đương,ta có thể chọn bất kỳ phần tử nào làm đại diện cho lớp Ví Dụ : Cho quan hệ S={ Việt Nam, Mỹ, Ý, Nhật, Áo, Úc, Nga, Libi, Lào, Anh, Peru, Maroc, Chile,Iran, Bỉ } Với x,y ϵ S:x R y x,y thuộc cùng một châu lục (R:quan hệ tương đương) [Việt Nam]={x ϵ S / x R Việt Nam}={Nhật, Lào, Việt Nam, Iran} [Mỹ]={Chile, Peru, Mỹ} [Ý]={Nga, Áo, Anh, Mỹ, Ý} [Úc]={Úc} [Libi]={Libi, Maroc} I/ Biểu đồ hasse: 1/Giới thiệu: Quan hệ thứ tự: quan hệ R trên tập A là quan hệ thứ tự nếu nó có tính chất phản xạ , phản xứng và bắc cầu. Ký hiệu: ≺ Cặp (A, ≺) được gọi là tập sắp xế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). Vd: quan hệ ước số trên tập số nguyên dương là quan hệ thứ tự , nghĩa là (Z+, |) là poset. -Tính phản xạ: có, x|x vì x=1*x -Tính phản xứng: có, a|b nghĩa là b=k.a(1) b|a nghĩa là a=j.b(2) thay 2 vào 1 ta có b=k.j.b đúng khi k=j=1 -Tính bắc cầu: a|b  b=k.a(1) b|c c=j.b(2) thay 1 vào 2 ta có c= j.k.a a|c Vd2 : (Z,|) là poset? Không phải vì không theo tính chất phản xứng : 3|-3 -3|3 nhưng 3!=-3 Ví dụ: Un= {aN: a|n} với quan hệ R: xRy  x|y U12={ 1,2,3,4,6,12} R={{1,1},{1,2} ,{1,3} ,{1,4} ,{1,6} ,{1,12}, {2,2},{2,4},{2,6},{2,12},{3,3},{3,6}, {3,12},{4,4},{4,12},(6,6}{6,12}, {12,12}} Trội, trội trực tiếp: Xét một tập hợp có thứ tự (X, ) và x, y là 2 phần tử bất kỳ của X. Khi đó ta nói: y trội x hay x được trội bởi y nếu x ≤ y y là trội trực tiếp của x nếu y ≠ x, y trội x và không tồn tại một trội z của x sao cho x < z < y Quan hệ thứ tự - chận dưới Cho (X,  ) là một tập hợp có thứ tự, và A  X Ta gọi một phần tử x  X là một chận dưới của tập hợp A nếu và chỉ nếu với mọi a  A ta có : x  a Chận dưới lớn nhất (nếu có), tức là phần tử lớn nhất trong tập hợp tất cả những chận dưới của A được ký hiệu là inf (A) Quan hệ thứ tự - chận trên: Cho (X,  ) là một tập hợp có thứ tự, và A  X Ta gọi một phần tử x  X là một chận trên của tập hợp A nếu và chỉ nếu với mọi a  A ta có : a  x Chận trên nhỏ nhất (nếu có), tức là phần tử nhỏ nhất trong tập hợp tất cả những chận trên, của A được ký hiệu là sup (A) Thứ tự tốt: Một tập hợp có thứ tự được gọi là có thứ tự tốt (hay được sắp tốt) nếu và chỉ nếu mọi tập con khác rỗng đều có phần tử nhỏ nhất. Tập hợp có thứ tự (N,  ) là một tập hợp được sắp tốt. Tập hợp có thứ tự (Z,  ) không phải là một tập hợp được sắp tốt vì Z không có phần tử nhỏ nhất. 2/Biểu đồ hasse: Định nghĩa: Mỗi poset có thể biễu diễn bởi đồ thị đặc biệt ta gọi là biểu đồ Hasse. Để định nghĩa biểu đồ Hasse chúng ta cần các khái niệm phần tử trội và trội trực tiếp. Phẩn tử trội:Phần tử b trong poset (S,) được gọi là phần tử trội của phần tử a trong S nếu a ≺b. Chúng ta cũng nói rằng a là được trội bởi b . Phần tử b đượ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 ≺c ≺b. a!=c!=b. Ta định nghĩa Biểu đồ Hasse của poset (S, ≺) là 1 đồ thị: -Mỗi phần tử của S được biễu diễn bởi một điểm trên mặt phẳng . -Nếu b là trội trực tiếp của a thì vẽ một cung đi từ a đến b VD: Biểu đồ Hasse của poset ({1,2,3,4}, <) có thể vẽ như sau 1____2_____3_____4( với quy ước mỗi cung đi từ trái qua phải) -Phần tử tối tiểu và phần tử tối đại : Xét tập hợp có thứ tự (A, ≺). + Phần tử tối tiểu: a là phần tử tối tiểu của A nếu như trong A không tồn tại x sao cho a!=x ≺ a. + Phần tử tối đại : b là phẩn tử tối đại của A nếu như trong A không tồn tại x sao cho b≺x !=b Như vậy, ta có thể tóm tắt lại như sau: -Trong biểu đồ Hasse không có cung nào xuất phát từ đỉnh tối đại và không có cung nào kết thúc ở đỉnh tối tiểu. - Trong 1 poset S hữu hạn, phần tử tối đại và phần tử tối tiểu luôn luôn tồn tại. -Phần Tử Min, Max:xét tập (A, ≺) +Phần tử Min :a là phần tử nhỏ nhất của tập A (ký hiệu a=min(A)), nếu mọi x thuộc A ta có:a ≺x. +Phần tử Max: b là phần tử lớn nhất của tập A (ký hiệu b=max(A)), nếu mọi x thuộc A ta có:x≺b. VD: trong tập hợp thứ tự (A,<=), với A={x Z/x*x<100). Ta có min(A)=-9, max(A)=9 -Phần tử min và max có thể không tồn tại. vd : trong tập (R,<=) -Phần tử min và max nếu tồn tại là duy nhất. - Nếu (A, ≺ ) là tập hợp hữu hạn được sắp thứ tự toàn phần thì min(A) và max(A) đều tồn tại. Vídụ:Tìm phần tử tối đại, tối tiểu,min, max của poset ({2, 4, 5, 10, 12, 20, 25}, | ) ? Điểm cực đại :12,20,25 Điểm cực tiểu: 2,5 Min, max: không tồn tại. Giải bài tập