 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH
BIỂU DIỄN TRI THỨC VÀ SUY LUẬN
Đề tài:
TÌM HIỂU MẠNG TÍNH TOÁN VÀ ỨNG DỤNG
GIẢI BÀI TOÁN HÓA HỌC
Giảng viên hướng dẫn : PGS.TS ĐỖ VĂN NHƠN
Học viên thực hiện : TRỊNH NAM VIỆT
MSHV : CH1301115
MỤC LỤC
CH1301115 – Trịnh Nam Việt  Page 1
2014
Tháng 3/2014
 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
Mở đầu 2
I. Các phương pháp biểu diễn tri thức cơ bản 3
1. Logic mệnh đề và logic vị từ 3
2. Biểu diễn tri thức bằng luật dẫn 3
3. Biểu diễn tri thức bằng mạng ngữ nghĩa 4
II. Mô hình biểu diễn tri thức COKB 5
1. Đối tượng tính toán (C-Object) 5
2. Mô hình cho một C-Object 6
3. Các thành phần của mô hình COKB 7
III. Mạng các đối tượng tính toán 8
1. Mạng con, đối tượng tính toán 9
2. Mạng các đối tượng tính toán 10
IV. Ứng dụng 13
1. Thiết kế cơ sở tri thức cho miền hóa học vô cơ 14
2. Thiết kế bộ suy diễn tự động của chương trình 15

và các toán tử áp lên các ký hiệu để suy luận logic. Logic đã cung cấp cho các nhà
nghiên cứu những công cụ hình thức để biểu diễn và suy luận tri thức. Các phép tóan
logic được sử dụng phổ biến của dạng là: and ( Λ ), or ( V ), not ( ~ ) và phép kéo theo
( → ), tương đương ( ≡ ).
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.
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.
2. Biểu diễn tri thức bằng luật dẫn
Phương pháp biểu diễn tri thức bằng luật dẫn được phát minh bởi Newell và Simon, trong
lúc hai ông đang cố gắng xây dựng một hệ giải bài toán tổng quát. Đây là một kiểu biểu diễn tri
thức có cấu trúc. Ý tưởng cơ bản là tri thức có thể được cấu trúc bằng một cặp giả thiết và kết
luận dưới dạng: nếu <giả thiết> thì <kết luận>. Đây là dạng biểu diễn tri thức rất phổ biến. Mô
hình biểu diễn tri thức dạng này thường bao gồm: tập các ký hiệu mô tả các sự kiện (có cấu trúc
đơn giản) và tập luật dẫn. Trong đó phần giả thiết và kết luận của luật là tập các sự kiện. Mỗi sự
kiện được mô tả có cấu trúc đơn giản như (tên đối tượng - thuộc tính - giá trị). Ví dụ: quả cam –
màu vàng.
Ph ng pháp suy lu n trong cách bi u di n tri th c d ng này là s d ng suyươ ậ ể ễ ứ ạ ử ụ
di n ti n và suy di n lùiễ ế ễ :
CH1301115 – Trịnh Nam Việt  Page 4
 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
Suy di n ti n: là quá trình suy lu n xu t phát t m t s s ki n ban u, xácễ ế ậ ấ ừ ộ ố ự ệ đầ
nh các s ki n có th c sinh ra t s ki n này“ ”đị ự ệ ể đượ ừ ự ệ .
Suy di n lùi: là quá trình suy lu n ng c xu t phát t m t s s ki n ban u,ễ ậ ượ ấ ừ ộ ố ự ệ đầ
ta tìm ki m các s ki n ã sinh ra s ki n này. M t ví d th ng g p trong th c t“ ”ế ự ệ đ ự ệ ộ ụ ườ ặ ự ế
là xu t phát t các tình tr ng c a máy tính, t ó ta ch n oán xem máy tính ã bấ ừ ạ ủ ừ đ ẩ đ đ ị
h ng hóc âuỏ ở đ .
Các lu t có u i m là d hi u nên d dàng dùng trao i v i ng i dùng.ậ ư đ ể ễ ể ễ để đổ ớ ườ
Có th d dàng xây d ng c c ch suy lu n và gi i thích t các lu t. Ngòai ra,ể ễ ự đượ ơ ế ậ ả ừ ậ

Bước 2: Lặp lại bước sau cho đến khi kích hoạt đượ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.
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à tính giá trị đỉnh còn lại này thông qua công thức ở đỉnh
hình chữ nhật).
II. Mô hình bi u di n tri th c COKBể ễ ứ
1. Đối tượng tính toán (C-Object)
Trong nhiều vấn đề giải toán dựa trên tri thức ta thường đề cập đến các đối tượng khác
nhau và mỗi đối tượng có cấu trúc bao gồm một số thuộc tính với những quan hệ nhất định.
Những quan hệ này giúp ta thực hiện sự suy diễn, tính toán và giải một số bài toán suy diễn-tính
toán trên các thuộc tính của đối tượng. Ví dụ: trong giải toán hình học, một tam giác với các
thuộc tính như 3 cạnh, 3 góc trong, diện tích, nửa chu vi, bán kính vòng tròn ngoại tiếp, v.v …
CH1301115 – Trịnh Nam Việt  Page 6
 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
