Bài giảng Toán rời rạc - Vũ Đinh Hoà

Bài giảng Toán rời rạc do Vũ Đinh Hoà biên soạn, cung cấp cho người học những kiến thức như: Lý thuyết tập hợp; Một số công thức tổ hợp; Đại số Boole và cấu trúc mạch lôgic; Thuật toán; Lý thuyết đồ thị;...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - Vũ Đinh Hoà 1/231TOÁN RỜI RẠCVu Dinh HoaHanoi University of EducationDepartment of Information TechnologyHanoi, Viet Name-mail address: hoavd@fpt.com.vn JJ II J I Back Close2/231 JJ II J IBackClose 3/231Chương 1Lôgic mệnh đềGeorge Boole Các định luật của tư duy 1854. JJ II J I Back CloseMệnh đề lôgic 4/231Khái niệm mệnh đề và phủ định của mệnh đềĐịnh nghĩa 1.1. Một mệnh đề (lôgic) là một khẳng định mà nội dungcủa nó là đúng hoặc là sai, chứ không thể vừa đúng vừa sai.Ví dụ. 1. Mưa bay, gió cuốn. 2. Cuốn sách này là của ai vậy? 3. x + 3 = 7. 4. Hà nội là thủ đô của Việt nam. JJ II 5. Tổng các góc của một tam giác bằng 100◦ . J 6. 4 + 4 = 7. I Back CloseGiá trị chân lý của một một mệnh đề lôgicGiá trị chân lý của mệnh đề lôgic là T (true) hoặc F (false). 5/231Ví dụ. 1. p: Hà nội là thủ đô của Việt nam. 2. q : Tổng các góc của một tam giác bằng 100◦ . 3. r: 4 + 4 = 7. Bảng 1.1: Bảng giá trị chân lý. p q r F F F JJ II J I Back CloseMệnh đề phức hợpVí dụ. 1. Nếu x là số nguyên, thì x2 cũng là số nguyên. 6/231 2. Trời vừa nắng vừa mưa. 3. Biển không phải là ao hồ. 4. Để được đi học nước ngoài, hoặc là bạn phải học giỏi hoặc là bạn phải có tiền tự túc.Tính chất. Liên từ liên kết các mệnh đề đơn giản tạo nên mệnh đề phứchợp: JJVí dụ. “Bạn không được đi xe máy, nếu bạn dưới 16 tuổi trừ phi đó IIlà xe phân khối nhỏ hoặc khi bạn có giấy phép đặc biệt. J I Back ClosePhủ định mệnh đềĐịnh nghĩa 1.2. Cho trước mệnh đề lôgic p. Khi đó câu không phảilà p cũng là một mệnh đề lôgic, được gọi là phủ định của p và đượcký hiệu là p¯ hoặc là ¬p. Nếu p đúng thì p¯ sai và ngược lại. 7/231Ví dụ. p: Ngày 20-11-2008 là ngày chủ nhật. p¯: Ngày 20-11-2008 không phải là ngày chủ nhật. Bảng 1.2: Bảng giá trị chân lý mệnh đề phủ định p p¯ T F F T JJ II J I Back ClosePhép hộiĐịnh nghĩa 1.3. Cho trước hai mệnh đề lôgic p và q . Khi đó câu nóip và q cũng là một mệnh đề lôgic, ký hiệu p ∧ q . Hội của p và q chỉđúng khi cả hai mệnh đề p và q đều đúng và sai trong các trường hợp 8/231còn lại.Ví dụ. p: Bác Hồ sinh vào ngày 19-5. q : Bác Hồ là Chủ tịch nước. p ∧ q : Bác Hồ sinh vào ngày 19-5 và Bác Hồ là Chủ tịch nước. Bảng 1.3: Bảng giá trị chân lý của phép hội p q p∧q T T T JJ T F F II F T F J F F F I Back ClosePhép tuyểnĐịnh nghĩa 1.4. Cho trước hai mệnh đề lôgic p và q . Khi đó câu nói“ p hoặc q ” cũng là một mệnh đề lôgic và được ký hiệu là p ∨ q . Tuyểncủa p và q chỉ sai khi cả p và q cùng sai và đúng trong các trường hợp 9/231còn lại.Ví dụ. p: Hồ Xuân Hương sinh vào ngày 3-5. q : Hồ Xuân Hương sinh vào ngày 9-5. p ∨ q : Hồ Xuân Hương sinh vào ngày 3-5 hoặc vào ngày 9-5. Bảng 1.4: Bảng giá trị chân lý của phép tuyển p q p∨ ...