TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐÀO TẠC THẠC SĨ CNTT QUA MẠNG
MỘT SỐ MÔ HÌNH BIỂU DIỄN TRI THỨC
Bộ môn: Biểu diển tri thức và ứng dụng
Giáo viên hướng dẫn: PGS.TS. Đỗ Văn Nhơn
Sinh viên: Trần Hoài Phong
MSSV: CH1101027
Niên khóa 2011 - 2013
Mục lục
Lời mở đầu
Mức độ phát triển của các hệ thống dựa trên tri thức của con người đã được mở
rộng ngày một nhanh. Nó đã thoát khỏi lĩnh vực thông thường, nhu cầu cần có một mô
hình để biểu diển tri thức cho các chương trình chuyên gia đã trở nên vô cùng cần thiết.
Có một điều cần phải biết là lĩnh vực này đang ngày càng trở nên phức tạp vì tính đặc
Niên khóa 2011 - 2013
2
thù của ngôn ngữ tự nhiên, do đó cần một hệ thống để có thể giao tiếp với các chuyên
gia theo ngôn ngữ của họ là không thể bỏ qua. Ngoài ra các công việc như chuẩn đoán
y khoa, phân tích kịch bản, hiểu được ngôn ngữ tự nhiên và chơi trò chơi, tất cả đã
từng bước phát triển các mô hình để có thể biểu diển được một phần những tri thức
chưa đầy đủ lên trên hệ thống máy tính.
Chính vì tính chất phức tạp cùng với việc các mô hình hiện tại vẫn chưa thể biểu
diễn đầy đủ tri thức của con người lên hệ máy tính. Do đó ngày càng nhiều công trình
nghiên cứu về các mô hình và phương pháp để có thể biểu diễn tri thức để có thể đưa
vào ứng dụng thực tế.
Trong bài tiểu luận này em sẽ đưa ra một số mô hình để biểu diễn tri thức để
giúp hiểu rõ hơn cách làm thế nào mà tri thức của con người có thể được biểu diễn trên
một hệ thống ứng dụng thực tế cũng như hiểu rõ hơn được các đặc trưng cơ bản của
từng mô hình. Vì thời gian và kiến thức có hạn nên bài tiểu luận vẫn còn nhiều hạn chế
rất mong được sự đóng góp ý kiến từ thầy.
Cuối cùng em xin cám ơn thầy đã rất nhiệt tình hướng dẫn trong quá trình giảng

với đà phát triển. Tỷ lệ người có trình độ về khoa học máy tính chỉ chiếm tỷ lệ rất thấp
trên dân số có việc làm. Nghĩa là trong khi càng ngày càng nhiều người phải làm việc
với máy tính trong cuộc sống hàng ngày của họ, tỷ lệ người có trình độ cao trong khoa
học máy tính lại duy trì với mức rất thấp. Kết quả là càng ngày càng nhiều người
không có đủ kiến thức cụ thể cần thiết trong lĩnh vực khoa học máy tính để có thể giao
tiếp được với máy tính.
Tình trạng này làm tăng lên sự cần thiết của việc liên lạc với máy tính theo cách
dễ dàng và trực quan nhất mà không cần phải yêu cầu kiến thức chuyên sâu từ người
Niên khóa 2011 - 2013
4
dùng. Tuy nhiên trên thực tế con người và máy tính dùng các loại ngôn ngữ hoàn toàn
khác biệt đó là một trong những trở ngại lớn nhất trong việc giao tiếp giữa con người
với máy tính. Máy tính sử dụng các ngôn ngữ hình thức như ngôn ngữ lập trình hay
ngôn ngữ logic trong khi con người thể hiện họ bằng ngôn ngữ tự nhiên.
Giải pháp đơn giản nhất cho vấn đề này là viết các chương trình máy tính sao
cho chúng có khả năng xử lý ngôn ngữ tự nhiên sao cho hợp lý nhất. Mặc dù đã có
nhiều thành công bước đầu trong lĩnh vực nghiên cứu này, việc xử lý ngôn ngữ tự
nhiên trở thành một vấn đề vô cùng khó khăn. Từ những cố gắng đầu tiên, một lượng
lớn các nghiên cứu đã trực tiếp làm việc trên vấn đề này trong vài thập kỷ trở lại đây.
Mặc dù thực tế là có những tiến triển trên một số khía cạnh, máy tính vẫn thất bại trong
việc xử lý ngôn ngữ tự nhiên một cách tổng quát và đáng tin cậy nhất.
Trong khi máy tính thất bại trong việc hiểu ngôn ngữ tự nhiên, thì con người
được biết là gặp rất nhiều khó khăn trong việc học ngôn ngữ hình thức. Ví dụ rất nhiều
người sử dụng web thất bại trong việc dùng chính xác các toán tử vô cùng đơn giản
trong các công cụ tìm kiếm. Ngoài ra việc sử dụng các ngôn ngữ logic cũng gặp rất
nhiều khó khăn.
Nhìn chung, kết quả hiển nhiên là con người và máy tính có thể giao tiếp nhau
nhưng không thể dùng ngôn ngữ của hai bên. Một số mô hình đã ra đời để giải quyết
vấn đề này trên một số khía cạnh nhất định đó là có thể phần nào biểu diễn những tri
thức quý giá của con người lên máy tính và có thể tự phân tích được dựa vào những tri

