Bài giảng Biểu diễn tri thức

• Khái niệm • BDTT bằng Logic hình thức • BDTT bằng mạng ngữ nghĩa BDTT bằng mạng ngữ nghĩa • BDTT bằng hệ luật dẫn

Phạm Thi Vương

Biểu diễn tri thức và ứng dụng 30/10/07 2

• Tri thức (knowledge) ?

• Khái niệm

• Knowledge: the psychological result of perception and learning and reasoning (English English and learning and reasoning (English – English Dictionary)

ậ

, ọ ập • Tri thức là kết quả của quá trình nhận thức, học tập q

và lập luận

– Khái niệm: điểm, tam giác… • Các sự kiện, các nguyên lý, định lý, định Các sự kiện, các nguyên lý, định lý, định luật, quan hệ giữa các khái niệm = luật 2 tam giác có 3 cạnh bằng nhau thì bằng – 2 tam giác có 3 cạnh bằng nhau thì bằng nhau Kinh nghiệm • Kinh nghiệm

• Sự hiểu biết của con người trong một phạm vi, 1

lĩnh vực nào hay 1 vấn đề nào đó.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 3 30/10/07 4

• Tập hợp các tri thức liên quan đến vấn đề

mà chương trình quan tâm giải quyết.

• tìm ra các kỹ thuật, các phương pháp thể hiện, diễn đạt tri thức nhằm tổ chức được cơ sở tri thức trên máy tính và thực hiện các xử lý tri thức, vận dụng tri thức giải quyết vấn đề.

ệ

g

• BDTT: biểu diễn các loại tri thức của con người bằng các cấu trúc dữ liệu mà máy y g tính có thể xử lý được

1. Representational adequacy:

Dạng hình thức

Dạng thực

Khả năng biểu diễn tất cả các tri thức cần thiết cho lĩnh vực đó. 2. Inferential adequacy: 2 Inferential adequacy:

- Facts (sự kiện): sự thật trong lĩnh vực

- Representations (sự biểu diễn): dạng biểu diễn của sự kiện theo lược ợ đồ được chọn.

ọ

Khả năng xử lý các cấu trúc sẵn có để sinh ra các cấu trúc mới tương ứng với tri thức mới được cấu trúc mới tương ứng với tri thức mới được sinh ra từ tri thức cũ.

Cái cần biểu diễn

Cái có thể xử lý được

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 5 30/10/07 6

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 7 30/10/07 8

Inferential efficiency:

– Không một hệ thống nào có thể tối ưu tất cả các khả năng trên cho mọi kiểu tri thức.

Khả năng thêm vào cấu trúc tri thức thông tin bổ Khả năng thêm vào cấu trúc 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ấtnhất.

4. Acquisitional efficiency:

– Nhiều kỹ thuật dùng cho biểu diễn tri thức

cùng tồn tại. ồ

á iệ h

hấ là h

– Chương trình thường dùng nhiều hơn 1 kỹ

Khả năng thu được thông tin mới dễ dàng. 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 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 ì h ó hể kiể được tri thức.

thuật biểu diễn.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 9 30/10/07 10

• Tri thức thủ tục: mô tả cách thức, các

• Tri thức khai báo: cho biết một vấn đề

buớc để giải quyết một vấn đề.

được thấy như thế nào.

Loại tri thức này bao gồm các phát biểu

Loại tri thức này đưa ra giải pháp để

p p

ạ

g

y

thực hiện một công việc nào đó.

đơn giản, dưới dạng các khẳng định logic đúng hoặc sai

Các dạng tri thức thủ tục tiêu biểu Các dạng tri thức thủ tục tiêu biểu

thường là các luật, chiến lược, lịch trình, và thủ tục thủ tục

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 11 30/10/07 12

• Tri thức heuristic: mô tả các "mẹo" để dẫn

dắt tiến trình lập luận.

• Siêu tri thức: mô tả tri thức về tri thức. Loại tri thức này giúp lựa chọn tri thức thích hợp nhất trong số các tri thức khi giải quyết một vấn đề.

Tri thức heuristic còn được gọi là tri thức Tri thức heuristic còn được gọi là tri thức nông cạn do không bảm đảm hoàn toàn chính xác về kết quả giải quyết vấn đề. chính xác về kết quả giải quyết vấn đề

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 13 30/10/07 14

• Thụ động

ự

(

– Gián tiếp: những tri thức kinh điển. – Trực tiếp: những tri thức kinh nghiệm (không g g ệ g kinh điển) do “chuyên gia lĩnh vực” đưa ra

• Chủ độngộ g

• Dựa trên logic hình thức: dạng biểu diễn tri thức cổ điển nhất trong máy tính, với hai dạng phổ biến là logic mệnh đề và logic vị từ. Cả hai kỹ thuật này đều dùng ký hiệu để thể hiện tri thức và các toán tử áp lên các ký hiệu để suy luận logic.

ự p

g p

ệ

– Đối với những tri thức tiềm ẩn, không rõ ràng hệ thống phải tự phân tích, suy diễn, khám phá để có thêm tri thức mới

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 15 30/10/07 16

• Dạng luật dẫn: là cấu trúc tri thức dùng

• Dạng sơ đồ mạng: là 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

để 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.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 17 30/10/07 18

• Dạng cấu trúc frames, classes: là cấu

trúc dữ liệu để thể hiện tri thức đa dạng về khái niệm hay đối tượng nào đó.

• Sử dụng các ngôn ngữ đặc tả

• Logic mệnh đề • Logic vị từ cấp 1, cấp cao • Logic đa trị: các mệnh đề không đúng không sai Logic đa trị: các mệnh đề không đúng không sai • Logic mờ • Logic thời gian thời

L i

i

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 19 30/10/07 20

• Mệnh đề là một khẳng định, một phát biểu mà giá trị của nó chỉ có thể hoặc là đúng hoặc là sai (có thể phụ thuộc vào không gian, thời gian, chủ thể phát biểu, hoặc luôn có chân trị xác định).

( ),

),

g

(

• Các ký hiệu đại diện cho các mệnh đề có chân trị đúng hoặc sai: p,q,r,...(có thể phụ thuộc vào không gian, thời gian, chủ thể phát biểu, hoặc luôn có chân trị xác định. • Các toán tử logic not(¬), and(∧), or(∨), (cid:198) • Quy ước ngữ nghĩa: hằng đúng, hằng sai • Các tiên đề, các quy luật • Các tiên đề các quy luật

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 21 30/10/07 22

• Các ký hiệu đại diện cho các mệnh đề có

• Biểu thức logic được định nghĩa đệ quy

như sau: – Các hằng logic (True, False) và các biến

g g (

)

chân trị đúng hoặc sai: p,q,r. g

( ),

),

(

mệnh đề là các biểu thức logic

– Các biểu thức logic kết hợp với các toán tử

• Các toán tử logic not(¬), and(∧), or(∨), (cid:198) • Quy ước ngữ nghĩa: hằng đúng, hằng sai • Các tiên đề, các quy luật • Các tiên đề các quy luật

ể

logic (phép tuyển (∨), phép hội (∧ ), phủ định (¬ , ~, ), phép kéo theo (⇒, →), phép tương đương (⇔, ≡)) là các biểu thức logic đ )) là á biể thứ l i

(

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 23 30/10/07 24

ề

• Biểu thức logic dạng chuẩn: là biểu thức được xây dựng từ các biến mệnh đề và các phép toán ¬, ∧, ∨.

– Tập kí hiệu, mỗi kí hiệu đại diện cho môt vấn đề cơ bản trong tri thức: p,q,r... Các mệnh đề ề phức hợp của các mệnh đề cơ bản được viết dưới dạng các biểu thức logic. dưới dạng các biểu thức logic

– Các luật thể hiện những liên hệ trên các

mệnh đề và các biểu thức mệnh đề và các biểu thức

• Ta có cơ sở tri thức mô tả mối quan hệ của các

ể ế

thành phần trong một tam giác như sau: thành phần trong một tam giác nh sa – Nếu biết 3 cạnh của 1 tam giác ta có thể biết nữa chu

vi của tam giác đó

i ủ

ột t

– Nếu biết 2 cạnh và nữa chu vi của một tam giác thì ta

ủ

– Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của một tam giác thì ta có thể biết được diện tích của tam giác đó – Nếu biết ba cạnh và nữa chu vi của một tam h à ữ h Nế biết b giác thì ta biết được diện tích của tam giác đó Nế biết diệ tí h à đ ờ – Nếu biết diện tích và đường cao của một tam ột t giác thì ta biết được cạnh tương ứng với đường cao của tam giác đó đường cao của tam giác đó

– Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của

h à ột ó k

h đó ủ

iữ 2

có thể biết được cạnh còn lại của tam giác đó Nếu biết được diện tích và một cạnh của một tam – Nếu biết được diện tích và một cạnh của một tam giác thì ta có thể biết được chiều cao tương ứng với cạnh đó Nế biết 2 một tam giác thì ta có thể biết được cạnh còn lại của tam giác đó.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 25 30/10/07 26

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 27 30/10/07 28

Thuật giải Vương Hạo

á ñ à h

ø k á

û hi

B1 Ph ù bi B1 : Phaùt bieåu laïi giaû thieát vaø keát luaän cuûa vaán ñeà theo i daïng chuaån sau :

• Vấn đề: chứng minh tính đúng đắn của

GT → KL KL

GT1, GT2, ..., GTn GT GT

→ KL1, KL2, ..., KLm KL

suy diễn a(cid:198)b q y

• Giải quyết:

Trong ñoù caùc GTi vaø KLi laø caùc meänh ñeà ñöôïc xaây döïng tö cac bien meänh ñe va 3 phep noi cô ban : ∧, ∨, döng töø caùc bieán meänh ñeà vaø 3 pheùp noái cô baûn : ∧ ∨ ¬

sử dụng các phép suy luận và biến đổi

g

g p ∨ r → s

(r ∧ s)

logic (cid:206) khó cài đặt ặ Sử dụng bảng chân trị O(2n) 2 phương pháp với độ phức tạp O(n) 2 phương pháp với độ phức tạp O(n)

⇒

B2 : Chuyen ve cac GTi va KLi co daïng phu ñònh. B2 : Chuyeån veá caùc GTi vaø KLi coù dang phuû ñònh. Ví duï : p ∨ q, ¬ (r ∧ s), ¬g, p ∨ r → s, ¬p p ∨ q p p ∨ q, p ∨ r, p → (r ∧ s), g, s

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 29 30/10/07 30

Thuật giải Vương Hạo

ù h ù

h á h ù

b è

B5 : Moät doøng ñöôïc chöùng minh neáu toàn taïi chung moät meänh ñe ô ô ca hai phía. meänh ñeà ôû ôû caû hai phía

B3 : Neáu ôû GTi coù pheùp ∧ thì thay theá pheùp ∧ baèng daáu “,” h h d á Neáu ôû KLi coù pheùp ∨ thì thay theá pheùp ∨ baèng daáu “,” Ví duï :

Ví duï :

ñöôïc chöùng minh

p ∧ q, r ∧ (¬p ∨ s) → ¬q, ¬s p, q, r, ¬p ∨ s → ¬q, ¬s

⇒

p, q → q p, ¬p → q ⇒

p→ p, q

B4 : Neáu ôû GTi coù chöùa pheùp ∨ thì taùch thaønh hai doøng con. Neu ô KLi co chöa phep ∧ thì tach thanh hai dong con. Neáu ôû KLi coù chöùa pheùp ∧ thì taùch thaønh hai doøng con.

á kh â

û h i

ät bi

ù h

û 2

Ví duï :

p, ¬p ∨ q → q

B6 : a) Neáu moät doøng khoâng coøn pheùp noái ∧ hoaëc ∨ ôû caû hai veá vaø ôû 2 veá khoâng coù chung moät bieán meänh ñeà ä h ñ à thì doøng ñoù khoâng ñöôïc chöùng minh.

b) Moät vaán ñeà ñöôc chöùng minh neáu taát caû doøng daãn b) Moät van ñe ñöôïc chöng minh neu tat ca dong dan xuaát töø daïng chuaån ban ñaàu ñeàu ñöôïc chöùng minh.

