BỘ GIÁO DỤC & ĐÀO TẠO
ĐẠI HỌC QUỐC GIA TP HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI BÁO CÁO MÔN HỌC:
BIỂU DIỄN TRI THỨC VÀ
ỨNG DỤNG
ĐỀ TÀI: MẠNG TÍNH TOÁN
TP.HCM,Tháng 2,năm 2013
GVHD:
PGS.TS. ĐỖ VĂN NHƠN
SINH VIÊN THỰC HIỆN:
PHẠM QUANG DIỆU CH1101077
UNIVERSITY OF INFORMATION TECHNOLOGY
PHẦN NHẬN XÉT VÀ CHO ĐIỂM
GIẢNG VIÊN NHẬN XÉT:
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
………………………………………………………………………………………
Xếp loại ý thức, thái độ học tập và chấp hành nội quy của sinh viên:
Tốt Khá Trung bình Yếu Kém
Điểm:
Bằng chữ:…………………………………………………………………….

1.1 VẤN ĐỀ BIỂU DIỄN TRI THỨC
• Trong cấu trúc của một hệ giải toán dựa trên tri thức, 2 thành phần trung
tâm là cơ sở tri thức và bộ suy diễn dựa trên tri thức.
• Đã có nhiều phương pháp biểu diễn tri thức và suy diễn đã được nghiên cứu
và đề xuất. Tuy nhiên mỗi phương pháp đều chỉ thể hiện được một khía
cạnh nào đó của tri thức và có những nhược điểm nhất định.
⇒ Cần xây dựng và phát triển các mô hình biểu diễn tri thức giúp thiết kế và cài
đặt phần tri thức cũng như phần suy diễn của các hệ giải toán dựa trên tri thức.
1.2 CÁC VÍ DỤ DẪN TỚI MÔ HÌNH
Trong nhiều chủ đề giải toán thường gặp những vấn đề đặt ra dưới dạng
như sau:
4
UNIVERSITY OF INFORMATION TECHNOLOGY
• Cần 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.
Ví dụ 1:
Giả sử chúng ta đang quan tâm đến một số yếu tố trong một tam giác,
chẳng hạn : 3 cạnh a, b, c; 3 góc tương ứng với 3 cạnh : α, β, γ; 3 đường cao
tương ứng : ha, hb, hc; diện tích S của tam giác; nửa chu vi p của tam giác; bán
kính đường tròn nội tiếp r của tam giác.
Giữa 12 yếu tố trên có các công thức thể hiện những mối quan hệ giúp ta có
thể giải quyết được một số vấn đề tính toán đặt ra như: Tính một yếu tố từ một số
yếu tố được cho trước. Chẳng hạn, tính S khi biết a, b và p.
Trong tam giác chúng ta có thể kể ra một số quan hệ dưới dạng công thức
sau đây:
• Liên hệ giữa 3 góc : α + β + γ = π

b
/2;
5
γβα
sin
c

sin
b
sin
a
==
UNIVERSITY OF INFORMATION TECHNOLOGY
S=c.h
c
/2;
S = p.r
• Công thức tính diện tích theo 3 cạnh (công thức Heron):
Ví dụ 2.
Một vật thể có khối lượng m chuyển động thẳng với gia tốc không thay đổi
là a trong một khoảng thời gian tính từ thời điểm t
1
đến thời điểm t
2
. Vận tốùc
ban đầu của vật thể là v
1
, vận tốc ở thời điểm cuối là v
2
, và vận tốc trung bình

