Bài giảng : Logic part 7

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

Thêm vào BST

Báo xấu

121
lượt xem 22
download

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

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

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 7

Slide 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 →. 79
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)) 80
Slide 4.13: từ ngôn ngữ tự nhiên sang logics và ngược lại Phé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ông tươ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ới ngôn ngữ tự nhiên- giống khoa học máy tính hay triết học-, nhưng 1 trong nhữ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, logic Hoare, logic đặc biệt, logic xác định, logic bậc cao, logic chùm, logic thay thế,…một số được biết với nhiều phiên bản. 81
Slide 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. 82
Slide 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. 83
Slide 4.16: biến buộc và biến tự do- hình thức Cho Φ 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ột biến sẽ hoặc là tự do hoặc là buộc (không thể cả hai). 84
Slide 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)) ?? 85
Slide 4.18: Cảnh báo: mâu thuẫn giữa các biến Ta 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ào của y là tự do, nên giá trị thật của nó không độc lập với y. 86
Slide 4.19: mâu thuẫn giữa các biến- ví dụ cụ thể Cho những số tự nhiên, S(x,y): “x100”, Q(x): “x>10”. Công thức trong ví dụ trên trở thành: Φ(x)=∃y(x100)→(x>10)) và Φ(10) là đúng. Cho f(x)=2*x. với phép thế “không an toàn” *2*y/x+ ta có: Φ(2*y)=∃y(2*y 100)→(x>10)) Φ(10)= Φ(2*5) là sai. Sử dụng bản thay thế “an toàn” sau: Φ(2*y)=∃z(2*y 100)→(x>10)) và Φ(10)= Φ(2*5) là đúng, như trong công thức gốc. 87
Slide 4.20: Đổi tên biến Một cách giải quyết vấn đề trên là  thay tên biến buộc với một tên mới để bác bỏ mâu thuẫn. Trong trường hợp ví dụ trên ta có thể thay tên y bằng z ∃yS(x,y)∧∀x(P(x)→Q(x)) =∃zS(x,z)∧∀x(P(x)→Q(x)) Sau đó áp dụng phép thế: {∃zS(x,z)∧∀x(P(x)→Q(x))} [f(y)/x] =∃zS(f(y),z)∧∀x(P(x)→Q(x)) 88
Slide 4.21: Đổi tên biến Định nghĩa: Cho một term t, một biến x, và một công thức Φ, ta nói rằng t là tự do với x trong Φ nếu không lá x tự do nào xuất hiện trong phạm vi của ∀y hoặc ∃y với mọi y xuất hiện trong t. Thực sự: điều kiện này là đủ để phép thế là “an toàn” Ví dụ: ∃yS(x,y)∧∀x(P(x)→Q(x)) thì f(z) là tự do với x trong Φ, nhưng g(z,y) là không tự do với x trong Φ. 89
Slide 4.22: Suy diễn tự nhiên Quy tắc:  Logic vị từ là mở rộng của logic mệnh đề, nên tất cả các phép suy diễn tự nhiên trong logic mệnh đề nó sẽ được kế thừa.  Ta phải có them những luật mới để phân phối với lượng từ và với kí hiệu bằng. Vậy thì ta đang miêu tả ở đây là logic bậc nhất với dấu bằng. Thường thì logic vị từ ban đầu bắt đầu với trường hợp đơn giản hơn với việc không có dấu bằng. 90
Slide 4.23: Các quy tắc chứng minh với dấu bằng Các quy tắc chứng minh với dấu bằng t  t [t / x] ( e) 1 2 1 ( i ) [t / x] =: t t 2 Ví dụ: x+1=1+x, (x+1>1)→(x+1)>0 ├ (1+x>1)→(1+x>0) Tiền đề 1. 1+x=x+1 Tiền đề 2. (x+1>1)→(x+1>0) (=e) cho 1,2 3. (1+x>1)→(1+x>0) Công thức Φ sử dụng trong bước cuối là (x>1)→(x>0) 91