p, ¬p → q

p, q → q

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 31 30/10/07 32

Thuật giải Vương Hạo

r, ¬p ∨ p ∨ r

s → ¬q, ¬r ∧ s s → q r ∧ s

a ∧ b → c và b ∧ c → d và a và b, suy ra d a ∧ b → c và b ∧ c → d và a và b, suy ra d

Xét các câu đúng sau: • • • •

“Nếu trời mưa thì Lan mang theo dù” “Nếu Lan mang theo dù thì Lan không bị ướt” “Nếu trời không mưa thì Lan không bị ướt” Xây dựng các câu trên bằng các biểu thức logic mệnh đề

Hãy chứng minh rằng “Lan không bị ướt” bằng

phương pháp Vương Hạo

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 33 30/10/07 34

• Cho các biểu thức logic mệnh đề đúng

• Thuaät giaûi naøy hoaït ñoäng döïa treân phöông

( → )

p

g

ä

• Chöùng minh pheùp suy luaän (a → b) laø ñuùng g y

phaùp chöùng minh phaûn chöùng. C p (vôùi a laø giaû thieát, b laø keát luaän).

a → f a → (f → p) p ^ q → d p q a a d →g a ^ d →g

• Phaûn chöùng : giaû söû b sai suy ra ¬b laø ñuùng • Phan chöng : gia sö b sai suy ra ¬b la ñung. • Baøi toaùn ñöôïc chöùng minh neáu a ñuùng vaø ¬b â

