ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

BÁO CÁO
Đề

t

ài

:
THIẾT KẾ BỘ SUY DIỄN CHUỖI
PHẢN ỨNG HÓA HỌC
Môn họ

c: Biểu diễn tri thức và suy luận
Giảng viên hướng dẫn:
PGS.TS. Đỗ Văn Nhơn
Học viên:
Huỳnh Thanh Việt – CH1301114
TPHCM, Tháng 3 – 2014
NHẬN XÉT CỦA GIẢNG VIÊN

MỤC LỤC
LỜI CÁM ƠN
Đầu tiên, em xin chân thành cám ơn thầy PGS.TS. Đỗ Văn Nhơn đã truyền đạt hết sức
nhiệt tình cho chúng em những kiến thức quý báu trong môn Biễu diễn tri thức và ứng dụng
để em hoàn thành đề tài này.
Em cũng xin gửi lời cám ơn chân thành đến các thầy cô trong trường Đại học Công
Nghệ Thông Tin đã tận tình giúp đỡ em trong thời gian học vừa qua.
Xin cảm ơn tất bạn bè đã và đang động viên, giúp đỡ tôi trong quá trình học tập và hoàn
thành đề tài này.

TPHCM, ngày 27 tháng 03 năm 2014
Lớp CH08
Học viên thực hiện
Huỳnh Thanh Việt
4
LỜI NÓI ĐẦU
Một trong những vấn đề hiện nay đang được quan tâm của “Trí Tuệ Nhân Tạo” là
nghiên cứu các phương pháp biểu diễn và xử lý tri thức. Trên cơ sở đó có thể tạo ra những
chương trình “thông minh” ở một mức độ nào đó.
Trong nhiều lĩnh vực chúng ta thường gặp những vấn đề đặt ra dưới dạng như sau :
Chúng ta phải thực hiện những tính toán hay suy diễn ra những yếu tố cần thiết nào đó từ
một số yếu tố đã được biết trước.
Để giải quyết vấn đề người ta phải vận dụng một số hiểu biết (tri thức) nào đó về những
liên hệ giữa các yếu tố đang được xem xét. Những liên hệ cho phép ta có thể suy ra được
một số yếu tố từ giả thiết đã biết một số yếu tố khác. Trong bài báo cáo này chúng ta xét
đến một mô hình biểu diễn và xử lý tri thức có thể áp dụng giải tự động các bài toán và là
mô hình “Mạng tính toán”.
5
CHƯƠNG 1 : MỘT SỐ MÔ HÌNH BIỂU DIỄN TRI THỨC
I. Giới thiệu về tri thức
Tri thức (knowledge): là sự hiểu biết của người trong một phạm vi, lĩnh vực nào đó;
được xem xét theo các mục tiêu hay các vấn đề nhất định.
Ví dụ:
- Kiến thức về một lĩnh vực y học và khả năng chẩn đoán bệnh là tri thức.
- Biết một tam giác có các yếu tố nào cùng với các công thức liên hệ giữa các yếu tố
là tri thức.
- Biết các dạng cấu trúc dữ liệu thường dùng trong lập trình cùng với các thuật toán
xử lý cơ bản trên các cấu trúc là tri thức.
Các dạng tri thức
- Tri thức mô tả: các khái niệm, các đối tượng cơ bản.

- Tri thức cấu trúc: các khái niệm cấu trúc, các quan hệ, các đối tượng phức hợp,
- Tri thức thủ tục: các luật dẫn, các thủ tục xử lý, các chiến lược, …
- Tri thức meta: tri thức về các dạng tri thức khác và cách sử dụng chúng.
Tri thức là một hệ thống phức tạp, đa dạng và trừu tượng bao gồm nhiều thành tố với
những mối liên hệ tác động qua lại như:
- Các khái niệm (concepts), với những mối liên hệ cơ bản nhất định (relationships).
- Các quan hệ (relations): Xem lại kiến thức về quan hệ ở góc độ toán học trong giáo
trình “Toán Rời Rạc”:
o Định nghĩa quan hệ 2 ngôi.
o Các tính chất về một quan hệ 2 ngôi R trên một tập X: phản xạ, đối xứng,
phản xứng, bắc cầu.
o Quan hệ thứ tự.
o Quan hệ tương đương.
o Cách biểu diễn của một quan hệ 2 ngôi R trên tập X: Biểu diễn dựa trên “tập
hợp”,biểu diễn bằng ma trận, biểu đồ (đồ thị).
- Các toán tử (operators), phép toán, các biểu thức hay công thức
o Phép toán 2 ngôi T trên tập X là ánh xạ
T : XxX  X
(a,b)  a T b ≡ T(a,b)
Ví dụ: T: NxN  N
(a,b)  a+b
o Phép toán 1 ngôi S trên tập X là
S : X  X
6
o Các tính chất thường được xem xét: giao hoán, kết hợp, phần tử trung hòa,
phần tử nghịch đảo, phần tử đối, phân phối (hay phân bố), …
- Các hàm (functions).
- Các luật (rules).
- Sự kiện (facts).
- Các thực thể hay đối tượng, một phần tử cụ thể (objects).