6
c)b)(pa)(pp(p −−−
UNIVERSITY OF INFORMATION TECHNOLOGY
2.1 Khái niệm tri thức
° Tri thức không có được định nghĩa chính xác
° Khái niệm: Tri thức (knowledge) là sự hiểu biết về một lĩnh vực của chủ đề.
° Lĩnh vực: miền chủ đề được chú trọng.
° Tri thức thuờng bao gồm các khái niệm, các loại sự kiện, các luật,
Ví dụ:
1. 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.
2. 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.
3. 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.
2.2 Khái niệm về biểu diễn tri thức
° Biểu diễn tri thức (Knowledge Representation) là sự diễn đạt và thể hiện
của tri thức dưới những dạng thích hợp để có thể tổ chức một cơ sở tri thức của
hệ thống.
° Tại sao phải biểu diễn tri thức?Biểu diễn tri thức giúp có thể tổ chức và cài
đặt một cơ sở tri thức cho các hệ chuyên gia, các hệ cở sở tri thức và các hệ
giải bài toán dựa trên tri thức.
Công cụ cho việc biểu diễn tri thức
° Các cấu trúc dữ liệu cơ bản: dãy, danh sách, tập hợp, mẫu,
° Các cấu trúc dữ liệu trừu tượng: ngăn xếp, hàng đợi.
° Các mô hình toán học: đồ thị, cây.
° Các mô hình đối tượng.
° Các ngôn ngữ đặc tả tri thức.
Vídụ:
Kiến thức về một tam giác cần thiết cho việc giải bài toán tam giác có thể
được biểu diễn gồm:

- 2.b.c.cos α
• f
3
: b
2
= a
2
+ c
2
- 2.a.c.cos β
• f
4
: c
2
= a
2
+ b
2
- 2.a.b.cos γ
• f
5
: a / sin α = b / sin β
• v.v
2.3 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

thử nghiệm nhiều chiến lượt điều khiển khác nhau trên cùng một cơ sở tri
thức.
3.2 Vấn đề biểu diễn tri thức
° Biểu diễn tri thức đóng vai trò rất quan trọng trong thiết kế và xây dựng
một hệ giải bài toán thông minh và các hệ chuyên gia.
° Phương pháp biểu diễn tri thức thích hợp sẽ tạo nên một hệ thống có trái
tim khỏe mạnh.
° Xây dựng và phát triển các phương pháp biểu diễn tri thức là một hướng
nghiên cứu quan trọng cho các nhà nghiên cứu về Trí tuệ Nhân tạo
3.3 Vấn suy diễn tự động
° Suy diễn tự động để giải quyết các bài toán dựa trên tri thức cũng là một
vấn đề quan trọng.
° Các phương pháp suy diễn tự động nhằm vận dụng kiến thức đã biết trong
quá trính lập luận giải quyết vấn đề trong đó quan trọng nhất là các chiến
lược điều khiển giúp phát sinh những sự kiện mới từ các sự kiện đã có.
• Xây dựng và phát triển các phương pháp biểu diễn tri thức là một hướng
nghiên cứu quan trọng cho các nhà nghiên cứu về Trí tuệ Nhân tạo
IV. CÁC PHƯƠNG PHÁP BIỂU DIỄN
TRI THỨC
4.1 Logic hình thức
° Sử dụng các biểu thức logic hình thức trong một hệ thống logic để diễn đạt
các sự kiện và các luật trong cơ sở tri thức.
° Phép tính logic vị từ cấp 1 được sử dụng phổ biến nhất và có cả một ngôn
ngữ lập trình hỗ trợ cho phương pháp này. Đó là ngôn ngữ lập trình
PROLOG.
° Trong ngôn ngữ PROLOG, chỉ cần khai báo các sự kiện và các luật. Hệ
thống sẽ thức hiện giải quyết vấn đề được yêu cầu dựa trên tri thức được
khai báo.
4.2 Hệ luật dẫn
° Mỗi luật dẫn được phát biểu dưới dạng:

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 viết 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 trên và ta gọi mô hình này là
“Mạng tính toán”.
2. 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
11
UNIVERSITY OF INFORMATION TECHNOLOGY
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.
2.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
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ệ f giữa 3 góc trong một tam giác trên đây là một quan hệ đối xứng có hạng
1.
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.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).
Ví dụ: Mạng tính toán của một hình chữ nhật
13
A
B

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?
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
, ,
14
UNIVERSITY OF INFORMATION TECHNOLOGY
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

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.
4. GIẢI QUYẾT VẤN ĐỀ :
4.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 4.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ể 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ý 4.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

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 4.1. tìm bao đóng của tập A ⊆ M :
Nhập :Mạng tính toán (M,F),

Thuật toán 4.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
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

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,

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 4.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
đối xứng and Card (M(f
i
) \ A) ≤ r(f
i
) ) or
( f
i
không đối xứng and M(f
i
) \ A ⊆ v(f
i
) ) then
A ← A ∪ M(f
i
);
2. if A ⊇ B then {f
1
, f
2
, , f
m
} là lời giải
else {f
1
, f
2
, , f
m
} không là lời giải;

