Bài giảng Toán ứng dụng trong tin học - Chương 1: Quan hệ & Suy luận toán học - Nguyễn Thanh Chuyên

GV. Nguyễn Thanh Chuyên Email: ntchuyen@gmail.com QUAN HỆ & SUY LUẬN TOÁN HỌCChương 1Bài giảng TOÁN ỨNG DỤNG TRONG TIN HỌC (Tài liệu cập nhật – 2009)1.1 Tập hợp và Quan hệ1.2 Suy luận toán học 1.3 Quan hệ hai ngôi 1- Khái niệm về tập hợp2- Quan hệ giữa các tập hợp3- Các phép toán về tập hợp 4- Quy nạp toán học5- Định nghĩa bằng đệ quy6- Các thuật toán đệ quy7- Tính đúng đắn của chương trình8- Quan hệ tương đương9- Quan hệ thứ tựChương 1: QUAN HỆ - SUY LUẬN TOÁN HỌCTOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC1.1- TẬP HỢP - QUAN HỆ 1- Khái niệm về Tập hợp+ TẬP HỢP; một số các phần tử cùng tính chất Tập hợp các SV lớp A, trường B Tập hợp các số nguyên Tập hợp các điểm trên một đường tròn+ Tập hợp A , B, C --- các phần tử x, y, z... phần tử x thuộc tập hợp A, x không thuộc tập hợp B ABXYZCC là tập hợp rỗng TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 1.1- TẬP HỢP - QUAN HỆ (tt)+ CÁCH DIỄN TẢ MỘT TẬP HỢP; LNR+ Liệt kê+ Đặc trưngA = xx có tính chất p+ THCS tự nhiên N+ THCS nguyên Z+ THCS hữu tỷ Q+ THCS vô tỷ+ Tập hợp các số thực R+ THCS nguyên tố NT+ THCS chẵn C+ THCS lẻ L....+ THCS phức P+ THCS ảo A1- Khái niệm về Tập hợpB = {x x=n2+1; nN và 1 trên Z không phản xạ vì 1 > 112341234Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số nguyên a là ước của chính nó .Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa đường chéo của A × A :  = {(a, a); a  A}1.3 Quan hệ hai ngôi TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌCĐịnh nghĩa. Quan hệ R trên A được gọi là đối xứng nếu:a  A b  A (a R b)  (b R a) Quan hệ R được gọi là phản xứng nếu a  A b  A (a R b)  (b R a)  (a = b)Ví dụ. Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập A = {1, 2, 3, 4} là đối xứngQuan hệ  trên Z không đối xứng. Tuy nhiên nó phản xứng vì (a  b)  (b  a)  (a = b)281.3 Quan hệ hai ngôi TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌCĐịnh nghĩa. Quan hệ R trên A có tính bắc cầu (truyền) nếua  A b  A c  A (a R b)  (b R c)  (a R c)Ví dụ. Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)}trên tập A = {1, 2, 3, 4} có tính bắc cầu.Quan hệ  và “|”trên Z có tính bắc cầu(a  b)  (b  c)  (a  c)(a | b)  (b | c)  (a | c)291.3 Quan hệ hai ngôi TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC1.3 Quan hệ hai ngôi a  ba  c a  e Phản xạa bc d efBắc cầuPhản đối xứngĐối xứngTính chất của Quan hệ hai ngôi Ví dụ 1.12:TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC1.3 Quan hệ hai ngôi 8- Quan hệ tương đươngPhản xạBắc cầuPhản đối xứng –xx--Đối xứngTính chất của Quan hệ tương đươngVí dụ 1.13:TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌCVí dụ.Cho S = {sinh viên của lớp}, gọi R = {(a,b): a có cùng họ với b}HỏiYesYesYesMọi sinh viêncó cùng họ thuộc cùng một nhóm. R phản xạ? R đối xứng? R bắc cầu?321.3 Quan hệ hai ngôi TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC8- Quan hệ tương đươngĐịnh nghĩa. Quan hệ R trên tập A được gọi là tương đương nếu nó có tính chất phản xạ, đối xứng và bắc cầu :Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu a và b có cùng độ dài. Khi đó R là quan hệ tương đương.Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b nguyên. Khi đó R là quan hệ tương đương331.3 Quan hệ hai ngôi TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC1.3 Quan hệ hai ngôi 9- Quan hệ thứ tựTính chất của Quan hệ thứ tựPhản xạ--xx--Bắc cầuĐối xứng—xx--Phản xạPhản đối xứngVí dụ 1.14:TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌCQuan hệ >= trên tập số thực