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...
Nội dung trích xuất từ tài liệu:
Bài giảng : Logic part 10Slide 5.20: Ngữ nghĩaĐịnh nghĩa: Cho Φ1,…,Φn là các công thức logic vị từ. Thì quan hệ thứ tựΦ1,…,Φn⊨Ψ thoả mãn nếu và chỉ nếu khi M ⊨lΦi với 1≤i≤n, thì M ⊨lΨ, với tất cảcác mô hình M và môi trường l. 118PHỤ LỤC 1191 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ứcB= tập những biểu thức gồm các kí hiệu mệnh đề đơn.F= {ℰ , ℰ∧, ℰ∨, ℰ→, ℰ↔}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 B⊂S (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 α∈S thì qua phép biến đổi ℰ (α) biểu thức đạt được vẫn phải thoả mãn ℰ (α) ∈ S ( tức chứng minh nó vẫn thoả - mãn giả thiết đã đặt ra). Thì S đóng dưới hàm ℰ . Tiếp theo, ta đi chứng minh với α, β∈S thì qua phép biến đổi ℰ∧(α,β), ℰ∨(α,β), ℰ→(α,β), ℰ↔(α,β) 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 W⊂ S. Nên tất cả các công thức trong W sẽ thoả mãn các tính chấtcủ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. 120 Các bài tập áp dụng được giao về nhà như trang 35 lecture 1 hay chứng minh tập { , ∨+ hay tập { , ∧} là đủ đều có thể chứng minh bằngquy nạp. Hay chứng minh tính đúng, tính đủ của thuật toán ở trang 36-37 lecture 1.Chú ý: Với các bài toán chứng minh tính chất của các phần tử của một tập xây dựng theo quy nạp, ta đều có thể làm tương tự. Bài toán với tập cáccông thức xây dựng đúng chỉ là một trường hợp riêng thường gặp. 1 VÀI CHÚ Ý:Chú ý ở trang 29: về 2 điều kiện :  Giới hạn của mỗi hàm f∈ F đến C phải là tương ứng 1-1.  Phạm vi của giới hạn của mỗi hàm trong F phải là rời với tất cả phạm vi giới hạn của các hàm khác trong F và từ B.Các bạn đọc nghe có vẻ khó hiểu. Mình xin giải thích theo như mình đã tham khảo (ko dám khẳng định là đúng) được ở một số tài liệu và hiểu bằngví dụ như sau:Giả sử F có hai hàm ℰ∧(α,β)=(α∧β), ℰ∧ (α,β)=(α∨β) thì một công thức ℰ được tạo từ f∈ F mà có dạng ℰ=(γ∧µ) khi và chỉ khi từ hàm ℰ∧tạo nên,cũng tương tự với hàm ℰ∧. Đó là sự tương ứng giữa một phần từ thuộc C với một hàm f ∈ F mà ta gọi tắt là 1-1.Ví dụ ở trang 28 lecture 1 về hàm h có hỏi là h(1)=? h(1) theo như đ ịnh nghĩa đó dễ thấy sẽ có tới 2 giá trị là 2 và 4 và không đảm bảo được địnhnghĩa của ánh xạ. Cũng thấy rằng, vì tại giá trị 1 thuộc vào N không có sự tương ứng 1-1 với các hàm trong F. Vì succ(0)=mult(1,1)=1.Giải thích về ý nghĩa của thuyết đọc được duy nhất: { nghĩa của nó là đảm bảo hai điều kiện ở trang 29 thoả mãn tập wff’s W, để cùng với nguyênlí quy nạp sẽ đảm bảo cho hàm v được xác định đúng.Bổ đề ở trang 35 lecture 1: chúng ta thấy rằng, khi đọc qua thì dễ bị ngộ nhận nó là đương nhiên và sao nó cứ giống định nghĩa vậy. Nhưng không,khi đọc kĩ sẽ thấy rằng: ở định nghĩa là ta đang xây dựng công thức wff và điểm bắt đầu là từ tập các kí hiệu mệnh đề đơn, còn ở bổ đề này, ta 121khẳng định nó sẽ là công thức xây dựng đúng hay không ở một điểm bất kì. Và ta cũng phải chứng minh bổ đề này bằng qui nạp, có thể dùngphương pháp đã nêu ở trên.Các bạn tự hỏi về SAT: SAT là một kí hiệu đại diện để nói về thuật toán kiểm tra tính thoả mãn được của một công thức bất kì bằng việc sử dụngbảng sự thật.1 Số giải thích về định lí compactness: Về tên gọi: không có được cách giải thích chính xác cho trường hợp chung. Ta sẽ giải thích nó cho trường hợp này sau khi phân tích vấn đề ởdưới đây. Định lí: Một tập wff là thoả mãn được khi và chỉ khi nó thoả mãn được hữu hạn. Các bạn sau khi đọc xong định lí này hay lâm vào tình trạng là thấy nó thật đương nhiên, vì nghĩ rằng:-Một tập wff thoả mãn được tức tồn tại một phép gán v để ...