1. Biểu diễn tri thức bằng luật dẫn(luật sinh)
1.1Khái niệm
Phương pháp biểu diễn tri thức bằng luật sinh đượ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
điều kiện và hành động: "NẾU điều kiện xảy ra THÌ hành động sẽ được thi hành". Chẳng
hạn, NẾU đèn giao thông là đỏ THÌ bạn không được đi thẳng, NẾU máy tính đã mở mà
không khởi động được THÌ kiểm tra nguồn điện,…
Ngày nay, các luật sinh đã trở nên phổ biến và được áp dụng rộng rãi trong nhiều hệ
thống trí tuệ nhân tạo khác nhau.Luật sinh có thể là một công cụ mô tả để giải quyết các vấn
đề thực tế thay cho các kiểu phân tích vấn đề truyền thống.Trong trường hợp này, các luật
được dùng như là những chỉ dẫn (tuy có thể không hoàn chỉnh) nhưng rất hữu ích để trợ
giúp cho các quyết định trong quá trình tìm kiếm, từ đó làm giảm không gian tìm kiếm.Một
ví dụ khác là luật sinh có thể được dùng để bắt chước hành vi của những chuyên gia. Theo
cách này, luật sinh không chỉ đơn thuần là một kiểu biểu diễn tri thức trong máy tính mà là
một kiểu biễu diễn các hành vi của con người.
Một cách tổng quát luật sinh có dạng như sau:
P
1
∧ P
2
∧ ∧ Pn  Q
Tùy vào các vấn đề đang quan tâm mà luật sinh có những ngữ nghĩa hay cấu tạo khác
nhau:
- Trong logic vị từ: P
1
, P
2
, , Pn, Q là những biểu thức logic.
- Trong ngôn ngữ lập trình, mỗi một luật sinh là một câu lệnh.

IF (P
1
AND P
2
AND AND Pn) THEN Q.
- Trong lý thuyết hiểu ngôn ngữ tự nhiên, mỗi luật sinh là một phép dịch:
ONE  một.
TWO  hai.
7
JANUARY  tháng một.
Để biễu diễn một tập luật sinh, người ta thường phải chỉ rõ hai thành phần chính sau:
- Tập các sự kiện F(Facts)
F = {f
1
, f
2
, fn}
- Tập các quy tắc R (Rules) áp dụng trên các sự kiện dạng như sau :
f
1
^ f
2
^ ^ f
i
 q
Trong đó, các f
i
, q đều thuộc F
• Cơ chế suy luận trên các luật sinh
- 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.
Sự kiện ban đầu: H, K
R3: H  A {A, H. K }
R1: A  E { A, E, H, K }
R5: E ∧K  B { A, B, E, H, K }
R2: B  D { A, B, D, E, H, K }
R6: D ∧ E ∧ K  C { A, B, C, D, E, H, K }
- 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, chẩn đoán xem máy tính đã bị hỏng hóc ở
đâu.
• Vấn đề tối ưu luật
Tập các luật trong một cơ sở tri thức rất có khả năng thừa, trùng lắp hoặc mâu
thuẫn.Dĩ nhiên là hệ thống có thể đổ lỗi cho người dùng về việc đưa vào hệ thống những tri
thức như vậy. Tuy việc tối ưu một cơ sở tri thức về mặt tổng quát là một thao tác khó (vì
giữa các tri thức thường có quan hệ không tường minh), nhưng trong giới hạn cơ sở tri thức
dưới dạng luật, ta vẫn có một số thuật toán đơn giản để loại bỏ các vấn đề này.
- Rút gọn bên phải:
luật sau hiển nhiên đúng :A ∧ B A (1)
8
do đó luật:A ∧ BA ∧ C
là hoàn toàn tương đương với: A ∧ BC
Quy tắc rút gọn : Có thể loại bỏ những sự kiện bên vế phải nếu những sự kiện đó
đã xuất hiện bên vế trái. Nếu sau khi rút gọn mà vế phải trở thành rỗng thì luật đó là luật
hiển nhiên. Ta có thể loại bỏ các luật hiển nhiên ra khỏi tri thức.
- Rút gọn bên trái:
Xét các luật : (L1) A, B  C (L2) A  X (L3) X  C
Rõ ràng là luật A, B  C có thể được thay thế bằng luật A  C mà không làm ảnh
hưởng đến các kết luận trong mọi trường hợp. Ta nói rằng sự kiện B trong luật (1) là dư
thừa và có thể được loại bỏ khỏi luật dẫn trên.

- Phân rã và kết hợp luật:
Luật: A ∧ B  C
Tương đương với hai luật: A  C và B  C
Với quy tắc này, ta có thể loại bỏ hoàn toàn các luật có phép nối HOẶC.Các luật có
phép nối này thường làm cho thao tác xử lý trở nên phức tạp.
- Luật thừa:
Một luật dẫn A  B được gọi là thừa nếu có thể suy ra luật này từ những luật còn lại.
Ví dụ : trong tập các luật gồm {A  B, B  C, A  C} thì luật thứ 3 là luật thừa
vì nó có thể được suy ra từ 2 luật còn lại.
- Thuật toán tối ưu tập luật dẫn:
Thuật toán này sẽ tối ưu hóa tập luật đã cho bằng cách loại đi các luật có phép nối
HOẶC, các luật hiển nhiên hoặc các luật thừa.
Thuật toán bao gồm các bước chính:
B1: Rút gọn vế phải
Với mỗi luật r trong R
Với mỗi sự kiện A ∈VếPhải(r)
9
Nếu A ∈VếTrái(r) thì Loại A ra khỏi vế phải của R.
Nếu VếPhải(r) rỗng thì loại bỏ r ra khỏi hệ luật dẫn : R = R \{r}
B2: Phân rã các luật
Với mỗi luật r : X
1
∨X
2
∨ … ∨ X
n
 Y trong R
Với mỗi i từ 1 đến n R := R + { X
i
 Y }

R := R \ {r}
B3: Loại bỏ luật thừa
Với mỗi luật r thuộc R
Nếu VếPhải(r) ∈BaoĐóng(VếTrái(r), R-{r}) thì R := R \ {r}
B4: Rút gọn vế trái
Với mỗi luật dẫn r : X : A
1
∧A
2
, …, A
n
 Y thuộc R
