Tài liệu giảng dạy Toán rời rạc & lý thuyết đồ thị (Ngành/Nghề: Công nghệ thông tin – Trình độ Cao đẳng) - Trường CĐ Kinh tế - Kỹ thuật Vinatex TP. HCM (2019)

Tài liệu giảng dạy Toán rời rạc & lý thuyết đồ thị (Ngành/Nghề: Công nghệ thông tin – Trình độ Cao đẳng) gồm có 2 phần. Phần 1 gồm có 4 chương với những nội dung về toán rời rạc như: cơ sở logic, phương pháp đếm, quan hệ, hàm bool và đại số bool. Phần 2 gồm 4 chương với những kiến thức về lý thuyết đồ thị như: đồ thị, các bài toán về chu trình, cây, bài toán về con đường ngắn nhất. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Tài liệu giảng dạy Toán rời rạc & lý thuyết đồ thị (Ngành/Nghề: Công nghệ thông tin – Trình độ Cao đẳng) - Trường CĐ Kinh tế - Kỹ thuật Vinatex TP. HCM (2019) TẬP ĐOÀN DỆT MAY VIỆT NAM TRƢỜNG CAO ĐẲNG KINH TẾ - KỸ THUẬT TP.HCM TÀI LIỆU GIẢNG DẠY MÔN HỌC: TOÁN RỜI RẠC & LÝ THUYẾT ĐỒ THỊ NGÀNH/NGHỀ: CÔNG NGHỆ THÔNG TIN TRÌNH ĐỘ: CAO ĐẲNG TP. HỒ CHÍ MINH, năm 2019 TUYÊN BỐ BẢN QUYỀN Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể đƣợc phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. LỜI GIỚI THIỆU Tài liệu giảng dạy đƣợc biên soạn dựa trên tài liệu Toán rời rạc của GS. Nguyễn Hữu Anh, trƣờng Đại học Tổng hợp TP. Hồ Chí Minh, tài liệu Lý thuyết đồ thị của Pts. Nguyễn Cam, Pts. Chu Đức Khánh. Tài liệu giảng dạy Toán rời rạc và lý thuyết đồ thị đƣợc dùng làm tài liệu học tập cho sinh viên ngành Công nghệ thông tin, đƣợc trình bày theo đúng chƣơng trình môn học đã đƣợc xây dựng. Tài liệu giảng dạy này giúp cho sinh viên những kiến thức cơ bản về Toán rời rạc, Lý thuyết đồ thị. Tài liệu giảng dạy bao gồm: Phần 1: Toán rời rạc Chƣơng 1: Cơ sở logic Chƣơng 2: Phƣơng pháp đếm Chƣơng 3: Quan hệ Chƣơng 4: Hàm Bool và đại số Bool Phần 2: Lý thuyết đồ thị Chƣơng 1: Đồ thị Chƣơng 2: Các bài toán về chu trình Chƣơng 3: Cây Chƣơng 4: Bài toán về con đƣờng ngắn nhất Trong quá trình biên soạn, mặc dù đã có nhiều cố gắng nhƣng không tránh khỏi những hạn chế và một số thiếu sót nhất định, nhóm tác giả rất mong nhận đƣợc những ý kiến đóng góp của quý đọc giả để tài liệu giảng dạy này ngày càng hoàn thiện hơn. Xin chân thành cảm ơn TP. HCM, ngày ….. tháng ….. năm Tham gia biên soạn Ths. Võ Thị Thục Hà MỤC LỤC Phần 1: Toán rời rạc Chƣơng 1: CƠ SỞ LOGIC ..................................................................................... 1 I. Phép tính mệnh đề............................................................................................... 1 1. Khái niệm về mệnh đề ................................................................................. 1 2. Phân loại mệnh đề........................................................................................ 1 3. Các phép toán logic ..................................................................................... 1 4. Dạng mệnh đề .............................................................................................. 1 II. Qui tắc suy diễn ................................................................................................. 5 III. Vị từ và lƣợng từ .............................................................................................. 7 1. Vi từ ............................................................................................................. 7 2. Lƣợng từ ...................................................................................................... 7 IV. Nguyên lý quy nạp ........................................................................................... 8 Chƣơng 2: PHƢƠNG PHÁP ĐẾM ........................................................................ 9 I. Tập hợp ............................................................................................................... 9 1. Khái niệm về tập hợp ................................................................................... 9 2. Các phép toán trên tập hợp ........................................................................ 10 3. Tính chất của các phép toán ...................................................................... 10 4. Tích Descartes của tập hợp ........................................................................ 11 II. Ánh xạ.............................................................................................................. 11 III. Giải tích tổ hợp ............................................................................................... 13 1. Phép đếm ................................................................................................... 13 2. Giải tích tổ hợp .......................................................................................... 14 Chƣơng 3: QUAN HỆ .......................................................................................... 17 I. Quan hệ ............................................................................................................. 17 II. Quan hệ tƣơng đƣơng ...................................................................................... 18 III. Quan hệ thứ tự ................................................................................................ 18 Chƣơng 4: ĐẠI SỐ BOOL VÀ HÀM BOOL ..................................................... 20 I. Đại số Bool ....................................................................................................... 20 II. Hàm Bool......................................................................................................... 21 III. Mạng các cổng và công thức tối tiểu ............................................................. 24 1. Các cổng logic ........................................................................................... 24 2. Tổ hợp các cổng logic................................................................................ 25 3. Tối thiểu hóa hàm Boole ........................................................................... 25 IV. Phƣơng pháp ...