Mô hình biểu diễn tri thức của hệ luật dẫn gồm có hai thành phần chính (Facts,
Rules). Trong đó Facts bao gồm các phát biểu chỉ các sự kiện hay các tác vụ nào đó,
còn Rules gồm các luật dẫn có dạng “if…then….”
Ví dụ: Một phần cơ sở tri thức của tam giác
- Các yếu tố của tam giác ví dụ cạnh a, b, c; góc A, B, C, chu vi p, diện tích S,
đường cao ha, hb, hc….
Niên khóa 2011 - 2013
6
 Đưa vào Facts = {a, b, c, A, B, C, p, S, ha, hb, hc, …}
- Các luật sinh ví dụ: nếu có góc A, góc B thì có góc C,…
 Đưa vào Rules = {
r1: {A, B} -> {C= pi – A – B}
…
}
1.1.3. Tổ chức lưu trữ
Khi tiến hành lưu trữ tuỳ theo cấu trúc của Facts mà ta có thể sữ dụng các cấu
trúc dữ liệu phổ biến như struct, frames, classes,…
Ví dụ một tổ chức lưu trữ: hệ thống sẽ lưu hai tập tin dạng text có cấu trúc:
Fact.txt và Rule.txt. Trong đó cấu trúc của mỗi tập tin như sau:
 Fact.txt
Begin
a: cạnh a của tam giác
b: cạnh b của tam giác
…
End
 Rule.txt
Begin
{A, B} => {C = 180 - A - B}
…
End

B1: Giả sử mục tiêu đúng
B2: Phát sinh các mục tiêu con
B3: Kiểm tra các mục tiêu con
Niên khóa 2011 - 2013
8
If mục tiêu đáp ứng then goto B8
B4: Tìm luật có thể phát sinh sự kiện mới
B5: If không tìm được luật then
Dừng không tìm được lời giải
B6: If B4 thành công then
Ghi nhận thông tin về luật vào lời giải và sự kiện mới vào giả thiết được
phát sinh từ các luật.
B7: Goto B4
B8: Tìm được lời giải trong danh sách luật solution
1.1.5. 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 như
 Rút gọn vế phải:
A ∧ B  A ∧ C sẽ trở thành A ∧ B  C
 Rút gọn vế trái
(L1) A, B  C (L2) A  X (L3) X  C sẽ trở thành A  C do đó L1 bị dư
thừa có thể loại bỏ
 Phân rã và kết hợp luật
A ∧ B  C sẽ trở thành A  C, B  C
 Luật thừa
Một luật là thừa nếu có thể suy ra từ luật khác ví dụ A  B, B  C, A  C thì