cùng với các công thức liên hệ giữa các thuộc tính đó sẽ cho ta một cấu trúc của một đối tượng
như thế. Theo cách tiếp cận hướng đối tượng trong biểu diễn tri thức và giải toán, chúng ta tích
hợp vào cấu trúc đối tượng trên một số hành vi giải toán nhất định để tạo ra một đối tượng. Dựa
trên các đối tượng này, nhiều bài toán khác nhau có thể được biểu diễn dưới dạng mạng các đối
tượng. Cách biểu diễn này có thể được áp dụng một cách có hiệu quả trong các hệ giải toán,
chẳng hạn như các hệ giải các bài toán hình học. So với các phương pháp được trình bày ở trên,
cách mô hình này tỏ ra có nhiều ưu điểm, đặc biệt là khả năng biểu diễn hầu như toàn bộ tri thức
và các dạng bài toán tổng quát thuận tiện cho việc phát triển các thuật toán giải tự động và cung
cấp những lời giải tự nhiên và phù hợp với cách nghĩ và viết của con người. Ngoài ra, nó còn
giúp ích cho việc thiết kế và cài đặt phần cơ sở tri thức cũng như ngôn ngữ qui ước để đặc tả bài
toán.
Định nghĩa 1: Ta gọi một đối tượng tính toán (C-Object) là một đối tượng O có cấu trúc
bao gồm:
(1) Một danh sách các thuộc tính Attr(O) = {x
1
, x

a^2 = b^2 + c^2 - 2*b*c*cos(GocA), . . . }
 Facts = {}
 Rules = { {GocA = GocB}⇒ {a = b},
{a = b} ⇒ {GocA = GocB},
{a^2 = b^2+c^2}⇒{GocA=pi/2},
{GocA=pi/2} ⇒ {a^2 = b^2+c^2, b ⊥ c}, }
3. Các thành phần của mô hình COKB
Mô hình cơ sở tri thức của các đối tượng tính toán (mô hình COKB) gồm 6 thành
phần:
(C, H, R, Ops, Funcs, Rules)
CH1301115 – Trịnh Nam Việt  Page 8
 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
Trong đó,
(1) C là tập hợp các khái niệm về C-Object.
(2) H là tập hợp các quan hệ phân cấp giữa các loại đối tượng.
(3) R là tập hợp các khi niệm về các loại quan hệ trên C-Object.
(4) Ops là tập hợp các toán tử.
(5) Funcs là tập hợp các hàm.
(6) Rules là tập hợp các luật.
Trong mô hình này mỗi đối tượng tính toán (C-Object) có cấu trúc và được phân cấp dựa
trên các thiết lập của đối tượng.
Ngoài ra, mô hình này có 11 loại sự kiện sau:
- Sự kiện loại 1: Sự kiện thông tin loại của đối tượng.
- Sự kiện loại 2: Sự kiện về tính xác định của một đối tượng hay của một thuộc tính của
đối tượng.
- Sự kiện loại 3: Sự kiện về tính xác định của một đối tượng hay của một thuộc tính của
đối tượng thông qua biểu thức hằng.
- Sự kiện loại 4: Sự kiện về sự bằng nhau của một đối tượng hay một thuộc tính của đối
tượng với một đối tượng hay một thuộc tính khác.
- Sự kiện loại 5: Sự kiện về sự phụ thuộc giữa các đối tượng và các thuộc tính của các

 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
Ngoài ra đối tượng tính toán, giả sử là O, còn có khả năng đáp ứng lại một số thông điệp
yêu cầu từ bên ngoài. Trong các khả năng đó của đối tượng tính toán ta có thể kể đến những
điểm sau đây :
(1) Xác định bao đóng (trong đối tượng O) của một tập A ⊆ M(O).
(2) Xác định tính giải được của một bài toán A → B,
trong đó A ⊆ M(O), B ⊆ M(O).
(3) Tìm một lời giải tốt cho bài toán A → B trên mạng ( M(O), F(O) ),
trong đó A ⊆ M(O), B ⊆ M(O).
2. Mạng các đối tượng tính toán
Mạng các đối tượng tính toán bao gồm một tập hợp các đối tượng tính toán :
O = {O
1
,O
2
, , O
n
}
và một tập hợp các quan hệ tính toán :
F = {f
1
,f
2
, , f
m
}.
Đặt :
M(f
i
) = tập hợp các biến có liên quan với nhau bởi quan hệ f

là tập hợp những biến của đối tượng O
i
được xem xét trên mạng
các đối tượng tính toán. Ngoài ra ta còn có :
⊇ M ⊇ ,
hay M(O) ⊇ M ⊇ M(F).
Mô hình biểu diễn tri thức dạng này cho phép ta thực hiện tính toán các biến của một hay
hiều đối tượng dựa trên tập biến của các đối tượng khác.
Thuật toán: Thuật toán tìm một lời giải cho bài toán A → B trên mạng các đối tượng tính
toán (O, F) có tập biến được xem xét là M.
Nhập : Mạng các đối tượng tính toán (O,F), với tập biến là M,
tập giả thiết A ⊆ M,
tập biến cần tính B ⊆ M.
Xuất : lời giải cho bài toán A → B.
1. Solution ← empty; // Solution là dãy các quan hệ giữa các đối tượng
// hay các đối tượng sẽ áp dụng
2. if B ⊆ A then
CH1301115 – Trịnh Nam Việt  Page 12
M(O
i
i 1
n
)
=

M(f
i
i 1
m
)

i
∈ O (theo thứ tự ưu tiên đã nói ở trên) sao cho
O
i
(A) ≠ A;
if (chọn được O
i
) then
begin
A ← O
i
(A);
Solution ← Solution ∪ { O
i
};
if (B ⊆ A) then
begin
Solution_found ← true;
goto 5;
end;
else
goto 3;
end;
end;
5. if not Solution_found then
Bài toán không có lời giải;
else
Solution là một lời giải;
CH1301115 – Trịnh Nam Việt  Page 14
 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn

- “Axit” + “Bazơ” → “Muối” + “Nước”.
- “Kim loại kiềm” + “Nước” → “Bazơ” + H
2
2. Thiết kế bộ suy diễn tự động của chương trình
Về mặt tri thức người ta đã biết được nhiều chất và các phản ứng hóa học có thể chuyển
hóa từ một số chất này thành các chất khác. Ta có thể xem tri thức đó như một mạng tính toán mà
mỗi phản ứng là một quan hệ của mạng.
(O, F, G)
Bài toán 1

: Viết phương trình phản ứng (PTPU) biểu diễn các biến hóa sau:
Zn → ZnO → ZnSO
4
Mô hình bài toán:
O = { [Zn, ZnO, ZnSO
4
] }
F = { tập các phương trình phản ứng hóa học }
G = {}
CH1301115 – Trịnh Nam Việt  Page 16
 Biểu diễn tri thức & Suy luận PGS.TS Đỗ Văn Nhơn
Bài toán 2

: Từ lưu huỳnh (S) và nước (H
2
O) ta có thể điều chế được axit sunfuaric
(H
2
SO
4

2
] }
F = { tập các phương trình phản ứng hóa học }
G = {}
Bài toán 4

: Hoàn thành các phương trình phản ứng sau:
Mg + H
2
SO
4
→ . . .
Fe(OH)
3
+ H
2
SO
4
→ . . .
K
2
CO
3
+ H
2
SO
4
→ . . .
Ba(NO
3

= …],
[Ba(NO
3
)
2
+ H
2
SO
4
= …] }
F = { tập các phương trình phản ứng hóa học }
G = {}
Bài toán 5

: Viết PTPU theo các sơ đồ sau:
FeS + ? → FeCl
2
+ ?
CuSO
4
+ ? → ? + Na
2
SO
4
Mô hình bài toán:
O = { [FeS + ? = FeCl
2
+ ?],
[CuSO
4

di n tri th c.V i mô hình COKB là m t mô hình r t t t cho vi c bi u di n các tri th cễ ứ ớ ộ ấ ố ệ ể ễ ứ
c a con ng i, c bi t là các tri th c v Toán h c, V t lý, Hóa h c H n n a, sủ ườ đặ ệ ứ ề ọ ậ ọ ơ ữ ự
m r ng c a mô hình COKB b ng vi c thêm b t các thành ph n i t ng m t cáchở ộ ủ ằ ệ ớ ầ đố ượ ộ
d dàng phù h p v i t ng bài toán c th .ễ để ợ ớ ừ ụ ể
Trong ch ng trình demo Hóa h c trên, em ch d ng l i m c c b n do th iươ ọ ỉ ừ ạ ở ứ ơ ả ờ
gian có h n. Quá trình suy di n tìm ra c các ph ng trình ph n ng c n choạ ễ để đượ ươ ả ứ ầ
quá trình i u ch , nh ng các ph ng trình ó ch a c t i u (ph n ng t ti nđ ề ế ư ươ đ ư đượ ố ư ả ứ đắ ề
trong th c t , ch a nh n ra c ch t k t t a ). H ng phát tri n c a ch ng trìnhự ế ư ậ đượ ấ ế ủ ướ ể ủ ươ
là:
- T i u c ph ng trình ph n ng c n cho quá trình i u ch .ố ư đượ ươ ả ứ ầ đ ề ế
- K th a phát tri n thành bài toán Nh n bi t ch t hóa h c.ế ừ để ể ậ ế ấ ọ
Tài li u tham kh o chính:ệ ả
1.PSG.TS. Đỗ Văn Nhơn. Bài giảng Biểu diễn tri thức và ứng dụng, 2013.
2. GS.TSKH. Hoàng Kiếm & PSG.TS. Đỗ Văn Nhơn, Mạng tính toán và ứng dụng, Tạp chí
Tin học và điều khiển học, T.13, S.3(1997)
CH1301115 – Trịnh Nam Việt  Page 22