UỶ BAN NHÂN DÂN TỈNH ĐỒNG THÁP TRƢỜNG CAO ĐẲNG CỘNG ĐỒNG ĐỒNG THÁP GIÁO TRÌNH MÔN HỌC: TOÁN RỜI RẠC NGÀNH, NGHỀ: CÔNG NGHỆ THÔNG TIN TRÌNH ĐỘ: CAO ĐẲNG (Ban hành kèm theo Quyết định số /QĐ-CĐCĐ ngày tháng năm 20… của Hiệu trƣởng trƣờng Cao đẳng Cộng đồng Đồng Tháp) Đồng Tháp, năm 2017 MỤC LỤC CHƢƠNG 1: ĐẠI SỐ MỆNH ĐỀ. PHÉP TOÁN MỆNH ĐỀ . Khái niệm mệnh đề . Phân loại mệnh đề: gồm 2 loại . BẢNG CHÂN TRỊ . CÁC PHÉP TOÁN VỀ MỆNH ĐỀ . Phép phủ định . Phép kéo theo (mệnh đề có điều kiện) . Phép kéo theo hai chiều (Phép tƣơng đƣơng). BIỂU THỨC LOGIC (DẠNG MỆNH ĐỀ) . Một số tính chất . MỘT SỐ PHƢƠNG PHÁP SUY LUẬN . QUY TẮC KHẲNG ĐỊNH (MODUS PONENS) . QUY TẮC PHỦ ĐỊNH (MODUS TOLLENS) . TAM ĐOẠN LUẬN (SYLLOGISM) . QUY TẮC MÂU THUẨN (CHỨNG MINH BẰNG PHẢN CHỨNG) . QUY TẮC CHỨNG MINH THEO TRƢỜNG HỢP. MỘT VÀI VÍ DỤ CỤ THỂ CÓ SỬ DỤNG KẾT HỢP NHIỀU QUY TẮC SUY DIỄN . VỊ TỪ VÀ LƢỢNG TỪ . Các phép toán trên vị từ . LƢỢNG TỪ HÓA VỊ TỪ HAI BIẾN . PHỦ ĐỊNH MỆNH ĐỀ LƢỢNG TỪ . 18 BÀI TẬP ÔN TẬP CHƢƠNG 1 . 20 CHƢƠNG 2: PHÉP ĐẾM . Khái niệm tập hợp . Biểu diễn tập hợp . Một số dạng tập hợp . TẬP HỢP CON, TẬP HỢP BẰNG NHAU . Tập hợp con . Tập hợp bằng nhau. Lực lƣợng của tập hợp . Tích Descartes của tập hợp và lực lƣợng của nó . Biểu diễn các tập hợp trên máy tính . ĐƠN ÁNH, TOÀN ÁNH VÀ SONG ÁNH . ẢNH VÀ ẢNH NGƢỢC CỦA MỘT TẬP HỢP . Ánh xạ hợp . Các tính chất của ánh xạ . QUY TẮC ĐẾM . Nguyên lý bù trừ . Nguyên lý chuồng bồ câu (Nguyên lý Dirichlet) . GIẢI TÍCH TỔ HỢP . Hoán vị lặp, chỉnh hợp lặp và tổ hợp lặp . Công thức nhị thức Newton . 43 BÀI TẬP ÔN TẬP CHƢƠNG 2 . 46 CHƢƠNG 3 ĐẠI SỐ QUAN HỆ . Tính phản xạ . Tính đối xứng. Tính bắc cầu (truyền) . QUAN HỆ TƢƠNG ĐƢƠNG . LỚP TƢƠNG ĐƢƠNG . QUAN HỆ THỨ TỰ . THỨ TỰ TOÀN PHẦN VÀ BÁN PHẦN . PHẦN TỬ LỚN NHẤT, PHẦN TỬ NHỎ NHẤT . PHẦN TỬ TỐI ĐẠI, PHẦN TỬ TỐI TIỂU . TẬP THỨ TỰ TỐT . NGÔN NGỮ TRUY VẤN DỮ LIỆU . CÁC PHÉP TOÁN TẬP HỢP . CÁC PHÉP TOÁN QUAN HỆ . 62 BÀI TẬP ÔN TẬP CHƢƠNG 3 . 64 CHƢƠNG 4 ĐẠI SỐ BOOLE . ĐẠI SỐ BOOLE . Các hằng đẳng thức của đại số Boole . Tính đối ngẫu của đại số Boole . DẠNG NỐI RỜI CHÍNH TẮC . DẠNG NỐI RỜI CHÍNH TẮC . Cách tìm dạng nối rời chính tắc cho hàm Boole . BÀI TOÁN MẠCH ĐIỆN . CÁC CỔNG ĐIỆN TỬ CƠ BẢN . CỔNG NOR VÀ NAND . ƢỚC LƢỢNG CÔNG THỨC . PHƢƠNG PHÁP BIẾN ĐỔI ĐẠI SỐ . PHƢƠNG PHÁP BIỂU ĐỒ KARNAUGH . Biểu đồ Karnaugh của một hàm Boole f . Tế bào và tế bào lớn . Phƣơng pháp Karnaugh tìm công thức đa thức tối tiểu của hàm Boole . 93 BÀI TẬP ÔN TẬP CHƢƠNG 4 . 99 TÀI LIỆU THAM KHẢO . 102 iii CHƢƠNG 1: ĐẠI SỐ MỆNH ĐỀ Giới thiệu Trong chƣơng này sẽ giới thiệu về mệnh đề, biểu thức mệnh đề, các phép toán, ví dụ ứng dụng, giới thiệu một số thuật ngữ chuyên dùng, tƣơng đƣơng logic và cách chứng minh. Mục tiêu Kiến thức: trình bày các nội dung sau: - Các khái niệm, các phép toán về mệnh đề. - Một số phƣơng pháp suy luận. - Vị từ, lƣợng từ. Kỹ năng: Thực hiện đƣợc các yêu cầu sau: - Giải các bài toán mệnh đề. - Sử dụng các phƣơng pháp suy luận phù hợp. Năng lực tự chủ và trách nhiệm: - Vận dụng kiến thức đã học để hình thành kỹ năng cần thiết. Phép toán mệnh đề 1. Khái niệm mệnh đề. Mệnh đề toán học là một phát biểu mà có thể gán cho nó một trong hai giá trị logic là đúng hoặc sai (không thể vừa đúng vừa sai). Thƣờng ký hiệu mệnh đề toán học bằng các chữ cái Latin hoa: P, Q, R, S,. Ví dụ 1: - Các khẳng định sau là mệnh đề: “Thành Phố Cao Lãnh là trung tâm của tỉnh Đồng Tháp” “2 + 3 = 7” “4 là số chẳn.” - Các khẳng định sau không phải mệnh đề: “X là số nguyên tố” “Hôm nay ngày thứ mấy?” "x 3 = 5" Lưu ý: Câu hỏi, câu cảm thán, câu mệnh lệnh, hàm phán đoán,. không phải là mệnh đề. Phân loại mệnh đề: gồm 2 loại - Mệnh đề phức hợp: là mệnh đề đƣợc xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ (và, hay, nếu., khi và chỉ khi,…) hoặc trạng từ “không” Ví dụ 2: 1 - Nếu thông minh thì tôi sẽ học giỏi. - 2 là số nguyên tố và là số lẻ. - 3 không phải là số chẳn - B đang học toán rời rạc hoặc học kỹ thuật lập trình - Mệnh đề sơ cấp (nguyên thủy): Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không” Ví dụ 3: - Hôm nay trời mƣa. - 4 là số nguyên tố. Bảng chân trị Chân trị của mệnh đề: Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngƣợc lại ta nói P có chân trị sai. P có chân trị đúng ta viết P = 1 (hoặc Đ, T), P có chân trị sai ta viết P = 0 (hoặc S, F) Ví dụ 4: - P = “Thành phố Hồ Chí Minh là thủ đô nƣớc Việt Nam” P=0 - Q = “10 là số chẳn” Q=1 Bảng chân trị là bảng thể hiện tất cả các trân trị của một mệnh đề logic, biểu diễn mối quan hệ giữa những giá trị chân lý của các mệnh đề 1. Các phép toán về mệnh đề 1. Phép phủ định. Cho trƣớc mệnh đế P, định nghĩa một mệnh đề mới, kí hiệu P hay P , đọc là “không P” hoặc “phủ định của P”. Gọi P là mệnh đề phủ định của P. Bảng chân trị của phép phủ định: P P 1 0 0 1 Ví dụ 5: a) P = “ Minh giỏi lập trình”. P = “ Minh không giỏi lập trình” Nếu P = 1 P = 0 . Phép hội (phép nối liền, giao) Cho trƣớc hai mệnh đề P, Q mệnh đề nối liền của hai mệnh đề P, Q đƣợc kí hiệu là P Q (đọc là “P và Q”) Mệnh đề P Q đúng khi cả P và Q cùng đúng, còn sai trong các trƣờng hợp còn lại. Bảng chân trị của phép hội. P Q P Q 1 1 1 1 0 0 0 1 0 0 0 0 Ví dụ 6: a) P = “ 3 là số nguyên tố” Q = “ 3 là số chẳn” P Q = “ 3 là số nguyên tố và 3 là số chẳn” Ta có P = 1, Q = 0, do đó P Q= 0 b) P = “Hôm nay là chủ nhật” Q = “Hôm nay trời mƣa” Mệnh đề P Q đúng vào hôm chủ nhật trời mƣa, và là sai vào bất kì ngày nào không phải chủ nhật và vào ngày chủ nhật mà trời lại không mƣa. Lưu ý: - Khi nối hai mệnh đề bởi từ và trong phép hội, thƣờng ta bỏ bớt một số từ trùng lặp hoặc sửa đổi chút ít câu văn. Ví dụ 7: Dây đồng (dẫn điện) và dây chì dẫn điện - Phép hội đôi khi còn diễn đạt bởi liên từ khác nhƣ: đồng thời, nhƣng, mà,.hoặc bằng một dấu phẩy. Ví dụ 8: - “ An giỏi tin học nhưng yếu anh văn” - “ Lan vừa giỏi tin học vừa giỏi anh văn” - “ Anh, chị có thể đọc sách ở thƣ viện” - “ Món này cay mà ngon” - Không phải từ và bao giờ cũng là ý nghĩa của phép hội Ví dụ 9: - “Lý luận và thực hành phải đi đôi với nhau” - “Trắng và đen là hai màu sắc đối lập nhau” 3 1. Mệnh đề P Q sai khi cả hai P, Q cùng sai, trong các trƣờng hợp khác P Q đúng. Bảng chân trị của phép tuyển. P Q P Q 1 1 1 1 0 1 0 1 1 0 0 0 Ví dụ 10: a) P = "3 > 4" , Q = "3 > 5" P Q = "3 > 4 hay 3 > 5" P = 0,Q = 0 P Q= 0 b) P = “An là ca sĩ”, Q = “An là nhạc sĩ”. Khi đó ta có mệnh đề nối rời của P và Q là P Q = “An là ca sĩ hay An là nhạc sĩ”. Mệnh đề nối liền này sẽ đúng nếu nhƣ một trong hai mệnh đề trên là đúng hoặc cả hai mệnh đề trên đều đúng. Nếu cả hai mệnh đề P và Q đều sai thì P Q sẽ sai. Lưu ý: Mệnh đề P Q , từ hay (hoặc) để chỉ P hoặc Q hoặc cả P, Q. Tuy nhiên cótrƣờng hợp chỉ P hoặc chỉ Q chứ không có trƣờng hợp chỉ cả hai P, Q. Để phân biệt rõ ràng ta có thêm phép tuyển chặt: - P hoặc Q để chỉ P hoặc Q và có thể cả P lẫn Q, dùng kí hiệu , gọi là phép tuyển không chặt (phép tuyển) - P hoặc Q để chỉ P hoặc Q không thể cả P lẫn Q, dùng kí hiệu , gọi là phép tuyển chặt. Bảng chân trị của phép tuyển chặt P Q P Q 1 1 0 1 0 1 0 1 1 0 0 0 Ví dụ 11: Hôm nay là thứ 7 hoặc là chủ nhật 4 1. Phép kéo theo (mệnh đề có điều kiện) Mệnh đề P kéo theo mệnh đề Q là một mệnh đề, kí hiệu P Q (đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”). Xét ví dụ: P = “A trúng số”, Q = “A mua laptop mới”, khi đó mệnh đề P kép theo Q sẽ là “Nếu A trúng số thì A sẽ mua laptop mới”. Ta có các trƣờng hợp sau đây: - A đã trúng số và anh ta mua laptop mới: hiển nhiên mệnh đề P Q là đúng. - A đã trúng số nhƣng anh ta không mua laptop mới: rõ ràng mệnh đề P Q là sai. - A không trúng số nhƣng anh ta vẫn mua laptop mới: mệnh đề P Q vẫn đúng. - A không trúng số và anh ta không mua laptop mới: mệnh đề P Q đúng. Mệnh đề P Q chỉ sai khi P đúng Q sai, và đúng trong mọi trƣờng hợp còn lại. Bảng chân trị của phép kéo theo P Q P Q 1 1 1 1 0 0 0 1 1 0 0 1 1.
Giáo trình Toán Rời Rạc Ngành Công Nghệ Thông Tin - Trường Cao Đẳng Cộng Đồng Đồng Tháp
Giáo trình Toán rời rạc cho công nghệ thông tin biên soạn theo chương trình đào tạo chuẩn, phù hợp sinh viên ngành công nghệ thông tin
Trường đại học
Trường Cao Đẳng Cộng Đồng Đồng ThápChuyên ngành
Công Nghệ Thông TinNgười đăng
Ẩn danhThể loại
Giáo TrìnhPhí lưu trữ
35 PointMục lục chi tiết
THÔNG TIN CHI TIẾT
Trường học: Trường Cao Đẳng Cộng Đồng Đồng Tháp
Chuyên ngành: Công Nghệ Thông Tin
Đề tài: Giáo Trình Toán Rời Rạc
Loại tài liệu: Giáo Trình
Năm xuất bản: 2017
Địa điểm: Đồng Tháp
Trích đoạn nội dung tài liệu
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