ñung sinh ra moät mau thuan. ñ ù

th ã

i h

ät

• Hãy dùng phương pháp Vương Hạo để

chứng minh hoặc bác bỏ g≡1 chứng minh hoặc bác bỏ g 1

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 35 30/10/07 36

• B1 : Phaùt bieåu laïi giaû thieát vaø keát luaän cuûa vaán ñeà döôùi daïng

chuaån nhö sau :

GTn → KL1 KL2

l i hì h

i h N

B5 (

GT1, GT2, ...,GTn → KL1, KL2, .., KLm GT1 GT2 KLm Trong ñoù : GTi vaø KLj ñöôïc xaây döïng töø caùc bieán meänh

• B4 : Neáu trong danh saùch meänh ñeà ôû böôùc 3 coù 2 meänh ñeà ñoái ngaãu nhau thì baøi toaùn ñöôïc chöùng minh. Ngöôïc laïi thì chuyeån sang B5. (a vaø ¬a goïi laø i l ø å hai meänh ñeà ñoái ngaãu nhau)

ñeà vaø caùc pheùp toaùn : ∧, ∨, ¬

• B2 : Neáu ôû GTi coù pheùp ∧ thì thay theá pheùp ∧ baèng daáu “,” Neu ô KLi co phep ∨ thì thay the phep ∨ bang dau , Neáu ôû KLi coù pheùp ∨ thì thay theá pheùp ∨ baèng daáu “ ”

∨

p ∨ ¬q

• B3 : Bieán ñoåi doøng chuaån ôû B1 veà thaønh danh saùch meänh ñeà

• B5 : Xay döïng moät meänh ñe môi bang cach tuyen • B5 : Xaây döng moät meänh ñeà môùi baèng caùch tuyeån moät caëp meänh ñeà trong danh saùch meänh ñeà ôû böôùc 3. Neáu meänh ñeà môùi coù caùc bieán meänh ñeà ñoái ngaãu nhau thì caùc bieán ñoù ñöôïc loaïi boû. á Ví duï : Hai meänh ñeà ¬q, q laø ñoái ngaãu neân seõ ñöôïc loaïi boû i b û H i

¬r ∨ s ∨ q õ ñ â ã

l ø ñ ái

nhö sau :

{ GT1, GT2, ..., GTn , ¬ KL1, ¬ KL2, ..., ¬ KLm }

ä h ñ à ⇒ p ∨ ¬r ∨ s

• B6 : Thay theá hai meänh ñeà vöøa tuyeån trong danh

ä h ñ à b è

ä h ñ à

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 37 30/10/07 38

• Chöùng minh raèng • ¬p ∨ q, ¬q ∨ r, ¬r ∨ s, ¬u ∨ ¬s → ¬p, ¬u

saùch meänh ñeà baèng meänh ñeà môùi. ù h ôùi Ví duï :

{ p ∨ ¬q , ¬r ∨ s ∨ q , w ∨ r, s ∨ q } { p ∨ s ∨ q }

r ∨ s ∨ q

w ∨ r

q

⇒ { p ∨ ¬r ∨ s , w ∨ r, s ∨ q }

• B7 : Neáu khoâng xaây döïng ñöôïc theâm moät meänh ñeà môùi naøo vaø trong danh saùch meänh ñeà khoâng coù 2 meänh ñeà naøo ñoái ngaãu nhau thì vaán ñeà khoâng ñöôïc chöùng minh.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 39 30/10/07 40

• Tuyeån hai caëp meänh ñeà ñaàu tieân: ¬p ∨ r ∨ ¬r ∨ s ⇒ ¬p ∨ s

ù h

ä h ñ à th ø h {

• B3: { ¬p ∨ q, ¬q ∨ r, ¬r ∨ s, ¬u ∨ ¬s, p, u } • B4 : Coù taát caû 6 meänh ñeà nhöng chöa coù meänh ñeà

Danh saùch meänh ñeà thaønh {¬p ∨ s, ¬u ∨ ¬s, p, u } D h } Vaãn chöa coù hai meänh ñeà ñoái ngaãu

naøo ñoái ngaãu nhau.

• B5 : ⇒ tuyeån moät caëp meänh ñeà (choïn hai meänh ñeà

• Tuyeån hai caëp meänh ñeà ñaàu tieân: ¬p ∨ s ∨ ¬u ∨ ¬s ⇒ ¬p ∨ ¬u

Danh saùch meänh ñeà thaønh : {¬p ∨ ¬u, p, u } Vaãn chöa coù hai meänh ñeà ñoái ngaãu

¬q ∨ r

⇒ ¬p ∨ r

• Tuyeån hai caëp meänh ñeà : ¬p ∨ ¬u ∨ u ⇒ ¬p

Danh saùch meänh ñeà trôû thaønh : {¬p p } Danh sach meänh ñe trô thanh : {¬p, p } Coù hai meänh ñeà ñoái ngaãu neân bieåu thöùc ban ñaàu ñaõ ñöôïc

coù bieán ñoái ngaãu). Choïn hai meänh ñeà ñaàu : ¬p ∨ q ∨ Danh saùch meänh ñeà thaønh : {¬p ∨ r , ¬r ∨ s, ¬u ∨ ¬s, p, u } Vaãn chöa coù meänh ñeà ñoái ngaãu.

chöùng minh.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 41 30/10/07 42

• Logic mệnh đề: không thể can thiệp vào cấu trúc của một mệnh đề. Hay nói một cách khác là mệnh đề không có cấu trúc.

• Vị từ là một phát biểu đề cập tới các phần tử thuộc những phạm vi nhất định và chân trị phụ thuộc các phần tử này.

• Khi các phần tử xác định rõ thì phát biểu

ệ

trở thành mệnh đề.

• Ví dụ:

“n là 1 số nguyên tố” n là 1 số nguyên tố “m là ước số của n”

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 43 30/10/07 44

• Về mặt toán học vị từ là hàm lấy giá trị logic phụ thuộc

• Liên quan đến vị từ ta cũng có các phép

bao gồm tên và biến.

ồ

ế

toán vị từ: ¬, ∧, ∨, →, ↔.

• Khi thực hiện các phép toán trên vị từ ta

p p

ị

ệ

• Kí hiệu: hàm bao gồm tên và biến ố

ự được vị từ mới Các lượng từ: ∃, ∀, ∃! • Các lượng từ: ∃ ∀ ∃!

– p(n)= “n là 1 số nguyên tố” ố – us(m,n)=“m là ước số của n” – Vi(Cam, ngọt)=”Vị cam là ngọt” Vi(Cam ngọt) ”Vị cam là ngọt” – Mau(Cam, xanh)=”Cam co mau xanh”

(cid:206) Vitu(, , ,...);

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 45 30/10/07 46

Tri thức biễu diễn theo logic vị từ gồm 2

thành phần:

–

• Các phát biểu có lượng từ (các phát biểu lượng từ hóa) là phát biểu có lượng từ và có các vị từ từ hóa) là phát biểu có lượng từ và có các vị từ theo các biến Vd: ∃x,p(x) ∀x, p(x)

