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. 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ả...
Nội dung trích xuất từ tài liệu:
Bài giảng : Logic part 6Trang 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ạiKhô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. 66Trang 27: CompactnessBâ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ứngminh 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 α∉∆. 67Trang 28: CompactnessHệ 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 Σ⊨α. 68LESSON 4: PHÉP TÍNH VỊ TỪ CÚ PHÁP VÀ NGỮ NGHĨA (từ slide 4.2 đến slide 4.30) 69Slide4.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ẻ”,… 70Slide 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ả “xSlide 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) 72Slide 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) 73Slide 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⊨ Ψ 74Slide 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 ...