TAILIEUCHUNG - Thuật toán và giải thuật - Hoàng Kiếm Part 9

Thuật giải Robinson thuật giải này hoạt động dựa trên phương pháp chứng minh phản chứng chứng minh phép suy luận là đúng ( với a là giả thuyết và b là kết luận) | p q r p s q s B4 Nếu GTi có phép thì tách thành hai dòng con. Nếu ở KLi có phép thì tách thành hai dòng con. Ví dụ p p q q p p q p q q B5 Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở ở cả hai phía. Ví dụ p q q được chứng minh p p q pũ p q B6 a Nếu một dòng không còn phép nối hoặc ở cả hai vế và ở 2 vế không có chung một biến mệnh đề thì dòng đó không được chứng minh. b Một vấn đề được chứng minh nếu tất cả dòng dẫn xuất từ dạng chuẩn ban đầu đều được chứng minh. Thuật giải Robinson Thuật giải này hoạt động dựa trên phương pháp chứng minh phản chứng. Phương pháp chứng minh phản chứng Chứng minh phép suy luận a b là đúng với a là giả thiết b là kết luận . Phản chứng giả sử b sai suy ra b là đúng. Bài toán được chứng minh nếu a đúng và b đúng sinh ra một mâu thuẫn. B1 Phát biểu lại giả thiết và kết luận của vấn đề dưới dạng chuẩn như sau GT1 GT2 . GTn KL1 KL2 . KLm Trong đó GTi và KLj được xây dựng từ các biến mệnh đề và các phép toán B2 Nếu GTi có phép thì thay bằng dấu 57 Sưu tầm bởi Nếu KLi có phép thì thay bằng dấu B3 Biến đổi dòng chuẩn ở B1 về thành danh sách mệnh đề như sau GT1 GT2 . GTn KL1 KL2 . KLm B4 Nếu trong danh sách mệnh đề ở bước 2 có 2 mệnh đề đối ngẫu nhau thì bài toán được chứng minh. Ngược lại thì chuyển sang B4. a và a gọi là hai mệnh đề đối ngẫu nhau B5 Xây dựng một mệnh đề mới bằng cách tuyển một cặp mệnh đề trong danh sách mệnh đề ở bước 2. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu nhau thì các biến đó được loại bỏ. Ví dụ p q r s q Hai mệnh đề q q là đối ngẫu nên sẽ được loại bỏ p r s B6 Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng mệnh đề mới. Ví dụ p q r s q w r s q p r s w r s q B7 Nếu không xây dựng được thêm một mệnh đề mới nào và trong danh sách mệnh đề không có 2 mệnh đề nào đối ngẫu nhau thì vấn đề không được chứng minh. Ví dụ Chứng minh rằng p q q r r s u s p u B3 p q q r r s u s p u B4 Có tất cả 6 mệnh đề nhưng chưa có mệnh đề nào đối ngẫu nhau. B5 tuyển một cặp mệnh đề chọn hai .

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao