Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ (Phần 3) - Nguyễn Thanh Sơn

Download

III. Ngữ nghĩa của

luận lý vị từ

ntsơn

Diễn dịch của 1 công thức

• Xác định một diễn dịch I cho công thức F là xác

định các yếu tố sau :

1. Chọn miền đối tượng D.

2. Định nghĩa các hàm (gán giá trị cho hằng).

3. Định nghĩa các vị từ của F.

Chương 3

ntsơn

Diễn dịch của 1 công thức

Thí dụ : F = x (p(x) → q(f(x), a)).

F có : hằng a, hàm f(_), vị từ p(_), q(_,_).

Một diễn dịch của F :

Chọn D = {1, 2, 3}. Chọn hằng a = 2.

Chọn f(1) = 2, f(2) = 1, f(3) = 3.

Chọn {p(1), p(2),  p(3)}.

Chọn {q(1,1), q(1,2), q(1,3),

q(2,1), q(2,2), q(2,3),

q(3,1), q(3,2), q(3,3)}.

Chương 3

ntsơn

Diễn dịch của 1 

Thí dụ :  = <R, F, C>

R = {}, F = {s(_), p(_,_)}, C = {}.

Diễn dịch I :

D = Z⁺,

I() = 0.

I(s) là hàm suc (phần tử kế) trong Z,

I(p) là hàm + trong Z.

Nếu x được gán 3 thì s(s() + s(x)) = 6.

Chương 3

ntsơn

Diễn dịch của 1 

Thí dụ :  = <R, F, C>.

R = {}, F = {s(_), p(_,_)}, C = {}.

Diễn dịch I :

D = {word | word là từ trên tập ký tự {a, b}},

I() = a.

I(s) là hàm kết nối ký tự a vào cuối từ,

I(p) là hàm kết nối 2 từ.

Nếu x được gán aba thì

s(s() + s(x)) = aaabaaa.

Chương 3

ntsơn

Diễn dịch của 1 

Thí dụ :

Drinkers paradox^[15]: There is someone in the

pub such that if he/she is drinking then

everybody in the pub is drinking.

More formally:

x (drink(x) → y drink(y)).

Prove that this formula is valid.

Chương 3

ntsơn

Đánh giá công thức trong 1 dd

• Công thức vị từ F = x p(x).

• Cho diễn dịch I :

D = {1, 2}, {p(1), p(2)}.

→ F gồm {p(1), p(2)} với p(1) đúng, p(2) sai.

 Vậy F là đúng hay sai trong dd I ?.

• Làm sao xác định tính đúng sai của công thức

trong luận lý vị từ ?.

Chương 3

ntsơn

Đánh giá công thức trong 1 dd

• Tính đúng, sai của công thức đóng trong một

diễn dịch I được xác định nhờ lượng từ.

x F là đúng, nếu F đúng, x  D.

x F là đúng, nếu F[a/x] đúng, a  D.

 Không xác định được tính đúng, sai trong 1 diễn

dịch của công thức tự do.

• Khi nói một công thức F là đúng, hay sai nghĩa

là đúng hay sai trong một diễn dịch.

Diễn dịch có thể không được nhắc đến nhưng

phải được ngầm hiểu.

Chương 3

ntsơn

Đánh giá CT đóng trong 1 dd

Thí dụ :

F = x y ( (p(x)  q(y)) → (t q(t)  z q(z)) )

Cho diễn dịch : D = {, }, {p(), p(), q(), q()}.

• Lấy x = ,

* lấy y =  : p()q() → (t)q(t)(z)q(z).

(1  1) → (1  1) = 1.

* lấy y =  : p()q() → (t)q(t)(z)q(z).

(1  1) → (1  1) = 1.

Chương 3

ntsơn

Đánh giá CT đóng trong 1 dd

• Lấy x = ,

* lấy y =  : (p()q()) → (t q(t)  z q(z)).

(0  1) → (1  1) = 1.

* lấy y =  : (p()q()) → (t q(t)  z q(z)).

(0  1) → (1  1) = 1.

Vậy công thức F đúng trong diễn dịch trên.