Với mỗi sự kiện A
i
∈ r
Gọi luật r
1
: X - A
i
 Y
S = (R - {r}) ∪{r
1
}
Nếu BaoĐóng (X - A
i
, S) ≡ BaoĐóng (X, R) thì loại sự kiện A ra khỏi X
2. Biểu diễn tri thức sử dụng mạng ngữ nghĩa
2.1 Khái niệm
Mạng ngữ nghĩa là một phương pháp biểu diễn tri thức đầu tiên và cũng là phương
pháp dễ hiểu nhất đối với chúng ta.Phương pháp này sẽ biểu diễn tri thức dưới dạng một đồ

thị, trong đó đỉnh là các đối tượng (khái niệm) còn các cung cho biết mối quan hệ giữa các
đối tượng (khái niệm) này.
Chẳng hạn: giữa các khái niệm chích chòe, chim, hót, cánh, tổ có một số mối quan hệ
như sau:
10
- Chích chòe là một loài chim.
- Chim biết hót
- Chim có cánh
- Chim sống trong tổ
- Các mối quan hệ này sẽ được biểu diễn trực quan bằng một đồ thị như sau:
Do mạng ngữ nghĩa là một loại đồ thị cho nên nó thừa hưởng được tất cả những mặt
mạnh của công cụ này. Nghĩa là ta có thể dùng những thuật toán của đồ thị trên mạng ngữ
nghĩa như thuật toán tìm liên thông, tìm đường đi ngắn nhất,… để thực hiện các cơ chế suy
luận. Điểm đặc biệt của mạng ngữ nghĩa so với đồ thị thông thường chính là việc gán một ý
nghĩa (có, làm, là, biết, ) cho các cung. Trong đồ thị tiêu chuẩn, việc có một cung nối giữa
hai đỉnh chỉ cho biết có sự liên hệ giữa hai đỉnh đó và tất cả các cung trong đồ thị đều biểu
diễn cho cùng một loại liên hệ.Trong mạng ngữ nghĩa, cung nối giữa hai đỉnh còn cho biết
giữa hai khái niệm tương ứng có sự liên hệ như thế nào.Việc gán ngữ nghĩa vào các cung
của đồ thị đã giúp giảm bớt được số lượng đồ thị cần phải dùng để biễu diễn các mối liên hệ
giữa các khái niệm. Chẳng hạn như trong ví dụ trên, nếu sử dụng đồ thị thông thường, ta
phải dùng đến 4 loại đồ thị cho 4 mối liên hệ : một đồ thị để biểu diễn mối liên hệ "là", một
đồ thị cho mối liên hệ "làm", một cho "biết" và một cho "có".
Một điểm khá thú vị của mạng ngữ nghĩa là tính kế thừa. Bởi vì ngay từ trong khái
niệm, mạng ngữ nghĩa đã hàm ý sự phân cấp (như các mối liên hệ "là") nên có nhiều đỉnh
trong mạng mặc nhiên sẽ có những thuộc tính của những đỉnh khác. Chẳng hạn theo mạng
ngữ nghĩa ở trên, ta có thể dễ dàng trả lời "có" cho câu hỏi : "Chích chòe có làm tổ không?".
Ta có thể khẳng định được điều này vì đỉnh "chích chòe" có liên kết "là" với đỉnh "chim" và
đỉnh "chim" lại liên kết "biết" với đỉnh "làm tổ" nên suy ra đỉnh "chích chòe" cũng có liên
kết loại "biết" với đỉnh "làm tổ". (Nếu để ý, bạn sẽ nhận ra được kiểu "suy luận" mà ta vừa
thực hiện bắt nguồn từ thuật toán "loang" hay "tìm liên thông" trên đồ thị!). Chính đặc tính

kế thừa của mạng ngữ nghĩa đã cho phép ta có thể thực hiện được rất nhiều phép suy diễn từ
những thông tin sẵn có trên mạng.
11
Tuy mạng ngữ nghĩa là một kiểu biểu diễn trực quan đối với con người nhưng khi đưa
vào máy tính, các đối tượng và mối liên hệ giữa chúng thường được biểu diễn dưới dạng
những phát biểu động từ (như vị từ). Hơn nữa, các thao tác tìm kiếm trên mạng ngữ nghĩa
thường khó khăn (đặc biệt đối với những mạng có kích thước lớn). Do đó, mô hình mạng
ngữ nghĩa được dùng chủ yếu để phân tích vấn đề. Sau đó, nó sẽ được chuyển đổi sang
dạng luật hoặc frame để thi hành hoặc mạng ngữ nghĩa sẽ được dùng kết hợp với một số
phương pháp biểu diễn khác.
3. Biểu diễn tri thức bằng Frame
3.1 Khái niệm
Frame là một cấu trúc dữ liệu chứa đựng tất cả những trithức liên quan đến một đối
tượng cụ thể nào đó. Frames có liên hệ chặt chẽ đến khái niệm hướng đối tượng (thực ra
frame là nguồn gốc của lập trình hướng đối tượng). Ngược lại với các phương pháp
biểudiễntrithức đã được đề cập đến, frame "đóng gói" toàn bộ một đối tượng, tình huống
hoặc cả một vấn đề phức tạp thành một thực thể duy nhất có cấu trúc. Một frame bao hàm
trong nó một khối lượng tương đối lớn trithức về một đối tượng, sự kiện, vị trí, tình huống
hoặc những yếu tố khác. Do đó, frame có thể giúp ta mô tả khá chi tiết một đối tượng.
Dưới một khía cạnh nào đó, người ta có thể xem phương pháp
biểudiễntrithứcbằngframe chính là nguồn gốc của ngôn ngữ lập trình hướng đối tượng. Ý
tưởng của phương pháp này là "thay vì bắt người dùng sử dụng các công cụ phụ như dao
mở để đồ hộp, ngày nay các hãng sản xuất đồ hộp thường gắn kèm các nắp mở đồ hộp ngay
bên trên vỏ lon. Như vậy, người dùng sẽ không bao giờ phải lo lắng đến việc tìm một thiết
bị để mở đồ hộp nữa!". Cũng vậy, ý tưởng chính của frame (hay của phương pháp lập trình
hướng đối tượng) là khi biểudiễn một trithức, ta sẽ "gắn kèm" những thao tác thường gặp
trên trithức này. Chẳng hạn như khi mô tả khái niệm về hình chữ nhật, ta sẽ gắn kèm cách
tính chu vi, diện tích.
Frame thường được dùng để biểudiễn những trithức "chuẩn" hoặc những trithứ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ẽ. Bộ não