Vd: bất kỳ số nào cũng có số nguyên tố lớn hơn

–

Tập các vị từ, trong đó mỗi vị từ đại diện cho một phát biểu Tập các sự kiện và luật dưới dạng các biểu thức logic vị từ

nónó – p(y) = “y là số nguyên tố” – ∀x∈N, ∃y∈N, p(y) ∧ (y>x) Hoặc có thể viết ể ế - ∀x, ∃y, p(y) ∧ (y>x)

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 47 30/10/07 48

• Vd: “A là bố của B nếu B là anh hoặc là em

• Để biểu diễn tri thức theo logic vị từ ta

ộ

ời

một người con của A ” ủ A ” Bo(A,B)= ∃Z: Bo(A,Z) ∧ (Anh(B,Z) ∨ Anh (Z,B))

a) Bố ("An", "Bình") có giá trị đúng (Anh là bố của

thực hiện 2 giai đoạn sau: – Gđ1: Xác lập các vị từ cần thiết cho việc biễu diễn(mỗi vị từ phải có tên gọi, biến phải có kiểu xác định)

Bình) Bình)

– Gđ2: Viết các sự kiện và luật thành(dưới

ế

b) Anh("Tú", "Bình") có giá trị đúng (Tú là anh của

dạng) các công thức logic vị từ

Bình) Bình)