Chương 3

ntsơn

Đánh giá CT đóng trong 1 dd

Thí dụ :

F = x y ( (p(x)  q(y)) → (t q(t)  z q(z)) )

Diễn dịch I :

D = {, , },

{p(), p(), p(), q(), q(), q()}.

Lấy x = ,

lấy y =  : (p()  q()) → (t q(t)  z q(z)).

(1  1) → (1  0).

Vậy công thức F sai trong diễn dịch I.

Chương 3

ntsơn

Ngữ nghĩa

• Các khái niệm :

Hằng đúng

Hằng sai

Khả đúng-Khả sai

Mô hì nh

Tương đương (=)

Hệ quả luận lý (╞═)

được định nghĩa tương tự như trong LLMĐ.

Chương 3

ntsơn

Ngữ nghĩa

Nhận xét :

Các định nghĩa hằng sai, hằng đúng, khả đúng,

khả sai, mô hình, tương đương, hệ quả luận lý

là working trong LLMĐ nhưng non-working

trong LLVT.

Chương 3

ntsơn

Công thức tương đương

• F, P là công thức và P không chứa hiện hữu tự

do của x (đối với P).

1. (x F)  P = x (F  P)

1'. (x F)  P = x (F  P)

2. (x F)  P = x (F  P)

2'. (x F)  P = x (F  P)

Chương 3

ntsơn

Công thức tương đương

Chứng minh : (x F)  P = x (F  P)

Tương đương với việc chứng minh 2 bài toán :

1. (x F)  P ╞═ x (F  P)

2. x (F  P) ╞═ (x F)  P

Các công thức tương đương khác được chứng

minh tương tự.

Chương 3

ntsơn

Công thức tương đương

Chứng minh : (x F)  P ╞═ x (F  P)

Lấy 1 mô hình I của (x F)  P.

Nếu (x F) đúng thì F[/x]  P đúng D_I

(D_Ilà miền đối tượng của I).

Do đó x (F  P) đúng.

Nếu (x F) sai thì P phải đúng.

Do đó F[/x]  P đúng D_I,

hay x (F  P) đúng.

Vậy (x F)  P ╞═ x (F  P)

Chương 3

ntsơn

Công thức tương đương

Thí dụ :

(x p(x))  q(y) = x (p(x)  q(y))

(x p(x)  q(x))  r(y) = x ((p(x)  q(x))  r(y) )

(x p(x))  q(x, y)  x (p(x)  q(x, y))

vì q chứa hiện hữu tự do của x.

q(y, z)  x p(x, y) = x (q(y, z)  p(x, y))

Chương 3

ntsơn

Hội giao mở rộng

• Hôi, giao mở rộng.

Ký hiệu A_iI= A₁ A₂ A₃,

A_iI= A₁ A₂ A₃, với I = {1, 2, 3}

Định nghĩa giao mở rộng :

x  A_iI i (x  A_i)

Định nghĩa hội mở rộng :

x  A_iI i (x  A_i)

Chương 3

ntsơn

Công thức tương đương

Thí dụ minh họa ứng dụng công thức

(xF)  P = x (F  P)

A₁, A₂, A₃, B là các tập hợp.

Đặt I = {1, 2, 3} và B_i= (A_i B)

(A₁A₂A₃)  B = (A₁B)  (A₂B)  (A₃B )

viết lại A_i B = B_i.

Chương 3

ntsơn

Công thức tương đương

Thí dụ :

Chứng minh A_i B  B_i.

Lấy x  A_iI B,

→ (x  A_iI)  (x  B)

→ i (x  A_i)  (x  B)

Đặt p(i) = “x  A_i”, q = “x  B”

→ i p(i)  q

→ i (p(i)  q) vì ((x F)  Q = x (F  Q))

→ x  B_i.

Chương 3

ntsơn

Tải về để xem bản đầy đủ

48 trang myanh 23180 Free

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ (Phần 3) - Nguyễn Thanh Sơn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

bai_giang_luan_ly_toan_hoc_chuong_3_luan_ly_vi_tu_phan_3_ngu.ppt