của con người chúng ta vẫn luôn "lưu trữ" rất nhiều các trithức chung mà khi cần, chúng ta
có thể "lấy ra" để vận dụng nó trong những vấn đề cần phải giải quyết.Frame là một công cụ
thích hợp để biểudiễn những kiểu trithức này.
Frame : XE HƠI
Thuộc lớp :phương tiện vận chuyển.
Tên nhà sản xuất : Audi
Quốc gia của nhà sản xuất : Đức

Frame MÁY
Xy-lanh : 3.19 inch
Tỷ lệ nén : 3.4 inche
Xăng : TurboCharger
Mã lực : 140 hp
12
Model : 5000 Turbo
Loại xe : Sedan
Trọng lượng : 3300lb
Số lượng cửa : 4 (default)
Hộp số : 3 số tự động
Số lượng bánh : 4 (default)
Máy (tham chiếu đến frame Máy)
Kiểu : In-line, overhead cam
Số xy-lanh : 5
Khả năng tăng tốc
0-60 : 10.4 giây
¼ dặm : 17.1 giây, 85 mph.
Cấu trúc một Frame xe hơi
3.1 Cấu trúc của Frame
Mỗi một 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. Một slot là một thuộc tính đặc tả đối tượng được biểudiễn bởi frame. Ví dụ :

trong frame mô tả xe hơi, có hai slot là trọng lượng và loại máy.
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 (giá trị) : cho biết giá trị của thuộc tính đó (như xanh, đỏ, tím vàng nếu slot
là màu xe).
- Default (giá trị mặc định) : hệ thống sẽ tự động sử dụng giá trị trong facet này nếu
slot là rỗng (nghĩa là chẳng có đặc tả nào!). Chẳng hạn trong frame về xe, xét slot
về số lượng bánh. Slot này sẽ có giá trị 4. Nghĩa là, mặc định một chiếc xe hơi sẽ có
4 bánh!
- Range (miền giá trị) : (tương tự như kiểu biến), cho biết giá trị slot có thể nhận
những loại giá trị gì (như số nguyên, số thực, chữ cái, )
13
- If added: mô tả một hành động sẽ được thi hành khi một giá trị trong slot được thêm
vào (hoặc được hiệu chỉnh). Thủ tục thường được viết dưới dạng một script.
- If needed :được sử dụng khi slot không có giá trị nào. Facet mô tả một hàm để tính
ra giá trị của slot.
3.2 Tính kế thừa
Trong thực tế, một hệ thống trí tuệ nhân tạo thường sử dụng nhiều frame được liên kết
với nhau theo một cách nào đó. Một trong những điểm thú vị của frame là tính phân cấp.
Đặc tính này cho phép kế thừa các tính chất giữa các frame.
Hình sau đây cho thấy cấu trúc phân cấp của các loại hình hình học cơ bản.Gốc của
cây ở trên cùng tương ứng với mức độ trừu tượng cao nhất. Các frame nằm ở dưới cùng
(không có frame con nào) gọi là lá. Những frame nằm ở mức thấp hơn có thể thừa kế tất cả
những tính chất của những frame cao hơn.
Các frame cha sẽ cung cấp những mô tả tổng quát về thực thể. Frame có cấp càng cao thì
mức độ tổng quát càng cao. Thông thường, frame cha sẽ bao gồm các định nghĩa của các
thuộc tính. Còn các frame con sẽ chứa đựng giá trị thực sự của các thuộc tính này.
Quan hệ giữa các đối tượng hình học phẳng
14