c) Bố ("An", "Tú") sẽ có giá trị là đúng. (An là bố

của Tú).

•

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 49 30/10/07 50

• Vd: “Không có vật gì lớn nhất và không có

Bất kì số tự nhiên nào cũng là ước số của chính nó chính nó 1 là ước của mọi số tự nhiên

ọ

ự

vật gì nhỏ nhất” , y

(∀x, ∃y : LớnHơn(y,x) ) ∧ (∀x, ∃y : , y (

(y, ) )

(

• • Mọi số tự nhiên đều là ước số của 0 •

LớnHơn(x,y) )

•

Với a,b,c tuỳ ý ta có nếu a là ước số của b và b là ước số của c thì à là ước số của c. USCLN ủ 1 ố tù ý à 0 là bằ • USCLN của 1 số a tùy ý và 0 là bằng a. USCLN của 0 và 1 số a tùy ý là bằng a. Với a >b, ta có uscln của a-b và b cũng chính g , là uscln của a và b Với a

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 51 30/10/07 52

• Thuật toán hợp giải • Ngôn ngữ Prolog

• Kiểu biểu diễn tri thức vị từ giống như hàm trong các ngôn ngữ lập trình, đối tượng tri thức là tham số của hàm, giá trị mệnh đề chính là kết quả của hàm (kiểu Boolean). (kiểu Boolean)

ệp

ộ

ệ

• Biểu diễn tri thức bằng mệnh đề gặp khó khăn là không thể can thiệp vào cấu trúc của một mệnh đề → đưa ra khái niệm lượng từ, vị từ.

• Với vị từ có thể biểu diễn tri thức dưới dạng các mệnh đề tổng quát tổng quát.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 53 30/10/07 54

Mạng ngữ nghĩa là 1 mô hình biểu diễn tri thức có dạng đồ thị trong đó:

Mỗi đỉnh(nút) của sơ đồ thể hiện một yếu tố – Mỗi đỉnh(nút) của sơ đồ thể hiện một yếu tố nào đó của tri thức.

– Mỗi cung thể hiện một sự liên hệ nào đó giữa

ộ ự

ệ

các yếu tố của tri thức

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 55 30/10/07 56

ù h t å

h ùt

iöõ

ù kh ùi

giöõa caùc khaùi nieäm chích choøe, chim, hoùt, caùnh, toå coù hí h h ø ù i moät soá moái quan heä nhö sau :

Chích choe la moät loai chim. Chích choøe laø moät loaøi chim

cánh

Chim bieát hoùt

có

Hoùt

bieát

laø

Chích choe choøe

Sẽ Sẽ

Chim Chim

là là

Chim coù caùnh Chi ù h

Chim

di chuyển

Chim soáng trong toå

coù

bay b

Caùnh

Toå

laø m

Một số tri thức về loài “chim sẽ” được biểu diễn trên mạng ngữ nghĩa

Caùc moái quan heä naøy seõ ñöôïc bieåu dieãn tröïc quan baèng moät ñoà thò beân treân

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 57 30/10/07 58

Vấn đề:

Trên mạng ngữ nghĩa có một số đỉnh

g y

• Ví dụ 2: Bài toán tam giác tổng quát • Một số bài toán thông thường về tam giác như: Cho 3 • Một số bài toán thông thường về tam giác như: “Cho 3 cạnh của một tam giác, tính chiều dài các đường cao”, “cho góc a, b và cạnh AC, tính chiều dài các đường trung tuyến”, …

được cho trước. được cho trước

Ta muốn đạt đến 1(nhiều) đỉnh mục tiêu.

• Tồn tại hay không một chương trình tổng quát có thể giải được tất cả những bài toán tam giác dạng này ? Câu trả lời là có.

• Bài toán sẽ giải bằng mạng ngữ nghĩa: • Có 22 yếu tố liên quan đến cạnh và góc của tam giác.

Đỉnh kích hoạt: đỉnh đã biết

Để xác định hay để xây dựng một tam giác ta cần 3 yếu Để xác định hay để xây dựng một tam giác ta cần 3 yếu tố trong đó có yếu tố cạnh

• Sử dụng khoảng 200 đỉnh để chứa công thức + 22 đỉnh

để chứa các yếu tố của tam giác.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 59 30/10/07 60

Đỉ h ủ đồ thị b

Bước1: Kích hoạt các đỉnh được cho trước Bước 2: while (chưa đạt tới mục tiêu)

{{

( ý ệ

2.1 Tìm đỉnh để có thể truyền kích hoạt

• Mạng ngữ nghĩa cho bài toán có cấu trúc như sau • Đỉnh của đồ thị bao gồm 2 loại: i ồ 2 l • Đỉnh chứa công thức (ký hiệu bằng hình chữ nhật) • ) g Đỉnh chứa yếu tố tam giác (ký hiệu bằng hình tròn) • Cung: chỉ nối từ đỉnh hình tròn đến đỉnh hình chữ nhật cho biết yếu tố tam giác xuất hiện trong công thức nào

tới

• Lưu ý: Trong một công thức liên hệ giữa n yếu tố của

thấy mục tiêu

tam giác, ta giả định rằng nếu đã biết giá trị của n-1 yếu tố thì sẽ tính được giá trị của yếu tố còn lại ố

ủ

ế

ố

2.2 if(tìm không được) KL: không tìm y 2.3 else kích hoạt đỉnh mới

} }

0 0

A ) ) A

B B

) )

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 61 30/10/07 62 30/10/07

• Ví dụ: Cho hai góc A, B và chiều dài cạnh a của tam giác. Tính chiều dài đường cao hc . Với mạng ngữ nghĩa đã cho trong hình trên. Các bước thi hành của thuật toán như sau:

