Bài giảng : Logic part 8

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

Thêm vào BST

Báo xấu

101
lượt xem 22
download

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

Những quy tắc này được sinh ra từ luật ∧. Chú ý với luật (∀xi): trong luật này, hộp bắt đầu với một biến “fresh” x0 , biến này không xuất hiện ở bất cứ đâu ngoài hộp. Nếu công thức Φ đúng cho phần từ sinh ra đó, thì nó đúng cho tất cả các terms.

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 8

Slide 4.24: Tính chất của dấu bằng: Dấu bằng có Tính phản xạ : ├ t=t Tính đối xứng: t1=t2├ t2=t1 1. t1=t2 Tiền đề 2. t1=t1 (=i) 3. t2=t1 (=e) do 1,2 (với Φ là “x=t1”) Tính bắc cầu: t1=t2, t2=t3├t1=t3 1. t2=t3 Tiền đề 2. t1=t2 Tiền đề 3. t1=t3 (=e) do 1,2 (với Φ là “t1=x”) 92
Slide 4.25: Mở rộng các quy tắc cho logic vị từ: Quy tắc chứng minh với lượng từ toàn thể: x ∀x: [t / x] (xe) (∀ xi) Những quy tắc này được sinh ra từ luật ∧. Chú ý với luật (∀xi): trong luật này, hộp bắt đầu với một biến “fresh” x0 , biến này không xuất hiện ở bất cứ đâu ngoài hộp. Nếu công thức Φ đúng cho phần từ sinh ra đó, thì nó đúng cho tất cả các terms. 93
Slide 4.26: Lượng từ toàn thể- Những ví dụ(1) Ví dụ 1: P(t), ∀x(P(x)→ Q(x))├ Q(t)   1 P(t) Tiền đề 2 ∀xP(x) Tiền đề 3 P(t)→ Q(t) (∀xe) do 2  (→e) do 3,1 4 Q(t)  94
Slide 4.27: Lượng từ toàn thể- Những ví dụ(2) Ví dụ 2: ∀x(P(x)→Q(x)),∀xP(x)├ ∀xQ(x) ∀x(P(x)→Q(x)) 1 Tiền đề ∀xP(x) 2 Tiền đề P(x0)→ (∀xe) do 1 3 x0 Q(x0) P(x0 (∀xe) do 2 4 Q(x0) (→e) do 3,4 5 ∀xQ(x) (∀xi) do 3-5 6 95
Slide 4.28: Quy tắc chứng minh với lượng từ tồn tại Quy tắc chứng minh với lượng từ tồn tại: ∃x: (∃xe) [t / x] (xi ) x Quy tắc này sinh ra từ quy tắc ∨. Chú ý với luật (∃xe): lần này, hộp cũng bắt đầu với biến “fresh” x0, biến này không xuất hiện ở bất cứ đâu ngoài hộp. Nếu công thức ∃xΦ là đúng thì Φ đúng trong một trường hợp cụ thể nào đó của x. Để có kết luận là  ta cần chứng minh trên toàn bộ các khả năng xảy ra các giá trị của x. Nên hộp bắt đầu với Φ đúng để với phần tử thoả mãn điều kiện này sẽ dẫn đến kết luận  . 96
Slide 4.29: Lượng từ tồn tại – Ví dụ (1) Ví dụ 1: ∀xΦ├ ∃xΦ 1 ∀xΦ Tiền đề (∀xe) do 1 2 Φ*x0/x] 3 ∃xΦ (∃xi) do 2 97
Slide 4.30: lượng từ tồn tại – ví dụ(2) Ví dụ 2: ∀x(P(x)→Q(x)), ∃xP(x)├∃xQ(x) ∀x(P(x)→Q(x)) 1 Tiền đề ∃xP(x) 2 Tiền đề 3 x0 P(x0) Giả sử P(x0)→Q(x0) (∀xe) do 1 4 Q(x0) (→e) do 4,3 5 ∃xQ(x) (∃xi) do 5 6 ∃xQ(x) (∃xe) do 2,3- 7 6 98
LESSON 5: PHÉP TÍNH VỊ TỪ ĐỊNH LÍ CHỨNG MINH VÀ NGỮ NGHĨA (từ slide 5.2 đến 5.20) 99
Slide 5.2: Suy diễn tự nhiên Những quy tắc mới (cho dấu bằng, cho lượng từ toàn thể và lượng từ tồn tại) t  t [t / x] ( e) 1 2 1 [t / x] =: ( i ) t t 2 ∀x: (∀ xi) x (xe ) [t / x] ∃x: (∃xe) [t / x] (xi ) x 100
Slide 5.3: Ví dụ: Ví dụ 1: ∀x(Q(x)→R(x)), ∃x(P(x)∧Q(x))├∃x(P(x)∧R(x)) ∀x(Q(x)→R(x)) 1 Tiền đề ∃x(P(x)∧Q(x)) 2 Tiền đề P(x0)∧Q(x0) 3 Giả sử x0 (∧e2) do 3 4 Q(x0) Q(x0)→R(x0) (∀xe) do 1 5 (→e) do 4,5 6 R(x0) (∧ e1) do 3 7 P(x0) P(x0)∧Q(x0) (∧i) do 7,6 8 ∃x(P(x)∧R(x)) (∃xi) do 8 9 ∃x(P(x)∧R(x)) (∃xe) do 2,3-9 10 Dịch sang ngôn ngữ tự nhiên: Nếu tất cả các tín đồ là theo chủ nghĩa cải lương và nếu có một người theo đạo tin lành là tín đồ, thì có một người theo đạo tin lành cũng theo chủ nghĩa cải lương. 101
Slide 5.4: … ví dụ Ví dụ: ∃xP(x), ∀x∀y(P(x)→Q(y))├∀yQ(y) ∃xP(x) 1 Tiền đề ∀x∀y(P(x)→Q(y)) 2 Tiền đề 3 y 0 4 x0 P(x0) Giả sử ∀y(P(x0)→Q(y)) (∀xe) do 2 5 P(x0)→Q(y0) (∀ye) do 5 6 (→e) do 6,4 7 Q(y0) (∃xe) do 1,4-7 8 Q(y0) ∀yQ(y) (∀yi) do 3-8 9 102
Slide 5.5: … ví dụ Ví dụ 3( chứng minh lỗi): ∃xP(x), ∀x(P(x)→Q(x))├∀yQ(y) ∃xP(x) 1 Tiền đề ∀x(P(x)→Q(x)) 2 Tiền đề 3 x0 4 x0 Giả sử P(x0) P(x0)→Q(x0) (∀xe) do 2 5 Q(x0) (→e) do 5,4 6 Q(x0) (∃xe) do 1,4-6 7 ∀yQ(y) (∀yi) do 3-7 8 Lỗi chính: 2 hộp sử dụng cùng một biến “fresh” x0. 103
Slide 5.6: Những hằng hữu ích ∀xΦ┤├ ∃x Φ 2a ∀xΦ∧Ψ ┤├ ∀x(Φ∧Ψ) 1a   ∃xΦ ┤├ ∀x Φ 2b ∀xΦ∨Ψ ┤├ ∀x(Φ∨Ψ) 1b   3a ∀xΦ∧∀Ψ ┤ ∀x(Φ∧Ψ) ├ 2c ∃xΦ∧Ψ ┤ ∃x(Φ∧Ψ) ├ 3b ∃xΦ∨∃Ψ ┤├ ∃x(Φ∨Ψ) 2d ∃xΦ∨Ψ ┤ ∃x(Φ∨Ψ) ├ 4a ∀x∀yΦ┤├ ∀y∀xΦ 2e ∀x(Ψ→Φ)┤├ Ψ→∀Φ 4b ∃x∃yΦ┤ ∃y∃xΦ ├ 2f ∃x(Φ→Ψ)┤ ∀xΦ→Ψ ├ 2g ∃x(Ψ→Φ)┤ Ψ→∃Φ ├ 2h ∀ x(Φ→Ψ)┤├ ∃xΦ→Ψ Với các trường hợp 2 có điều kiện là x không tự do trong Ψ. Ta sẽ chứng minh một số trường hợp. Cách hay: tìm chứng minh tương tự trong trường hợp mệnh đề và chuyển chúng sang trường hợp vị từ. 104