4. Biểu diễn tri thức bằng Script
Script là một cách biểu diễn tri thức tương tự như frame nhưng thay vì đặc tả một đối
tượng, nó mô tả một chuỗi các sự kiện.Để mô tả chuỗi sự kiện, script sử dụng một dãy các
slot chứa thông tin về các con người, đối tượng và hành động liên quan đến sự kiện đó.
Tuy cấu trúc của các script là rất khác nhau tùy theo bài toán, nhưng nhìn chung một
script thường bao gồm các thành phần sau :
- Điều kiện vào(entry condition): mô tả những tình huống hoặc điều kiện cần được
thỏa mãn trước khi các sự kiện trong script có thể diễn ra.
- Role (đóng vai): là những con người có liên quan trong script.
- Prop (tác tố): là tất cả những đối tượng được sử dụng trong các chuỗi sự kiện sẽ
diễn ra.
- Scene(Tình huống): là chuỗi sự kiện thực sự diễn ra.
- Result (Kết quả): trạng thái của các Role sau khi script đã thi hành xong.
- Track (phiên bản): mô tả một biến thể (hoặc trường hợp đặc biệt) có thể xảy ra
trong đoạn script.
Script rất hữu dụng trong việc dự đoán điều gì sẽ xảy đến trong những tình huống xác
định.Thậm chí trong những tình huống chưa diễn ra, script còn cho phép máy tính dự đoán
được việc gì sẽ xảy ra và xảy ra đối với ai và vào thời điểm nào.Nếu máy tính kích hoạt một
script, người dùng có thể đặt câu hỏi và hệ thống có thể suy ra được những câu trả lời chính
xác mà không cần người dùng cung cấp thêm nhiều thông tin (trong một số trường hợp có
thể không cần thêm thông tin). Do đó, cũng giống như frame, script là một dạng biểu diễn
tri thức tương đối hữu dụng vì nó cho phép ta mô tả chính xác những tình huống "chuẩn"
mà con người vẫn thực hiện mỗi ngày hoặc đã nắm bắt chính xác.
5. Mô hình COKB
Mô hình biểu diễn tri thức COKB(Computational Objects Knowledge Base) là một
mô hình tri thức của các đối tượng tính toán. Mô hình COKB là một hệ thống gồm 6 thành
phần chính được ký hiệu bởi bộ 6 như sau:
(C,H,R,Opts, Funcs,Rules)
Tập hợp C (các khái niệm về các C_Object):
Các khái niệm được xây dựng dựa trên các đối tượng. Mỗi khái niệm là một lớp các

đối tượng tính toán có cấu trúc nhất định và được phân cấp theo sự thiết lập của cấu trúc đối
tượng, bao gồm:
15
- Các đối tượng (hay khái niệm) nền: là các đối tượng (hay khái niệm) được mặc
nhiên thừa nhận. Ví dụ: như một số đối tượng kiểu boolean (logic), số tự nhiên
(natural), số nguyên (integer), số thực (real), tập hợp (set), danh sách (list) hay một
số kiểu tự định nghĩa.
- Các đối tượng cơ bản (hay khái niệm) cơ bản cấp 0: có cấu trúc rỗng hoặc có cấu
trúc thiết lập trên một số thuộc tính kiểu khái niệm nền: Các đối tượng(hay khái
niệm) này làm nền cho các đối tượng(hay các khái niệm) cấp cao hơn. Ví dụ: đối
tượng DIEM có kiểu mô tả không có cấu trúc thiết lập.
- Các đối tượng (hay khái niệm) cấp 1: Các đối tượng này chỉ có các thuộc tính kiểu
khái niệm nền và có thể được thiết lập trên một danh sách nền các đối tượng cơ bản.
Ví dụ: đối tượng DOAN[A,B] trong đó A, B là các đối tượng cơ bản loại DIEM,
thuộc tính a biểu thị độ dài đoạn thẳng có kiểu tương ứng là “real”.
- Các đối tượng (hay khái niệm) cấp 2: Các đối tượng này có các thuộc tính kiểu khái
niệm nền và các thuộc tính loại đối tượng cấp 1, có thể được thiết lập trên một danh
sách nền các đối tượng cơ bản. Ví dụ: đối tượng TAMGIAC[A,B,C] trong đó A, B,
C là các đối tượng cơ bản loại DIEM, các thuộc tính như GocA, a, S có kiểu tương
ứng là “GOC[C,A,B]”, “DOAN[B,C]”, “real”.
- Các đối tượng (hay khái niệm) cấp n >0: Các đối tượng này có các thuộc tính kiểu
khái niệm nền và các thuộc tính loại đối tượng cấp thấp hơn, có thể được thiết lập
trên một danh sách nền các đối tượng cấp thấp hơn.
Cấu trúc bên trong của mỗi lớp đối tượng:
- Kiểu đối tượng: Kiểu này có thể là kiểu thiết lập trên một danh sách nền các đối
tượng cấp thấp hơn.
- Danh sách các thuộc tính của đối tượng: Mỗi thuộc tính có kiểu thực, kiểu đối
tượng cơ bản hay kiểu đối tượng cấp thấp hơn. Phân ra làm 2 loại là tập các thuộc
tính thiết lập của đối tượng và tập các thuộc tính khác (còn gọi là tập thuộc tính).
- Tập hợp các điều kiện ràng buộc trên các thuộc tính.

- Tập hợp các tính chất nội tại hay sự kiện vốn có liên quan đến các thuộc tính của
đối tượng.
- Tập hợp các quan hệ suy diễn - tính toán trên các thuộc tính của đối tượng. Các
quan hệ này thể hiện các luật suy diễn và cho phép ta có thể tính toán một hay một
số thuộc tính từ các thuộc tính khác của đối tượng.
16
- Tập hợp các luật suy diễn trên các loại sự kiện khác nhau liên quan đến các thuộc
tính của đối tượng hay bản thân đối tượng. Mỗi luật suy diễn có dạng: {các sự kiện
giả thiết} ⇒ {các sự kiện kết luận}.
Tập hợp H (các quan hệ phân cấp giữa các đối tượng)
Trong tập C, ta có các quan hệ mà theo đó có thể có những khái niệm là sự đặc biệt
hoá của những khái niệm khác. Có thể nói, H là một biểu đồ Hasse trên C khi xem quan hệ
phân cấp là một quan hệ thứ tự trên C.
Cấu trúc của một quan hệ phân cấp:
[<tên lớp đối tượng cấp cao>, <tên lớp đối tượng cấp thấp> ]
Tập hợp R các khái niệm về các loại quan hệ trên các C-Object
Mỗi quan hệ được xác định bởi tên quan hệ và danh sách các loại đối tượng của quan
hệ. Đối với quan hệ 2 hay 3 ngôi thì quan hệ có thể có các tính chất như tính phản xạ, tính
phản xứng, tính đối xứng và tính bắc cầu.
Cấu trúc của một quan hệ:
[ < tên quan hệ > , < loại đối tượng > , < loại đối tượng > ,…] , {< tính chất > , < tính
chất >}.
Tập hợp Opts các toán tử
Các toán tử thể hiện các qui tắc tính toán nhất định trên các biến thực cũng như trên
các đối tượng. Chẳng hạn như các phép toán số học, các phép tính toán trên các đối tượng
đoạn, góc tương tự như đối với các biến thực hay các phép tính toán vecto, tính toán ma
trận,… Trong trường hợp các phép toán 2 ngôi thì phép toán có thể có các tính chất như tính
giao hoán, tính kết hợp,tính nghịch đảo, tính trung hoà.
Tập hợp Funcs các hàm
Tập hợp Funcs trong mô hình COKB thể hiện tri thức về các hàm hay nói cách khác