3 3

B B

) )

+ + f A B C π π + + − = f A B C 1 : : 1 b sin( sin( b i ( sin( −

a sin( sin( c i ( C sin( C =

−

p p a p b p c

)(

(

)

f S : 4

f S − 5 :

ch c 2

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 63 30/10/07 64

A+ B + C - π = 0 A+ B + C π = 0

(4) (4)

C

B

A

• Thuật giải lan truyền kích hoạt B1 Kích hoạt những đỉnh hình tròn đã cho ban • B1: Kích hoạt những đỉnh hình tròn đã cho ban đầu (những yếu tố đã có giá trị)

• B2: Lặp lại bước sau cho đến khi kích hoạt

ặp ạ

ạ

(1)

(2)

a sin

b b sin

c sin

b b sin

được tất cả những đỉnh ứng với những yếu tố cần tính hoặc không thể kích hoạt được bất kỳ đỉnh nào nữa đỉnh nào nữa

c

a

b

hc

(5)

(3)

)(

S – ½ hc.c = 0

S =

)c-pb-pa-pp (

• Nếu một đỉnh hình chữ nhật có cung nối với n đỉnh hình tròn mà n-1 đỉnh hình tròn đã được kích hoạt thì kích hoạt đỉnh hình tròn còn lại (và kích hoạt thì kích hoạt đỉnh hình tròn còn lại (và tính giá trị đỉnh còn lại này thông qua công thức ở đỉnh hình chữ nhật).

S

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 65 30/10/07 66

• Kích hoạt:

• Quy tắc lan truyền

y

g

p ụ g

ệ

Yếu tố: đã biết do giả thiết hay do tính từ công thức g Công thức: Công thức áp dụng được để tạo yếu tố mới tạo yếu tố mới

Đối với công thức: công thức được áp dụng khi trong số các yếu tố liên hệ với công thức có đúng một yếu tố chưa biết. Đối với yếu tố: kích hoạt được khi có Đối với yếu tố: kích hoạt được khi có một công thức được kích hoạt quan hệ với yếu tố đó yếu tố đó

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 67 30/10/07 68

A+ B + C - π = 0 A+ B + C π = 0

(4) (4)

C

CC

B

A

(1)

(2)

a sin

b b sin

a sin

b b sin

c sin

b b sin

c sin

b b sin

c

a

b

hc

(5)

(3)

)(

S – ½ hc.c = 0

S =

)c-pb-pa-pp (

S =

)c-pb-pa-pp (

S

A+ B + C - π = 0 A+ B + C π = 0

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 69 30/10/07 70

(4) (4)

C

B

A

(1)

(2)

a sin

b b sin

a sin

b b sin

c sin

b b sin

c sin

b b sin

c c

c

a

b

b b

hc

(5)

(3)

)(

S – ½ hc.c = 0

S =

)c-pb-pa-pp (

S =

)c-pb-pa-pp (

S

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 71 30/10/07 72

A+ B + C - π = 0 A+ B + C π = 0

(4) (4)

C

B

A

• Giả thiết: a=5, b=4, A=Pi/2 • Mục tiêu: S • Kết quả: S=6 Kết quả: S=6

(1)

(2)

a sin

b b sin

c sin

b b sin

c

a

b

hc

(5)

(3)

)(

S – ½ hc.c = 0

S =

)c-pb-pa-pp (

SS

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 73 30/10/07 74

• E = tập các yếu tố liệt kê theo thứ tự

• Biễn diễn đồ thị dưới dạng ma trận • Biễn diễn đồ thị dưới dạng danh sách

π ;

f A B C 1

= {a,b,c,A,B,C,S,R,p....} • F = tập các công thức F = tập các công thức = + + =

b sin(

⎧ ⎨ ⎩

⎫ ... ⎬ ⎭

a ) A sin( Giả sử có m công thức, n yếu tố (cid:206) r là ma Giả ử ó thứ

B ) ế tố (cid:206) là

neáu f coù quan heä vôùi yeáu toá j

j [ ][ ]

R i

ô trận cấp mxn 1 ⎧= ⎨ ⎩

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 75 30/10/07 76

Öu ñieåm Ö ñi å

(cid:57) Maïng ngöõ nghóa raát linh ñoäng, ta coù theå deã daøng theâm vaøo mang caùc ñænh hoaëc cung môùi ñeå boå sung them vao maïng cac ñænh hoaëc cung môi ñe bo sung caùc tri thöùc caàn thieát.

(cid:57) Maïng ngö nghóa co tính tröïc quan cao nen rat de (cid:57) Mang ngöõ nghóa coù tính tröc quan cao neân raát deã hieåu.

=

R

P

= 2 P I R

P=UI

U I I

2 U R R

(cid:57) Mang ngöõ nghóa cho pheùp caùc ñænh coù theå thöøa keá Maïng ngö nghóa cho phep cac ñænh co the thöa ke caùc tính chaát töø caùc ñænh khaùc thoâng qua caùc cung loaïi “laø”, töø ñoù, coù theå taïo ra caùc lieân keát “ngaàm” giöõa nhöng ñænh khong co lien ket tröïc tiep vôi nhau. nhöõng ñænh khoâng coù lieân keát tröc tieáp vôùi nhau

(cid:57) Maïng ngöõ nghóa hoaït ñoäng khaù töï nhieân theo caùch thöc con ngöôi ghi nhaän thong tin. thöùc con ngöôøi ghi nhaän thoâng tin

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 77 30/10/07 78

Nhược điểm: Nhược điểm:

(cid:57) Cho ñeán nay, vaãn chöa coù moät chuaån naøo quy ñònh caùc giôùi haïn cho caùc ñænh vaø cung cuûa maïng. Nghóa laø baïn coù theå gaùn gheùp baát kyø khaùi nieäm naøo cho ñænh hoaëc cung!

(cid:57) Tính thöøa keá (voán laø moät öu ñieåm) treân mang seõ coù (cid:57) Tính thöa ke (von la moät öu ñiem) tren maïng se co theå daãn ñeán nguy cô maâu thuaãn trong tri thöùc.

Gaø

Hoùt

bieát

laø

Chích Chích choøe

Chim

coù

lam laøm

Toå å

C ù Can h

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 79 30/10/07 80

Nếu 2 tam giác có 3 cạnh tương ứng bằng nhau thì bằng nhau

• Luật dẫn? • Luật dẫn là phát biểu dưới dạng if p1 p2 if p1, p2, ..., pm p then q1, q2,..., qn

Biểu diễn: T1: tam giác T2: tam giác iá T2 t

là á

pi là các sự kiện giả thiết qj là các sự kiện kết luận kiệ kết l ậ

If T1.a=T2.a, T1.b=T2.b, T1.c=T2.c then T1 T2 then T1=T2

1 1

2 2

m (cid:198) 1 m (cid:198) 1

2 2

n n

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 81 30/10/07 82

• Mỗi phản ứng hóa học có thể xem là một

• Hệ luật dẫn là tri thức gồm một tập các luật

trên tập sự kiện

luật dẫn

HCl + NaOH (cid:198) NaCl +H2O

• Hệ luật dẫn gồm 2 thành phần chính: (F,R) )

ệ ậ

( ,

p

g

• F=tập sự kiện R tập luật dẫn, mỗi luật có dạng A(cid:198)B • R=tập luật dẫn mỗi luật có dạng A(cid:198)B

Biễu diễn Biễu diễn

HCl, NaOH (cid:198) NaCl, H2O

Thường tổ chức hệ luật dẫn với vế phải chỉ là 1 sự kiện Thường tổ chức hệ luật dẫn với vế phải chỉ là 1 sự kiện

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 83 30/10/07 84

0 0

• Biễu diễn quan hệ dẫn xuất giữa các yếu

=

f f

2 : :

tố trong tam giác

A )

B

)

• Biễu diễn phản ứng hóa học dưới dạng ạ g g

p

ọ

=

f

3 :

luật dẫn

B

)

+ + f A B C π π + + − = f A B C 1 : : 1 b sin( b b sin( −

a sin( c c C sin( =

−

p p a p b p c

)(

(

)

f S 4 :

f S − 5 :

ch c h 2

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 85 30/10/07 86

Vấn đề:

trên một tri thức dạng hệ luật dẫn(F,R), giả sử cho trước tập sự kiện GT G và có 1 giả sử cho trước tập sự kiện GT G và có 1 tập sự kiện mục tiêu KL K mà ta muốn đạt được. được

Hãy tìm một quá trình áp dụng các luật dẫn để từ GT G suy ra KL K để từ GT G KL K

Cho một cơ sở tri thức r1: A, B → C • C r1 A B r2: C, D → E • r3: F B → G r3: F, B → G • r4: A, E → H • r5: F → E • r6: B, E → G • Với các sự kiện B đúng, D, đúng. Hã t ì h bà Hãy trình bày quá trình lập luận tiến và lập luận lùi à lậ l ậ lùi á t ì h lậ l ậ tiế để biết G đúng hay sai.

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 87 30/10/07 88

• Ví dụ:

• 2 kỹ thuật suy diễn cơ bản là:

F = {a,b,c, A, B, C…} R={A,B(cid:198)C,…} R={A B(cid:198)C }

Suy diễn tiến Suy diễn lùi Suy diễn lùi

• Bài toán

GT = {a,b,A} GT { b A} KL={S,R}

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 89 30/10/07 90

• Bước 1: Đặt A là tập sư kiện đang có.

A=GT

• Là quá trình suy diễn đi từ giả thiết đến kết luận thông qua việc áp dụng các định luật, định lý.

• Bước 2: while(mục tiêu chưa thuộc A) Bước 2: while(mục tiêu chưa thuộc A)

p

• Quá trình này trải qua nhiều bước suy g

{ ………… }

ợ

g

ụ

y

luân xuất phát từ giả thiết ban đầu để sinh ra những sự kiện mới cho tới khi đạt được mục tiêu hay tới khi không tìm được luật ậ nào áp dụng được để sinh ra sự kiện mới.

• Bước 3: Kết luận: tìm được mục tiêu

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 91 30/10/07 92

Bước 2: while(mục tiêu chưa thuộc A)

• Là phép suy luận truy ngược đi từ mục

tiêu trở về giả thiết iê ở ề iả hiế

{{ Tìm kiếm luật r để áp dụng sinh ra sụ kiện mới if( khong tim duoc luật) if( khong tim d oc l ật)

• Xuất phát từ mục tiêu ta xem xét hệ luật ó thể dẫ

kiệ

hữ

à

Dừng, kết luận không giải được

lelse

để tì để tìm xem những sụ kiện nào có thể dẫn ra được mục tiêu và sự kiện này sẽ được xem xét như là mục tiếu mới cho các xem xét như là mục tiếu mới cho các bước truy ngược tiếp theo.

Ghi nhận r đã được sử dụng Bổ sung sự kiến mới tìm được vào A ế

ổ

}

• Quá trình này kết thúc khi tất cả các mục • Quá trình này kết thúc khi tất cả các mục tiêu phát sinh đầu đã được biết hay thuộc giả thiết. giả thiết

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 93 30/10/07 30/10/07 94

ậ

ứ

ẫẫ

Ưu điểm:

• Quá trình suy diễn ngược này này sẽ phát sinh ra 1 sơ đồ cây AND/OR các mục tiêu nên việc cài đặt khá phức tạp.

ï g

(cid:153) Caùc luaät raát deã hieåu neân coù theå deã daøng duøng ñeå trao ñoåi vôùi ngöôøi duøng (vì noù laø moät trong g ) nhöõng dang tö nhieân cuûa ngoân ngöõ).

(cid:153) Coù theå deã daøng xaây döïng ñöôïc cô cheá suy luaän vaø giaûi thích töø caùc luaät.

(cid:153) Vieäc hieäu chænh vaø baûo trì heä thoáng laø töông ñoái deã daøng.

(cid:153) Coù theå caûi tieán deã daøng ñeå tích hôïp caùc luaät môø.

(cid:153) Caùc luaät thöôøng ít phuï thuoäc vaøo nhau. g p

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 95 30/10/07 96

ứ

ậ

ẫẫ

Nhược điểm:

class Luat {{ public:

(cid:153) Caùc tri thöùc phöùc tap ñoâi (cid:153) Cac tri thöc phöc taïp ñoi luc ñoi hoi qua nhieu luùc ñoøi hoûi quaù nhieàu (haøng ngaøn) luaät dẫn. Ñieàu naøy seõ laøm naûy sinh nhieàu vaán ñeà lieân quan ñeán toác ñoä laãn quaûn trò heä thoáng.

sets gt; sets gt; sets kl; int dsd; Luat(); friend ostream & operator <<(ostream &o,Luat &L);

(cid:153) Ngöôøi xaây döïng heä thoáng thích söû duïng luaät dẫn hôn taát caû phöông phaùp khaùc, neân hoï thöôøng tìm moïi cach ñe bieu dien tri thöc bang luaät cho du co phöông caùch ñeå bieåu dieãn tri thöùc baèng luaät cho duø coù phöông phaùp khaùc thích hôïp hôn! Ñaây laø nhöôïc ñieåm mang tính chuû quan cuûa con ngöôøi.

}};

ù h ä dö t

ë kh ù kh ê

(cid:153) Cô sôû tri thöùc luaät dẫn lôùn seõ laøm giôùi haïn khaû naêng tìm kieám cuûa chöông trình ñieàu khieån. Nhieàu heä thoáng gaëp kho khan trong vieäc ñanh gia cac heä döïa tren luaät ät ä ñ ù h i cuõng nhö gaëp khoù khaên khi suy luaän treân luaät. 30/10/07

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 97 30/10/07 98

• void khoitao(); • void nhaplieu(); • int timluat(); int timluat(); • void Giaitoan();

sets Tapsukien; Luat Tapluat[50]; int soluat; int soluat; sets GT; sets KL; t KL

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 99 30/10/07 100

void Giaitoan() {

int i; while(!in(GT,KL) && (i=timluat())>-1) {{

void main() {

if(!in(GT,Tapluat[i].kl)) {{

GT.insert(Tapluat[i].kl); Tapluat[i].dsd=1;

}} else Tapluat[i].dsd=1;

clrscr(); clrscr(); init(); input(); t() i Giaitoan(); getch();

}} if(!in(GT,KL)) cout<<"Khong giai duoc"; else cout<<"Thanh cong";

} }

}

void Giaitoan() {

int i,buoc; b buoc=0; 0 while(!in(GT,KL) && (i=timluat())>-1) {

int timluat() {

if(!in(GT,Tapluat[i].kl)) if(!in(GT Tapluat[i] kl)) {

for(int i=0;i

{

(

[ ]

Gia thiet: "<

GT.insert(Tapluat[i].kl); Tapluat[i] dsd=1; Tapluat[i].dsd 1; buoc++; cout<<"Buoc "<

} else Tapluat[i].dsd=1;

if(Tapluat[i].dsd==0 && in(GT,Tapluat[i].gt)) return i; } return -1;

} }

} if(!in(GT,KL)) cout<<"Khong giai duoc"; else cout<<"Thanh cong"; "

t<<"Th

}

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 101 30/10/07 102

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 103 30/10/07 104

class congthuc{

class yeuto{ char s[3]; [3]

char s[30];

public:

]

(){ [

(

py(

(

h public: ;}; yeuto(){s[0]='\0';}; y yeuto(char *s1){strcpy(s,s1);}; void set(char *s1){strcpy(s,s1);}; friend istream & operator >>(istream &i,yeuto &yt); & ) & f i d i friend ostream & operator <<(ostream &o,yeuto &yt); (yeuto yt1,yeuto yt2); friend int operator ==(yeuto yt1 yeuto yt2); friend int operator

congthuc(){s[0]='\0';}; void set(char *s1){strcpy(s,s1);}; ) } ){ congthuc(char *s1){strcpy(s,s1);}; friend ostream & operator <<(ostream p &o,congthuc &ct);

};

} };

id i

void khoitao(); void input(); t() void Giaitoan(); void output(); p (); int vitri(yeuto y); int timcongthuc();

float tinhtheocongthuc(int i, int vt);

float congthuc0(int vt); float congthuc1(int vt); float congthuc1(int vt); float congthuc2(int vt); float congthuc3(int vt); float congthuc4(int vt); float congthuc5(int vt);

Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 105 30/10/07 106 30/10/07