Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boole | TOÁN RỜI RẠC (Discrete Mathematics) Chương 3 Quan hệ (Relations) 1. Một số khái niệm cơ bản Định nghĩa : 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ụ : 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, ),(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 Bình Chánh Long Thành Đồng Nai 1. Một số khái niệm cơ bản Ví dụ : 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ì: | TOÁN RỜI RẠC (Discrete Mathematics) Chương 3 Quan hệ (Relations) 1. Một số khái niệm cơ bản Định nghĩa : 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ụ : 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, ),(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 Bình Chánh Long Thành Đồng Nai 1. Một số khái niệm cơ bản Ví dụ : 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ụ : Trên tập L ={các đường thẳng trong mặt phẳng} Xét quan hệ R ”Song song” được định nghĩa bởi: L1,L2 L , L1 R L2 L1//L2 Ví dụ : Trên tập S là 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ụ : 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 n 1. 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ụ : Cho A={4,5,6},B={1,2,3} và R={(4,1),(4,2),(5,2),(6,3)} 4 1 5 2 6 3 Hoặc 4 5 6 1 2 3 A B R A B 1. Một số khái niệm cơ bản Ví dụ : Cho tập A={2,4,6} và B={a,b,c,d} Có bao nhiêu quan hệ khác nhau có thể có giữa A và B? Có bao nhiêu quan hệ có chứa cặp (2,b)? Có bao nhiêu .
