LOGIC HÌNH THỨC
Nội dung chính : Trong chương này, chúng ta giới thiệu phép tính vị từ như một ngôn ngữ biểu diễn dùng cho Trí tuệ nhân tạo. Những ưu điểm của việc dùng phép tính vị từ bao gồm một ngữ nghĩa hình thức (formal semantics) được định nghĩa chính xác ...
Nội dung chính : Trong chương này, chúng ta giới thiệu phép tính vị từ như một ngôn ngữ biểu diễn dùng cho Trí tuệ nhân tạo. Những ưu điểm của việc dùng phép tính vị từ bao gồm một ngữ nghĩa hình thức (formal semantics) được định nghĩa chính xác cùng với các luật suy diễn vững chắc và đầy đủ. Chương này bắt đầu bằng việc nhắc lại phép tính mệnh đề, định nghĩa cú pháp và ngữ nghĩa của phép tính vị từ. Tiếp theo, chúng ta thảo luận về các luật suy diễn của phép tính vị từ và việc sử dụng chúng trong giải quyết vấn đề. Phần cuối chương sẽ minh họa cách sử dụng phép tính vị từ để cài đặt một cơ sở tri thức trong lĩnh vực tư vấn đầu tư tài chính.
Mục tiêu cần đạt : Sau chương này, sinh viên có thể :
- Hiểu Logic mệnh đề và Logic vị từ
- Vận dụng các phép biến đổi tương đương
- Biết biểu diễn tri thức của vấn đề bằng logic vị từ bậc nhất.
- Vận dụng các phép suy diễn để chứng minh một vấn đề đơn giản.
- Vận dụng phép hợp nhất và giải thuật đối sánh mẫu
Kiến thức tiên quyết : Khái niệm về Trí tuệ nhân tạo, Logic mệnh đề, Logic vị từ, …
Tài liệu tham khảo :
- George F. Luger, William A. Stubblefield – Albuquerque – Artificial Intelligence – Wesley Publishing Company, Inc – 1997 (Chapter 2)
- Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu trúc và chiến lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần II)
- Wikipedia – Bách khoa toàn thư mở - Phép tính vị từ bậc nhất
http://en.wikipedia.org/wiki/Predicate_calculus
Định nghĩa – Ký hiệu phép tính mệnh đề
Mệnh đề :
Mệnh đề là một phát biểu có thể khẳng định tính đúng hoặc sai.
Các ký hiệu (symbol) của phép tính mệnh đề là các ký hiệu mệnh đề : P, Q, R, S, … (thông thường nó là các chữ cái in hoa nằm gần cuối bảng chữ cái tiếng Anh), các ký hiệu chân lý – chân trị (truth symbol) : true, false hay các phép toán kết nối như : ∧, ∨, , ⇒, =
Các ký hiệu mệnh đề (propositional symbol) biểu thị các mệnh đề (proposition) hay các phát biểu về thế giới thực mà giá trị của chúng có thể là đúng hoặc sai.
Thí dụ 2.1: Các mệnh đề
với mọiChiếc xe hơi kia màu đỏvới mọi
với mọiNước thì ướtvới mọi
Câu :
Câu trong phép tính mệnh đề được cấu tạo từ những ký hiệu sơ cấp (atomic symbol) theo các luật sau đây :
- Tất cả các ký hiệu mệnh đề và ký hiệu chân lý đều là câu (sentences) : true, P, Q và R là các câu.
- Phủ định của một câu là một câu : P và false là các câu
- Hội hay và của hai câu là một câu : P ∧ P là một câu
- Tuyển hay hoặc của hai câu là một câu : P ∨ P là một câu
- Kéo theo của một câu để có một câu khác là một câu : P ⇒ Q là một câu.
- Tương đương của hai câu là một câu : P ∨ Q = R là một câu
Các câu hợp lệ được gọi là các công thức dạng chuẩn (well-formed formula) hay WFF.
Trong các câu phép tính mệnh đề, các ký hiệu ( ) và [ ] dùng để nhóm các ký hiệu vào các biểu thức con và nhờ đó kiểm soát được thứ tự của chúng trong việc đánh giá biểu thức và diễn đạt. Ví dụ (P ∨ Q) = R hoàn toàn khác với P ∨ (Q = R).
Biểu thức :
Một biểu thức là một câu hay công thức dạng chuẩn, của phép tính mệnh đề khi và chỉ khi nó có thể được tạo từ những ký hiệu hợp lệ thông qua một dãy những luật này.
Thí dụ 2.2: (( P ∧ Q) ⇒ R = P ∨ Q ∨ R là một câu dạng chuẩn trong phép tính mệnh đề vì : P, Q, R là các mệnh đề và do đó là các câu.
P ∧ Q, hội của hai câu là một câu.
(P ∧ Q) ⇒ R, kéo theo của một câu là một câu.
P và Q, phủ định của các câu là câu.
P ∨ Q, tuyển của hai câu là câu.
P ∨ Q ∨ R, tuyển của hai câu là câu.
(( P ∧ Q) ⇒ R = P ∨ Q ∨ R, tương đương của hai câu là câu.
Đây là câu xuất phát, nó đã được xây dựng thông qua một loạt các luật hợp lệ và do đó nó có dạng chuẩn.
Sự gán giá trị chân lý cho các câu mệnh đề được gọi là một sự diễn giải (interpretation), một sự khẳng định chân trị của chúng trong một thế giới khả hữu (possible world) nào đó. Một cách hình thức, một diễn giải là một ánh xạ từ các ký hiệu mệnh đề vào tập hợp {T, F}.
Phép gán giá trị chân lý cho các mệnh đề phức tạp thường được mô tả thông qua bảng chân trị như sau :
Thí dụ 2.3: Chân trị của mệnh đề
được cho như trong bảng sau :
Hai biểu thức trong phép tính mệnh đề là tương đương nhau nếu chúng có cùng giá trị trong mọi phép gán chân trị. Một số công thức biến đổi tương đương của các mệnh đề đươc cho như trong bảng sau:
Bảng 2.1 – Bảng công thức biến đổi t ươ ng đ ươ ng
Những đồng nhất thức trong bảng 2.1 trên được dùng để biến đổi các biểu thức mệnh đề sang một dạng khác về mặt cú pháp nhưng tương đương về mặt logic. Có thể dùng các đồng nhất thức này thay cho các bảng chân trị để chứng minh hai biểu thức mệnh đề là tương đương nhau.
Câu hỏi :
Sử dụng bảng chân trị, hãy chứng minh sự tương đương của các đồng nhất thức trong bảng 2.1.
Phép tính vị từ
Trong phép tính mệnh đề, mỗi ký hiệu câu sơ cấp P, Q, … biểu thị một mệnh đề và chúng ta không thể tác động vào từng phần riêng lẻ của câu. Phép tính vị từ (predicate calculus) cung cấp cho chúng ta khả năng này. Chẳng hạn, đặt mệnh đề với mọihôm qua trời mưavới mọilà P, từ đó chúng ta có thể tạo ra một vị từ chỉ thời tiết mô tả quan hệ giữa một ngày và thời tiết trong ngày ấy: thời_tiết (hôm_qua, mưa). Thông qua các luật suy diễn, chúng ta sẽ có thể thao tác trên các biểu thức phép tính mệnh đề, truy xuất và suy ra những câu mới.
Ký hiệu vị từ : là tập hợp gồm các chữ cái, chữ số, ký hiệu với mọi_với mọi, và được bắt đầu bằng chữ cái.
Thí dụ 2.4: X3, tom_and_jerry
Ký hiệu vị từ có thể là:
- Ký hiệu chân lý: true, false
- Hằng: dùng để chỉ một đối tượng / thuộc tính trong thế giới.
Hằng được ký hiệu bắt đầu bằng chữ thường: helen, yellow, rain, …
- Biến: dùng để chỉ một lớp tổng quát các đối tượng/thuộc tính.
Biến được ký hiệu bắt đầu bằng chữ hoa: X, People, Students, …
- Hàm: dùng để chỉ một hàm trên các đối tượng.
Hàm được ký hiệu bắt đầu bằng chữ thường: father, plus, …
Mỗi ký hiệu hàm có một ngôi n, chỉ số lượng các đối số của hàm.
- Vịtừ: dùng để định nghĩa một mối quan hệ giữa không hoặc nhiều đối tượng.
Vị từ được ký hiệu bắt đầu bằng chữ thường: likes, equals, part_of, …
Biểu thức hàm: là một ký hiệu hàm theo sau bởi n đối số.
Ví dụ: father(david) price(bananas) like(tom, football)
Mục (term): là một hằng, một biến hay một biểu thức hàm
Câu sơ cấp: là một hằng vị từ với n ngôi theo sau bởi n thành phần nằm trong cặp dấu ( ), cách nhau bởi dấu ‘,’, và kết thúc với dấu ‘.’
- Trị chân lý true, false là các câu sơ cấp.
- Câu sơ cấp còn được gọi là: biểu thức nguyên tử, nguyên tử hay mệnh đề
Thí dụ 2.5 : friends(helen, marry). likes(hellen, mary).
likes(helen, sister(mary)). likes(X, ice-cream).
Ký hiệu vị từ trong các câu này là friends, likes.
Câu: được tạo ra bằng cách kết hợp các câu sơ cấp sử dụng:
- Các phép kết nối logic:
- Các lượng tử biến:
+ Lượng tử phổ biến với mọi: dùng để chỉ một câu là đúng với mọi giá trị của biến lượng giá
- Ví dụ: với mọiX likes(X, ice-cream).
+ Lượng tử tồn tại $: dùng để chỉ một câu là đúng với một số giá trị nào đó của biến lượng giá.
Ví dụ: $Y friends(Y,tom).
Thí dụ 2.6 :
Ngữ nghĩa - Phép tính vị từ
Tương tự như phép tính mệnh đề, ngữ nghĩa của phép tính vị từ cung cấp một cơ sở để xác định chân trị của các biểu thức dạng chuẩn. Chân trị của các biểu thức phụ thuộc vào ánh xạ từ các hằng, các biến, các vị từ và các hàm vào các đối tượng và quan hệ trong lĩnh vực được đề cập.
Sự thông dịch (cách diễn giải) của một tập hợp các câu phép tính vị từ: là một sự gán các thực thể trong miền của vấn đề đang đề cập cho mỗi ký hiệu hằng, biến, vị từ và hàm.
Giá trị chân lý của một câu sơ cấp được xác định qua sự thông dịch. Đối với các câu không nguyên tố, sử dụng bảng chân lý cho cho các phép nối kết, và:
- Giá trị của câu với mọiX <câu> là true nếu <câu> là T cho tất cả các phép gán có thể được cho X.
- Giá trị của câu $ X <câu> là true nếu tồn tại một phép gán cho X làm cho <câu> có giá trị T.
Thí dụ 2.7: Cho trước một tập hợp các quan hệ gia đình như sau :
Ta có thể suy luận:
parent(eve,abel) parent(eve,cain)
parent(adam,abel) parent(adam,cain)
sibling(abel,cain) sibling(cain,abel)
sibling(abel,abel) sibling(cain,cain) ! Không có nghĩa
Phép tính vị từ bậc nhất (First – order predicate calculus)
Phép tính vị từ bậc nhất cho phép các biến lượng giá tham chiếu đến các đối tượng trong miền của vấn đề đang đề cập nhưng KHÔNG được tham chiếu đến các vị từ và hàm.
Thí dụ 2.8 : Ví dụ không hợp lệ: với mọi(Likes) Likes(helen, ice-cream)
Ví dụ hợp lệ:
Hầu hết bất kỳ câu đúng ngữ pháp nào cũng có thể biểu diễn trong phép tính vị từ bậc nhất bằng cách sử dụng các ký hiệu, các phép kết nối và ký hiệu biến.
Các luật suy diễn
Ngữ nghĩa của phép tính vị từ cung cấp một cơ sở cho lý thuyết hình thức về suy diễn logic. Khả năng suy ra những biểu thức đúng mới từ một tập hợp các khẳng định đúng là một đặc trưng quan trọng của phép tính vị từ. Logic vị từ dùng các luật suy diễn sau :
Luật Modus Ponens (MP): P 
Q
Thí dụ 2.9: Nếu ta có quan sát sau đây với mọinếu trời mưa thì sân ướtvới mọi(P Þ Q) và với mọitrời đang mưavới mọi(P) thì ta dễ dàng suy ra được với mọisân ướtvới mọi(Q).
Luật Modus Tollens (MT): 
Luật triển khai phổ biến (Universal Instantiation):
với mọiX P(X)
a thuộc miền xác định của X
P(a)
Thí dụ 2.10: Cho trước:
Download slide bài giảng tại đây
