This Paper
A short summary of this paper
37 Full PDFs related to this paper
Thảo luận trong 'Máy Tính' bắt đầu bởi Social, Thg 12 5, 2020.
Lượt xem: 4,172
Tags:
- bài tập toán rời rạc có lời giải
[Bạn phải Đăng nhập hoặc Đăng ký để trả lời bài viết.]
Tóm tắt nội dung tài liệu
- Chương 3 Quan hệ [Relations] 1.1 Định nghĩa 1.1: Quan hệ R [2 ngôi] giữa 2 tập hợp A và B là một tập con của A× B. Một quan hệ giữa A và A gọi là một quan hệ trên A Nếu [a,b]∈R, ta viết aRb. Ví dụ 1.1: A=Tập các quận-huyện. B=Tập các tỉnh-TP Quan hệ R ≡ “Quận/Huyện thuộc tỉnh” giữa 2 tập A và B là tập của A× B: Chắng hạn: R={[Long Khánh,Đồng Nai],[Gò vấp, Tp. HCM], [Bình chánh, Tp.HCM],[Long Thành, Đồng nai]} Quan hệ này có thể trình bày ở dạng bảng: Quận-Huyện Tỉnh-TP Long Khánh Đồng Nai Gò Vấp Tp.HCM Bình Chánh Tp.HCM Long Thành Đồng Nai Ví dụ 1.2: Cho tập A={2,4,6} và B={a,b,c,d} a] Có bao nhiêu quan hệ khác nhau có thể có giữa A và B? b] Có bao nhiêu quan hệ có chứa cặp [2,b]? c] Có bao nhiêi quan hệ không chứa cặp [1,a] và [3,b]? Giải: 1.2. Định nghĩa 1.2: Một quan hệ R có n ngôi trên các tập A1,A2, …,An là một tập con A1× A2× … × An. Các tập A1, A2,…, An gọi là các miền của R. Ví dụ 1.8: Cho A1: Tập chuyến các tàu , A2: Tập các nhà ga A3={0,1,2,…23}: Giờ trong ngày A4={0,1,2,…59}: Phút trong giờ Xét quan hệ R [4 ngôi] gồm các bộ có dạng [x, y, z, t] cho biết lịch tàu đến tại mỗi ga, với x: số hiệu tàu, y: ga, z: giờ, t: phút. Nếu tàu S1 đến ga Nha trang lúc 13h30, thì: [S1, Nha Trang ,13,30]∈R Nếu tàu S3 đến ga Sài gòn lúc 4h30 thì [S3,Saì Gòn,4,30]∈R Nếu tàu S1 đến ga Tuy Hòa lúc 17h45 thì : [S1,Tuy Hòa,17,45]∈R Nếu tàu LH2 đến ga Bình Định lúc 4h00 thì: [LH2,Bình Định,4,0]∈R Có thể bố trí các phần tử của quan hệ ở dạng bảng:
- Số Tàu Ga Giờ Phút S1 Nha Trang 13 30 S3 Sài Gòn 4 40 S1 Tuy Hòa 17 45 LH2 Bình Định 4 00 Mỗi dòng là một bộ của R 1.3. Định nghĩa 1.3: Cho trước các tập A1, A2, …, An. Ánh xạ chiếu lên các thành phần thứ i1,i2, …, im [m ≤ n] được định nghĩa: πi1 ,i2 ,...,im : A 1 × A 2 × ... × A n → A i1 × A i2 × ... × A im [a 1 × a 2 × ... × an ] π [ai1 × ai2 × ... × aim ] Khi đó, với R là một quan hệ trên A1, A2, …, An, thì : πi1 ,i2 ,...,im [ R ] Gọi là quan hệ chiếu Ví dụ 1.9: Cho A1={Số hiệu các chuyến tàu}; A2={các ga} ; A3={Giờ đến}={0,1,2, …,23}; A4={phút}={0,1,2,…, 59} và quan hệ R=“Lịch tàu” giữa A1, A2, A3. Nếu chỉ muốn biết danh sách các tàu và ga đến [không cần quan tâm đến thời điểm], ta xét quan hệ chiếu: π SoTau ,Ga [R ] πSoTau ,Ga [R] R Số Tàu Ga Giờ Phút S1 Nha Trang 13 30 S3 Sài Gòn 4 40 S1 Tuy Hòa 17 45 Số Tàu Ga LH2 Bình Định 4 00 S1 Nha Trang S3 Sài Gòn S1 Tuy Hòa LH2 Bình Định 2. Một số tính chất của quan hệ: Một quan hệ R trên A có thể có các tính chất sau đây: a] Tính phản xạ [reflexivity]: R phản xạ [reflexive relaiton]⇔ ∀a∈A, aRa Ví dụ 2.1: Cho A={1,2,3,4,5}, R: Một quan hệ trên A. R={[1,1],[2,2],[2,3],[3,3],[3,4], [3,5],[4,2] ,[4,4], [5,1], [5,5]} R: có tính phản xạ.
- A ∆ 5 • • 4 • • 3 • • 2 • • 1 • • 1 2 3 4 5 A b] Tính đối xứng [Symmetry]: R đối xứng [symmetric relation]⇔ ∀a,b ∈A, aRb ⇒ bRa Ví dụ 2.3: A={1,2,3}, xét quan hệ trên A R3 = {[1,1], [3,2], [1,3], [3,1], [2,3]} là quan hệ đối xứng R4 = {[2,1], [1,2], [3,2], [1,3], [3,1], [3,3]} là quan hệ không đối xứng c] Tính phản xứng [Antisymmetry]: R phản xứng [Antisymmetric relation] ⇔∀a,b∈A, [aRb]^[bRa] ⇒ a=b Ví dụ 2.8: Quan hệ “≤ ” trên tập số thực R, có tính phản xứng. Vì: ∀x,y∈R, [x≤ y ] ∧[y ≤ x] ⇒ x= y Ví dụ 2.9: Cho tập A={1,2,3,4} và quan hệ R trên A là: R1={[1,1],[2,3],[2,2],[4,3],[4,4]} R1 không có tính phản xạ, nhưng có tính phản xứng. R2={[1,1],[3,3],[4,4]} : Đối xứng, phản xứng d] Tính bắt cầu [Transitivity]: R có tính bắt cầu [transitive relation] ⇔ ∀x,y∈A [xRy ∧ yRz] ⇒ xRz Ví dụ 2.10: Các quan hệ “=“, “ ≤ ” trên R là các quan hệ có tính bắt cầu Quan hệ ”≠ ” trên R không có tính bắt cầu? Quan hệ “//” trên L là quan hệ có tính bắt cầu. Quan hệ “ ⊥” trên L là quan hệ không có tính bắt cầu. Quan hệ đồng dư modulo n trên Z là quan hệ có tính bắt cầu. d] Tính bắt cầu [Transitive]: R có tính bắt cầu ⇔ ∀x,y∈A [xRy ∧ yRz] ⇒ xRz Ví dụ 2.10: Các quan hệ “=“, “ ≤ ” trên R là các quan hệ có tính bắt cầu Quan hệ ”≠ ” trên R không có tính bắt cầu? Quan hệ “//” trên L là quan hệ có tính bắt cầu. Quan hệ “ ⊥” trên L là quan hệ không có tính bắt cầu. Quan hệ đồng dư modulo n trên Z là quan hệ có tính bắt cầu. Ví dụ 2.5: Xét quan hệ đồng dư modulo n trên z. ∀a,b∈z, a≡ b[mod n] ⇔ a-b chia hết cho n.
- [Nghĩa là: a, b có cùng số dư khi chia cho n] Ta có: ∀a∈z, a-a = 0 chia hết cho n. Hay ∀ a∈z, a≡ a[mod n] Vậy ≡ [mod n] có tính phản xạ. ∀a,b∈z, a≡ b[mod n] ⇔ a-b chia hết cho n ⇒a-b=kn với k∈z ⇒b-a=-kn ⇒b-a chia hết cho n ⇒ b≡ a[mod n] Vậy ≡ [mod n] có tính đối xứng ∀a,b,c∈z, a≡ b[mod n] và b≡ c[mod n] ⇔ a – b = k1n và b-c = k2n với k1, k2∈z ⇒ a-c = [a-b]+[b-c]=[k1+k2]n hay a-c chia hết cho n. Hay a≡ c[mod n] . vậy ≡ [mod n] có tính bắt cầu Ví dụ 2.11: A={Các tỉnh/Thành phố} R: “Láng giềng” [xem ví dụ trước] R: có tính phản xạ, đối xứng, nhưng không có tính phản xứng, và không có tính bắt cầu. Ví dụ 2.12: A={Người}; R:”Quen biết” [xem ví dụ trước] R: Không có tính bắt cầu Ví dụ 2.13: A={Con người}, Xét quan hệ R:”Anh em” được định nghĩa: ∀x,y∈A, xRy ⇔ x có cùng cha mẹ với y R: có tính phản xạ, đối xứng và bắc cầu. 3. Biểu diễn quan hệ bằng ma trận Một quan hệ trên tập hữu hạn A={a1, a2, …, an} có thể biểu diễn bằng ma trận vuông 0-1 cấp n được định nghĩa: RA=[rij] với rij bằng 1 nếu [ai,aj]∈R và bằng 0 nếu [ai,aj]∉R Ví dụ 4.1: Cho A={1,2,3,4,5,6} , quan hệ được định nghĩa: ∀x,y∈A, x R y ⇔ “x cùng tính chẵn lẻ với y” R={[1,1],[1,3], [1,5], [2,2],[2,4], [2,6], [3,1], [3,3], [3,5], [4,2], [4,4], [4,6], [5,1], [5,3], [5,5], [6,2], [6,4], [6,6]} 1 2 3 4 5 6 1 1 0 1 0 1 0 2 0 1 0 1 0 1 3 1 0 1 0 1 0 4 0 1 0 1 0 1 5 1 0 1 0 1 0 6 0 1 0 1 0 1 Ví dụ 4.2: Cho E={a,b,c}, quan hệ bao hàm [⊂] trên tập P[E] . ∀A,B∈ P[E], ARB ⇔ A ⊂ B
- ∅ {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c} φ 1 1 1 1 1 1 1 1 {a} 0 1 0 0 1 1 0 1 {b} 0 0 1 0 1 0 1 1 {c} 0 0 0 1 0 1 1 1 { a ,b } 0 0 0 0 1 0 0 1 { a ,c } 0 0 0 0 0 1 0 1 { b ,c } 0 0 0 0 0 0 1 1 { a ,b , c } 0 0 0 0 0 0 0 1 4. Quan hệ tương đương Định nghĩa 4.1: Quan hệ R trên tập hợp A gọi là quan hệ tương đương nếu thỏa các tính chất: Phản xạ, đối xứng và bắc cầu Ví dụ 4.1: Xét quan hệ R trên tập số nguyên z được định nghĩa: ∀m,n∈ z, mRn ⇔ “m cùng tính chất chẵn lẻ với n” Ta có: ∀m ∈ z , m cùng tính chẵn lẻ với chính nó. Vậy R phản xạ. ∀m,n ∈ z, mRn ⇔“m cùng tính chẳn lẻ với n” ⇒ “n cùng tính chẳn lẻ với m” ⇒ nRm. Vậy R đối xứng. ∀m,n,k∈z mRn ⇔“m cùng tính chẳn lẻ với n” ⇒ m-n=2r [k∈z] nRk ⇔“n cùng tính chẳn lẻ với k” ⇒ m-k=2t [t∈z] ⇒ m-k = [m-n]+[n-k]=2[r+t] ⇒ “m và k vùng tính chẵn lẻ” ⇒ mRk. Có tính bắt cầu . Kết luận: R phản xạ, đối xứng và bắc cầu nên R là quan hệ tương đương trên Z. Ví dụ 4.2: Quan hệ R trên tập S gồm các chuỗi kí tự được định nghĩa: ∀s1,s2∈S, s1Rs2 ⇔ len[s1]=len[s2]. là quan hệ tương đương. Định nghĩa 4.2[lớp tương đương]: Cho R là một quan hệ tương đương trên A và x∈A, lớp tương đương chứa x là tập con của A gồm những phần tử có quan hệ R với x. Nói cách khác: Lớp tương đương chứa x là tập con của A được định nghĩa: [x]R={y∈A/yRx} Ví dụ 4.7: Trên z định nghĩa quan hệ R: ∀a,b∈ z, aRb ⇔ “a cùng tính chẵn lẻ với b” R: là quan hệ tương đương [xem ví dụ trước] Lớp tương đương chứa 2 là: [2]={Các số chẵn} = {…-4, -2, 0, 2, 4,…} Lớp tương đương chứa 1 là: [1] ={Các số lẻ}= {…-5, -3, -1, 1, 3,5,…} Ví dụ 4.8: Quan hệ ≡ [mod 4] trên Z Có 4 lớp tương đương Z4={[0],[1],[2],[3]} [0]={n∈Z/ n chia hết cho 4}={…..-8,-4,0,4,8,…}={4k/k∈Z} [1]={n∈Z/ n chia cho 4 dư 1}={…,-7,-3,1,5,9,…}={4k+1/k∈Z} [2]={n∈Z/ n chia cho 4 dư 2}={…,-6,-2,2,6,10,…}={4k+2/k∈Z} [3]={n∈Z/ n chia cho 4 dư 3}={…,-5,-1,3,7,11,…}={4k+3/k∈Z}
- Tổng quát: Quan hệ ≡ [mod n] trên Z có n lớp tương đương. Zn={[0],[1],…,[n-1]} Định lý 4.1: Cho R là một quan hệ tương đương trên tập A. Ta có: i] ∀x∈A, x∈[x] ii] ∀x,y ∈A, xRy ⇔ [x]=[y] iii] ∀x,y ∈A, [x]∩[y]≠ ∅ ⇒[x]=[y] C/m?: i] R phản xạ nên ∀x∈A, xRx ⇒ x∈[x] [theo định nghĩa] ii] mà R đối xứng nên xRy ⇒ yRx ⇒ y∈[x] Biểu Diễn Các Quan Hệ Biểu diễn quan hệ bằng ma trận: Một quan hệ giữa các tập hữu hạn có thể được biểu diễn bằng một ma trận 0-1. Giả sử R là quan hệ từ A={a1,a2,…,am} đến B ={b1,b2,…,bn}. Quan hệ R này có thể được biểu diễn bằng ma trận MR = [mij], trong đó : - mij = 1 neáu [ai,bj] ∈ R - mij = 0 neáu [ai,bj] ∉ R Thí dụ: Cho A = {1,2,3}, B = {1,2}. Cho quan hệ R từ tập A đến tập B như sau: R={[2,1],[3,1],[3,2]}. Ma trận biểu diễn cho quan hệ R: 0 0 MR= 1 0 1 1 Thí dụ: Cho A = {a1,a2,a3}, B = {b1, b2, b3, b4, b5}. Cho ma trận biểu diễn quan hệ R từ tập A đến tập B như sau: 0 1 0 0 0 MR = 1 0 1 1 0 1 0 1 0 1 => R = {[a1,b2], [a2,b1], [a2,b3], [a2,b4], [a3,b1], [a3,b3], [a3,b5]} Tích Boole: Cho A = [aij] là ma trận 0-1 m x k và B = [bij] là ma trận 0-1 k x n. Khi đó tích boole của A và B, kí hiệu A B, là ma trận m x n có phần tử ở vị trí . i,j là [Cij] vớiCij = [ai1 ∧ b1j] ∨ [ai2 ∧ b2j] ∨ ...∨ [aik ∧ bkj ] Thí dụ : Tìm tích Boole của A và B với :
- 1 0 A= 0 1 B=1 1 0 0 1 1 1 0 [1 ∧ 1] ∨ [0 ∧ 0] [1 ∧ 1] ∨ [0 ∧ 1] [1 ∧ 0] ∨ [0 ∧ 1] A . [0 ∧ 1] ∨ [1 ∧ 0] [0 ∧ 1] ∨ [1 ∧ 1] [0 ∧ 1] ∨ [1 ∧ 1] B= [1 ∧ 1] ∨ [0 ∧ 0] [1 ∧ 1] ∨ [0 ∧ 1] [1 ∧ 0] ∨ [0 ∧ 1] Thí dụ tích Boole tiếp theo: 1∨ 0 1∨ 0 0∨ 0 . A 0∨ 0 0 ∨1 0 ∨1 1∨ 0 1∨ 0 0∨ 0 B= 1 1 0 = 0 1 1 1 1 0 Một số tính chất: 1- M R1∪R2 = M R1 ∨ M R2 2- M R1∩R2 = M R1 ∧ M R2 3- M R1R2 = M R1 .M R 2 Thí dụ: Cho các quan hệ R1 và R2 trên tập A được biểu diễn bởi các ma trận 1 0 1 1 0 1 MR = 1 1 0 0 M R2 = 0 1 1 0 1 0 1 0 0 Thí dụ tiếp theo : 1 1- M R1∪ R2 = M R1 ∨ M R2 0 1 = 1 1 1 1 1 0 1 0 1 2- M R1∩ R2 = M R1 ∧ M R2 = 0 0 0 0 0 0
Page 2
YOMEDIA
Quan hệ R [2 ngôi] giữa 2 tập hợp A và B là một tập con của A´ B. Một quan hệ giữa A và A gọi là một quan hệ trên A. Nếu [a,b]ÎR, ta viết aRb.
15-06-2010 1677 104
Download
Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.