TOÁN RỜI RẠC - CHƯƠNG 3

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-TPQuan 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:
Nội dung trích xuất từ tài liệu:
TOÁN RỜI RẠC - CHƯƠNG 3 TOÁN RỜI RẠC (Discrete Mathematics) Chương 3 Quan hệ (Relations) 1. Một số khái niệm cơ bản1.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:1. Một số khái niệm cơ bản 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 Nai1. Một số khái niệm cơ bảnVí dụ 1.2: Cho 2 tập hợp A={các sinh viên} và B={các môn học}, Chẳng hạn: A={sv1, sv2, sv3, sv4} B={Toán RR, LTM1, PPsố, Triết} Xét quan hệ R ≡ ” Đăng ký môn học” giữa A và B được định nghĩa: ∀x∈Ay∈B, xRy ⇔ “sinh viên x có đăng ký môn học y”  Nếu sv2 đăng ký môn PPSố, thì: (sv2, PPSố) ∈ R  Nếu sv1 đăng ký môn Toán RR, thì: (sv1,toán RR) ∈ R  Nếu sv1 không đăng ký môn Triết, thì: (sv1,Triết) ∉ R  ,…1. Một số khái niệm cơ bản Ví dụ 1.3: Trên tập L ={các đường thẳng trong mặt phằng} Xét quan hệ R≡ ”Song song” được nghĩa bởi: ∀L1,L2∈ L , L RL 1 2 ⇔L1//L2 Ví dụ 1.4: Trên tập Slà tập các đa giác trong mặt phẳng. Quan hệ R≡ ”đồng dạng” được định nghĩa như sau: ∀a,b∈ S, a R b ⇔ “a và b đồng dạng” Ví dụ 1.5: Trên tập số nguyên z, cho trước số n>1. Xét quan hệ: a R b ⇔ a – b chia hết cho n ⇔ a và b có cùng số dư khi chia cho n1. Một số khái niệm cơ bản Quan hệ này gọi là quan hệ đồng dư modulo n. Kí hiệu a≡ b (mod n). Ví dụ như: 1≡ 8(mod 7); 3≡ 11(mod 8),… Có thể biễu diễn quan hệ 2 ngôi bằng biểu đồ: Ví dụ 1.6: Cho A={4,5,6},B={1,2,3} và R={(4,1),(4,2),(5,2),(6,3)} B A B 3 R • Hoặc 4• •1 2 • • 5• •2 1 • 6• •3 4 5 6 A1. Một số khái niệm cơ bảnVí dụ 1.7: 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êu quan hệ không chứa cặp (1,a) và (3,b)?Giải:a) Ta có |A× B|=|A|× |B|=3× 4=12 Sồ tập con khác nhau của A× B là 212. Mà mỗi tập con của A× B là một quan hệ. vậy số quan hệ khác nhau có thể có giữa A và B là 212.b) Số quan hệ có chứa cập (2,b)?1. Một số khái niệm cơ bản b) Gọi X là một quan hệ thoả điều điện đã cho (nghĩa là X có chưá ít nhất là 1 cặp (2,b)). X có dạng: X = {(2,b)} ∪ Y với Y ⊂ A × B {(2,b)} Có 1 cách chọn tập {(2,b)} Mỗi cách chọn {(2,b)} có 2|A × B{(2,b)}| = 211. Theo nguyên lý nhân, số quan hệ X có thể tìm được là 1× 211=211.c) Tính số quan hệ giữa A và B không chứa (1,a) và (3,b)? (bài tập)d) Có bào nhiêu quan hệ có đúng 5 cặp (a,b) với a∈A và b∈B? (bài tập): Bằng số tổ hợp 212 chọn 5 = …..1. Một số khái niệm cơ bản (tt)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 (3 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 gia, 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)∈RMột số khái niệm cơ bản (tt) 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ố Ga Giờ Phút Mỗidònglà Tàu mộtbộcủaR S1 Nha Trang 13 30 S3 Sài gòn 4 40 S1 Tuy hòa 17 45 LH2 Bình Định 4 001. Một số khái niệm cơ bản (tt)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 : A1 × A 2 × ... × A n → A i1 × A i2 × ... × A im ...