LUẬN LÝ TOÁN HỌC - CHƯƠNG 3 (phần 1)

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

Thêm vào BST

Báo xấu

83
lượt xem 9
download

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

Luận lý vị từ Nội dung I. Cấu trúc của luận lý vị từ II. Suy luận tự nhiên trong luận lý vị từ III. Ngữ nghĩa của luận lý vị từ IV. Phân giải

Chủ đề:

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

Lưu

Nội dung Text: LUẬN LÝ TOÁN HỌC - CHƯƠNG 3 (phần 1)

Chương 3. Luận lý vị từ ntsơn
Nội dung I. Cấu trúc của luận lý vị từ II. Suy luận tự nhiên trong luận lý vị từ III. Ngữ nghĩa của luận lý vị từ IV. Phân giải Chương 3 ntsơn
I. Cấu trúc của luận lý vị từ ntsơn
Sự yếu kém của LLMĐ • Tam đoạn luận Nếu là người thì phải chết (= P). Socrates là người (= Q). Vậy Socrates phải chết (= R). Biểu diễn hình thức đánh mất sự liên kết ((P ∧ Q) → R) của 3 phát biểu trên. Chương 3 ntsơn
Biểu diễn bằng quan hệ • Chọn các quan hệ từ các mệnh đề P, Q, R : * quan hệ người(x) (ie, x là người). * quan hệ chết(x) (ie, x chết). • Khi đó các mệnh đề P, Q, R trở thành : Px = nếu người(x) thì chết(x). QSocrates = người(Socrates). RSocrates = chết(Socrates). Vậy ((PSocrates ∧ QSocrates) → RSocrates) Cần một miền D để x lấy giá trị trên đó. Chương 3 ntsơn
Biểu diễn bằng quan hệ Biểu diễn bằng luận lý mệnh đề : Socrates là danh nhân = A. Nguyễn Du là danh nhân = B. Cao Bá Quát là danh nhân = C. Biểu diễn bằng luận lý vị từ : danhnhân(x) = x là danh nhân, với x ∈ D = {Socrates, NguyễnDu, CaoBáQuát}. Vậy {A, B, C } ↔ {danhnhân(x)| x ∈ D}. Chương 3 ntsơn
Luận lý vị từ • Luận lý vị từ (LLVT) có các thuật ngữ tiếng anh tương ứng : first order logic (FOL), predicates logic. Chương 3 ntsơn
Cấu trúc của luận lý vị từ • Bảng ký tự : Tập hợp hữu hạn các ký tự. • Ký hiệu : Chuỗi hữu hạn ký tự. • Miền đối tượng : Ký hiệu hằng. Ký hiệu biến • Lượng từ : Phổ dụng ∀ : dạng sử dụng (∀x). Hiện hữu ∃ : dạng sử dụng (∃x) • Hàm : là ánh xạ giữa các miền đối tượng. • Vị từ. Chương 3 ntsơn
Vị từ • Vị từ là hàm : − Có miền ảnh là tập chân trị {1, 0}. − Không sử dụng làm thông số của hàm khác. − Chỉ kết hợp với toán tử logic. • Ảnh của hàm được gọi là biểu thức hàm. Thí dụ : Hàm : nhân(_,_), lớnhơn(_,_), yêunhau(_._). Biểu thức hàm : nhân(2, 3), lớnhơn(x, 3), lớnhơn(nhân(2, 3), 3), yêunhau(x, y). Chương 3 ntsơn
Khái niệm định nghĩa • Hình thức định nghĩa : Khái niệm cần định nghĩa ↔ Các điều kiện. • Ngôn ngữ tạo định nghĩa : Ngôn ngữ tự nhiên, lý thuyết tập hợp, luận lý toán học, ... • Sử dụng : Định lý được sử dụng như thế nào thì định nghĩa được sử dụng y như vậy. Chương 3 ntsơn
Khái niệm định nghĩa • Phân loại định nghĩa : 1. Non-working definition. 2. Working definition. Recursive, inductive definition : − Tập hợp điểm bắt đầu. − Tập hợp luật. Chương 3 ntsơn
Nguyên từ • Nguyên từ (term) : (i) Ký hiệu hằng (constant) là nguyên từ. (ii) Ký hiệu biến (variable) là nguyên từ. (iii) Nếu t1, ... , tn là nguyên từ thì biểu thức hàm f(t1, ... , tn) là nguyên từ. (với hàm f không là vị từ). Chương 3 ntsơn
Nguyên từ Thí dụ : Hằng a, b, c là nguyên từ. Biến x, y, z là nguyên từ. Biểu thức hàm f(a,x) là nguyên từ bởi hàm f(_,_). Biểu thức hàm g(y) là nguyên từ bởi hàm g(_). Biểu thức hàm h(g(y),a,x) là nguyên từ bởi hàm h(_,_,_), và g(_). Biểu thức hàm g(f(h(x, y, z), c)) là nguyên từ bởi hàm g(_), f(_,_), và h(_,_,_). Chương 3 ntsơn
Công thức nguyên • Nếu p là vị từ và t1, ... , tn là nguyên từ thì p(t1, ... , tn) là công thức nguyên. • Biểu thức vị từ là công thức nguyên. Thí dụ : p(x), p(a), p(f(a, x)) là các công thức nguyên. Chương 3 ntsơn
Công thức nguyên Thí dụ : Các nhà thơ tiền chiến : XuânDiệu, HoàngCầm, VănCao. Sử gia : Lê Văn Hưu. Vua : QuangTrung. Đặt vị từ p(x) = x là nhà thơ. p(x), x ∈{XDiệu, HCầm, VCao, LvHưu,QTrung}. p(x), p(XDiệu) là công thức nguyên. Chương 3 ntsơn
Công thức nguyên Nhận xét : Một công thức nguyên của LLVT. ⎥⎢ {công thức nguyên của LLMĐ}. Chương 3 ntsơn
Công thức hoàn hảo • Công thức hoàn hảo được gọi đơn giản là công thức. • Công thức : (i) Công thức nguyên là CT. (ii) CT kết hợp với ¬, ∧, ∨, → cũng là CT. (iii) CT kết hợp với (∀x), (∃x) cũng là CT. Sự kết hợp các yếu tố trên chỉ gồm hữu hạn phần tử. Chương 3 ntsơn
Phạm vi của lượng từ • Trong công thức (∀x F), F thuộc phạm vi ảnh hưởng của ∀x. • Trong công thức (∃x F), phạm vi ảnh hưởng của ∃x là F. Thí dụ : (∃y)(r(y)) ∧ (∀x)(p(x) → q(f(x), a)). Phạm vi của (∃y) là r(y), phạm vi của (∀x) là (p(x) → q(f(x), a)). Chương 3 ntsơn
Hiện hữu • Hiện hữu của một biến là sự xuất hiện của biến đó trong công thức. Thí dụ : ((∀x) p(x,y) ∧ q(t,y)) → (∃y)(r(x,y,z)) có 4 biến. Biến x có 2 hiện hữu, biến y có 3 hiện hữu. Biến z có 1 hiện hữu, biến t có 1 hiện hữu. • Hiện hữu ràng buộc là hiện hữu thuộc phạm vi của lượng từ có biến cùng tên với nó. • Hiện hữu tự do là hiện hữu không ràng buộc. Chương 3 ntsơn
Hiện hữu Thí dụ : ((∀x)(∀y) p(x, y, z)) ∧ ((∀z) q(y, z)) Hiện hữu ràng buộc Hiện hữu tự do (∀z p(z, y)) ∧ (∀x q(x, y, z)) Chương 3 ntsơn