tailieunhanh - Bài giảng : Logic part 10

PHƯƠNG PHÁP CHỨNG MINH HAY ÁP DỤNG: Nguyên lí quy nạp mà ta rút ra được ở trang 21 lecture 1 có { nghĩa rất quan trọng. Đối với chúng ta, thì sau khi học xong nguyên lí này sẽ rút ra được phương pháp chứng minh một dạng bài toán rất hay gặp ở môn logic này : Đó là chứng minh một tập công thức xây dựng đúng wff thỏa mãn một tính chất nào đó. Từ nguyên lí quy nạp, ta sẽ rút ra hướng giải quyết như sau: Với : U= tập tất cả các. | Slide Ngữ nghĩa Định nghĩa Cho 01 _ Qn là các công thức logic vị từ. Thì quan hệ thứ tự 01 _ 0n ụ thoả mãn nếu và chỉ nếu khi M loi với 1 i n thì M 1 với tất cả các mô hình M và môi trường l. 118 PHỤ LỤC 119 1 PHƯƠNG PHÁP CHỨNG MINH HAY ÁP DỤNG Nguyên lí quy nạp mà ta rút ra được ở trang 21 lecture 1 có ý nghĩa rất quan trọng. Đối với chúng ta thì sau khi học xong nguyên lí này sẽ rút ra được phương pháp chứng minh một dạng bài toán rất hay gặp ở môn logic này Đó là chứng minh một tập công thức xây dựng đúng wff thỏa mãn một tính chất nào đó. Từ nguyên lí quy nạp ta sẽ rút ra hướng giải quyết như sau Với U tập tất cả các biểu thức B tập những biể u thức gồm các kí hiệu mệnh đề đơn. F 8_ 8a 8v 8_ 8. Từ tập wff s W là sinh ra tự do từ B bởi F ta sẽ đặt một tập S là một tập tất cả các biể u thức thoả mãn tính chất như đề bài yêu cầu. Khi đó ta đi chứng minh BcS thường thì đề sẽ cho luôn hoặc rất dễ nhận ra . Ta chứng minh S đóng trên F - Ta đi chứng minh với aeS thì qua phép biến đổi 8 _ a biểu thức đạt được vẫn phải thoả mãn 8 _ a E S tức chứng minh nó vẫn thoả mãn giả thiết đã đặt ra . Thì S đóng dưới hàm 8 _. - Tiếp theo ta đi chứng minh với a 0GS thì qua phép biến đổi 8A a P 8v a P 8 . a P 8. . a P các biểu thức mới đạt được này vẫn phải thuộc S. Nếu việc chứng minh với mỗi hàm này quá phức tạp ta có thể lấy một trường hợp đại diện để chứng minh còn các trường hợp còn lại sẽ tương tự. Khi đó ta có thể kết luận là S là tập quy nạp được. Nên theo nguyên lí quy nạp Wc S. Nên tất cả các công thức trong W sẽ thoả mãn các tính chất của đề bài. Những bài đã áp dụng phương pháp này các bạn có thể tham khảo để thấy rõ hơn như Chứng minh mọi công thức wff có số ngoặc trái và phải bằng nhau ở trang 24 lecture 1 hay chứng minh bổ đề Mọi dãy khởi đầu thực sự của một wff chứa một số ngoặc vượt quá và dẫn đến nó không là wff ở trang 32 lecture 1. .