Ngữ nghĩa của luận lý mệnh đề

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:53

Thêm vào BST

Báo xấu

83
lượt xem 6
download

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

Tự thân đối tượng A, B không có “ý nghĩa” gì. Nó chỉ có ý nghĩa khi có chủ thể “nhìn” nó. • Chủ thể đứng ở đối tượng A nhìn đối tượng B, khác với khi chủ thể đứng ở đối tượng B nhìn đối tượng A.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ngữ nghĩa của luận lý mệnh đề

III. Ngữ nghĩa của luận lý mệnh đề Chương 2 ntsơn
Thái độ • Tự thân đối tượng A, B không có “ý nghĩa” gì. Nó chỉ có ý nghĩa khi có chủ thể “nhìn” nó. • Chủ thể đứng ở đối tượng A nhìn đối tượng B, khác với khi chủ thể đứng ở đối tượng B nhìn đối tượng A. A B A B ntsơn
Diễn dịch • Công thức của LLMĐ tự thân không có giá trị đúng sai. • Muốn có giá trị đúng sai của của công thức phải “nhúng” nó vào một thế giới thực. • Diễn dịch của một công thức là thế giới thực cùng với cách nhúng từng yếu tố của công thức vào thế giới thực đó. • Nói cách khác diễn dịch là “gán” cho công thức một ý nghĩa của thế giới thực mà nó được nhúng vào. ntsơn
Diễn dịch Thí dụ : Công thức ((H ∧ O) → W) chưa có giá trị đúng sai. Thế giới Luận lý mệnh đề … (H ∧ O) → W H Hồ Dzếnh là nhà thơ Nếu ∧ và → O Gái quê là 1 tập thơ H2 + O2 → H2O thì W Hồ Dzếnh là tác giả của Gái quê Thế giới thực (hoá học) Thế giới thực (văn học sử) ntsơn
Diễn dịch • Việc khảo sát công thức chỉ quan tâm đến giá trị đúng sai của công thức trong từng thế giới thực. • Dù số thế giới thực là vô hạn, nhưng mỗi công thức chỉ có hữu hạn các CTN, nên chỉ có hữu hạn trường hợp đánh giá đúng sai cho mỗi công thức trong mọi thế giới thực. ntsơn
Diễn dịch • Có thể đặc trưng diễn dịch của LLMĐ bằng 1 hàm đánh giá ν trên các CTN có trong công thức. Thí dụ : Qui ước CT đúng có giá trị 1 và sai là 0. Công thức (P ∧ Q) → R có diễn dịch I được đặc trưng bằng hàm đánh giá ν như sau : ν(P) = 1, ν(Q) = 0, ν(R) = 1. • Để tiện cho việc trình bày, còn sử dụng ký hiệu νF thay cho ν(F). ntsơn
Thực trị của một công thức • Nếu νA = 1, νB = 0 và νC = 0 thì ν((A→B) ∧ (C ∨¬A)) là đúng hay sai ?. Nếu νA = 0, νB = 1 và νC = 0 thì ν((¬A ∨ B) → ¬C) là đúng hay sai ?. Nếu νA = 0, νB = 1, νC = 0 và νD = 1 thì ν(((A ∨ C) ∧ B) → ¬D) là đúng hay sai. Cần phải xác định qui tắc đánh giá của các toán tử : ∨, ∧, ¬, →. ntsơn
Bảng thực trị • P, Q là các công thức nguyên. ¬P P∨Q P∧Q P→Q P Q 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 • Tất cả diễn dịch của một công thức trong LLMĐ tướng ứng với các dòng của bảng thực trị. ntsơn
Bảng thực trị • Một cách định nghĩa khác, bảng thực trị là một hàm trên tập 2 phần tử đúng, sai ({đ, s}). • Các toán tử luận lý là các hàm : ¬ : {đ, s} → {đ, s} ∧ : {đ, s} × {đ, s} → {đ, s} ∨ : {đ, s} × {đ, s} → {đ, s} → : {đ, s} × {đ, s} → {đ, s} ntsơn
Thực trị của một công thức Thí dụ : Tính thực trị của công thức (X → (¬Y∨Z)) ∧ ¬X ¬Y∨Z X→(¬Y∨Z) X Y Z CT 1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 1 ntsơn
Thủ tục số học • Chuyển công thức vào để tính thực trị. ν(P ∨ Q) = νP + νQ + νPνQ trong Z2, ν(P ∧ Q) = νPνQ trong Z2, ν¬P = 1 + νP trong Z2, ν(P → Q) = 1 + νP + νPνQ trong Z2. • Hệ quả : νP + νP = 0. νP.νP = νP. ν¬P.νP = 0. ntsơn
Thực trị của một công thức Thí dụ : tính thực trị của công thức (X → (¬Y ∨ Z)) ∧ ¬X ν((X → (¬Y ∨ Z)) ∧ ¬X) = ν(X → (¬Y ∨ Z))ν(¬X) = (1 + νX + νXν(¬Y ∨ Z))ν(¬X) = (1 + νX + νX.(ν(¬Y) + νZ + ν(¬Y)νZ))ν(¬X) = (1 + νX + νXν(¬Y) + νXνZ + νXν(¬Y)νZ)ν(¬X) = ν(¬X) + ν(¬X)νX + ν(¬X)νXν(¬Y) + ν(¬X)νXνZ + ν(¬X)νXν(¬Y)νZ = ν(¬X) + 0 + 0.ν(¬Y) + 0.νZ + 0.ν(¬Y)νZ = ν(¬X) = 1 + νX. ntsơn
Cây phân tích • Cây phân tích (parse tree) là biểu diễn bằng đồ thị có gốc của một công thức. • Đường là hành trình đi từ gốc đến đỉnh lá. Thí dụ : (X → (¬Y ∨ Z)) ∧ ¬X ∧ → ¬ ∨ X X ¬ Z Y ntsơn
Cây phân tích • Chiều cao (height) của 1 cây phân tích là chiều dài của con đường dài nhất cộng 1. Thí dụ : ¬ ∧ ∧ → ¬ → → ∨ X X ¬ ∨ Z X Y Z Chiều cao là 4 Z Y X Chiều cao là 5 ntsơn
Cây phân tích • Đánh giá CT nhờ cây phân tích. Thí dụ : Đánh giá công thức (X → (¬Y ∨ Z)) ∧ ¬X, với X, Y, Z lần lượt có giá trị đ, s, đ. s ∧ s đ→ ¬ đ đ đ ∨ X X đ¬ Z đ s Y ntsơn
Diễn dịch của LLMĐ • Diễn dịch trong LLMĐ có hữu hạn trường hợp đánh giá. A sai, B đúng A sai, B sai (A ∧ B) → ¬A A sai, B sai A đúng, B sai A đúng, B đúng • Số trường hợp tương ứng với với số dòng của bảng thực trị. ntsơn
Phân loại công thức • Dựa trên diễn dịch, các công thức được chia là 3 nhóm. Công thức hằng đúng Công thức khả đúng, khả sai Công thức hằng sai Không gian LLMĐ ntsơn
Phân loại công thức • I là diễn dịch của công thức X. X hằng đúng ↔ (∀I) νX = 1, trong I. X hằng sai ↔ (∀I) νX = 0, trong I. X khả đúng ↔ (∃I) νX = 1, trong I. ↔ (∃I) νX = 0, trong I. X khả sai Nhận xét : – Phủ định của một công thức hằng đúng là công thức hằng sai. – Công thức hằng đúng được gọi là tautology. ntsơn
Công thức tương đương • Công thức X và Y tương đương nếu đồng bộ trong việc đánh giá thực trị đối với mọi diễn dịch. Lấy diễn dịch I của X và Y. Nếu X đúng trong I thì Y cũng đúng trong I và ngược lại. Nếu X sai trong I thì Y cũng sai trong I và ngược lại. Ký hiệu X = Y. ntsơn
Mô hình • Mô hình I của công thức F là diễn dịch I của F và νF = 1 trong I. Chú ý : Diễn dịch = interpretation, valuation (tiếng Anh). Mô hình = model (tiếng Anh). Một số tài liệu dùng từ model cho khái niệm diễn dịch. ntsơn