+ Một quy tắc suy luận: u(f)  v(f), với u(f) ⊆ M, v(f) ⊆ M, và có một công
thức tương ứng để xác định (hoặc tính toán) các biến trong v(f) từ u(f). Ta có M(f) =
u(f) ∪ v(f).
Ví dụ: Tam giác ABC có thể được biểu diễn bởi mạng tính toán như sau M = {a,
b, c, A, B, C, R, S, p} và F = { f
1
: A + B + C = 180 f
2
:
sinB
b
sinA
a
=
f
3
:
sinB
b
sinC
c
=
f
4
:
sinC
c
sinA
a
=

Định nghĩa 2.2.2.1
Cho một mạng tính toán K = (M, F)
(i) Cho mỗi A ⊆ M và f
∈
F, ta ký hiệu f(A) = A ∪ M(f) là tập thu được từ A
bằng cách áp dụng f, cho S = [f1, f2, , fk] là một danh sách chứa các
quan hệ trong F, ký hiệu S(A) = fk(fk-1( (f2(f1(A)) )) được dùng để
biểu hiện một tập hợp các biến lấy được từ A bằng cách áp dụng các
quan hệ f.
Niên khóa 2011 - 2013
11
(ii) Danh sách S = [f1, f2, , fk] được gọi là một giải pháp của vấn đề H 
G nếu G ⊆ S(H). Giải pháp S được gọi là giải pháp tốt nhất nếu không có
một danh sách con S’ của S sao cho S’ cũng là giải pháp của vấn đề. Vấn
đề được xem là có thể giải quyết được nếu nó có một giải pháp.
Định nghĩa 2.2.2.2
Cho một mạng tính toán K = (M, F)
Cho A là tập con của M. Có thể dễ dàng xác định tồn tại một tập duy nhất
A
⊆
M sao cho bài toán A 
A
giải được; tập
A
được gọi là bao đóng của A.
1.1.9. Thuật toán
Định lý 1
Cho một mạng tính toán K = (M, F). Các dòng sau đây tương đương nhau
(i) Bài toán H  G giải được.
(ii)

Until Solution_found or (H = Hold);
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;
Thuật toán 2: Tìm lời giải tốt nhất từ một lời giải S = [f
1
, f
2
, , f
k
] của bài toán
H  G trên mạng tính toán (M, F).
1. D ← {f1, f2, , fm};
2. for i = m downto 1 do
if D \ {fi} là một lời giải then
D ← D \ {fi};
3. D là một lời giải tốt.
Niên khóa 2011 - 2013
13
Trên mạng tính toán K = (M,F). Có nhiều trường hợp bài toán H  G có một
lời giải S mà trong đó có nhiều quan hệ dẫn tới việc tính toán một số biến thừa. Do đó,
chúng ta cần xác định các biến thật sự cần thiết trong mỗi bước trong quá trình giải
quyết bài toán. Định lý sau đây cho ta thấy làm cách nào để phân tích một lời giải để
xác định ra các biến cần thiế để tính toán trong từng bước.
Định lý 2: Cho một mạng tính toán K = (M, F). Gọi {f1, f2, , fm} là một lời
giải tốt cho bài toán H → G. Đặt : A0 = H, Ai = {f1, f2, , fi}(H), với mọi
i=1, ,m. Khi đó có một dãy {B0, B1, , Bm-1, Bm}, thỏa các điều kiện sau đây:
(1) Bm = G.
(2) Bi ⊆ Ai , với mọi i=0,1, ,m.

phức tạp, việc giải quyết bài toán bằng mạng tính toán trở nên khó khăn cho người lập
trình.
2.3. Mạng các đối tượng tính toán:
1.1.11.Khái niệm
Trong rất nhiều bài toán chúng ta thường gặp rất nhiều loại đối tượng. Mỗi một
đối tượng có các thuộc tính và các mối quan hệ bên trong giữa chúng. Vì vậy, mạng
tính toán được mở rộng sao cho mỗi biến là một đối tượng tính toán.
Định nghĩa 1 Một đối tượng tính toán sẽ có những đặc tính sau:
(1) Nó có các thuộc tính giá trị. Một tập hợp các thuộc tính này của đối tượng O
sẽ được ký hiệu là M(O).
(2) Có các quan hệ tính toán nội bộ giữa các thuộc tính của đối tượng O. Chúng
được hiện ra trong các đặc trưng sau đây của đối tượng:
 Cho một tập con A của M(O). Đối tượng O có thể cho chúng ta thấy các
thuộc tính có thể xác định được từ tập con A.
 Đối tượng O sẽ đưa ra giá trị của một thuộc tính.
Niên khóa 2011 - 2013
15
 Nó có thể hiện lên các xử lý bên trong để xác định ra các thuộc tính.
Ví dụ: 1 tam giác với các tri thức (công thức, định lý, …) là một đối tượng. Các
thuộc tính của đối tượng tam giác là ba góc, 3 cạnh,… Một đối tượng tam giác có thể
trả lời một số câu hỏi ví dụ như là “Có không một lời giải cho một bài toán để tính toán
diện tích từ một cạnh và hai góc?”
Định nghĩa 2 Quan hệ tính toán f giữa các thuộc tính của một đối tượng cụ thể
được gọi là một quan hệ giữa các đối tượng. Mạng các đối tượng tính toán sẽ chứa một
tập hợp các đối tượng tính toán O = { O1, O2, …, On} và một tập các quan hệ tính
toán F = { f1, f2, … fm}. Có một số ký hiệu sau đây:
M(fi) = Tập hợp các thuộc tính của đối tượng tính toán trong quan hệ fi
M(F) =
M(f
i

ABDE, O4: hình vuông ACFG} và F = {f1, f2, f3, f4, f5} gồm các quan hệ sau
F1: O1.c = O3.a
F2: O1.b = O4.a
F3: O2.b = O4.a
F4: O2.c = O3.a
F5: O1.A + O2.A = 180
Định nghĩa 3 Cho (O, F) là mạng các đối tượng tính toán, M là tập hợp các
thuộc tính có liên quan. Giả sử A là một tập con của M
(a) Với mỗi f ∈ F, gọi f(A) là hội của tập hợp A và tập hợp gồm tất cả các thuộc
tính trong M suy ra từ A bởi f. Tương tự như vậy, với mỗi đối tượng tính
toán Oi ∈ O, Oi(A) là hội của tập hợp A và tập hợp bao gồm tất cả thuộc
tính (trong M) mà đối tượng Oi có thể xác định từ các thuộc tính trong A.
(b) Giả sử D = [t1, t2, …, tm] là một danh sách các yếu tố trong F ∪ O. Ký hiệu
Ao = A, A1 = t1(Ao), …., Am = tm(Am-1) và D(A) = Am
Chúng ta có Ao ⊆ A1 ⊆ …. ⊆ Am = D(A) ⊆ M.
Một bài toán H  G được gọi là giải được nếu có một danh sách D ⊆ F ∪ O
sao cho D(A) ⊇ B. Trong trường hợp này, chúng ta gọi D là một lời giải của
bài toán
Niên khóa 2011 - 2013
17
1.1.12.Thuật toán
Thuật toán 1: Tìm một lời giải cho bài toán H  G trên mạng các đối tượng
tính toán.
1. Solution ← empty;
2. if G ⊆ H then
begin
Solution_found ← true;
goto 5;
end
else

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;
Ví dụ:
Trong mô hình (O, F) trong ví dụ trên, và bài toán H  G. Trong đó H = {O1.a,
O1.A} và G = {O2.a}. Chúng ta có
M(f1) = {O1.c, O3.a};
M(f2) = {O1.b, O4.a};
Niên khóa 2011 - 2013
19
M(f3) = {O2.b, O4.a};
M(f4) = {O2.c, O3.a};
M(f5) = {O1.A, O2.A};
Thuật toán trên sẽ tạo ra một lời giải
D = {f5, O1, f1, f2, f3, f4, O2}
Và quá trình mở rộng tập hợp các thuộc tính như sau
A
0

5
f
 →
A
1


2
O
 →
A
7
Trong đó :
A
0
= A = {O
1
.a , O
1
.A},
A
1
= {O
1
.a , O
1
.A, O
2
.A},
A
2
= { O
1
.a , O
1
.A, O
2

.b, O
1
.c, O
3
.a, O
4
.a},
A
5
= {O
1
.a , O
1
.A, O
2
.A, O
1
.b, O
1
.c, O
3
.a, O
4
.a, O
2
.b},
A
6
= {O
1

3
.a, O
4
.a, O
2
.b, O
2
.c, O
2
.a}.
Thuật toán 2: Tìm lời giải tốt nhất từ một lời giải S = [f
1
, f
2
, , f
k
] của bài toán
H  G trên mạng tính toán (M, F).
1. D ← {f1, f2, , fm};
2. for i = m downto 1 do
if D \ {fi} là một lời giải then
D ← D \ {fi};
3. D là một lời giải tốt.
1.1.13.Ưu và khuyết điểm của mạng các đối tượng tính toán:
 Ưu điểm:
Niên khóa 2011 - 2013
20
Giải được hầu hết các bài toán GT  KL nếu như đáp ứng đầy đủ các giả thiết
cần thiết.
Thuật toán đơn giản dễ cài đặt cho nên việc bảo trì hệ thống tương đối đơn giản.

 Funcs là tập các hàm.
 Rules là tập các luật.
C tập hợp các đối tượng tính toán
Đối tượng tính toán có các đặc điểm sau:
(1) Nó có các thuộc tính giá trị. Một tập hợp chứa tất cả các thuộc tính của đối
tượng O được ký hiệu là M(O).
(2) Có các quan hệ tính toán bên trong giữa các thuộc tính của một đối tượng
tính toán O. Chúng được biểu thị qua các đặc trưng sau của đối tượng:
- Cho một tập con A của M(O). Đối tượng O có thể cho chúng ta biết các
thuộc tính có thể xác dịnh được từ A.
- Đối tượng O sẽ đưa ra giá trị của một thuộc tính.
- Nó cũng có thể hiện ra các xử lý nội bộ trong việc xác định thuộc tính.
Cấu trúc của một đối tượng tính toán có thể được mô hình bởi (Attrs, F, Fact,
Rules). Attrs là một tập các thuộc tính, F là một tập các suy diễn tính toán, Facts là tập
các tính chất hay sự kiện vốn có của đối tượng và Rules là tập các luật suy diễn trên
các sự kiện liên quan đến các thuộc tính cũng như liên quan đến bản thân đối tượng.
Ví dụ: Tri thức về một tam giác bao gồm các nhân tố (góc, cạnh, ) cùng với
các công thức và các thuộc tính có thể được mô hình như là một lớp của các đối tượng
tính toán như sau:
Attrs = { A, B, C, a, b, c, R, S, p, }
Niên khóa 2011 - 2013
22
F = {A+B+C=180,
R2
sinA
a
=
,
R2
sinB

tượng. Hầu hết lĩnh vực tri thức nào đều có một thành phần chứa các toán tử. Trong
hình học sẽ có một số toán tử như là cộng, nhân các vectơ, trong đại số tuyến tính có
Niên khóa 2011 - 2013
23
các toán tử trên các ma trận. Mô hình KBCO giúp tổ chức các tri thức này như là một
phần của hệ tri thức của hệ thống thông minh.
Funcs: Tập hợp các hàm số trên các đối tượng tính toán
Tri thức về các hàm cũng là loại phổ biến của tri thức trong hầu hết các lĩnh vực
tri thức trong thực tế, đặc biệt là trong các lĩnh vực khoa học tự nhiên như toán học
hoặc vật lý. Trong hình học chúng ta có các hàm: khoảng cách giữa hai điểm, khoảng
cách từ điểm đến một đường thẳng, mặt phẳng,
Rules: biểu diễn các luật
Tập hợp các luật là một phần của cơ sở tri thức. Các luật biểu hiện các câu nói,
định lý, nguyên tắc, công thức Hầu hết các luật viết dưới dạng “if <facts> then
<facts>”.
1.1.15.Các loại sự kiện trong mô hình KBCO
Trong mô hình KBCO có 11 loại sự kiện được chấp nhận. Các loại sự kiẹn này
được đề xuất từ các nghiên cứu dựa trên các yêu cầu thực và các vấn đề trong các lĩnh
vực tri thức khác nhau. Các loại sự kiện bao gồm:
Sự kiện loại 1: Sự kiện thông tin về loại của đối tượng.
Ví dụ: ABC là tam giác cân, ABCD là hình bình hành
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.
Ví dụ: Cho các điểm E và F, và đường thẳng (d). Giả sử E, F và (d) đã được xác
định. (P) là mặt phẳng thoả các quan hệ sau: E ∈ (P), F ∈ (P), (d) // (P). Tìm phương
trình mặt phẳng (P). Trong ví dụ này có 3 sự kiện loại 3: (1) điểm E được xác định
hoặc chúng ta biết được toạ độ của E, (2) điểm F xác định, (3) đường thẳng (d) được
xác định hoặc chúng ta biết được phương trình của (d).
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.

25