tailieunhanh - Bài 11 -ProofStrategy
Tham khảo tài liệu 'bài 11 -proofstrategy', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen 1/8/01 A word about organization: Since different courses have different lengths of lecture periods, and different instructors go at different paces, rather than dividing the material up into fixed-length lectures, we will divide it up into “modules” which correspond to major topic areas and will generally take 1-3 lectures to cover. Within modules, we have smaller “topics”. Within topics are individual slides. Module #11: Chiến lược chứng minh Proof Strategies Rosen 5th ed., § ~21 slides, ~1 lecture 1/8/01 Tổng quan Bài #11 Trong bài #2, ta đã thấy: Một số kiểu chứng minh của phép kéo theo p→q: Ngây thơ, Hiển nhiên, Trực tiếp, Gián tiếp Các kiểu chứng minh tồn tại: Xây dựng và không xây dựng. Một số phương pháp chứng minh . | University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen 1/8/01 A word about organization: Since different courses have different lengths of lecture periods, and different instructors go at different paces, rather than dividing the material up into fixed-length lectures, we will divide it up into “modules” which correspond to major topic areas and will generally take 1-3 lectures to cover. Within modules, we have smaller “topics”. Within topics are individual slides. Module #11: Chiến lược chứng minh Proof Strategies Rosen 5th ed., § ~21 slides, ~1 lecture 1/8/01 Tổng quan Bài #11 Trong bài #2, ta đã thấy: Một số kiểu chứng minh của phép kéo theo p→q: Ngây thơ, Hiển nhiên, Trực tiếp, Gián tiếp Các kiểu chứng minh tồn tại: Xây dựng và không xây dựng. Một số phương pháp chứng minh mệnh đề tổng quan: Chứng minh phân trường hợp, chứng minh phản chứng. Trong bài này, chúng ta xét các ví dụ về: Suy luận tới và lui. Chứng minh phân trường hợp. Chứng minh tồn tại thích hợp. Qui giả thuyết về các chứng minh. 1/8/01 Suy luận tới Ta có giả thiết p, và muốn chứng minh q. Tìm s1 sao cho p→s1 Khi đó, luật suy diễn modus ponens sẽ cho s1. Tiếp tục tìm s2 (sao cho) s1→s2. Khi đó, luật suy diễn modus ponens sẽ cho s2. Và hy vọng sẽ nhận được sn sn→q. Vấn đề với phương pháp này là Phải bền bỉ để nhìn thấy đường đi từ p. 1/8/01 Suy luận lui Backward Reasoning Thông thường dễ dàng hơn để thấy con đường tương tự nếu bạn bắt đầu từ kết luận q Như vậy, đầu tiên tìm s−1 sao cho s−1→q. Sau đó, tìm s−2 s−2→s−1, và tiếp tục Cho đến khi s−n p→s−n. Lưu ý ta cũng sử dụng luật suy diễn modus ponens để triển khai tính đúng đắn từ p đến s−n đến s-1 đến q! Chúng ta tìm được dãy lui nhưng áp dụng tiến tới. Đây không phải hoàn toàn như chứng minh gián tiếp Ở đó ta dùng .
đang nạp các trang xem trước
