Bài giảng môn học Toán học rời rạc

Bài giảng môn học Toán học rời rạc cung cấp cho các bạn những kiến thức chính về: Tập hợp và logic mệnh đề, giải thuật và các phương pháp đếm, lý thuyết đồ thị và cây. Để hiểu rõ hơn về bài giảng mời các bạn cùng tham khảo tài liệu.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Toán học rời rạc TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN KHOA HỌC MÁY TÍNH -------------o0o------------ BÀI GIẢNG MÔN HỌC TOÁN HỌC RỜI RẠC HỆ ĐẠI HỌC Số tín chỉ: 3TC Hệ đào tạo: ĐHCQ Ngành: CNTT, HTTTQL, TMĐT. Bộ môn giảng dạy: Bộ môn KHMT – Khoa CNTT. Thái Nguyên, năm 2015 0 MỤC LỤC Mục Trang Chương 1: TẬP HỢP VÀ LOGIC MỆNH ĐỀ……………………………… 2 1.1 Tập hợp và các phép toán trên tập hợp………………………………….. 2 1.2. Quan hệ…………………………………..……………………………... 5 1.3. Logic mệnh đề………………………………….. …………………….. 8 1.4. Suy luận toán học và các phương pháp chứng minh…………………… 16 Chương 2: GIẢI THUẬT VÀ CÁC PHƯƠNG PHÁP ĐẾM………………. 22 2.1. Thuật toán và các đặc trưng cơ bản của thuật toán……………………… 22 2.2. Thuật toán đệ quy…………………………………..……………………. 28 2.3. Thuật toán quay lui………………………………….. …………………. 33 2.4. Các nguyên lý đếm cơ bản………………………………….. ………… 37 2.5. Hoán vị và tổ hợp…………………………………..…………………… 40 Chương 3: LÝ THUYẾT ĐỒ THỊ VÀ CÂY………………………………… 50 3.1. Đồ thị và các khái niệm cơ bản trong đồ thị ……………………………. 50 3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị………………….. 54 3.3. Các phương pháp duyệt đồ thị…………………………………………... 57 3.4. Một số đơn đồ thị đặc biệt………………………………….. …………. 59 3.5. Đồ thị Euler…………………………………..…………………………. 63 3.6. Đồ thị Hamilton………………………………………………………… 68 3.7. Thuật toán tìm đường đi ngắn nhất. ………………………………….. 73 3.8. Cây và cây khung của đồ thị……………………………………………. 80 TÀI LIỆU THAM KHẢO…………………………………………………… 90 1 CHƯƠNG 1 TẬP HỢP & LOGIC MỆNH ĐỀ 1.1.Tập hợp 1.1.1 Khái niệm chung về tập hợp Tập hợp là một trong những khái niệm quan trọng nhất của toán học, nó là gốc rễ của các ngành toán học khác nhau. Vào nửa đầu thế kỷ 19, nhà toán học người Đức Geory Cautar (1845 – 1918) đã nghiên cứu các tập hợp và ứng dụng của chúng như là nền tảng của các ngành toán học (các công trình được công bố vào những năm từ 1871 – 1883) . Lý thuyết tập hợp sau khi xuất hiện đã thống nhất được nhiều quan niệm toán học và đã xây dựng nên các cơ sở logic của nhiều ngành toán học khác nhau. Tập hợp được coi là 1 cấu trúc rời rạc bao gồm nhiều đối tượng được nhóm lại với nhau, thông thường các đối tượng trong một tập hợp có một vài tính chất tương tự nhau. Các đối tượng trong tập hợp được gọi là các phần tử của tập hợp đó. Trật tự của các các phần tử trong tập hợp là không quan trọng, quan trọng là phần tử đó có mặt trong tập hợp hay không. Ví dụ: Tập hợp các số tự nhiên N. Tập N+ các số tự nhiên khác 0 Tập các số nguyên Z Tập các số hữu tỷ Q Tập các số thực R Ký hiệu: Phần tử tập hợp dùng chữ in thường. Tập hợp dùng chữ in hoa. Để ký hiệu x là phần tử của tập A, ta viết: xA (x thuộc A hay x là phần tử của A). Nếu x không là phần tử của tập A thì ta viết: xA (x không thuộc A). 1.1.2.Một số tập hợp đặc biệt a.Tập con Cho 2 tập hợp A và B. Nếu mọi phần tử của A đều là phần tử của B thì ta viết: AB hoặc BA và gọi là A là tập con của B (A được chứa trong B; A được bao hàm trong B; A là bộ phận của B; B bao hàm A…). Ví dụ: N*NZQR Hai tập A và B được gọi là bằng nhau nếu AB và BA. Ký hiệu là A=B Nếu AB và AB thì ta nói A là tập con thực sự của B, ký hiệu A  B. Nếu A không là tập con thực sự của B thì ta viết AB b.Tập hợp rỗng:Tập hợp không chứa phần tử nào gọi là tập rỗng. Tập rỗng được ký hiệu là .Với mọi tập A ta có A.Tập rỗng là duy nhất. c.Tập hợp các tập con của một tập hợp: Cho X là một tập hợp. Tập hợp các tập con của tập X ký hiệu là P(X) hay 2X. P(X) = {A | AX} Ví dụ: X =  thì P(X) = {} X = {a, b} thì P(X) = {, {a}, {b}, {a,b}} d. Tập hợp bù: Với mỗi AX đặt AC = X\A hay X  X \ A gọi là phần bù của A trong X. Ta có: AAC = X hay A  A  X ; AAC =  hay A  A   2 Theo tính chất ta có: (AB)C = ACBC (AB)C = ACBC 1.1.3 Cách xác định tập hợp a. Liệt kê các phần tử của tập hợp trong cặp ngoặc {…} Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó: A ...