Bài giảng : Logic part 9

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

Thêm vào BST

Báo xấu

127
lượt xem 31
download

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

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.

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 9

Slide 5.7: Trường hợp 1a- tương tự chứng minh mệnh đề (p1∧p2) 1 Tiền đề  ( p1∧ p2) 2 Giả sử    3 p1 Giả sử  p1∧ p2 (∨i1) do 3 4   ⊥ 5 ( e) do 4,2  6 p1 RAA do 3-5 3’ p2 Giả sử  p1∧ p2 (∨i2) do 3’ 4’   ⊥ 5’ ( e) do  4’,2’ do 3’-5’ 6’ p2 RAA p1∧p2 (∧i) do 6,6’ 7 ⊥ 8 ( e) do 7,1  p1∧ p2 9 RAA do 2-8   105
Slide 5.8: Trường hợp 1a Trường hợp 1a: ∀xΦ┤ ∃x Φ ├   Chứng minh trái sang phải: ∀xΦ 1 Tiền đề  ∃x Φ 2 Giả sử   3 x0 4 Φ*x0/x] Giả sử  ∃x Φ (∃xi) do 4 5  ⊥ 6 ( e) do 5,2  7 Φ*x0/x] RAA do 4-6 ∀xΦ (∀xi) do 3-7 8 ⊥ 9 ( e) do 8,1  ∃x Φ 10 RAA do 2,9  106
Slide 5.9: Trường hợp 1a Trường hợp 1a: ∀xΦ┤ ∃x Φ ├   Chứng minh phải sang trái: ∃x Φ 1 Tiền đề  ∀xΦ 2 Giả sử 3 x0 Φ*x0/x] Giả sử  (∀xe) do 2 4 Φ*x0/x] ⊥ 5 ( e) do 3,4  ⊥ (∃xe) do 1,3-5 6 ∀xΦ 7 ( i) do 2-6   107
Slide 5.10: Trường hợp 2a Trường hợp 2a: ∀xΦ∧Ψ ┤ ∀x(Φ∧Ψ) ├ Chứng minh từ trái sang phải: ∀xΦ∧Ψ 1 Tiền đề (∧e1) do 1 ∀xΦ 2 (∧e2) do 1 3 Ψ (∀xe) do 2 4 x0 Φ*x0/x] Φ*x0/x]∧Ψ (∧i) do 4,3 5 (Φ∧Ψ)*x0/x] 6 do 5, vì x không tự do trong Ψ ∀x(Φ∧Ψ) (∀xi) do 3-6 7 108
Slide 5.11: Trường hợp 2a Trường hợp 2a: ∀xΦ∧Ψ ┤ ∀x(Φ∧Ψ) ├ Chứng minh phải sang trái: ∀x(Φ∧Ψ) 1 Tiền đề (Φ∧ (∀xe) do 1 2 x0 Φ*x0/x]∧ 3 2, vì x không tự do trong Ψ)*x0/x] Ψ Ψ e1) do 3 (∧ 4 Φ*x0/x] ∀xΦ (∀xi) do 2-4 5 (Φ∧Ψ)*t/x+ (∀xe) do 1 6 Φ*t/x+∧Ψ 7 6, do x không tự do trong Ψ (∧e2) do 3 8 Ψ ∀xΦ∧Ψ (∧i) do 7,5 9 109
Slide 5.12: Trường hợp 3b Trường hợp 3b: ∃xΦ∨∃Ψ ┤├ ∃x(Φ∨Ψ) Chứng minh từ trái sang phải: ∃xΦ∨∃Ψ 1 Tiền đề ∃xΦ 2 Giả sử 3 X0 Φ*x0/x] Giả sử Φ*x0/x]∨Ψ*x0/x] (∨i) do 3 4 (Φ∨Ψ)*x0/x] 5 Đồng nhất ∃x(Φ∨Ψ) (∃xi) do 5 6 ∃x(Φ∨Ψ) (∃xe) do 2,3-6 7 Tương tự với ∃xΨ 2’-7’ … ∃x(Φ∨Ψ) (∨e) do 1,2-7,2’-7’ 8 110
Slide 5.13: trường hợp 3b Trường hợp 3b: ∃xΦ∨∃Ψ ┤├ ∃x(Φ∨Ψ) Chứng minh từ phải sang trái: ∃x(Φ∨Ψ) 1 Tiền đề (Φ∨Ψ)*x0/x] 2 Giả sử x0 Φ*x0/x]∨Ψ*x0/x] 3 Đồng nhất 4 Φ*x0/x] Giả sử ∃xΦ (∃xi) do 4 5 ∃xΦ∨∃Ψ (∨i) do 5 6 4’-6’ … Tương tự với Ψ*x0/x] ∃xΦ∨∃Ψ (∨e) do 3,4-6,4’-6’ 7 ∃xΦ∨∃Ψ (∃xe) do 1,2-7 8 111
Slide 5.14: Ngữ nghĩa của logic vị từ Định nghĩa: cho F là một tập các kí hiệu hàm và P là một tập các kí hiệu vị từ (những hằng được gộp trong F). Một mô hình M với (F,P) bao gồm:  Một tập không rỗng A, là tập vũ trụ các giá trị cụ thể.  với mỗi f∈F là hàm n ngôi, một hàm cụ thể fM: An→A. và  với mỗi P∈P với n ngôi, tập con PM∈An. Khi n là 0, An bao gồm một phần tử duy nhất (vectơ rỗng). Vì vậy giải thích của fM được xác định duy nhất bởi fM có trả về giá trị trong A. Ngắn gọn, một kí hiệu hằng được giải thích như một giá trị trong A. 112
Slide 5.15: Mô hình số học Ví dụ: Cho F ={0,1,s,+,*} và P ={=,≤,
Slide 5.16: Chuỗi Ví dụ: Cho F ={e, .} và P ={≤}, với e là một hằng và cái còn lại là vị từ 2 ngôi. Mô hình M của chúng ta là:  Miền xác đinh: tập những chuỗi (những từ)  eM là ℰ từ rỗng; .M là chuỗi nối vào  ≤M mô hình quan hệ “ tiền tố của”, ví dụ ≤M (v,w) là đúng khi và chỉ khi v là tiền tố của w. 114
Slide 5.17: Giải nghĩa của term Mỗi term được giải thích như một giá trị, với điều kiện ta cung cấp đầy đủ giá trị cho các biến. Định nghĩa: một môi trường là một phép gán l làm những biến nào đó nhận một giá trị trong A. Ta sử dụng định nghĩa l*x→a+ cho môi trường xảy ra với l, làm giá trị x nhận giá trị a. Định nghĩa: Cho M là một mô hình với (F,P) và t là một term trên F . Thì ta miêu tả tM,l trong A được xác định theo quy tắc sau:  Nếu t là một biến x, thì tM,l là l(x);  Nếu t là một hằng f, thì tM,l là fM  Nếu t là f(t1,…,tn), thì tM,l= M (t1M ,l ,..., t n ,l ) M f 115
Slide 5.18: Giải nghĩa của công thức Định nghĩa: Cho M là một mô hình với (F,P), Φ là một công thức trên (F,P), và l là môi trường của các biến. Quan hệ thoả mãn M ⊨l Φ được xác định quy nạp bằng M ⊨l P(t1,…,tn) thoả mãn khi và chỉ khi (t ∈ PM M ,l ,..., t n ,l ) M 1 M ⊨l ∀xΨ thoả mãn khi và chỉ khi M ⊨l[x→a] Ψ thoả mãn với tất cả a∈A M ⊨l ∃xΨ thoả mãn khi và chỉ khi M ⊨l[x→a] Ψ thoả mãn với một số trường hợp a ∈A M ⊨l Ψ thoả mãn khi và chỉ khi M ⊨l Ψ không thoả mãn  M ⊨lΨ1∨Ψ2 thoả mãn khi và chỉ khi M ⊨l Ψ1 hoặc M ⊨l Ψ2 thoả mãn M ⊨lΨ1∧Ψ2 thoả mãn khi và chỉ khi M ⊨l Ψ1 và M ⊨l Ψ2 thoả mãn M ⊨lΨ1→Ψ2 thoả mãn khi và chỉ khi M ⊨l Ψ2 thoả mãn khi M ⊨l Ψ1 thoả mãn. 116
Slide 5.19: Ví dụ Ví dụ: Giả sử: F={alma} (alma là một hằng), P={loves} (loves là một vị từ 2 ngôi), và M là một mô hình xác định bởi: (1) tập A={a,b,c}; (2) alma giải nghĩa như là a; và (3) loves giải nghĩa như là ,(a,a),(b,a),(c,a)-. Kiểm tra trường hợp: Không người yêu nào của người yêu Alma yêu cô ấy. Giả sử công thức của ta là : Φ=∀x∀y(loves(x,alma)∧loves(y,x)→ loves(y,alma))  Trả lời đó là sai: M ⊨l[x→a,y→b] loves(x,alma)∧loves(y,x)→ loves(y,alma) là sai;  M ⊨l[x→a] ∀y(loves(x,alma)∧loves(y,x)→ loves(y,alma)) là sai;  M ⊨[] ∀x∀y(loves(x,alma)∧loves(y,x)→ loves(y,alma)) là sai.  Nếu loves được giải nghĩa như là ,(b,a),(c,b)- công thức lại thoả mãn. 117