Tóm t t ắ
Bi u di n tri th c s d ng m ng ng nghĩa ễ ễ ứ ử ụ ạ ữ
Tác gi ả
•Ths. Đinh Nguy n Anh Dũngễ
•GS.TSKH. Hoàng Ki mế
BI U DI N TRI TH C S D NG M NGỄ Ễ Ứ Ử Ụ Ạ
NG NGHĨAỮ
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 :
•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. ẵ ạ
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. ễ
u đi m và nh c đi m c a m ng ng nghĩa Ư ể ượ ể ủ ạ ữ
u đi m Ư ể
•M ng ng nghĩa r t linh đ ng, ta có th d dàng thêm vào m ng các đ nh ho c cungạ ữ ấ ộ ể ễ ạ ỉ ặ
m i đ b sung các tri th c c n thi t. ớ ể ổ ứ ầ ế
•M ng ng nghĩa có tính tr c quan cao nên r t d hi u. ạ ữ ự ấ ễ ể
•M ng ng nghĩa cho phép các đ nh có th th a k các tính ch t t các đ nh khác thôngạ ữ ỉ ể ừ ế ấ ừ ỉ
qua các cung lo i "là", t đó, có th t o ra các liên k t "ng m" gi a nh ng đ nh khôngạ ừ ể ạ ế ầ ữ ữ ỉ
có liên k t tr c ti p v i nhau. ế ự ế ớ
•M ng ng nghĩa ho t đ ng khá t nhiên theo cách th c con ng i ghi nh n thông tin. ạ ữ ạ ộ ự ứ ườ ậ
Nh c đi m ượ ể
•Cho đ n nay, v n ch a có m t chu n nào quy đ nh các gi i h n cho các đ nh và cungế ẫ ư ộ ẩ ị ớ ạ ỉ
c a m ng. Nghĩa là b n có th gán ghép b t kỳ khái ni m nào cho đ nh ho c cung! ủ ạ ạ ể ấ ệ ỉ ặ
•Tính th a k (v n là m t u đi m) trên m ng s có th d n đ n nguy c mâu thu nừ ế ố ộ ư ể ạ ẽ ể ẫ ế ơ ẫ
trong tri th c. Ch ng h n, n u b sung thêm nút "Gà" vào m ng nh hình sau thì ta cóứ ẳ ạ ế ổ ạ ư
th k t lu n r ng "Gà" bi t "bay"!. S dĩ có đi u này là vì có s không rõ ràng trongể ế ậ ằ ế ở ề ự
ng nghĩa gán cho m t nút c a m ng. B n đ c có th ph n đ i quan đi m vì choữ ộ ủ ạ ạ ọ ể ả ố ể
r ng, vi c sinh ra mâu thu n là do ta thi t k m ng d ch không ph i do khuy tằ ệ ẫ ế ế ạ ở ứ ả ế
đi m c a m ng!. Tuy nhiên, xin l u ý r ng, tính th a k sinh ra ể ủ ạ ư ằ ừ ế r t nhi u ấ ề m i liênố
"ng m" nên kh năng n y sinh ra m t m i liên h không h p l là r t l n!ầ ả ả ộ ố ệ ợ ệ ấ ớ
H u nh không th bi n di n các tri th c d ng th t c b ng m ng ng nghĩa vì các kháiầ ư ể ể ễ ứ ạ ủ ụ ằ ạ ữ
ni m v th i gian và trình t không đ c th hi n t ng minh trên m ng ng nghĩa. ệ ề ờ ự ượ ể ệ ườ ạ ữ
M t ví d tiêu bi u ộ ụ ể
Dù là m t ph ng pháp t ng đ i cũ và có nh ng y u đi m nh ng m ng ng nghĩav n cóộ ươ ươ ố ữ ế ể ư ạ ữ ẫ
nh ng ng d ng vô cùng đ c đáo. Hai lo i ng d ng tiêu bi u c a m ng ng nghĩa là ngữ ứ ụ ộ ạ ứ ụ ể ủ ạ ữ ứ
d ng x lý ngôn ng t nhiên và ng d ng gi i bài toán t đ ng. ụ ử ữ ự ứ ụ ả ự ộ
Ví d 1ụ : Trong ng d ng x lý ngôn ng t nhiên, m ng ng nghĩa có th giúp máy tính phânứ ụ ử ữ ự ạ ữ ể
tích đ c c u trúc c a câu đ t đó có th ph n nào "hi u" đ c ý nghĩa c a câu. Ch ngượ ấ ủ ể ừ ể ầ ể ượ ủ ẳ
h n, câu ạ"Châu đang đ c m t cu n sách dày và c i khoái trá" ọ ộ ố ườ có th đ c bi u di n b ngể ượ ể ễ ằ
m t m ng ng nghĩa nh sau : ộ ạ ữ ư
Ví d 2 : Gi i bài toán tam giác t ng quátụ ả ổ
Chúng ta s không đi sâu vào ví d 1 vì đây là m t v n đ quá ph c t p đ có th trình bàyẽ ụ ộ ấ ề ứ ạ ể ể
trong cu n sách này. Trong ví d này, chúng ta s kh o sát m t v n đ đ n gi n h n nh ngố ụ ẽ ả ộ ấ ề ơ ả ơ ư
cũng không kém ph n đ c đáo. Khi m i h c l p trình, b n th ng đ c giáo viên cho nh ngầ ộ ớ ọ ậ ạ ườ ượ ữ
bài t p nh p môn đ i lo i nh ậ ậ ạ ạ ư "Cho 3 c nh c a 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 trung tuy n", ... ạ ề ế V i m i bài t p này, vi c b n c nớ ỗ ậ ệ ạ ầ
làm là l y gi y bút ra tìm cách tính, sau khi đã xác đ nh các b c tính toán, b n chuy n nóấ ấ ị ướ ạ ể
thành ch ng trình. N u có 10 bài, b n ph i làm l i vi c tính toán r i l p trình 10 l n. N uươ ế ạ ả ạ ệ ồ ậ ầ ế
có 100 bài, b n ph i làm 100 l n. Và tin bu n cho b n là s l ng bài toán thu c lo i này làạ ả ầ ồ ạ ố ượ ộ ạ
r t nhi u! B i vì m t tam giác có t t c ấ ề ở ộ ấ ả 22 y u t khác nhau!. Không l m i l n g p m t bàiế ố ẽ ỗ ầ ặ ộ
toán m i, b n đ u ph i l p trình l i? Li u có m t ch ng trình t ng quát có th t đ ng gi iớ ạ ề ả ậ ạ ệ ộ ươ ổ ể ự ộ ả
đ c ượ t t c ấ ả (vài ngàn!) nh ng bài toán tam giác thu c lo i này không? Câu tr l i là CÓ ! Vàữ ộ ạ ả ờ
ng c nhiên h n n a, ch ng trình này l i khá đ n gi n. Bài toán này s đ c 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. Đ xác đ nh m t tam giác hay đ xâyế ố ế ạ ủ ể ị ộ ể
d ng m t 1 tam giác ta c n có 3 y u t trong đó ph i có y u t c nh. Nh v y có kho ngự ộ ầ ế ố ả ế ố ạ ư ậ ả
C322 -1 (kho ng vài ngànả) cách đ xây d ng hay xác đ nh m t tam giác. Theo th ng kê, cóể ự ị ộ ố
kho ng 200 công th c liên quan đ n c nh và góc 1 tam giác. ả ứ ế ạ
Đ gi i bài toán này b ng công c m ng ng nghĩa, ta ph i s d ng kho ng 200 đ nh để ả ằ ụ ạ ữ ả ử ụ ả ỉ ể
ch a công th c và kho ng 22 đ nh đ ch a các y u t c a tam giác. M ng ng nghĩa cho bàiứ ứ ả ỉ ể ứ ế ố ủ ạ ữ
toán này có c u trúc nh sau : ấ ư
Đ nh c a đ th bao g m hai lo i : ỉ ủ ồ ị ồ ạ
• Đ nh ch a công th c (ký hi u b ng hình ch nh t) ỉ ứ ứ ệ ằ ữ ậ
• Đ nh ch a y u t c a 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 ứ(không có tr ng h p cung n i gi a hai đ nh hình tròn ho c cung n iườ ợ ố ữ ỉ ặ ố
gi a hai đ nh hình ch nh t). ữ ỉ ữ ậ
* L u ý : trong m t công th c liên h gi a n y u t c a 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. Ch ng h n nh trong côngị ủ ế ố ẽ ượ ị ủ ế ố ạ ẳ ạ ư
th c t ng 3 góc c a tam giác b ng 180ứ ổ ủ ằ 0 thì khi bi t đ c hai góc, ta s tính đ c góc còn l i. ế ượ ẽ ượ ạ
C ch suy di n th c hi n theo thu t toán "loang" đ n gi n sau : ơ ế ễ ự ệ ậ ơ ả
Gi s ta có m ng ng nghĩa đ gi i bài toán tam giác nh hình sau ả ử ạ ữ ể ả ư
Ví d : ụ"Cho hai góc α﹐ β 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 :ớ ạ ữ ướ ủ ậ ư
B t đ u : đ nh ắ ầ ỉ α﹐ β﹐ a c a đ th đ c kích ho t. ủ ồ ị ượ ạ
Công th c (1) đ c kích ho t (vì ứ ượ ạ α﹐ β﹐ a đ c kích ho t). T công th c (1) tính đ c c nh b.ượ ạ ừ ứ ượ ạ
Đ nh b đ c kích ho t. ỉ ượ ạ
Công th c (4) đ c kích ho t (vì ứ ượ ạ α﹐ β). T công th c (4) tính đ c góc δ ừ ứ ượ
Công th c (2) đ c kích ho t (vì 3 đ nh ứ ượ ạ ỉ β﹐ δ ﹐ b đ c kích ho t). T công th c (2) tính đ cượ ạ ừ ứ ượ
c nh ạc. Đ nh ỉc đ c kích ho t. ượ ạ
Công th c (3) đ c kích ho t (vì 3 đ nh a, b, c đ c kích ho t) . T công th c (3) tính đ cứ ượ ạ ỉ ượ ạ ừ ứ ượ
di n tích ệS. Đ nh S đ c kích ho t. ỉ ượ ạ
Công th c (5) đ c kích ho t (vì 2 đ nh S, c đ c kích ho t). T công th c (5) tính đ c hC.ứ ượ ạ ỉ ượ ạ ừ ứ ượ
Đ nh hC đ c kích ho t. ỉ ượ ạ
Giá tr hC đã đ c tính. Thu t toán k t thúc. ị ượ ậ ế
V m t ch ng trình, ta có th cài đ t m ng ng nghĩa gi i bài toán tam giác b ng m t m ngề ặ ươ ể ặ ạ ữ ả ằ ộ ả
hai chi u A trong đó : ề
C t ộ: ng v i công th c. M i c t ng v i m t công th c tam giác khác nhau (đ nh hình chứ ớ ứ ỗ ộ ứ ớ ộ ứ ỉ ữ
nh t). ậ
Dòng : ng v i y u t tam giác. M i dòng ng v i m t y u t tam giác khác nhau (đ nh hìnhứ ớ ế ố ỗ ứ ớ ộ ế ố ỉ
tròn).
Ph n t A[i, j] = ầ ử -1 nghĩa là trong công th c ng v i c t ứ ứ ớ ộ j có y u t tam giác ng v i c t ế ố ứ ớ ộ i.
Ng c l i A[i,j] = ượ ạ 0.
Đ th c hi n thao tác "kích ho t" m t đ nh hình tròn, ta đ t giá tr c a toàn dòng ng v i y uể ự ệ ạ ộ ỉ ặ ị ủ ứ ớ ế
t tam giác b ng 1. ố ằ
Đ ki m tra xem m t công th c đã có đ n-1 y u t hay ch a (nghĩa là ki m tra đi u ki nể ể ộ ứ ủ ế ố ư ể ề ệ
"đ 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ạ"), ta ch vi c l y ỉ ệ ấ hi uệ gi a ữt ngổ s ô có giá tr b ng 1 và ố ị ằ t ng ổs ô có giá tr ố ị -1 trên c tộ
ng v i công th c c n ki m tra. N u k t qu b ng ứ ớ ứ ầ ể ế ế ả ằ n, thì công th c đã có đ n-1 y u t . ứ ủ ế ố
Tr l i m ng ng nghĩa đã cho. Quá trình thi hành kích ho t đ c di n ra nh sau : ở ạ ạ ữ ạ ượ ễ ư
M ng bi u di n m ng ng nghĩa ban đ u ả ể ễ ạ ữ ầ
Kh i đ u : ở ầ đ nh ỉα﹐ β, a c a đ th đ c kích ho t. ủ ồ ị ượ ạ