là thể hiện tri thức về các khái niệm và các qui tắc tính toán trên các biến thực cũng như
trên các loại C-Object, được xây dựng thông qua các quan hệ tính toán dạng hàm. Mỗi hàm
được xác định bởi <tên hàm>, danh sách các đối số và một qui tắc định nghĩa hàm về
phương diện toán học.
Tập hợp Rules các luật
17
Mỗi luật cho ta một qui tắc suy luận để từ các sự kiện đang biết suy ra được các sự
kiện mới thông qua việc áp dụng các định luật, định lý hay các qui tắc tính toán nào đó. Mỗi
luật suy diễn r có thể được mô hình hoá dưới dạng :
r : {sk
1
, sk
2
, , sk
m
} ⇒ {sk
m+1
, sk
m+2
, , sk
n
}.
Cấu trúc của một luật:
[ Kind, BasicO, Hypos, Goals]
Trong đó:
- Kind: loại luật.
- BaseO: tập các đối tượng cơ bản.
- Hypos: tập các sự kiện giả thiết của một luật.
- Goals: tập các sự kiện kết luận của một luật.
18

CHƯƠNG 2: MÔ HÌNH MẠNG TÍNH TOÁN
I. MẠNG TÍNH TOÁN.
Mạng tính toán là một dạng biểu diễn tri thức có thể dùng biểu diễn các tri thức về các
vấn đề tính toán và được áp dụng một cách có hiệu quả để giải một số dạng bài toán. Mỗi
mạng tính toán là một mạng ngữ nghĩa chứa các biến và những quan hệ có thể cài đặt và
sử dụng được cho việc tính toán. Chúng ta xét một mạng tính toán gồm một tập hợp các
biến cùng với một tập các quan hệ (chẳng hạn các công thức) tính toán giữa các biến. Trong
ứng dụng cụ thể mỗi biến và giá trị của nó thường gắn liền với một khái niệm cụ thể về sự
vật, mỗi quan hệ thể hiện một sự tri thức về sự vật.
1. Các quan hệ:
Cho M = {x
1
,x
2
, ,x
m
} là một tập hợp các biến có thể lấy giá trị trong các miền xác định
tương ứng D
1,
D
2
, ,D
m
. Đối với mỗi quan hệ R ⊆ D
1
xD
2
x xD
m
trên các tập hợp

D
1,
D
2
, ,D
m
ta nói rằng quan hệ nầy liên kết các biến x
1
,x
2
, ,x
m
, và ký hiệu là R(x
1
,x
2
, ,x
m
)
hay vắn tắt là R(x) (ký hiệu x dùng để chỉ bộ biến < x
1
,x
2
, ,x
m
>). Ta có thể thấy rằng quan
hệ R(x) có thể được biểu diễn bởi một ánh xạ f
R,u,v
với u ∪ v = x, và ta viết : f
R,u,v

: u → v,
hay vắn tắt là f : u → v.
Đối với các quan hệ dùng cho việc tính toán, cách ký hiệu trên bao hàm ý nghĩa như là
một hàm: ta có thể tính được giá trị của các biến thuộc v khi biết được giá trị của các biến
thuộc u.
Trong phần sau ta xét các quan hệ xác định bởi các hàm có dạng f : u → v, trong đó u ∩
v = ∅ (tập rỗng). Đặc biệt là các quan hệ đối xứng có hạng (rank) bằng một số nguyên
dương k. Đó là các quan hệ mà ta có thể tính được k biến bất kỳ từ m-k biến kia (ở đây x là
bộ gồm m biến < x
1
,x
2
, ,x
m
>). Ngoài ra, trong trường hợp cần nói rõ ta viết u(f) thay cho u,
v(f) thay cho v. Đối với các quan hệ không phải là đối xứng có hạng k, không làm mất tính
tổng quát, ta có thể giả sử quan hệ xác định duy nhất một hàm f với tập biến vào là u(f) và
tập biến ra là v(f); ta gọi loại quan hệ nầy là quan hệ không đối xứng xác định một hàm, hay
gọi vắn tắt là quan hệ không đối xứng.
19
Ví dụ: quan hệ f giữa 3 góc A, B, C trong tam giác ABC cho bởi hệ thức:
A+B+C = 180 (đơn vị: độ)
2. Mạng tính toán và các ký hiệu:
Như đã nói ở trên, ta sẽ xem xét các mạng tính toán bao gồm một tập hợp các biến M
và một tập hợp các quan hệ (tính toán) F trên các biến. Trong trường hợp tổng quát có thể
viết:
M = {x
1
,x
2

, ,x
n
},
F = {f
1
,f
2
, ,f
m
}.
Đối với mỗi f ∈ F, ta ký hiệu M(f) là tập các biến có liên hệ trong quan hệ f. Dĩ nhiên M(f)
là một tập con của M: M(f) ⊆ M. Nếu viết f dưới dạng:
f : u(f) → v(f)
thì ta có M(f) = u(f) ∪ v(f).
II. BÀI TOÁN TRÊN MẠNG TÍNH TOÁN :
Cho một mạng tính toán (M,F), M là tập các biến và F là tập các quan hệ. Giả sử có
một tập biến A ⊆ M đã được xác định và B là một tập biến bất kỳ trong M.
Các vấn đề đặt ra là:
1. Có thể xác định được tập B từ tập A nhờ các quan hệ trong F hay không? Nói cách
khác, ta có thể tính được giá trị của các biến thuộc B với giả thiết đã biết giá trị của các biến
thuộc A hay không?
2. Nếu có thể xác định được B từ A thì quá trình tính toán giá trị của các biến thuộc B
như thế nào?
20
3. Trong trường hợp không thể xác định được B, thì cần cho thêm điều kiện gì để có thể
xác định được B.
Bài toán xác định B từ A trên mạng tính toán (M,F) được viết dưới dạng:
A → B,
trong đó A được gọi là giả thiết, B được gọi là mục tiêu tính toán của bài toán.
Định nghĩa 2.1:

Bài toán A → B được gọi là giải được khi có thể tính toán được giá trị các biến thuộc
B xuất phát từ giả thiết A. Ta nói rằng một dãy các quan hệ {f
1
, f
2
, , f
k
} ⊆ F là một lời
giải của bài toán A → B nếu như ta lần lượt áp dụng các quan hệ f
i
(i=1, ,k) xuất phát từ
giả thiết A thì sẽ tính được các biến thuộc B. Lời giải {f
1
, f
2
, , f
k
} được gọi là lời giải tốt
nếu không thể bỏ bớt một số bước tính toán trong quá trình giải, tức là không thể bỏ bớt một
số quan hệ trong lời giải.
Việc tìm lời giải cho bài toán là việc tìm ra một dãy quan hệ để có thể áp dụng suy ra
được B từ A. Điều nầy cũng có nghĩa là tìm ra được một quá trình tính toán để giải bài toán.
Định nghĩa 2.2 :
Cho D = {f
1
, f
2
, , f
k
} là một dãy quan hệ của mạng tính toán (M,F), A là một tập con

của M. Ta nói dãy quan hệ D là áp dụng được trên tập A khi và chỉ khi ta có thể lần lượt áp
dụng được các quan hệ f
1
, f
2
, , f
k
xuất phát từ giả thiết A.
Nhận xét : Trong định nghĩa trên, nếu đặt : A
0
= A, A
1
= A
0
∪ M(f
1
), . . . , A
k
= A
k-1
∪
M(f
k
), và ký hiệu A
k
là D(A), thì ta có D là một lời giải của bài toán A → D(A). Trong
trường hợp D là một dãy quan hệ bất kỳ (không nhất thiết là áp dụng được trên A), ta vẫn
ký hiệu D(A) là tập biến đạt được khi lần lượt áp dụng các quan hệ trong dãy D (nếu được).
Chúng ta có thể nói rằng D(A) là sự mở rộng của tập A nhờ áp dụng dãy quan hệ D.
III. GIẢI QUYẾT VẤN ĐỀ :

1. Tính giải được của bài toán :
Trong mục nầy chúng ta nêu lên một khái niệm có liên quan đến tính giải được của vấn
đề trên một mạng tính toán : bao đóng của một tập hợp biến trên một mạng tính toán.
Định nghĩa 3.1: Cho mạng tính toán (M,F), và A là một tập con của M. Ta có thể
thấy rằng có duy nhất một tập hợp B lớn nhất ⊆ M sao cho bài toán A → B là giải được, và
tập hợp B nầy được gọi là bao đóng của A trên mô hình (M,F). Một cách trực quan, có thể
21
nói bao đóng của A là sự mở rộng tối đa của A trên mô hình (M,F). Ký hiệu bao đóng của A
là
A
, chúng ta có định lý sau đây:
Định lý 3.1. Trên một mạng tính toán (M,F), bài toán A → B là giải được khi và chỉ
khi B ⊆
A
Từ định lý nầy, ta có thể kiểm tra tính giải được của bài toán A → B bằng cách tính bao
đóng của tập A rồi xét xem B có bao hàm trong
A
hay không.
Định lý 3.2. Cho một mạng tính toán (M,F), A, B là hai tập con của M. Ta có các
điều sau đây là tương đương:
(1) B ⊆
A
.
(2) Có một dãy quan hệ D = {f
1
, f
2
, , f
k
} ⊆ F thỏa các điều kiện :

(a) D áp được trên A.
(b) D(A) ⊇ B.
Chứng minh : Giả sử có (1), tức là B ⊆
A
. Khi đó bài toán A → B là giải được. Do đó
có một dãy quan hệ {f
1
, f
2
, , f
k
} ⊆ F sao cho khi ta lần lượt áp dụng các quan hệ f
i
(i=1, ,k) xuất phát từ giả thiết A thì sẽ tính được các biến thuộc B. Dễ dàng thấy rằng dãy
{f
1
, f
2
, , f
k
} nầy thỏa các điều kiện (2).
Đảo lại, giả sử có (2). Với các điều kiện có được bởi (2) ta thấy {f
i
} là lời giải của vấn
đề A
i-1
→ A
i
, với mọi i = 1,2, , k. Từ mệnh đề 3.2 suy ra bài toán A
0

