ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
o0o
BÁO CÁO TIỂU LUẬN
CƠ SỞ TRI THỨC
ĐỀ TÀI: HỆ LUẬT DẪN VÀ FUZZY LOGIC
Bộ Môn : CƠ SỞ TRI THỨC
Giảng viên : GS-TSKH HOÀNG VĂN KIẾM
Học viên thực hiện : NGUYỄN NGỌC TÚ
Mã Số Học Viên : CH1101053
Lớp : CH CNTTQM - 06
TP. Hồ Chí Minh, tháng 05 năm 2012
Lời nói đầu
rong sự phát triển không ngừng của xã hội ngày nay, đời sống con người ngày càng
được nâng cao hơn và nhu cầu cũng phát sinh nhiều hơn. Để đáp ứng được tất cả
các nhu cầu của con người, nhiều ngành nghề kinh tế và kĩ thuật đa dạng đã ra đời
phục vụ cho nhiều yêu cầu khác nhau. Và trong đó không thể không kể đến sự đóng góp
đáng kể của ngành Công Nghệ Thông Tin, nó luôn giữ một vị trí quan trọng trong xã hội
cũng như trong các ngành, nghề của cuộc sống. Hiện nay, Công Nghệ Thông Tin đang
được chú trọng đầu tư, phát triển ở mỗi quốc gia trên thế giới. Vì Công Nghệ Thông Tin
đang là một ngành mũi nhọn nhằm thúc đẩy sự phát triển chung cho nhiều ngành và kĩ
thuật tiên tiến cho mỗi nước. Công Nghệ Thông Tin đang cần một lượng lớn nhân lực phục
vụ cho sự phát triển chung của xã hội.
Các hệ thống thông minh ngày càng được ứng dụng trong nhiều lĩnh vực. Việc hoàn thiện
các chức năng của máy tính để ngày càng thực hiện tốt hơn những nhiệm vụ cho con người
ngày càng được quan tâm. Việc hoàn thiện máy tính ngày càng thông minh hơn và có khả
năng xử lý các công việc phức tạp đang trở thành vấn đề thiết yếu trong ngành công nghệ
thông tin. Đó cũng chính là lí do mà bộ môn cơ sở tri thức cung cấp những kiến thức cơ sở
ban đầu để có thể nạp tri thức cho máy tính và phát triển hoàn thiện hơn các chức năng,
chương trình của máy tính trong tương lai.
Lời cảm ơn
Tôi xin chân thành cảm ơn sự giúp đỡ nhiệt tình của thầy GS.TSKH HOÀNG KIẾM trong
suốt thời gian học cũng như quá trình làm đồ án môn học:”Cơ Sở Tri Thức”, và cũng xin
cảm ơn các bạn trong khoa đã có nhiều đóng góp để tôi hoàn thành đồ án nay. Tuy nhiên
do thời gian hạn hẹp, và sự hiểu biết của chúng em về môn học này chưa được sâu, cho
nên đề tài vẫn còn nhiều thiếu sót, nhiều luật chưa được hoàn chỉnh và phù hợp với thực tế
hiện nay. Vì vậy, tôi mong nhận được sự đóng góp của thầy và các bạn để chương trình
được hoàn thiện hơn.
Học viên thực hiện
Nguyễn Ngọc Tú
MỤC LỤC
A. HỆ SUY DIỄN 1
PHẦN I. CƠ SỞ LÍ THUYẾT CƠ BẢN 1
!"#$%
PHẦN II. GIỚI THIỆU CHƯƠNG TRÌNH CHUẨN ĐOÁN
LỖI MÁY TÍNH 3
PHẦN III. HỆ THỐNG CÀI ĐẶT 5
&'()*+,-./
01(2345/
601037859
:1;1<=>?@A7B
C-DEFG+,-H.I
#*)+6J)+ 010
KL)M01
#0<0/
#+ )GH-<)NO
!<.)P)!
B. FUZZY LOGIC········································································26
PHẦN I: GIỚI THIỆU VỀ FUZZY LOGIC··································26
PHẦN II:ỨNG DỤNG FUZZY LOGIC
TRONG BÀI TOÁN MÁY GIẶT···································28
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQR
:*2SQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQR
010QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQI
!T##UQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
/6$(QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
9#QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
TÀI LIỆU THAM KHẢO 35
= HỆ SUY DIỄN
PHẦN I:CƠ SỞ LÍ THUYẾT CƠ BẢN
Giới thiệu
-<)V'()*+,-.W-C2M0
$%XP)-<)Y#ZD)FXP)+
([<6F)$S)<H
Giới thiệu về suy diễn lùi
-<)U)Z'#*1$+)11F)P)
#-D-0\]^_4@T`>T$%
6^a6J)*'bZHP$cKd#eW)
2F)fcZ#e2 $]]^VLV8]
^#<W2Gg))G] $%C#$#<a1G
6h)U#<
U)1b)8<2 .#2)
U)WH-<)M(Z$[<iZ)
#GZVL(*j*C$-kZ$C$)
)1Z#.)P)2-<)Sl)$+)-e#
)< 1)$SXP)3E))$S2F)#j<-<)
M(W5F)]'b1
-<)*Z6j6^a6J))C1CG
EemUa6jF)a Z
<U-C#)XP))GE))$S2F)1G#
U)HK'#*$)H'2
<$+)-e
9
Các đặc điểm của suy diễn lùi.
n [<3)<5
n \j ]2.31-88<15
n \2 ]G )G 3<8]8<8885
n o010\-UVl)$
n o#ej(2J)l<)G 3p<-2
62p-<qq11<-81<85
n 0%-<)e2 '381q-5
n g.#<]G] L<$)e2 3<8]8r5
n 0%-<))GH
4 Ưu và nhược điểm của suy diễn lùi:
n Ưu điểm:
• s*-<)$H#1%16#<$
-)G -YV8)G WWD)2F)
• N01-)#<Ht<>Wj<-*<j'bm
U] C)V;Z <#G0l)$S
)
• ul)eW\F)t6 ZWm
e-U*1a+,-.H)l6#<)V;
• N$%)<-<)6#<)G] P$
#[<Z(<Z#ev
n Nhược điểm:
• >$%+6G#W$S) 18<w)Z
e.)-1G\),W#)2
• UW2^1P$%#6J))'l
0#083j2F))-j)5
O
PHẦN II:GIỚI THỆU VỀ CHƯƠNG TRÌNH CHUẨN ĐOÁN
LỖI MÁY TÍNH
>)#XP)Ht-,U1h6 ,2^1i+x-$S)iZg
1w)Z+]Z)eXP)-*)-t2^1i+$)
6 #1ay)$vH$$%1h6 )<j-\
E))$S<j*)<)M(>#*l)#2WU]0
Zea )$SXP)wjm6 ).g)zWZ2F)
1-v#EH2W(lVG-K#))'-
11.<)$SXP)
H\)MWWD)Ft] LV'()*#{[
<v<H|J)C1<)$S)*l2 .+6G
-<)e-vH\WWE)1$+)2^1P#EE
W]GK #Y#Wt] LV'()*U
)[<vF)]+ “Suy diễn lùi”}W6h)2
.Fi+,-.<Y 18<
~'ZeS)WjUWm\)j,V'()$+)-e+
)G[<vF)$S)s#-(])$S)WeC
<F)]*l6$2-g6G
R
N'V)vF)$S)H
ov:_AN
ovhM?n7As
ov7=s
! ov#e
/ ov6*)Y
9 ovh.)
O ovs:<-
R ov 6L
B ovU] •€
I ov]j)Y
ov+6G•<p
ov 6L)<j
ov-#e
! ov?-8
/ ‚-
CGv-UU]-( 1 1a.)+#1a
>W$,-*)[<<1a +Z$C
2^1P*a+
B
PHẦN III: HỆ THỐNG CÀI ĐẶT
Xây dựng một cơ sở tri thức
‚V'()*+,-.6<)YV'()x
ƒ01(2
ƒ010
Tập các sự kiện(Facts)
Bao gồm:
• =x u,*)$%
• =x sH<j*)$%
• =x _$%
• =!x uF)W?-8
• =/x Tb)1a
• =9x F)6<
• =Ox }j)Yj
• =Rx Tb)7=s
• =Bx F)6<M
• =IxTb)M
• =x„.)b)
• =xTb)#e
• =xob)1#e
• =!xKdh.))
• =/xW'ih.)
• =9xKd#e)
• =OxW#<H
• =Rx>W)•€
• =Bx>)Yb)
• =Ixs(78N835@s(^3I5
I
• =x•<pb)
• =xW )6H1:_AN
• =x:_ANb)
• =!xoU#e
• =/xsH6L‚-
• =9x-8<
• =OxTb)]j)Y
• =RxTb)s:<-
• =Bxs0 6L)<#
• =IxTb) 6L)<j3*Z6#1Hr5
• =xTb)-#e
• =x 6L)<j2F)<j*)
6 Tập các Luật(Rules)
:<)YI0+6Gx
• R1x> 2,*)$%T…<j*)6e$S)
• R2x> <j*)6e$S)#$%T…2F)b)
1a
• R3x> <j*)6e$S)#2F)$%T…b)
1a
• R4x> 2F)2,*)$%#2F)F)6<#W
):_ANT…b)7=s
• R5x> 2F)2,*)$%#F)6<MT…b)
M
• R6x> W#<H#2F)W'ih
.)<2F)Wdh.))T…h.)6Lb)
• R7x > W#<#d#e)#2,*)
$%#2F)U#eT…b)1#e
• R8x> W#<#W )6H1:_AN#2F)b)
1#eT…•<p6Lb)
• R9x> W#<#2F)W )61:_AN#
2F)b)1#eT…b)7=s
• R10x> (788#2F)2,*)$%T…b)
7=s
• R11x> dh.))T…h.)2F)6Lb)
• R12x> 2,*)$%#2F)b)1#e#
2F)U#eT…b)#e
• R13x> 2,*)$%#(788HT…H
6L‚-
• R14x> H<j*)6e$S)#(^T…
•€6LW)
• R15x> W#<H#U#e#2F)2,
*)$%T…•<p6Lb)
• R16x> 2F)2,*)$%#WF)6<#2F)W
)6H1:_ANT…:_AN6Lb)
• R17x> W#<H#d#e2F))
T…#eb)
• R18x> 2,*)$%#-8<T…p<pb)
• R19x> 2F)W#<HT…)Yb)
• R20x> <j*)6e$S)#6L-8<T…
H6L-
• R21x> <j*)6e$S)#6L-8<#W
F)6<MT…b)M
• R22x> 6L-8<#2F)6L-T…b)]j)Y
• R23x> W#2F)2,*)$%#]j
)Yb)T…b)s:<-
• R24x> W#]j)Yj#2F)U#
e#2F)WF)6<T…b)s:<-
• R25x> 2F)2,*)$%#]j)YjT…
b))Y
• R26x> 0 6L)<#T…2F)b)
s:<-
• R27x> 6L)<#2F)b)#2F)0
6L)<#T…b)s:<-
• R28xs2F)0 6L)<##WF)6<vT…
b)b) 6L)<#
• R29x> W )6H1:_AN#2F)U#e#2F)
b)1#eT…b)-#e
• R30x> 0 6L)<## 6L)<#2F)<j
*)T…$W?-8
-<)W0$%FG$x
ns*06<)Y(2$%#1ax
ƒG
ƒu 0
1a#$%U2 6J)\2WT…
n>†€x\2W6^a1a)G
nT…x\2W2 D1a)G #6^a1a2 0
n‚‡xo#<X=>?)l(2)G
nuTˆ>x<X>A)1L*(2
n=xU(2
n7xU0
Biểu diễn các phép toán AND/OR
LUẬT VẾ TRÁI (G ) VẾ PHẢI(u 0)
R1 A1 A2
R2 A2^A3 ~A5
R3 A2^(~A3) A5
R4 ~A1^~A6^A22 A8
R5 ~A1^A9 A10
R6 A17^~A15^~A14 A11
R7 A17^A16^~A24^A1 A13
R8 A17^A22^~A13 A21
R9 A17^~A22^~A13 A8
R10 A20^~A1 A8
R11 A14 ~A11
R12 A1^~A13^~A24 A12
R13 A1^A20 A25
R14 A2^~A20 A18
R15 ~A1^A17^A24 A21
R16 A6^~A1^ ~A22 A23
R17 A17^~A16 A12
R18 A1^A26 A21
R19 ~A17 A19
R20 A2^A26 A25
R21 A2^A26^A9 A10
R22 A26^~A25 A27
R23 ~A1^A17^~A7 A28
R24 A17^~A6^~A24^A7 A28
R25 ~A1^A7 A19
R26 A29 ~A28
R27 ~A29^~A30 A28
R28 A6^~A29 A30
R29 A22^~A13^~A24 A31
R30 A29^A32 A4
Kí hiệu:
~:NOT
^:AND
Cấu trúc dữ liệu mô tả Cơ sở tri thức.
:*D
:*0
!
sFG 0
‚e)DU0‰$%6
$j)x
‚HP<0R9x> W#<#2F)W )61:_AN#2F)b)
1#eT…b)7=s
A17^~A22^~A13 A8
TÊN NÚT VẾ TRÁI(gt) VẾ PHẢI(kl) THỨ TỰ BÍT
= I I I
= I I
= I I
=! I I
=/ I I !
=9 I I /
=O I I 9
=R I O
=B I I R
=I I I B
= I I I
= I I
= I I
=! I I
=/ I I !
=9 I I /
=O I 9
=R I I O
=B I I R
=I I I B
= I I I
= I I
= I I
=! I I
=/ I I !
=9 I I /
=O I I 9
=R I I O
=B I I R
=I I I B
= I I I
/
= I I
Š= I I
Š= I I
Š= I I !
Š=! I I /
Š=/ I I 9
Š=9 I I O
Š=O I I R
Š=R I I B
Š=B I I !I
Š=I I I !
Š= I I !
Š= I I !
Š= I !!
Š=! I I !/
Š=/ I I !9
Š=9 I I !O
Š=O I I !R
Š=R I I !B
Š=B I I /I
Š=I I I /
Š= I I /
Š= I /
Š= I I /!
Š=! I I //
Š=/ I I /9
Š=9 I I /O
Š=O I I /R
Š=R I I /B
Š=B I I 9I
Š=I I I 9
Š= I I 9
Š= I I 9
Cài đặt động cơ suy diễn bằng cơ chế suy diễn lùi:
2.1 Định nghĩa tập suy diễn lùi
9
&;0R17x> W#<H#d#e2F))
T…#eb)
K 2 0#b)#ee1G.)H
W#d#e2F))22,*)
}-e.),'#*v-U010
*)(l<j)E)$S#U)
ƒKaU.)W#<H2F)f
ƒKd#eW)2F)f
ƒ> )G -UD)e2 0d#e6Lb)
ƒ>)$%j HCW*-<))G e2 02F)
b)#e#TU)‰e*0102
+ 0#+ 6^a\*2 0#e
*v)G .)<2 0#>)M#
1GVC1\012 0o2UD,v $x
VẾ TRÁI‹Œ=Z=Z=Z=9Z=OZ=BZ=Z=!Z=/Z=9Z=OZ
=BZ=IZ=Z=!Z=/Z=9Z=BZ=IZ=•
VẾ PHẢI‹Œ=Z=!Z=/Z=RZ=IZ=Z=Z=Z=OZ=RZ=BZ
=Z=Z=/Z=OZ=RZ=IZ=•
Thuật toán phân loại nút:
O
CWE)DmVC, -#E)DmVC
-U 1G#WGE)DVC-UG ?(#<
WV'()11'<jD$x
Ki01D#<G)WC-D*)
Ki010#<G)WC-D*)
_1xUD
A1xo<jD
‚oAŽ_>•‹ŒZZ•‹Œ>D2 0ZD-))Z>D0
)•
?]01D
!?]010
-$S)%1x
ƒ>Dm,‚†•T•_xoAŽ_>•‹‘@@01D2 0
ƒ>Dm,‚†7’_xoAŽ_>•‹‘@@01D0)
ƒ>DW,‚†7’_#‚†•T•_xoAŽ_>•‹‘@@01D
-))
T 010
T 01D
>$0‰1'<j#01D23o<jZZ5x
ƒ01D2 0‹‚†•T•_“‚†7’_‹Œ=!Z=/Z=RZ=IZ=Z
=Z=RZ=BZ=Z=Z=OZ=RZ=•‹3DmW-<)‚†
•T•_5
ƒ01D-))‹‚†7’_
∩
‚†•T•_‹Œ=Z=Z=/Z=I•
‹DWG-<)01‚†7’_#‚†•T•_
ƒ01D0)‹‚†7’_“‚†•T•_‹Œ=Z=Z=9Z=OZ=BZ
=!Z=/Z=9Z=OZ=IZ=Z=!Z=9Z=BZ=•‹ŒDmW
-<)‚†7’_•
R
Kết quả của phân loại nút áp dụng vào cơ sở tri thức trên sẽ có kết quả
như saux
UD U(2 o<jDl
= u,*)$%
= sH<j*)$%
= _$%
=! uF)W?-8
=/ Tb)1a
=9 F)6<
=O W'
=R Tb)7=s
=B F)6<M
=I Tb)M
= „.)b)
= Tb)#e
= ob)1#e
=! Kdh.))
=/ W'ih.)
=9 Kd#e)
=O W#<H
=R >W)•€
=B >)Yb)
=I s(78N835@s(^3I5
= •<pb)
= W )6H1:_AN
= :_ANb)
=! oU#e
=/ sH6L‚-
=9 -8<
=O Tb)]j)Y
=R Tb)s:<-
=B s0 6L)<#
=I Tb) 6L)<j3*Z6#
1H5
= Tb)-#e
= 6L)<j2F)<j*)
B
ƒ01D2 0‹Œ=!Z=/Z=RZ=IZ=Z=Z=RZ=Z=Z
=OZ=RZ=Z=B•‹oAŽ_
2.2 Cài đặt thuật toán suy luận lùi:
-Tl)‰$%#$x
uH6L*(l#<W#D)lS[
<#V8H6L(l)ef$+)-e‰$-'1b)
C #2-uWVC2 j-<)012 0e
2 D1b)C#$-2 0>)$%jl)‰2F))G
H$%
nThuật toán suy diễn lùi:
.Input:01D2 0
.Output:s*2 0)<2F))G1$%(l#
Ki01D#<G)C-D*)
!Ki010#<G)C-D*)
/’1P)0<1'<jD
u 0J*1aX-<)01xŒ=!Z=/Z=RZ=IZ=Z=Z
=RZ=BZ=Z=Z=OZ=RZ=Z{uF))GH$%|•
W2 06J)I‘
6.Duyệt qua tập nút kết luận
ƒoC-*D2 0
e)-LDI
ƒ> )-LD2 0)V;6J)
&C-2 0D)
I
C.v
W2 06J)‘
T 01D2 0
> W2 06J)I
{&C-#2F))GH$%|
N'#Pe)-LDI‘
7. Duyệt qua tập luật
-L06J)‘
ƒ> D)V;#2 0*0ex
ƒoC- -0W@@)G
ƒo1j2 D-<) -
0
ƒ> *DtW)-Le
)-L0‹)-L0=>?)-LD
ƒ>)$%jx
ƒ-$S)%1o<jD‹@@>D-))
ƒe)-LDI
ƒ-$S)%1<jD‹@@D0)
”Ua01E<D#
)-L0‹)-L0=>?)-LD
D-<) -0
ƒ-LD)V;‹)-L0‘
NHẬN XÉT:
ƒ}-eH#]-ee)-LD2 0
u*D2 0W)-LD)e01.]-eC.
2 ]G#F)> 2F)WD2 0#<W)-LD)e]-e
0y)C.2 ]G#2F)#F)
ƒuM01P)<#w)12 %1)i#K]
#e)-LDI
2.3 Cài đặt cơ chế giải thích trong Suy diễn lùi.
Định nghĩa:
n}-ey)#]-el<j)E)$S)#
TU)KW#2U)a01E<(
2Ua~')$SWW]-E)'b
)C$j<f•T”)C1l#T<2e-
2 0#VC2 0<)$S)Ziy)W)C
$# #<fTA•#W2 ]G$0f
n‚-GS'b•T”#TA•H#+ )GH
U)
n+ )GHa1G$%#<)<)+
Cơ chế giải thích câu hỏi WHY?
V8*HPx
• R12:> 2,*)$%#2F)b)1#e#
2F)U#eT…b)#e
B1:
-giả thiết của R2:
+2,*)$%#<jD‹‘
+2F)b)1#e#<jDl‹‘
+uF)U#e#<jD‹‘
-Kết luận của R2:
ƒob)#e#<jDl
B2:
2.1. Vì 2F)b)1#e#<jDl‹U
-e 1#1W#2 00R7.
• R7x > W#<#d#e)#2,*)
$%#2F)U#eT…b)1#e
2.1.1-giả thiết:
ƒW#<#<jD‹
ƒKd#e)#<jD‹
ƒu,*)$%#<jDl‹
ƒuF)U#e#<jDl‹
2.1.2 ‚e<jD)G Wj)#DlUUa
01E
• W#<2F)f3”8@<5
• Kd#eW)2F)f3”8@<5
• u,*)$%2F)f3”8@<5
• uF)Ud#e1G2F)f3”8@<5
> -GS”8 !'e]G#b)1#e)'-L
2F)b)1#e)'-LI‚e b)#e
)'-L2F)
Tl)F)6<uF)b)#e
>)$%j-i)!'-GS<0R7 W*'-GS#><e
b)1#e)'-L#I2F)b)1#e,0
R12‰#'-L6<s#e6Lb)
-<)]-eU)Ua01Ee)$S)W
',j<f3•T”5DWU)a1GVC-
v0)GH•<j<a1G01E
K($%#e210-<)]-e
-Ua1G$0W-<)#e2M02#H
%1C-<)-$S)%1#D))2x2#2
nN2x.l.(D2 –<<V2W*01
nN2x<122*'b•T”$%-GS[6L<
'b2 1
Thủ tục Giải thích WHY
o1 22-v)
•<13N2Z6 5
>lv0WD2 0)#6
T 2
&Cv0-GS
N2)GHV<)
N2‹N2‘
Thuật toán suy diễn lùi cho câu hỏi WHY 0
1.Input:01D2 0
2.Output:s*2 0D)<2F))G1$%(l
#
3Ki01D#<G)C-D*)
4.Ki010#<G)C-D*)
5’1P)0<1'<jD
u 0J*1aX-<)01xŒ=!Z=/Z=RZ=IZ
=Z=Z=RZ=BZ=Z=Z=OZ=RZ=Z{uF))G
H$%|•
W2 06J)I‘
!
6.Duyệt qua tập nút kết luận
ƒoC-*D2 0
e)-LDI
ƒ> )-LD2 0)V;6J)
&C-2 0D)
C.v
W2 06J)‘
T 01D2 0
> W2 06J)I
{&C-#2F))GH$%|
N'#Pe)-LDI‘
7. Duyệt qua tập luật
-L06J)‘
ƒ> D)V;#2 0*0ex
•32Zl.(>D2 0)V;5
•32Zl.(D2 0)V;5
ƒoC- -0W@@)G
Lặp đến khi hết các nút trong vế trái của Luật
ƒ> *DtW)-Le
-L0‹)-L0=>?)-LD
ƒ>)$%jx
ƒ-$S)%1<jD‹@@>D-))
e)-LDI
ƒ-$S)%1<jD‹@@>D0)
”Ua01E<D#
-L0‹)-L0=>?)-LD
'b•T”fVC
iP)GH•T”I
/