Quan hệ

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:38

Thêm vào BST

Báo xấu

73
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tích đề các: − Tích đề-các của hai tập A&B là tập: A × B = {(a, b) / a ∈ A, b ∈ B} -− Tích đề-các của các tập A1, A2, …, An là tập: A1 × A2 × ... × An = {(a1 ,

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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: A × B = {(a, b) / a ∈ A, b ∈ B} -− Tích đề-các của các tập A1, A2, …, An là tập: A1 × A2 × ... × An = {(a1 , a2 ,...an ) / ai ∈ Ai }
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
(a, b) ∉ R, a R b
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 đó:
1 khi a i Rb j m ij =  0 khi a i Rb j
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:
1 3 7 9 1 1 0 0 0 M R = 21 1 1 1 0 28 1 0 1 0
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 ∈ x 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 = k giả 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²-9x vậ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)