Bài giảng : Logic part 10

Chia sẻ: Ouiour Isihf | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

202
lượt xem 37
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng : Logic part 10

Slide 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. 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= {ℰ  , ℰ∧, ℰ∨, ℰ→, ℰ↔} 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ấ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. 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ằng quy 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ác cô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ằng ví 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 định nghĩ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ên lí 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 121
khẳ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ùng phươ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ụng bả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 để nó thoả mãn tất cả các công thức trong tập đó, nên nó cũng sẽ làm tất cả các tập con của tập này thoả mãn được, nên nó sẽ thoả mãn được một cách hữu hạn → các bạn đã suy nghĩ đúng. -Một tập thoả mãn được hữu hạn tức là với mỗi tập con của nó, bao giờ cũng có ít nhất một phép gán thoả mãn được, do vậy tập con lớn nhất của nó chính là nó cũng thoả mãn mãn được → các bạn đã đúng nhưng chỉ với một trường hợp đặc biệt. Do định nghĩa thoả mãn được hữu hạn là cho tất cả các tập cả chứa hữu hạn hoặc vô hạn số phần tử. Các bạn đã suy luận đúng trong trường hợp nó có hữu hạn các phần tử. Nhưng với một tập vô hạn, ta không thể lấy từng phần tử nó ra, rồi cân đo đong đếm để xem nó có thoả mãn không→ sẽ mất cả đời không xong ^^. Ý nghĩa của định lí này cũng rất hay là như vậy, bằng cách từ những điều hữu hạn ta sẽ chứng minh được cho trường hợp vô hạn. Chính vì điều này mà người ta cũng gọi nó là compactness. Về bài tập con trong định lí. Mình xin được trình bày việc chứng minh có thể xây được tập ∆ như trong định lí bằng bổ đề sau: 122
Cho Σ là tập thoả mãn được hữu hạn. Thì mọi công thức wff α, một trong hai tập Σ∪{ α- và Σ∪{  α- là thoả mãn được hữu hạn. Chứng minh: Giả sử Σ ∪ ,α- là không thoả mãn được hữu hạn. Thì sẽ có một số tập X nào đó với X⊂Σ ∪ ,α- là không thoả mãn được hữu hạn. Bây giờ, nếu α∉ X và X là thoả mãn được (do giả thuyết S là tập thoả mãn được hữu hạn), sẽ dẫn đến điều mâu thuẫn. Vậy, ta phải có α∈X , nên X=C∪*α+ với C là một tập hữu hạn nào đó thoả mãn C⊂∆. Bây giờ ta đi chứng minh Σ∪*  α} là thoả mãn được hữu hạn. Cho một tập bất kì D⊂Σ. Thì C∪D là một tập con hữu hạn của Σ, nên theo giả thuyết có một phép gán v thoả mãn C∪D. Nếu v(α)=1 thì v thoả mãn được X=C∪*α+ mà điều này không thể có. Nên v(  α)=1, và vì vậy v thoả mãn D∪{  α}. Việc này cho thấy mọi tập D⊂ ∆ thì D∪{  α} là thoả mãn được. Nên ta có, Σ∪*  α} là thoả mãn được hữu hạn. Vậy, từ các điều kiện đã cho, nếu Σ ∪ ,α- là không thoả mãn được hữu hạn thì Σ∪*  α} là thoả mãn được hữu hạn. (→đpcm) Giải thích kí hiệu ⊥: các bạn cần chú ý ở trong logic mệnh đề thì nó là một giá trị hằng sai, còn trong logic vị từ thì nó là một kí hiệu vị từ với giải nghĩa “… điều sai” với … tuz vào ngữ cảnh Giải thích các quy tắc suy diễn: Do mọi người khi học về phần này, không hiểu các kí hiệu quy tắc này thế nào mà trong bài giảng cũng không có (thầy có nói miệng ^^) nên mình đưa ra giải thích của nó: t  t [t / x] ( e) 1 2 1 ( i ) =: [t / x] t t 2 x (xe) ∀x: (∀ xi) [t / x] 123
Trước khi giải thích một cách cụ thể thì mình giải thích là ở trên dấu “-------“ là giả thiết, còn ở dưới là điều có thể suy ra được từ các giả thiết đó. Giả thiết bao giờ cũng đúng hoặc ít nhất là được cho là đúng ở tại chỗ đang xét để áp dụng qui tắc. Giải thích luật (=i): không cần cái gì cùng có thể suy ra được t=t. Giải thích luật (=e): nếu t1=t2, và Φ*t1\t+ là đúng thì Φ*t2\t+ cũng đúng với Φ là một công thức. Giải thích luật (∀xe): nếu ∀xΦ đúng thì nó cũng phải đúng với một giá trị t cụ thể bất kì tức Φ*t\x+ đúng. Giải thích luật (∀xi): trong một hộp kín: xét một x0 bất kì (không xuất hiện ở đâu ngoài hộp tức không bị ràng buộc gì cả) nếu suy ra được một công thức Φ nào đó đúng với x0 này, thì tức là ở ngoài hộp nó đúng với mọi x0 tức suy ra được ∀xΦ. 2 luật với lượng từ tồn tại cũng được giảit thích tương tự, chỉ chú ý là ở ngoài hộp phải có điều kiện tồn tại để công thức nào đó đúng. Còn các luật (∧ei), (∧i), (∨ ei), (∨i), (→e),… là các luật về áp dụng với các trường hợp trong các bài chứng minh ví dụ là do tính thừa kế của logic vị từ với logic mệnh đề. Cách suy diễn hoàn toàn tương tự. 124