Bài giảng : Logic part 7

Slide 4.12: Ví dụ “mọi con trai của bố tôi là anh của tôi” Nó có nhiều cách để dịch, ví dụ:  (bố là vị từ) cho m miêu tả “tôi”, S(x,y)=”x là con của y”, F(x,y)= “x là bố của y”, và B(x,y)= “x là anh của y”; câu trên được mô tả bằng: ∀x∀y(F(x,m)∧S(y,x)→B(y,m)) hoặc:  (bố là hàm) giống như trên, nhưng f(x) miêu tả “bố của x”; câu trên được mô tả bằng: ∀x(S(x,f(m))→B(x,m)) ...
Nội dung trích xuất từ tài liệu:
Bài giảng : Logic part 7Slide 4.11: …công thức:Trong dạng biểu diễn Backus-Naur ta có thể viết:Φ::=P(t,…,t)| ⊥|( Φ)|(Φ∧Ψ)|(Φ∨Ψ)|(Φ→Ψ)|(∀xΦ)|(∃xΦ) với P là một vị từ n ngôi, t là term, x là các biến.Để cho tiện:  ,∀x và ∃x được ưu tiên hơn  sau đó đến ∧ và ∨  sau đó đến →. 79Slide 4.12: Ví dụ“mọi con trai của bố tôi là anh của tôi”Nó có nhiều cách để dịch, ví dụ:  (bố là vị từ) cho m miêu tả “tôi”, S(x,y)=”x là con của y”, F(x,y)= “x là bố của y”, và B(x,y)= “x là anh của y”; câu trên được mô tả bằng: ∀x∀y(F(x,m)∧S(y,x)→B(y,m))hoặc:  (bố là hàm) giống như trên, nhưng f(x) miêu tả “bố của x”; câu trên được mô tả bằng: ∀x(S(x,f(m))→B(x,m)) 80Slide 4.13: từ ngôn ngữ tự nhiên sang logics và ngược lạiPhép tính vị từ là rõ ràng, trong khi ngôn ngữ tự nhiên là mơ hồ hơn. Vì vậy:-(1)việc đọc công thức (từ logic sang ngôn ngữ tự nhiên) là dễ dàng, rõ ràng,nhưng chuyển một câu trong ngôn ngữ tự nhiên sang công thức logic(vị từ) thìnhiều vấn đề phải bàn hơn (một số sẽ trở nên khó hơn nhiều, một số khôngtương đương, nhiều khi phải loại bỏ).-(2)trong toán học một số lúc dưới những ví dụ đã cho rằng có chỉ một loại logic(phép tính vị từ hoặc logic bậc nhất cổ điển) trong nhiều trường hợp đóng vớingôn ngữ tự nhiên- giống khoa học máy tính hay triết học-, nhưng 1 trongnhững vấn đề mâu thuẫn là : có nhiều loại logics khác bao gồm: logic trực giác,logic hẹp, logic hình thức, logic thời gian, logic tin tưởng, logic động học, logicHoare, logic đặc biệt, logic xác định, logic bậc cao, logic chùm, logic thaythế,…một số được biết với nhiều phiên bản. 81Slide 4.14: biến tự do và biến buộc – ví dụ  Một biến x xuất hiện trong ∀xQ(x) là material hay buộc bởi ∀ (nó giống như trong phép tính: 0 sin xdx thì biến x bị buộc bởi  ). 1  Để xác minh xem ∀xQ(x) là đúng nghĩa là thay x bởi mọi khả năng xảy ra của nó và kiểm tra xem Q có thoả mãn tất cả chúng.  Tương tự với ∃xQ(x), nhưng trong trường hợp này ∃xQ(x) là đúng khi Q thoả mãn tối thiểu một giá trị cụ thể của x. 82Slide 4.15: biến tự do và biến buộc – ví dụNói một cách ngắn gọn:  Ta sẽ giải thích ∀x như một dãy tham số vô hạn phụ thuộc nhau : ∀xP(x)=P(a1)∧P(a2)∧P(a3)∧ ... với a1, a2, a3,… được giả sử là danh sách tất cả các giá trị có thể có của x.  Tương tự, ∃x sẽ được giải thích như dãy độc lập vô hạn: ∃xP(x)=P(a1)∨P(a2)∨P(a3)∨ … với a1, a2, a3,… được giả sử như trên. 83Slide 4.16: biến buộc và biến tự do- hình thứcCho Φ là một công thức trong logic vị từ.  Sự xuất hiện của x trong Φ gọi là tự do trong Φ nếu nó là lá con trong cây cú pháp của Φ để sao cho không có đường nào lên đến đỉnh từ gốc x lại qua một gốc có ∀x hoặc ∃x.  Sự xuất hiện của x trong Φ không tự do được gọi là buộc.Ví dụ: (để cho tiện: xanh mô tả tự do, đỏ mô tả buộc) trong: S(x,y)∧∀x(P(x)→Q(x))sự xuất hiện của biến x trong P và Q là buộc bởi ∀; trong trường hợp còn lại, sựxuất hiện của y và sự xuất hiện của x trong S là tự do.Phát biểu chính xác, ta không có biến tự do và biến buộc(như trong tiêu đề) nhưng có khái niệm sựxuất hiện tự do và/hoặc buộc của biến. Một biến có thể có cả hai trường hợp là xuất hiện tự do vàbuộc trong cùng một biểu thức (giống như x trong ví dụ trên), nhưng một sự xuất hiện của mộtbiến sẽ hoặc là tự do hoặc là buộc (không thể cả hai). 84Slide 4.17: Phép thếĐịnh nghĩa:  Cho một biến x, một term t, và một công thức Φ, ta xác định Φ*t/x+ là một công thức đạt được bằng việc thay mỗi sự xuất hiện tự do của biến x trong Φ bằng t.Ví dụ{S(x,y)∧∀x(P(x)→Q(x))} [f(x,y)/x]=S(f(x,y),y)∧∀x(P(x)→Q(x)){S(x,y)∧∀x(P(x)→Q(x))} [y/x]=S(y,y)∧∀x(P(x)→Q(x))Thế còn:{∃yS(x,y)∧∀x(P(x)→Q(x))} [f(y)/x]=∃yS(f(y),y)∧∀x(P(x)→Q(x)) ?? 85Slide 4.18: Cảnh báo: mâu thuẫn giữa các biếnTa sẽ bác bỏ:{∃yS(x,y)∧∀x(P(x)→Q(x))} [f(y)/x]=∃yS(f(y),y)∧∀x(P(x)→Q(x))Lí do: Nghĩa của biểu thức đã thay đổi ngoài ý muốn: term mới f(y) (cái đã thay x)làm ∀y buộc nhiều sự xuất hiện của biến hơn trong công thức gốc Φ.Những term khác:-Trong công thức Φ gốc thì sự xuất hiện đầu tiên của x là tự do, vì vậy Φ có giátrị đúng hay sai là độc lập với giá trị của x này.-Giả thiết này sẽ phải được duy trì bởi phép thế x bởi f(y), tức tương ứng với sựxuất hiện của biến y phải là tự do và giá trị thật của công thức phải độc lập với y.-Tuy nhiên, trong ∃yS(f(y),y)∧∀x(P(x)→Q(x)) thì lại không có sự xuất hiện nàocủa y là tự do, nên giá trị thật của nó không độc lập với y. 86Slide 4.19: mâu thuẫn giữa các biến- ...