Bài giảng : Logic part 6

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

Thêm vào BST

Báo xấu

136
lượt xem 28
download

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

Trang 26: Compactness Cho Σ là tập thoả mãn được hữu hạn. Ta mở rộng Σ thành tập ∆ thoả mãn được lớn nhất như sau: Cho α1,…, αn,… là một tập cố định danh sách tất cả các công thức xây dựng đúng. Tại sao có thể? Tập tất cả các dãy của một tập đếm được là đếm được. T Không khó để chứng minh rằng mọi ∆n là thoả mãn được hữu hạn (bài tập về nhà). Cho ∆ =∪n∆n. Rõ ràng rằng: 1.Σ⊂ ∆ 2.α∈∆ hoặc  αn với mọi wff α và 3.∆ là thoả...

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 6

Trang 26: Compactness Cho Σ là tập thoả mãn được hữu hạn. Ta mở rộng Σ thành tập ∆ thoả mãn được lớn nhất như sau: Cho α1,…, αn,… là một tập cố định danh sách tất cả các công thức xây dựng đúng. Tại sao có thể? Tập tất cả các dãy của một tập đếm được là đếm được. Thì, cho: ∆0 = Σ ∆n∪,αn+1} Nếu tập này là thoả mãn được { ∆n+1= ∆n∪{  αn+1} Ngược lại Không khó để chứng minh rằng mọi ∆n là thoả mãn được hữu hạn (bài tập về nhà). Cho ∆ =∪n∆n. Rõ ràng rằng: 1.Σ⊂ ∆ 2.α∈∆ hoặc  αn với mọi wff α và 3.∆ là thoả mãn được hữu hạn. 66
Trang 27: Compactness Bây giờ ta chứng minh rằng ∆ là thoả mãn được (và vậy nên Σ ⊂ ∆ cũng là thoả mãn được). Xác định một phép gán v như sau. Với mỗi kí hiệu mệnh đề Ai: v(Ai)=1 khi và chỉ khi Ai∈∆ Ta khẳng định rằng mọi công thức wff α, v thoả mãn α khi và chỉ khi α∈∆. Ta chứng minh bằng quy nạp trên các công thức xây dựng đúng. Trường hợp cơ sở: Dẫn đến từ định nghĩa của v. Trường hợp quy nạp: Ta sẽ xem xét một trường hợp. Giả sử α=β∧γ. Thì v (α)=1 khi và chỉ khi cả hai v (β)=1 và v (γ)=1 khi và chỉ khi β∈∆ và γ∈∆. Bây giờ, nếu cả hai β và γ thuộc ∆, thì từ ,β,γ,  α- là không thoả mãn được, ta phải có α ∈∆ . Tương tự, nếu một trong hai β và γ không thuộc ∆, thì phủ định của nó phải thuộc ∆, nên α∉∆. 67
Trang 28: Compactness Hệ quả: Nếu Σ⊨α thì có một tập hữu hạn Σ0⊂Σ để Σ0⊨α. Chứng minh: Giả sử rằng Σ0 αvới mọi tập hữu hạn Σ0⊂Σ. Thì Σ0∪{  α- là thoả mãn được với mọi Σ0⊂Σ. Nên theo định lí compactness, Σ∪{  α- là thoả mãn được trái với giả thiết Σ⊨α. 68
LESSON 4: PHÉP TÍNH VỊ TỪ CÚ PHÁP VÀ NGỮ NGHĨA (từ slide 4.2 đến slide 4.30) 69
Slide4.2: cần một ngôn ngữ phong phú hơn  Logic mệnh đề vừa đủ để phân phối với những câu hữu hạn tạo ra bằng việc sử dụng , , ,  .     Trên mô hình hữu hạn này có thể đủ để phân phối với “tồn tại”, “mọi”, “trong số”, “chỉ”. Ví dụ: nếu 3 sinh viên A,B và C với p= “A có mũ đỏ”, q= “B có mũ đỏ”, r= “C có mũ đỏ”, công thức “tồn tại một sinh viên có mũ đỏ” có thể mô hình hoá bằng p∨q∨r.  Trên những mô hình vô hạn có thể có những công thức vô hạn; ví dụ: “mọi số tự nhiên là chẵn hoặc lẻ” có thể dịch như sau (p0∨q0)∧(p1∨q1)∧(p2∨q2)… với p0= “0 là số chẵn”, q0= “0 là số lẻ”, p1= “1 là số chẵn”, q1= “1 là số lẻ”,… 70
Slide 4.3: Khoá đặc trưng  Logic vị từ (cũng được biết đến như logic bậc nhất) là một sự mở rộng của logic mệnh đề sử dụng biến thay cho đối tượng.  Ta sử dụng x với “x là một số tự nhiên”; biểu thức trên có thể viết ngắn gọn như sau: ∀(E(x)∨O(x)) với E(x)= “x là số chẵn” và O(x)= “x là số lẻ”  Những biến này được lien kết với kí hiệu hàm để miêu tả những đối tượng mới và với kí hiệu vị từ để mô tả mối quan hệ giữa các đối tượng. Ví dụ: nếu s(x) là hàm phần tử tiếp theo L(x,y) mô tả “x
Slide 4.4: Những ví dụ:  “Không phải tất cả chim có thể bay”: cho B(x) mô tả “x là một con chim” và F(x) mô tả “x có thể bay”; câu trên có thể miêu tả bằng công thức: (∀x(B(x)→F(x))   Tất cả đàn ông đều phải chết. Socrates là đàn ông. Theo đó, Socrates phải chết. Cho H(x) mô tả “x là đàn ông”, M(x) mô tả “x phải chết”, và s mô tả Socrates; Câu trên được miêu tả bằng suy siễn: ∀x(H(x)→M(x)),H(s)├ M(s)  Andy và Paul có cùng bà ngoại: ta sử dụng a và p cho Andy và Paul và M(x,y) cho “x là mẹ của y”; câu trên có thể được mô hình như sau: ∀x∀y∀u∀v(M(x,y)∧M(y,a)∧M(u,v)∧M(v,p)→ x=u) 72
Slide 4.5: ...ví dụ  Trong ví dụ trước ta cần dấu bằng – hình thức này được biết như là logic vị từ với dấu bằng.  Trong một số trường hợp (bao gồm cả trường hợp trên) các công thức có thể được đơn giản hoá bằng việc sử dụng hàm. Nếu m(x) mô tả mẹ của x (nó chỉ xác định một giá trị ứng với một giá trị của miền, vì thế nó thực sự là một hàm), thì câu ở ví dụ trên có thể được mô hình đơn giản hơn: m(m(a))=m(m(p))  Ann thích anh của Mary là có vẻ mơ hồ và có thể dịch như sau: ∃x(B(x,m)∧L(a,x)) (Ann thích một trong các anh trai của Mary) hoặc ∀x(B(x,m)→L(a,x)) (Ann thích tất cả anh trai của Mary) 73
Slide 4.6: Tính đúng và đầy đủ:  Ta sẽ mở rộng cả hai suy diễn tự nhiên ‘├’ và dãy suy diễn chuẩn ‘⊨’ đến phép tính vị từ.  Một kết quả cơ bản từ định lí về tính đúng và đầy đủ: Φ1, Φ2,…, Φn├ Ψ khi và chỉ khi Φ1, Φ2,…, Φn⊨ Ψ 74
Slide 4.7: Logic vị từ như một dạng ngôn ngữ Có 2 thành phần:  Những đối tượng: chúng được miêu tả bởi các terms, ví dụ: những hằng riêng biệt như a, p hay sử dụng kí hiệu hàm (ví dụ: ma(a) cũng là một đối tượng).  Những vị từ/ giá trị thật của quan hệ: chúng được mô tả bởi các công thức; một công thức thể hiện một mối quan hệ giữa các đối tượng; với việc đưa đối tượng và các công thức có thể nhận được giá trị đúng hoặc sai. Dạng này bắt đầu với việc kiến trúc nên các term, sau đó định nghĩa các công thức logic vị từ. Tập từ vựng bao gồm: -Một tập P các kí hiệu vị từ. -Một tập F các kí hiệu hàm. -Một tập C các kí hiệu hằng. (một số dạng trong C được gộp vào trong F: một hằng được coi như một biểu thức 0 ngôi). 75
Slide 4.8: Các Term Các term được xác định như sau:  Mọi biến là term  Mọi hằng trong C là term  Nếu t1, t2,…,tn là các term và f∈F là một hàm n ngôi, thì f(t1,t2,..,tn) là một term.  Không gì nữa là một term. Trong dạng biểu diễn Backus-Naur ta có thể viết: t::= x|c|f(t,t,…t) với x là biến, c∈C, f∈F là hàm n ngôi. 76
Slide 4.9: Cây cú pháp: 77
Trang 4.10: Những công thức: Những công thức trên (F,P) được xác định một cách quy nạp bằng việc sử dụng tập các term trên F như sau:  Nếu P là một vị từ trong P với n ngôi (n≥1) và t1, t2,…, tn là các term trên F, thì P( t1, t2,…, tn) là một công thức.  Nếu Φ là một công thức, thì ( Φ) cũng vậy.   Nếu Φ và Ψ là các công thức, thì (Φ∧Ψ), (Φ∨Ψ) và (Φ→Ψ).  Nếu Φ là một công thức và x là biến, thì (∀xΦ) và (∃xΦ) là một công thức.  Không gì nữa là công thức. 78