Chương 3. Biểu diễn tri thức
Ầ
TR N MINH THÁI Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn
1
Cập nhật: 05 tháng 09 năm 2015
Nội dung
#2
1.
Giới thiệu về tri thức
2.
Đặc trưng của tri thức
3.
Các phương pháp biểu diễn tri thức
4.
Logic
5.
Frame
6. Mạng ngữ nghĩa (Semantic Network)
7. Mạng nơron
8.
Các phương pháp khác
Giải bài toán AI cần
#3
• Tri thức về bài toán (có thể nhiều)
• Phương tiện để xử lý tri thức như: retrieve, update, infer
Hình thức hóa tri thức
#4
• Mức tri thức: Mức mà các sự kiện, gồm cách hành xử của
Gồm hai mức
• Mức ký hiệu: Mức mà sự biểu diễn của các đối tượng đã được chọn trong mức tri thức được viết ra ở dạng ký hiệu để có thể xử lý được bằng chương trình
agent và mục tiêu hiện tại, được mô tả
Mô hình vấn đề của con người và máy
#5
Tri thức?
#6
• Đối với máy tính dữ liệu (data) là các con số, ký hiệu mà máy tính có thể lưu trữ, biểu diễn, xử lý. Bản thân dữ liệu không có ý nghĩa
• Chỉ khi con người cảm nhận, tư duy thì dữ liệu mới có một ý
• Tri thức (knownlegded) là kết tinh, cô đọng, chắt lọc của thông
nghĩa nhất định, đó chính là thông tin (Information)
tin. Tri thức hình thành từ quá trình xử lý thông tin mang lại
Phân loại tri thức
#7
[1] Tri thức sự kiện khẳng định về một sự kiện, hiện tượng hay một khái niệm nào đó trong một hoàn cảnh không gian hoặc thời gian nhất định: định lý toán học, định luật vật lý, …
[2] Tri thức thủ tục mô tả cách giải quyết một vấn đề, quy trình xử lý các công việc, lịch trình tiến hành các thao tác: các luật, chiến lược, lịch trình như phương pháp điều chế hóa học, thuật toán, …
Phân loại tri thức
#8
[3] Tri thức mô tả các nhận định, kết luận về sự kiện, hiện tượng
[4]Tri thức heuristic các ước lượng, suy đoán hình thành qua kinh nghiệm. Không đảm bảo hòan tòan chính xác hoặc tối ưu theo một nghĩa nào đó về cách giải quyết vấn đề. Tri thức heuristic thường được coi là một mẹo nhằm dẫn dắt tiến trình lập luận
Nhu cầu xử lý tri thức
#9
• Trí tuệ, sự thông minh phải dựa trên nền tảng của tri thức. Tuy
• Biểu diễn tri thức là việc đưa tri thức vào máy tính. Chỉ có ý
nhiên, nó còn phụ thuộc vào việc vận dụng, xử lý tri thức
nghĩa nếu “xử lý tri thức” được thực hiện
Nhu cầu xử lý tri thức
#10
• Cú pháp bao gồm các ký hiệu và các quy tắc liên kết các ký hiệu (các luật cú pháp) để tạo thành các câu (công thức) trong ngôn ngữ
• Ngữ nghĩa xác định ý nghĩa của các câu trong một miền nào
Ngôn ngữ biểu diễn tri thức = Cú pháp + Ngữ nghĩa + Cơ chế suy diễn
• Cơ chế suy diễn để từ các tri thức trong cơ sở tri thức và các
đó của thế giới hiện thực
sự kiện ta nhận được các tri thức mới
Ví dụ
#11
• Cho 2 bình rỗng X, Y có thể tích lần lượt là Vx, Vy. Dùng 2 bình
• Với Vx = 5, Vy = 7 và z = 4 thì thực hiện như thế nào?
này để đong ra z lít nước
Ví dụ
#12
1. Múc đầy bình 7
2.
3.
Đổ qua cho đầy bình 5
4.
Đổ hết nước trong bình 5
5. Múc đầy bình 7
6.
Đổ phần còn lại trong bình 7 qua bình 5
7.
Đổ từ bình 7 qua cho đầy bình 5
Phần còn lại trong bình 7 là 4 lít
Biểu diễn tri thức?
#13
• Là phương pháp mã hoá tri thức, nhằm thành lập cơ sở tri thức
Bằng cách nào ?
Tri thức tính toán
Tri thức thực của lĩnh vực
ả
ạ B ng ánh x
ồ
ượ
ự
ữ
ấ
G m: ồ ố đ i t ng và các quan h ệ gi a chúng trong lĩnh v cự
ự
cho các hệ thống dựa trên tri thức
ằ dùng B ng cách: ể ượ c đ bi u các l ễ di n (scheme) ọ ồ ượ c đ cho Ch n l ứ ạ lo i tri th c là v n ọ ề đ quan tr ng
G m: ồ gi a ữ ố ượ Đ i t ng th c ố ượ đ i t ng tính toán ệ Quan h th c ệ quan h tính toán
Lược đồ biểu diễn tri thức
#14
• Dùng các biểu thức trong logic hình thức, như phép toán vị từ,
1. Lược đồ logic
• Các luật suy diễn áp dụng cho loại lược đồ này
• Ngôn ngữ lập trình hiện thực tốt nhất cho loại lược đồ này là:
để biểu diễn tri thức
PROLOG
Logic mệnh đề
#15
IF Xe không khởi động được (A) AND Khoảng cách từ nhà đến chỗ làm là xa(B) THEN
• Luật trên có thể biểu diễn lại như sau:
Sẽ trễ giờ làm (C)
A B C∧ ⇒
Logic vị từ
#16
• Tương tự logic mệnh đề
• Dùng các ký hiệu để thể hiện tri thức.
• Những ký hiệu này gồm hằng số, vị từ, biến và hàm
Ví dụ
#17
• Câu tiếng Anh:
“Spot is a dog”
• Dạng logic:
“Every dog has a tail”
1. dog(Spot).
2. X
3. (dog(X)→hastail(X)).
Ví dụ
#18
• Từ đó câu: “Spot has a tail”, có thể thu được qua các bước:
Từ 2, X = “Spot”: dog(Spot)→hastail(Spot).
• Ánh xạ ngược → “Spot has a tail”.
Từ1, 3: hastail(Spot).
Lược đồ biểu diễn tri thức
#19
• Khác với khai báo, lược đồ này biểu diễn tri thức như tập các
2. Lược đồ thủ tục
• Các chỉ thị lệnh trong lược đồ thủ tục chỉ ra bằng cách nào giải
chỉ thị lệnh để giải quyết vấn đề
• Ví dụ: hệ luật sinh điển hình cho loại lược đồ này
quyết vấn đề
Hệ luật sinh
#20
• Luật là cấu trúc tri thức dùng để liên kết thông tin đã biết với các thông tin khác giúp đưa ra các suy luận, kết luận từ những thông tin đã biết
• Thu thập các tri thức lĩnh vực trong một tập và lưu chúng trong cơ sở tri thức của hệ thống. Hệ thống dùng các luật này cùng với các thông tin để giải bài toán
• Việc xử lý các luật trong hệ thống dựa trên các luật được quản
lý bằng một module gọi là bộ suy diễn
Hệ luật sinh – 7 dạng cơ bản
#21
1. Quan hệ: IF Bình điện hỏng THEN Xe sẽ không khởi động được
2. Lời khuyên: IF Xe không khởi động được THEN Đi bộ
3. Hướng dẫn: IF Xe không khởi động được AND Hệ thống nhiên liệu tốt THEN Kiểm tra hệ thống điện
4. Chiến lược: IF Xe không khởi động được THEN Đầu tiên hãy kiểm tra hệ thống nhiên liệu, sau đó kiểm tra hệ thống điện
Hệ luật sinh – 7 dạng cơ bản
#22
5. Diễn giải: IF Xe nổ AND tiếng giòn THEN Động cơ hoạt động bình thường
6. Chẩn đoán: IF Sốt cao AND hay ho AND Họng đỏ THEN Viêm họng
7. Thiết kế: IF Là nữ AND Da sáng THEN Nên chọn Xe Spacy AND Chọn màu sáng
Lược đồ biểu diễn tri thức
#23
• Biểu diễn tri thức như là đồ thị; các đỉnh như là các đối tượng
3. Lược đồ mạng
• Ví dụ: mạng ngữ nghĩa (semantic network), lược đồ quan hệ
hoặc khái niệm, các cung như là quan hệ giữa chúng
phụ thuộc khái niệm đồ thị khái niệm
ạ
M ng ng
ữ nghĩa
#24
Mạng ngữ nghĩa là một phương pháp biểu diễn tri thức dùng đồ thị trong đó nút biểu diễn đối tượng và cung biểu diễn quan hệ giữa các đối tượng
ạ
M ng ng
ữ nghĩa
#25
Lược đồ biểu diễn tri thức
#26
• Là một mở rộng của lược đồ mạng; bằng cách cho phép các nút có thể là một CTDL phức tạp gồm các khe (slot) có tên và trị hay một thủ tục
• Ví dụ: kịch bản (script), khung (frame), đối tượng (object)
4. Lược đồ cấu trúc
Frame – Biểu diễn ở dạng khái niệm hay đối tượng
#27
• Mỗi frame mô tả một đối tượng (object)
• Một frame bao gồm 2 thành phần cơ bản là slot và facet
• slot là một thuộc tính đặc tả đối tượng được biểu diễn bởi
• Mỗi slot có thể chứa một hoặc nhiều facet
• Các facet (đôi lúc được gọi là slot "con") đặc tả một số thông tin hoặc thủ tục liên quan đến thuộc tính được mô tả bởi slot. Facet có nhiều loại khác nhau, sau đây là một số facet thường gặp: value, default value, range, ...
frame
Script
#28
Script: RESTAURANT
Scene 1: (Entering)
Track: Coffee Shop
Entry conditions:
S is hungry
S has money
Results:
S has less money
S PTRANS S into restaurant. S ATTEND eyes to tables S MBUILD where to sit S PTRANS S to table S MOVE S to sitting position ---
O has more money
S is not hungry
S is pleased (optional)
Scene 2: (Ordering) (Menu on table) S PTRANS menu to S
Tables
Props:
Menu
Food (F)
Check
Money
(S ask for menu) S MTRANS signal to W W PTRANS W to table S MTRANS ‘need menu’ to W W PTRANS W to menu
Custumer (S)
Roles:
Waiter(W)
Cook(C)
Cashier(M)
Owner(O)
Frame – Biểu diễn ở dạng khái niệm hay đối tượng
#29
Object1
Frame name:
Object2
Class:
Property 1 Value1
Properties:
Property 2 Value2
…
…
…
…
Frame
#30
• Frame thường được dùng để biểu diễn những tri thức "chuẩn"
• hoặc những tri thức được xây dựng dựa trên những kinh
nghiệm hoặc các đặc điểm đã được hiểu biết cặn kẽ
Đối tượng - Thuộc tính – Giá trị
#31
• Sự kiện gồm Object-Attribute -Value được dùng để xác nhận
• Ví dụ: "quả bóng màu đỏ" xác nhận "đỏ" là giá trị thuộc tính
giá trị của một thuộc tính xác định của một vài đối tượng.
"màu" của đối tượng "quả bóng"
Đối tượng - Thuộc tính – Giá trị
#32
• Một đối tượng có thể có nhiều thuộc tính với các kiểu giá trị khác nhau. Một thuộc tính cũng có thể có một (single-valued) hay nhiều giá trị (multi-valued) Linh động trong biểu diễn các tri thức cần thiết
• Các sự kiện không phải lúc nào cũng bảo đảm là đúng hay sai với độ chắc chắn hoàn toàn. Khi đó, trong sự kiện O-A-V sẽ có thêm một giá trị xác định độ tin cậy của nó là CF (Certainly Factor).
Các vấn đề trong biểu diễn tri thức
#33
• Có những thuộc tính cơ bản nào của đối tượng mà chúng xuất hiện trong mọi lĩnh vực không? Nếu có: những thuộc tính nào?
• Có chắc chắn là chúng sẽ được xử lý thích hợp trong từng cơ
• Có quan hệ quan trọng nào tồn tại cùng với thuộc tính không?
• Các đối tượng và các quan hệ có thể biểu diễn cho cái gì trong
chế được đề nghị không?
lĩnh vực?
Ví dụ: để biểu diễn cho ý “Nam cao 1 mét 70”, có thể dùng: chieucao(nam, 170). Để diễn tả “An cao hơn Nam”?
Các vấn đề trong biểu diễn tri thức
#34
• Tri thức được biểu diễn đến mức chi tiết nào?
• Bằng cách nào thể hiện được meta-knowledge?
• Bằng cách nào thể hiện tính phân cấp của tri thức: các hình thức: kế thừa, ngoại lệ, trị mặc định, ngoại lệ, đa thừa kế phải đặc tả như thế nào
Các vấn đề trong biểu diễn tri thức
#35
• Khi mô tả đối tượng, bằng cách nào có thể tích hợp một tri thức
• Với số lượng lớn tri thức được chứa trong CSDL, Bằng cách nào
thủ tục vào bản thân mô tả, khi nào thủ tục được thực hiện
truy xuất những thành phần cần thiết?
Đặc điểm của hệ thống biểu diễn tri thức
#36
• Khả năng biểu diễn tất cả các tri thức cần thiết cho lĩnh vực đó
• Khả năng xử lý các cấu trúc sẵn có để sinh ra các cấu trúc mới
• Khả năng thêm vào cấu trúc những tri thức thông tin bổ sung mà nó có thể được dùng để hướng dẫn cơ chế suy luận theo hướng có nhiều triển vọng nhất
tương ứng với tri thức mới được sinh ra từ tri thức cũ
Đặc điểm của hệ thống biểu diễn tri thức
#37
• Khả năng thu được thông tin mới dễ dàng
• Trường hợp đơn giản nhất là chèn trực tiếp tri thức mới (do con người) vào cơ sở tri thức. Lý tưởng nhất là chương trình có thể kiểm soát việc thu được tri thức
Tri thức có khả năng thừa kế
#38
• Một dạng bổ sung cơ chế suy diễn vào cơ sở tri thức quan hệ
• Thừa kế thuộc tính:
• Tổ chức các đối tượng thành các lớp (class).
• Các lớp được sắp xếp vào hệ thống phân cấp (hierachy) – có lớp cha
(tổng quát) và lớp con (cụ thể).
nói trên, đó là: thừa kế thuộc tính.
Các lớp con thừa kế các thuộc tính từ lớp cha
Tri thức có khả năng thừa kế
#39
Tri thức suy diễn
#40
• Thừa kế thuộc tính ở trên là 1 dạng suy diễn
• Logic truyền thống: cung cấp dạng suy diễn mạnh hơn
• Tri thức suy diễn: cần thủ tục suy diễn
• Thủ tục suy diễn: nhiều dạng
• Forward (tiến): sự kiện kết luận
• Backward (lùi): kết luận sự kiện đã cho
• Thủ tục thường dùng: resolution
Tri thức thủ tục
#41
• Tĩnh, dạng khai báo
• Một dạng tri thức khác: chỉ ra hành động được thi hành khi điều
• Cách biểu diễn trong chương trình
• Viết bằng các NNLT (VD LISP)
kiện nào đó thỏa → tri thức thủ tục
⇒ Máy sẽ thực thi mã để thực hiện công việc
Tri thức thủ tục – Trở ngại
#42
• Khó viết CT suy diễn về hành vi của CT khác
• Cập nhật/debug số lượng lớn mã → khó khăn
• Tri thức thủ tục dùng luật sinh (production rule)
• Luật sinh và cách sử dụng chúng: là định hướng hoạt động hơn các
dạng biểu diễn nói trước đây.
• Tuy nhiên phân biệt đâu là tri thức khai báo hay thủ tục là một công
việc khó khăn.
Các thuộc tính quan trọng
#43
• Cho biết quan hệ thành viên giữa đối tượng và lớp nó thuộc
1. Instance
vào
• Cho biết một lớp là con của lớp khác
• Cặp thuộc tính trên cho phép khả năng thừa kế thuộc tính
• Chúng có thể được gọi và biểu diễn khác nhau trong nhiều hệ
2. Isa
thống tri thức
Bằng cách nào biểu diễn hiệu quả chuỗi trạng thái cho bài toán tìm kiếm?
#44
• Bài toán robot:
on(Plant12, Table34).
under(Table34, Window13).
in(Table34, Room15).
• Khuyết: danh sách dài.
• từ trạng thái A → B: nhiều facts không thay đổi
• Vấn đề khung: bài toán về biểu diễn facts thay đổi cùng với
→ 1 trạng thái = danh sách các facts trên.
những facts không được biết
Thực tế?
#45
• Không một hệ thống nào có thể tối ưu tất cả các khả năng trên
• Nhiều kỹ thuật dùng cho biểu diễn tri thức cùng tồn tại
• Thường dùng nhiều hơn 1 kỹ thuật biểu diễn
cho mọi kiểu tri thức
Biểu diễn tri thức bằng logic mệnh đề
#46
• AI: Phát triển các chương trình có khả năng suy luận
• Suy luận giúp chương trình AI biết được tính đúng/sai của một
• Phép toán vị từ cung cấp một khả năng triển khai các quá
vấn đề nào đó
• Phép toán vị từ được hiện thực bằng ngôn ngữ lập trình trên
trình suy diễn trên máy tính
máy tính PROLOG
Cú pháp
#47
• Cú pháp của logic mệnh đề gồm tập các ký hiệu và tập các luật
• Các ký hiệu
• Hai hằng logic: True và False
• Ký hiệu mệnh đề (biến mệnh đề): P, Q, ...
• Các phép kết nối logic:
(∧ hội),
(∨ tuyển), ˥ (phủ định),
(⇒ kéo theo/
suy ra),
(⇔ tương đương)
• Cặp dấu ngoặc tròn: ( )
xây dựng công thức
Cách đánh giá giá trị của phép toán: Bảng chân trị
Ví dụ
#48
ề
ệ
ề ự ế
ệ
M nh đ th c t
§
ư
ế
ầ
ờ
ờ
“N u tr i m a thì b u tr i có
ể
mây”
ờ
ư § Tr i đang m a
ậ
ễ Q là
ầ
ờ
V y ậ B u tr i có mây
ờ
M nh đ logic ư ờ § P=“Tr i m a” ờ ầ § Q= “B u tr i có mây” Ta có hai phát bi u sau đúng: § P Q § P Theo lu t suy di n đúng. Nghĩa là: “B uầ tr i có mây”
Ví dụ
#49
ệ
ề
ề ự ế
ệ
M nh đ logic
M nh đ th c t
ề
ề
§
§P=“Nam có nhi u ti n”
ề
ế
ề “N u NAM có nhi u ti n thì NAM đi
§Q= “Nam đi mua s m”ắ
mua s m”ắ
ể
Ta có hai phát bi u sau đúng:
§
“Nam KHÔNG đi mua s m”ắ
ề
V y ậ Nam KHÔNG có nhi u ti n ề
§P Q §(cid:0)
Q
ậ
ậ V y theo lu t suy di n
ễ (cid:0)
P là đúng.
ề
ề
Nghĩa là: “Nam KHÔNG có nhi u ti n”
Mệnh đề
#50
• Mệnh đề là một phát biểu khai báo
• Mệnh đề chỉ nhận một trong hai giá trị:
• ĐÚNG (True)
• hoặc SAI (False)
Mệnh đề:
• Ngày 01 tháng giêng là ngày tết cổ truyền
• Môn bạn đang học là AI
Ví dụ:
Bảng chân trị
#51
P
Q
(cid:0) P P(cid:0) Q P v Q P=>Q P<=>Q
False False True False False True
True
False True True False True True
False
True False False False True False
False
True True False True True True
True
Qui tắc xây dựng công thức
#52
• Các công thức là các ký hiệu mệnh đề sẽ được gọi là các câu
• Các công thức không phải là câu đơn sẽ được gọi là câu phức
đơn hoặc câu phân tử
• Nếu P là ký hiệu mệnh đề thì P và ˥ P được gọi là literal, P là
hợp
literal dương, còn ˥ P là literal âm
Ngữ nghĩa
#53
• Xác định ý nghĩa của các công thức trong thế giới thực bằng cách kết hợp mỗi ký hiệu mệnh đề với sự kiện nào đó trong thế giới hiện thực
• Ký hiệu mệnh đề có thể ứng với sự kiện nào đó
• Sự kết hợp các kí hiệu mệnh đề với các sự kiện trong thế giới
• Một sự kiện chỉ có thể đúng hoặc sai. VD sự kiện “Paris là thủ
thực được gọi là một minh họa (interpretation)
đô nước Pháp” là đúng
Ví dụ
#54
P= “Nam học giỏi” ; Q= “Nam thông minh” ; R= “Nam đẹp trai”
ề ự ế
ệ
M nh đ th c t
ứ
ể
ệ
ề Bi u th c m nhđ
§
ọ
“Nam h c gi
i
ỏ , thông minh, đ p ẹ
§ P (cid:0) Q (cid:0) R
trai”
§ P (cid:0)
Q
§
ọ
ỏ
ặ
“Nam h c gi
i ho c thông minh”
§ (P (cid:0) (cid:0) R)(cid:0) ((cid:0) P (cid:0) R)
§
ặ ọ
ỏ
“Nam ho c h c gi
ặ ẹ i, ho c đ p trai”
§ Q (cid:0)
P
§
ọ
ỏ
“Nam thông mình thì h c gi
i”
Dạng chuẩn tắc
#55
• Chuẩn hóa các công thức
• Đưa các công thức về dạng thuận lợi cho việc lập luận, suy
• Sử dụng các phép biến đổi tương đương có thể đưa một
diễn.
công thức bất kỳ về dạng chuẩn tắc
Sự tương đương các công thức
#56
• A B ≡ ¬A
⇒ ∨ B
• A
• ¬(¬ A) ≡ A
⇔ ⇒ ∧ ⇒ B ≡ (A B) (B A)
Luật De Morgan
• ¬(A
∨ ∧ B) ≡ ¬A ¬B
• ¬(A
∧ ∨ B) ≡ ¬A ¬B
Sự tương đương các công thức
#57
Luật giao hoán
• A
∨ ∨ B ≡ B A
• A
∧ ∧ B ≡ B A
• (A
Luật kết hợp
• (A
∨ ∨ B) C ≡ A ∨ ∨ (B C)
∧ ∧ B) C ≡ A ∧ ∧ (B C)
Luật phân phối
• A
∧ ∨ ∧ ∧ ∨ (B C) ≡ (A B) (A C)
• A
∨ ∧ ∨ ∨ ∧ (B C) ≡ (A B) (A C)
Chuyển thành dạng chuẩn tắc
#58
• Để dễ dàng viết các chương trình máy tính đưa chúng về
• Một công thức ở dạng chuẩn hội nếu nó là hội của các câu
dạng biểu diễn dạng chuẩn hội
• Cách thực hiện
1.
⇒
⇒
Bỏ các dấu kéo theo (
) bằng cách thay (A B) bởi (¬AvB)
2.
Chuyển các dấu phủ định (¬) vào sát các ký hiệu mệnh đề bằng cách áp dụng luật De Morgan và thay ¬ (¬A) bởi A
3.
∨ ∧
∨ ∧ ∨
Áp dụng luật phân phối, thay các công thức có dạng A (B C) bởi (A
B)
B)
(A
tuyển
⇒
∨
∨
Ví dụ chuẩn hóa (P
Q)
¬(R
¬S)
#59
• (P
⇒ ∨ ∨ Q) ¬ (R ¬S)
• (¬P
∨ ∨ ∨ Q) ¬ (R ¬S) : Loại bỏ dấu ⇒
• (¬P
∧ Q) ∨ ∨ (¬R S) : Luật De Morgan
• ((¬P
∨ ∨ ∧ ∨ ∨ Q) ¬R) ((¬ P Q) S) : Luật phân phối
• (¬ P
∧ ∨ ∨ Q ¬ R) (¬ P ∨ ∨ Q S)
Tập hợp các câu tuyển
Câu Horn
#60
• Mọi công thức đều có thể đưa về dạng chuẩn hội, có dạng:
∨
∨
∨
• ¬P1
... ..
¬Pm
Q1
∨ ∨ .....
Qn
• tương đương với: P1
Pm => Q1
∨ ∨ ...
Qn gọi là
câu
∧ ∧ ... Kowalski (do nhà logic Kowalski đưa ra năm 1971)
• Khi n <=1, tức là câu tuyển chỉ chứa nhiều nhất một literal
• Nếu m > 0, n=1, câu Horn có dạng: P1
dương gọi là câu Horn (mang tên nhà logic Alfred Horn, năm 1951)
• Có thể biểu diễn thành các luật if-then:
∧ ∧ ... Pm => Q
If P1 and ... and Pm then Q
Luật suy diễn
#61
• H được xem là hệ qủa logic (logical consequence) của một tập công thức G ={G1,.....,Gm} nếu trong bất kỳ minh họa nào mà {G1,... ..,Gm} đúng thì H cũng đúng
• Dùng các tri thức trong cơ sở để suy ra tri thức mới mà nó là hệ quả logic của các công thức trong cơ sở tri thức: sử dụng các luật suy diễn (rule of inference)
• Một luật suy diễn gồm hai phần: một tập các điều kiện và một
kết luận
Một số luật suy diễn quan trọng
#62
ệ
ề
ế
ậ K t lu n
Lu tậ Modus Ponens
(cid:0) (cid:0)
Modus Tollens
¬(cid:0)
(cid:0)
ắ ầ B c c u
(cid:0)
ư
ạ ỏ ộ Lo i b h i ộ Đ a vào h i
(cid:0) i (cid:0) … (cid:0) (cid:0) m (cid:0) i, …, (cid:0) m
(cid:0) (cid:0)
ư
i (cid:0) … (cid:0) (cid:0) m i (cid:0) … (cid:0) (cid:0) m
(cid:0)
ể Đ a vào tuy n iả
Phân gi
Đi u ki n , (cid:0) (cid:0) (cid:0) , ¬(cid:0) (cid:0) (cid:0) (cid:0) , (cid:0) (cid:0) (cid:0) (cid:0) 1 (cid:0) … (cid:0) (cid:0) (cid:0) 1, … , (cid:0) i (cid:0) (cid:0)
, ¬(cid:0)
(cid:0) (cid:0)
(cid:0) i (cid:0) 1 (cid:0) … (cid:0) (cid:0) (cid:0) 1 (cid:0) … (cid:0) (cid:0) (cid:0) (cid:0)
ộ
ậ
ượ
c xem là tin c y n u b t k m t mô hình
ấ ỳ ộ ậ ủ ế
ả
ậ
ễ M t lu t suy di n đ ế ủ ủ nào c a gi
ậ ế ậ t c a lu t cũng là mô hình k t lu n c a lu t
thi
(cid:0) (cid:0)
Tiên đề, định lý, chứng minh
#63
• Các luật suy diễn cho phép suy ra các công thức mới từ các
• Các công thức đã cho được gọi là các tiên đề
• Các công thức được suy ra được gọi là các định lý
• Dãy các luật được áp dụng để dẫn tới định lý được gọi là một
công thức đã có bằng một dãy áp dụng các luật suy diễn
• Nếu các luật suy diễn là tin cậy, thì các định lý là hệ quả logic
chứng minh của định lý
của các tiên đề
Ví dụ
#64
Giả sử có các công thức:
• Q
∧ ⇒ ∨ G S H (1)
• P
⇒ Q (2)
• R
• P (4)
• R (5)
⇒ S (3)
• Áp dụng luật Modus Ponens: Từ (2) và (4) suy ra Q. Từ (3) và (5) suy ra S
∧ • Từ Q, S ta suy ra Q S (luật đưa vào hội)
Cần chứng minh công thức G H∨
• Từ (1) và Q S ta suy ra G H ∧
∨
∨ Công thức G H đã được chứng minh
Vấn đề chứng minh phép suy diễn
#65
• Tính đúng đắn của phép suy diễn: a → b?
• Hai phép suy luận cơ bản của logic mệnh đề (Modus Ponens, Modus Tollens) cộng với các phép biến đổi hình thức có thể chứng minh được phép suy diễn
• Tuy nhiên, thao tác biến đối hình thức là rất khó cài đặt trên
máy tính
Vấn đề chứng minh phép suy diễn
#66
• Công cụ máy tính có thể dễ dàng chứng minh được mọi bài
• Phương pháp chứng minh mệnh đề với độ phức tạp chỉ có
toán bằng cách lập bảng chân trị Độ phức tạp của phương pháp này là quá lớn: O (2n) với n là số biến mệnh đề
O(n): Thuật giải Vương Hạo và Robinson
Thuật giải Vương Hạo
#67
• B1 : Phát biểu lại giả thiết và kết luận của vấn đề theo dạng
chuẩn sau:
• Trong đó các GTi và KLi là các mệnh đề được xây dựng từ các biến
mệnh đề và 3 phép nối cơ bản :
∧ ∨ ,
, ¬
• B2 : Chuyển vế các GTi và KLi có dạng phủ định
GT1, GT2, ..., GTn → KL1, KL2, ..., KLm
Thuật giải Vương Hạo
#68
• Ví dụ:
∨ p q, ∨ ¬ (r s)∧ , ¬ g, p r → s, ¬ p
chuyển thành:
∨ ∨ p q, p r , p →(r s)∧ , g, s
Thuật giải Vương Hạo
#69
• B3 : Nếu GTi có phép
∧ bằng dấu ",“. Nếu
thì thay thế phép ∨ ∨ ∧ thì thay thế phép bằng dấu "," KLi có phép
Ví dụ:
∧ ∧ ∨ p q , r (¬ p s) →¬ q, ¬ s
chuyển thành:
∨ p, q, r, ¬ p s → ¬ q, ¬ s
• B4 : Nếu GTi có phép ∧
∨ thì tách thành hai dòng con. Nếu ở KLi
có phép thì tách thành hai dòng con
Thuật giải Vương Hạo
#70
• Ví dụ :
p, ¬ p ∨ q →q
tách thành:
p, ¬ p →q
và p, q →q
Thuật giải Vương Hạo
#71
• B5 : Một dòng được chứng minh nếu tồn tại chung một mệnh
đề ở cả hai phía
• B6 :
∨
∧
• a) Nếu một dòng không còn phép nối
và phép nối
ở cả hai vế và 2 vế không có chung biến mệnh đề thì dòng đó không được chứng minh
• b) Một vấn đề được chứng minh nếu tất cả dòng dẫn xuất từ dạng
chuẩn ban đầu đều được chứng minh
Ví dụ: p, q → q được chứng minh
Thuật giải Vương Hạo – Ví dụ
#72
r suy ra p (cid:0) r
q, q (cid:0) r (cid:0) p (cid:0) r
Chứng minh: giả thuyết p (cid:0) Cần chứng minh: p (cid:0) q, q (cid:0) (cid:0) p (cid:0) r B1: (cid:0) p (cid:0) q, (cid:0) q (cid:0) r (cid:0) (cid:0) p, r B3: (cid:0) p (cid:0) q, (cid:0) q (cid:0) r (cid:0)
(cid:0) p (cid:0) q, (cid:0) q (cid:0) r, p (cid:0) r
r (1)
B4: Tách mệnh đề đầu (cid:0) p , (cid:0) q (cid:0) r, p (cid:0) q, (cid:0) q (cid:0) r, p (cid:0) r (2)
Thuật giải Vương Hạo – Ví dụ
#73
r, p: được chứng minh
r tách thành
r (2.1)
r (2.2): được chứng minh
r, q: được chứng minh
Từ (1): (cid:0) q (cid:0) r, p (cid:0) Từ (2): q, (cid:0) q (cid:0) r, p (cid:0) q, (cid:0) q, p (cid:0) q, r, p (cid:0) Từ (2.1): q, p (cid:0) Kết luận: p (cid:0) q, q (cid:0) r (cid:0) p (cid:0) r
Bài tập
#74
1.
2.
∧ ∨ p (¬ p q) → q
3.
∨ ∨ (p ∨ ∧ q) (¬ p r) → q r
∧ ∧ (a b) → c, (b c) → d, ¬d. Chứng minh: a → b
Thuật giải Robinson
#75
• Thuật giải này hoạt động dựa trên phương pháp chứng minh
• Chứng minh phản chứng:
• Chứng minh phép suy luận (a → b) là đúng (với a là giả thiết, b là kết
luận).
• Phản chứng : giả sử b sai suy ra ¬ b là đúng.
phản chứng và phép hợp giải Robinson.
Thuật giải Robinson
#76
• Phép hợp giải Robinson:
∧
∨
• p
(¬ p
q) →q
∨
∨
• (p
∨ ∧ q)
(¬ p
r) →q
r
Bài toán được chứng minh nếu:
a đúng và ¬ b đúng sinh ra một mâu thuẫn
Thuật giải Robinson
#77
• B1 : Phát biểu lại giả thiết và kết luận của vấn đề dưới dạng
• Trong đó : GTi và KLj được xây dựng từ các biến mệnh đề và các
phép toán :
∧ ∨ ,
, ¬
chuẩn như sau: GT1, GT2, ..., GTn → KL1, KL2, ..., KLm
∧ thì thay bằng dấu ",“. Nếu KLi có phép
• B2 : Nếu GTi có phép thì thay bằng dấu ","
• B3 : Biến đổi dòng chuẩn ở B1 về thành danh sách mệnh đề
∨
như sau:
{ GT1, GT2, ..., GTn , ¬ KL1, ¬ KL2, ..., ¬ KLm }
Thuật giải Robinson
#78
• B4 : Nếu trong danh sách mệnh đề ở B2 có 2 mệnh đề đối
• B5 : Xây dựng mệnh đề mới bằng cách tuyển một cặp trong mệnh đề ở B2. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu thì các biến đó được loại bỏ.
• B6 : Áp dụng phép hợp giải
∧
∨
• p
(¬ p
q) → q
∨
∨
• (p
∨ ∧ q)
(¬ p
r) → q
r
ngẫu nhau thì bài toán được chứng minh. Ngược lại thì chuyển sang B5. (a và ¬a gọi là hai mệnh đề đối ngẫu)
Thuật giải Robinson
#79
• Nếu không xây dựng được thêm một mệnh đề mới nào
• và trong danh sách mệnh đề không có 2 mệnh đề nào đối ngẫu
nhau thì vấn đề không được chứng minh
Thuật giải Robinson – Ví dụ
#80
Chứng minh:
∨ ∨ (¬p ∨ ∧ q) (¬q ∨ ∧ r) (¬r ∨ ∧ s) (¬u ¬s) → ¬p ¬u
• B3: Danh sách mệnh đề:
∨ ∨ ∨ ∨ B2: ¬ p q, ¬ q r, ¬ r s, ¬ u ¬s → ¬ p, ¬u
• B4: Có 6 mệnh đề nhưng không đối ngẫu sang B5
∨ ∨ ∨ ∨ {¬ p q, ¬ q r, ¬ r s, ¬ u ¬s, p, u}
Thuật giải Robinson – Ví dụ
#81
∨
∨
∨
∨
{¬ p
q, ¬ q
• B5: Chọn cặp mệnh đề ¬ p
r, ¬ r ∨ ∨ q
s, ¬ u ∨ (cid:0) r
¬s, p, u} r∨
• B6: Danh sách mệnh đề mới:
(cid:0) ¬ q ¬ p
∨ ∨ {¬ p r , ¬ r ∨ , ¬ u s ¬s, p, u}
• Chọn cặp mệnh đề ¬ p
chưa có cặp mệnh đề đối ngẫu
∨ ∨ r ¬ r ∨ (cid:0) s ¬ p s∨
• Danh sách mệnh đề mới: {¬ p
∨ ∨ s, ¬ u ¬s, p, u} chưa có cặp
mệnh đề đối ngẫu
Thuật giải Robinson – Ví dụ
#82
∨
∨
{¬ p
s, ¬ u
¬s, p, u}
• Chọn cặp mệnh đề
∨
¬ p
∨ ∨ s
¬ u
¬s
¬ p
¬ u∨
∨
• Danh sách mệnh đề mới: {¬ p
¬ u, p, u} chưa có căp mệnh đề đối
ngẫu
∨
• Chọn cặp mệnh đề ¬ p
¬ u
∨ (cid:0) p
¬ u
• Danh sách mệnh đề mới: {¬ u, u} có cặp mệnh đề đối ngẫu Biểu
thức ban đầu được chứng minh
(cid:0)
Bài tập
#83
• Chứng minh:
{p → q, q → r, r → s, p} (cid:0) p s∧
Q&A
#84