→ A
k
là giải được.
Do đó bài toán A → B cũng giải được, suy ra B ⊆
A
theo định lý 3.1. 
Qua các định lý trên, ta thấy rằng việc xác định bao đóng của một tập biến trên mô hình
tính toán là cần thiết. Dưới đây là thuật toán cho phép xác định bao đóng của tập hợp A ⊆
M. Trong thuật toán nầy chúng ta thử áp dụng các quan hệ f ∈ F để tìm dần những biến
thuộc M có thể tính được từ A; cuối cùng sẽ được bao đóng của A.
Thuật toán 3.1. tìm bao đóng của tập A ⊆ M :
22
Nhập : Mạng tính toán (M,F),
A ⊆ M.
Xuất :
A
Thuật toán :
1. B ← A;
2. Repeat
B1 ← B;
for f ∈ F do
if ( f đối xứng and Card (M(f) \ B) ≤ r(f) ) or
( f không đối xứng and M(f) \ B ⊆ v(f) ) then
begin
B ← B ∪ M(f);
F ← F \ {f}; // loại f khỏi lần xem xét sau
end;
Until B = B1;
3.
A

← B;
2. Lời giải của bài toán :
Ở trên ta đã nêu lên cách xác định tính giải được của bài toán. Tiếp theo, ta sẽ trình bày
cách tìm ra lời giải cho bài toán A → B trên mạng tính toán (M,F).
Mệnh đề 3.4 : dãy quan hệ D là một lời giải của bài toán A → B khi và chỉ khi D áp
dụng được trên A và D(A) ⊇ B.
Do mệnh đề trên, để tìm một lời giải ta có thể làm như sau: Xuất phát từ giả thiết A, ta
thử áp dụng các quan hệ để mở rộng dần tập các biến có giá trị được xác định; và quá trình
nầy tạo ra một sự lan truyền tính xác định trên tập các biến cho đến khi đạt đến tập biến B.
Dưới đây là thuật toán tìm một lời giải cho bài toán A → B trên mạng tính toán (M,F).
Thuật toán 3.2. tìm một lời giải cho bài toán A → B :
Nhập : Mạng tính toán (M,F), 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
23
Thuật toán :
1. Solution ← empty; // Solution là dãy các quan hệ sẽ áp dụng
2. if B ⊆ A then
begin
Solution_found ← true; // biến Solution_found = true khi bài toán là
// giải được
goto 4;
end
else
Solution_found ← false;
3. Repeat
Aold ← A;
Chọn ra một f ∈ F chưa xem xét;
while not Solution_found and (chọn được f) do
begin
if ( f đối xứng and 0 < Card (M(f) \ A) ≤ r(f) ) or

( f không đối xứng and ∅ ≠ M(f) \ A ⊆ v(f) ) then
begin
A ← A ∪ M(f);
Solution ← Solution ∪ {f};
end;
if B ⊆ A then
Solution_found ← true;
Chọn ra một f ∈ F chưa xem xét;
end; { while }
Until Solution_found or (A = Aold);
4. 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;
Ghi chú :
1. Về sau, khi cần trình bày quá trình giải (hay bài giải) ta có thể xuất phát từ lời giải tìm
được dưới dạng một dãy các quan hệ để xây dựng bài giải.
2. Lời giải (nếu có) tìm được trong thuật toán trên chưa chắc là một lời giải tốt. Ta có
thể bổ sung thêm cho thuật toán ở trên thuật toán để tìm một lời giải tốt từ một lời giải
24
đã biết nhưng chưa chắc là tốt. Thuật toán sẽ dựa trên định lý được trình bày tiếp theo
đây.
Định lý 3.3. Cho D={f
1
, f
2
, , f
m
} là một lời giải của bài toán A → B. Ưng với mỗi
i=1, ,m đặt D

i
= {f
1
, f
2
, , f
i
}, D
0
= ∅. Ta xây dựng một họ các dãy con S
m
, S
m-1
, , S
2
, S
1
của dãy D như sau :
S
m
= ∅ nếu D
m-1
là một lời giải,
S
m
= {f
m
} nếu D
m-1
không là một lời giải,

S
i
= S
i+1
nếu D
i-1
∪ S
i+1
là một lời giải,
S
i
= {f
i
} ∪ S
i+1
nếu D
i-1
∪ S
i+1
không là một lời giải,
với mọi i = m-1, m-2, , 2, 1.
Khi đó ta có :
(1) S
m
⊆ S
m-1
⊆ ⊆ S
2
⊆ S
1

.
(2) D
i-1
∪ S
i
là một lời giải của bài toán A → B với mọi i=m, , 2, 1.
(3) Nếu S’
i
là một dãy con thật sự của S
i
thì D
i-1
∪ S’
i
không phải là một lời giải của
bài toán A → B với mọi i.
(4) S
1
là một lời giải tốt của bài toán A → B.
Thuật toán 3.3. tìm một lời giải tốt từ một lời giải đã biết.
Nhập : Mạng tính toán (M,F),
lời giải {f
1
, f
2
, , f
m
} của bài toán A→ B.
Xuất : lời giải tốt cho bài toán A → B
Thuật toán :

1. D ← {f
1
, f
2
, , f
m
};
2. for i=m downto 1 do
if D \ {f
i
} là một lời giải then
D ← D \ {f
i
};
3. D là một lời giải tốt.
Trong thuật toán 3.3 có sử dụng việc kiểm tra một dãy quan hệ có phải là lời giải hay
không. Việc kiểm tra nầy có thể được thực hiện nhờ thuật toán sau đây:
Thuật toán kiểm tra lời giải cho bài toán :
Nhập : Mạng tính toán (M,F), bài toán A→ B, dãy các quan hệ {f
1
, f
2
, , f
m
}.
Xuất : thông tin cho biết {f
1
, f
2
, , f

m
} có phải là lời giải
25