Bài giảng Toán rời rạc: Chương 3 - ThS. Trần Quang Khải

Bài giảng Toán rời rạc: Chương 3 Suy luận và Chứng minh, cung cấp cho người học những kiến thức như: Giới thiệu; Các quy tắc suy luận; Phương pháp chứng minh; Quy nạp toán học; Phát biểu đệ quy. 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: Chương 3 - ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 3:Suy luận – Chứng minh Giảng viên: ThS. Trần Quang Khải Nội dung 1. Giới thiệu. 2. Các quy tắc suy luận 3. Phương pháp chứng minh. Quy nạp toán học. 4. Phát biểu đệ quy. 5. Bài tập – Hỏi đáp.Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 2 Giới thiệu Hai vấn đề trong toán học:1. Khi nào một suy luận toán học là ĐÚNG?2. PHƢƠNG PHÁP nào để xây dựng các suy luận toán học?Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 3 Giới thiệu – Trong toán họcToán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 4 Giới thiệu - Trong tin học OK Dữ liệu 1 Program Kết quả 1 OK Dữ liệu 2 Program Kết quả 2 Dữ liệu n Program Kết quả n Hmmm! Tầm bậy!Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 5 Các khái niệm Định lý: theorem = a TRUE statement một phát biểu hoặc công thức được suy luận ra từ các tiên đề dựa vào các quy tắc suy luận sự chứng minh. Tiên đề (Axiom – còn gọi là định đề) một mệnh đề không phụ thuộc vào sự chứng minh.  giả thiết cơ sở của các cấu trúc toán học. Giả thiết (Hypothesis) Những mệnh đề/phát biểu đúng được sử dụng để tranh luận hoặc nghiên cứu. Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 6 Chứng minh là gì? Định lý đã Giả thiết Tiên đề của định lý được CM Quy tắc suy luận Định lý Quy tắc suy luận = cơ chế rút ra kết luận từ những điều đã được khẳng định khác. Sự chứng minh có thể thực hiện bằng việc kết hợp các bước chứng minh.Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 7 Các quy tắc suy luận (1) Addition (Luật cộng) Simplification (Luật rút gọn) Modus ponens (Luật tách rời)Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 8 Các quy tắc suy luận (2) Modus tollens Hypothetical syslogism (Tam đoạn luận giả định) Disjunctive syslogism (Tam đoạn luận tuyển)Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 9 Ví dụ1. “Kaka từng đoạt quả bóng vàng Thế Giới. Do đó Kaka từng đoạt quả bóng vàng Thế Giới hoặc giải học sinh giỏi toán rời rạc cấp phường.”2. “Trời thì nóng nực và bạn đang quăng bom. Do đó bạn đang quăng bom.”3. “Nếu bạn chém gió thì bạn của bạn cảm lạnh. Nếu bạn của bạn cảm lạnh thì bạn ấy hắt xì. Vậy nếu bạn chém gió thì bạn của bạn hắt xì.”4. “Nếu lợn biết lập trình thì gà biết chơi Game. Gà không biết chơi game. Vậy lợn biết lập trình.” Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 10 Quy tắc suy luận với lượng từ Universal instantiation (Sự cụ thể hóa ∀) với bất kỳ Universal generalization (Sự tổng quát hóa ∀) Existential instantiation với một số (Sự cụ thể hóa ∃) với một số Existantial generalization (Sự tổng quát hóa ∃)Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 11 Phương pháp chứng minh 1. Chứng minh trực tiếp (direct). 2. Chứng minh gián tiếp (indirect). 3. Chứng minh bằng phản chứng (contradiction). 4. Chứng minh quy nạp (inductive).Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 12 1. Chứng minh trực tiếp Chứng minh p  q bằng cách chỉ ra: “Nếu p là đúng thì q phải đúng”. Ví dụ: “Nếu n là số lẻ thì n2 cũng là số lẻ” CM: giả sử n lẻ thì n = 2k + 1 n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(k2+2k) + 1 (là số lẻ) Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 13 2. Chứng minh gián tiếp Chứng minh p  q bằng cách: thực hiện chứng minh trực tiếp ¬q  ¬p. sử dụng (p → q) ⇔ (¬q → ¬p). Ví dụ: “Nếu 3n+2 là số lẻ thì n là số lẻ” CM: Giả sử n chẵn (kết luận ở trên là FALSE): n = 2k 3n + 2 = 6k + 2 = 2(3k + 1) (chẵn) Vậy giả thiết là FALSE. Định lý được chứng minh. Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 14 3. Chứng minh bằng phản chứng Mô tả: Cần chứng minh phát biểu p là T. Giả sử tìm được mâu thuẫn q sao cho ¬p → q là T. Tức (¬p → F) là T. Khi đó ¬p phải là F thì p là T.  Được sử dụng khi có thể tìm được mâu thuẫn dạng r ¬r, tức mệnh đề ¬p → (r ¬r) là T. Toán rời rạc: 2011-2012 Chương 3: Suy luận - Chứng minh 15 3. Chứng minh bằng phản chứng Ví dụ: “ ...