, B
1
, , B
m-1
, B
m
}, thỏa các điều kiện sau đây:
(1) B
m
= B.
(2) B
i
⊆ A
i
, với mọi i=0,1, ,m.
(3) Với mọi i=1, ,m, {f
i
} là lời giải của bài toán B
i-1
→ B
i
nhưng không
phải là lời giải của bài toán G → B
i
, trong đó G là một tập con thật sự tùy ý của
B
i-1
.
Ghi chú :
(1) Từ định lý trên ta có quá trình tính toán các biến để giải bài toán A→B như

’, B
m
’} rời nhau cần lần lượt tính toán trong quá
trình giải bài toán (B
i
’ = B
i
\ B
i-1
) gồm các bước chính như sau:
• xác định các tập A
0
, A
1
, , A
m
.
• xác định các tập B
m
, B
m-1
, , B
1
, B
0
.
• xác định các tập B
1
’, B
2

sin
b
sin
α β
=
f
3
:
c
sin
b
sin
γ β
=
f
4
:
a
sin
c
sin
α γ
=
f
5
: p = (a+b+c) /2 f
6
: S = a.h
a
/ 2

f
 →
{a, β, γ, α}
2
f
 →
{a, β, γ, α, b}
3
f
 →
{a, β, γ, α, b, c}
5
f
 →
{a, β, γ, α, b, c, p}
9
f
 →
{a, β, γ, α, b, c, p, S}.
Có thể nhận thấy rằng lời giải nầy không phải là lời giải tốt vì có bước tính toán
thừa, chẳng hạn là f
5
. Thuật toán 3.3 sẽ lọc ra từ lời giải trên một lời giải tốt là
{f
1
, f
2
, f
9
}:

các chất khác. Tạm thời bỏ qua một số điều kiện phản ứng, 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. Ví dụ như
phản ứng điều chế Clo từ axít Clohidric và đioxit mangan :
MnO
2
+ HCl → MnCl
2
+ Cl
2
↑ + H
2
O.
Phản ứng trên có thể được xem như một quan hệ cho chúng ta có được các chất
Cl
2
, MnCl
2
, H
2
O từ các chất MnO
2
, HCl.
Giả sử ta đã biết một số những phản ứng hóa học. Chẳng hạn như một số
phản ứng của Clo sau đây:
Na + Cl
2
→ NaCl
Fe + Cl
2
→ FeCl

O → Cl
2
↑ + H
2
↑ + NaOH
K + Cl
2
→ KCl
Bây giờ giả sử ta phải giải quyết bài toán điều chế như sau: cho rằng ta có
các chất hóa học S, H
2
O, NaCl; hãy tìm các phản ứng điều chế các chất hóa học
Na
2
SO
4
, H
2
SO
4
,HCl, Na.
21
UNIVERSITY OF INFORMATION TECHNOLOGY
Bằng các tiến hành thuật giải tìm lời giải nêu trong phần III.2 ở trên trong
tập các phản ứng hóa học ta có thể tìm ra các phản ứng sau đây:
H
2
O + NaCl → NaOH + H
2
+ Cl

3
+ H
2
O → H
2
SO
4

H
2
SO
4
+ NaOH → Na
2
SO
4
+ H
2
O
22
UNIVERSITY OF INFORMATION TECHNOLOGY
VI. TÀI LIỆU THAM KHẢO
[1] Enn Tyugu. (1988). Knowledge-based Programming.
ADDISON-WESLEY PUBLISHING COMPANY.
[2] Elaine Rich & Kevin Knight. (1991). Artificial Intelligence.
McGraw-Hill, Inc.
[3] Jean-Louis Laurière. (1990). Problem-Solving and Artificial Intelligence.
Prentice Hall.
[4] Bạch Hưng Khang & Hoàng Kiếm. (1989). Trí Tuệ Nhân Tạo, các phương
pháp