Giáo trình Logic Toán (Phần 2) - Trịnh Huy Hoàng

Nội dung text: Giáo trình Logic Toán (Phần 2) - Trịnh Huy Hoàng

1. GiáotrìnhLogicToán BÀI6:GÔGỮPROLOG 1.TưduylậptrìnhvàđịnhnghĩavấnđềtrênProlog ĐốivớiProlog,mộtchươngtrìnhcóthểhiểunhưlàcáctrithứcđượcngườilậptrình cungcấpchohệthốngProlog.N hờvàocáckiếnthứcđượccungcấp,hệthốngcóthểtrảlời đượccáccâuhỏiđượcđặtra,vàcâutrảlờicóthểđạtđượcnhờcơchếsuyluậncủahệthống dựatrênnhữngkiếnthứcđượccungcấpbanđầu. ĐơnvịkiếnthứcmàngườilậptrìnhcungcấpchoProloggọilàcácvịtừ(predicate). Cácvịtừdùngđểbiểudiễncáckháiniệmmàngườilậptrìnhmuốnhệthốngdùngđểsuyluận đểđạtđượccáckiếnthứckhácmàmìnhmongmuốn.Vềmặtkỹthuật,cácpredicatecóthể đượcxemnhưcáchàm,nhưnggiátrịtrảvềchỉcóthểlàcácgiátrịluậnlýđúnghoặcsai.Và giátrịtrảvềnàychỉcóthểsửdụngđểsuyluận,Prologkhôngcócơthếchồngchấthàmnhư cácngônngữthủtục khác,chínhđiềunàysẽlàmnhữngngườiquenvớiviệclậptrìnhthủtục gặpkhókhănkhibướcđầulậptrìnhvớiProlog.CôngviệcđầutiênkhilậptrìnhtrênProloglà địnhnghĩacácvịtừcáckháiniệmmàmìnhcầncungcấpchochươngtrình. Xétcácvídụsau: VD1: Dữkiệnbanđầu: Mọingườiđềuphảichết.Socrateslàngười. Yêucầu: Chúngtamuốnhệthốngphảicókhảnăngsuyluậnvàtrảlờiđượccácvấnđềliênquan đếncáckháiniệmtrên:ailàngười,aikhônglàngười,aiphảichết,aikhôngphảichết.Ởđây chúngtacómộtsựsuyluậnthôngminhđặctrưngchosứcmạnhcủaProlog:hệthốngsẽtự độngsuyluậnrằngSocratesphảichết(điềukhôngđượccungcấpbanđầu). ĐểbiểudiễncácvấnđềtrênbằngngônngữProlog,chúngtacầnphảixácđịnhcần phải biểudiễnnhữngkháiniệmgì.Trongvấnđềnàychúngtacóhaikháiniệmcầnbiểudiễn: mộtthựcthểnàođócó thểlàngười(hoặckhông),vàmộtthựcthểnàođócóthểchết. N hưvậychúngtabiểudiễnvấnđềđầutiênbằngngônngữProlognhưsau: nguoi(symbol) SymbollàmộtkiểudữliệuđặcbiệtcủaProlog,dùngđểbiểudiễnchomộtthựcthể,mộtkhái niệmtổngquát.Chúngtasẽtrởlạivấnđềnàysau.N hưvậychúngtavừađịnhnghĩamộtkhái niệm:mộtsymbolnàođócóthểlàngười,mộtsymbolnàokhácthìkhông. Hiểunhưmộtsựđịnhnghĩahàm,chúngtacóthểxemnhưđịnhnghĩamộthàmmangtên nguoi,hàmnàycóthôngsốmộtbiếnthuộckiểudữliệusymbol,vàkếtquảcủahàmnày, khôngcầnphảikhaibáothuộcvềkiểugì,vìchỉcóthểthuộckiểuboolean,chỉcóthểđúng hoặcsai.N hiệmvụcủaProloglàphảitrảlờiđượcvớigiátrịsymbolnhậpvào,thìhàmnày Gv:TrịnhHuyHoàng Trang58
2. GiáotrìnhLogicToán chorakếtquảđúnghoặcsai,tứcsymbolấycóphảilàngườihaykhông.Prologchỉcóthểlàm đượcđiềunàynếunhưnếunhưchúngtacungcấpchohệthốngmộtcơchếsuyluậnđúng đắn,tứclàgiảithíchđượcchoProloghiểu nhưthếnàolàngười? Tươngtựnhưvậy,chúngtađịnhnghĩavềvấnđềmộtthựcthểnàođóphảichếtbằngvịtừsau chet(symbol) N hưvậyvớibàitoánđãnêu,chúngtasẽđặtrahaivịtừ nguoi(symbol) chet(symbol) VD2: Yêucầu:tínhgiátrịgiaithừacủamộtsốnguyênbấtkỳ. Bàitoántrênkhôngchobiếtdữkiệnbanđầu.Chúngtaphảicungcấpcácdữkiệnbanđầu,để Prologcóthểdựavàođóđểsuyluận,đểtừđóhệthốngcóthểgiảiquyếtđượcyêucầucủa chúngta.Việccungcấpdữkiệnbanđầuchohệthốnglàrấtquantrọngquyếtđịnhvấnđềgiải quyếtyêucầucủachúngta.Mộttrongnhữngcáchgiảiquyếtcóthểđượclựachọnlàchúngta sẽchohệthốngbiếtgiátrịgiaithừacủatoànbộsốnguyên:giaithừacủa0là1,giaithừacủa 1là1,giaithừacủa2là2,giaithừacủa3là6,giaithừacủa4là24 Dễdàngnhậnthấy rằngcáchnàylàkhôngkhảthi,vàtrongthựctế, conngườicũngkhôngtiếpthutrithứctheo cáchnày . Chúngtacóthểcungcấpdữkiệnchohệthốngtheocáchkhác:giaithừacủamộtsốlàtích cácsốtừ1đếnsốđó.N hưvậyvớicáchgiảiquyếtnày,chúngtacóhaikháiniệmcầnphải cungcấp:giaithừacủamộtsốlàgì,vàtíchcủacácsốnguyêntínhtừ1đếnmộtsốlàgì? Cáchđặtvấnđềnàycóthểgiảiquyếtđượcbàitoán,tuynhiênchúngtacóthểđặtvấnđềtheo mộtcáchkhácđơngiản,vàhợpvớitinhthầncủaProloghơn:giaithừacủa0là1,vàgiaithừa củamộtsốlớnhơn0làgiaithừacủasốliềntrướcnónhânvớichínhnó. Vớicáchđặtvấnđềnày,chúngtachỉcómộtkháiniệmphảibiểudiễn:giaithừacủamộtsốlà gì?(thậtrachúngtacònmộtsốkháiniệmphảiđưara:mộtsốđứngtrướcmộtsốlàgì,nhân haisốnghĩalàgì,tuynhiênPrologđãcungcấpcáctoántửđểgiảiquyếtvấnđềnày.Hiểu theomộtnghĩanàođó,cácvấnđềtrênlàcáctiênđề,khôngcầnphảigiảithíchvớihệthống.) N ếuquenvớingônngữlậptrìnhthủtục,chúngtacókhuynhhướngkhaibáovịtừdiễntả kháiniệmgiaithừanhưsau: giaithua(integer) ỞđâycáchđặtvấnđềnhưvậylàkhôngthíchhợpvớingônngữProlog,vì.Mộtvịtừchỉcó thểtrảlờilàđúnghoặcsai,trongkhichúngtađangmongmuốnkếtquảtrảvềtheocáchkhai báonàymộtsố.N gônngữPrologkhôngcósựchồngchấthàm,nghĩalàkếtquảcủahàm(vị từ)khôngthểdùngnhưmộtthôngsốchomộtvịtừkhác,trongkhichúngtađangđịnhdùng kếtquảcủahàmnàyđểtínhtiếpgiátrịchomộthàmkhác.(Chúngtađịnhdùnghàmnàyđể tínhgiaithừacủan1,rồinhântiếpchonđểrakếtquảcuốicùng). Gv:TrịnhHuyHoàng Trang59
3. GiáotrìnhLogicToán Vịtừthíchhợpsẽđượckhaibáonhưsau: giaithua(integer,integer) Điềunày,hiểutheongônngữthủtục,nghĩalàchúngtakhaibáomộthàmcóthôngsốlàhai sốnguyên,vàkếtquảtrảvềsẽlàđúnghoặcsai.Điềuchúngtamuốndiễntảcónghĩalà:giai thừacủamộtsốnguyên(integer)sẽlàmộtsốnguyênkhác. N ếuchúngtagiảithíchđượcchoProloghiểugiaithừacủamộtsốnguyênsẽđượctínhnhư thếnào,hệthốngsẽcókhảnăngtrảlờichocảcâuhỏithuận(giaithừacủamộtsốnguyênlà gì),câuhỏinghịch(sốnguyênnàocógiaithừabằngsốnguyênnày),vànghivấn(giaithừa củamộtsốnguyênXcóphảilàsốnguyênYhaykhông). Tuynhiênmụcđíchcủachúngtachỉcungcấpcácdữkiệnđểhệthốngcóthểtrảlờicâuhỏi thuận(vàcóthểtrảlờithêmcâuhỏinghivấn)màthôi. Tómtắt:
   LậptrìnhtrênProloglàcungcấpchohệthốngcáckháiniệmvàdiễngiảicáckhái niệmđó.
   Cáckháiniệmđượccungcấpquacácvịtừ.
   Cácvịtừcóthểxemnhưcáchàmnhưchỉtrảvềgiátrịđúnghoặcsai.
   Việchệthốngcóthểtrảlờiđượcnhữngcâuhỏinàoliênquanđếnkháiniệmđãcung cấpphụthuộcvàoviệcchúngtadiễngiảicáckháiniệmtrênchohệthống 2.Cácclause,cáchgiảithíchcácvấnđềtrênProlog Saukhiđãcungcấpchohệthốngcáckháiniệmcầnthiết,chúngtacầnphảigiảithích cáckháiniệmmìnhđãcungcấp,Prologsẽdùngcáclờigiảithíchnàyđểthựchiệnviệcsuy luậnvàtrảlờicâuhỏicủachúngta.Cáclờigiảithíchnàyđượcgọilàcácmệnhđề(clauses). Cóhaidạngmệnhđề:sựkiện(fact),vàluật(rule). Cácsựkiệnlànhữngđiềumàchúngtacôngnhậnlàđúng.Luậtlànhữngquytắcmàchúngta xácđịnhđiềukiệnđúngchochúng. VD3: hãyviếtphầnclausechovịtừnguoi đãđịnhnghĩatrongVD1 Dữkiệnbanđầuchỉcungcấpchochúngtamộtvấnđề liên quan đến người: Socrates là người.Theonhưcáchtưduytrongkhônggiancủabàitoán,chỉcómộtconngườiduynhất: Socrates.Khôngaikháclàngười.N hưvậychúngtasẽviếtphầnclausechovịtừnàynhưsau: nguoi(socrates). Chúngtavừaviếtmộtsựkiện:socrateslàngườilàđiềuchắcchắnđúng.Bấtkỳsymbolnào cótênlàsocrateslàngườilàchắcchắnđúng,khôngcầnphảicómộtđiềukiệnràngbuộcnào kèmtheo. Lưuý: i/Cóhaicáchviếtdạnghằng(literal)chosymboltrênProlog: - Mộtdanhhiệumởđầubằngkýtựthường(socrates,sOCRATES ) Gv:TrịnhHuyHoàng Trang60
4. GiáotrìnhLogicToán - Một chuỗi ký hiệu đặt trong cặp ký hiệu "," ("socrates","SOCRATES"," sOCRATES","Socrates" ) ii/mộtmệnhđềluônkếtthúcbằngkýtự'.' VD4: hãyviếtphầnclausechovịtừchet trongVD1. Dữkiệnbanđầuchỉcungcấpchochúngtamộtsựkiệnliênquanđếnvấnđềnày:symbolsẽ phảichếtnếu(vàchỉnếu)đólàngười.Điềunàysẽxácđịnhmộtquytắc:symbolsẽchỉphải chết,tứcvịtừsẽtrảvềkếtquảtrue,nếusymbolđólàngười.Vấnđềsymbolnàolàngườivà symbolnàokhônglàngườichúngtađãđưarakháiniệmvàgiảithíchchoPrologtrongcácví dụ1và3. N hưvậyphầnmệnhđềsẽđượcviếtnhưsau: chet(X):nguoi(X). Mệnhđềdạngrulesẽbaogồmhaiphần,nằmởhaibêncặpkýhiệu":".Phầnbêntráicho biếtvịtừđangđượcđềcậpvàcácthôngsốtươngứng.Phầnbênphải,xácđịnhđiềukiệntrả lờiđúngcholuậttrên,baogồmcáclờigọicácvịtừkhác,đượcngăncáchbởikýhiệu',',gọi làcácmệnhđềcon(subclause).Trongvídụtrên,chỉcómộtsubclause. Mộtluậtchỉtrảlời đúngnếutấtcảcácsubclausebênvếphảiđềutrả lờiđúng . Trongvídụtrên,chúngtacómộtbiếnX. Tấtcảcácthôngsốmởđầubằngkýtựhoađều đượcProloghiểulàbiến.Biếnnàylàthôngsốcủavịtừchet. Dođãkhaibáoởphầnvịtừ,X sẽđượchiểulàmộtbiếnthuộckiểusymbol.Kếtquảsẽtrảvềđúngnếutấtcảsubclausebên vếphảiđềutrảlờilàđúng.Trongtrườnghợpnày,chỉcómộtsubclausexácđịnhxemXcó phảilàngườikhông.N hưvậychúngtađãbiểudiễnđượckháiniệmmộtsymbolsẽphảichết nếusymbolđólàngười,tứclàtấtcảnhữngdữkiệnbanđầuđượccungcấp. VD5: Hãyviếtphầnclausechovịtừgiaithua ởVD2. Từcácdữkiệnđượccungcấp(dochúngtatựcungcấpchomìnhđểgiảibàitoán),chúngta thấycómộtsựkiệnchắcchắnđúng:giaithừacủa0là1,vàcómộtluậtsuydiễn:giaithừa củanlà(n1)!*n. Chúngtasẽviếtphầnmệnhđềchovịtừnàynhưsau: giaithua(0,1). giaithua(X,Y):X1=X1,giaithua(X1,Y1),Y=Y1*X. Trướckhihiểunhữngđiềuđượcmôtảtrongcácvídụtrên,chúngtasẽcómộtsốnhậnxét nhưsau: - Trướctiên,chúngtathấyvịtừ giaithua đượcbiểudiễnbằnghaimệnhđề:mộtsự kiệnvàmộtluật.Khiviếtnhiềumệnhđềchomộtvịtừ, cácmệnhđềphảiđượcviết liêntiếpnhau(khôngđượcxenmệnhđềcủavịtừkhácvào). Gv:TrịnhHuyHoàng Trang61
5. GiáotrìnhLogicToán - Chúngtasẽhiểuhaimệnhđềconđầutiên X1=X1,giaithua(X1,Y1) biểudiễn cho công việc tính giai thừa của X1. Tuy nhiên chúng ta không được viết giaithua(X1,Y1).Thôngsốcủacácmệnhđềconphảilàbiến,khôngđượcphéplà biểuthức. - Chúngtathấysựxuấthiệncủakýhiệu'='vàsẽhiểunhưmệnhđềconX1=X1là phépgán. TrênPrologkhôngcóphépgán. Kýhiệu'='biểudiễnchomộtphéptoán đặcbiệtcủaProlog,phéphợpnhất(unification),vàcũngnhưcácmệnhđềkhác, phéphợpnhấtnàysẽtrảvềkếtquảđúnghoặcsai,biểudiễnchokếtquảcôngviệc hợpnhấtthànhcônghaykhông.Xemthêmvềphéphợpnhấttrongcácphầnsau. - Phầnvịtừtrênbiểudiễnchoviệcsửdụngkỹthuậtlậptrìnhđệquy,sẽlàsứcmạnh lậptrìnhchủyếucủaProlog.XemthêmvềphầnlậptrìnhđệquytrênPrologtrong cácphầnsau. Tómtắt
   Cáckháiniệmđượcmôtảquacácvịtừsẽđượcgiảithíchbằngcácmệnhđề.
   Cóhailoạimệnhđề:sựkiệnvàluật.
   Thôngsốđượctruyềntronglờigọicácmệnhđềconphảilàbiến.
   CáckỹthuậtchủyếuđểlậptrìnhtrênProloglàhợpnhấtvàđệquy. 3.Thựcthichươngtrình.Đặtcâuhỏivànhậncâutrảlời Đếnđâychúngtađãcóthểthựcthicácchươngtrìnhtrên.TrêncửasổProlog,nhập nộidungđoạnchươngtrìnhvàovùngcửasổsoạnthảo.(Chúngtacóthểluônchuyểnvềvùng cửasổnàybằngphímnóngAlt+E). VD6: ViếtchươngtrìnhhoànchỉnhchoVD1. N ộidungchươngtrìnhnhậphoànchỉnhchoVD1nhưsau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). chet(X):nguoi(X). N hưvậychúngtathấytrongmộtchươngtrìnhProlog,cácphầnkhaibáocácvịtừvàhiện thực các mệnh đề được bắt đầu bằng các từ khoá predicates và clauses . Lưu ý: Phần predicatesphảiđượcviếttrướcphầndànhchoclauses.ChúngtasửdụngTurboPrologđểthử cácvídụtrên: Giaodiệnchươngtrìnhsẽnhưsau: Gv:TrịnhHuyHoàng Trang62
6. GiáotrìnhLogicToán Đểthựcthichươngtrình,ngườisửdụngnhậpyêucầu(câuhỏi)củamìnhchohệ thống.Yêucầunàygọilàgoal.Cóhailoạigoal:goalnộivàgoalngoại.Phầnnàychỉtrìnhbày vềgoalngoại.Đểnhậpgoalngoại,saukhiđãhoàntấtviệcsoạnthảochươngtrình,chúngta dùngphímtắtAlt+Rđểchuyểnsangvùnggiaotiếpcủachươngtrình.Câuhỏichúngtađặtra chohệthốngphảichỉdựavàocáctrithứcmàchúngtađãcungcấpchohệthống.Chúngtađã cungcấpchohệthốngcáckháiniệm nguoi và chet ,nhưvậychúngtachỉcóthểđặtcáccâu hỏiliênquanđếnhaikháiniệmnày.N gaysaudấunhắc Goal: tạivùngcửasổnày,chúngta cóthểnhậpcâuhỏinhưsau: nguoi("Socrates") Dựatrêntinhthầncủacủakháiniệm,câuphátbiểucủachúngtacónghĩalà"Socrateslà người",vàvìđâylàcâuphátbiểutrongvùnggoal,nênhệthốngsẽhiểurằngchúngtamuốn đặtmộtcâuhỏinghivấn"Socrateslàngườiphảikhông?" SaukhiấnEnter,chúngtasẽthấyhệthốngcóngaycâutrảlời:Yes. Thaybằngmộttênkhác,vídụ: nguoi("Xeda") HệthốngsẽtrảlờiN o. Chúngtathấycáccâutrảlờicủahệthốngdựatrênkiếnthứcmàchúngtađãcungcấp.Dựa vàonhữnggìmàchúngtađãcungcấp,hệthốngchỉbiếtcómộtngườilàSocrates,tấtcả nhữngsymbolkhácđềukhôngphảilàngười. Tuynhiên,vớicơchếsuyluậnmàchúngtacungcấp,hệthốngcóthểsuyluậnranhữngđiều chưađượccungcấpsẳn.ĐâychínhlàđiểmtạonênsứcmạnhlậptrìnhcủaProlog. Gv:TrịnhHuyHoàng Trang63
7. GiáotrìnhLogicToán N hậpvàogoalnhưsau: chet("Socrates") Câutrảlờilà:Yes. Vớimộttênngườikhác: chet("Xeda") Câutrảlờilà:N o. Hệthốngđãtựđộngsuyluậntheonguyênlýmàchúngtamuốnnóphải"học":ailàngườithì ngườiđóphảichết.N goàinhữngcâuhỏidạngYes/N o,Prologcóthểtrảlờicáccâuhỏiyêu cầutìmđápsố. Chúngtanhậpvàomộtgoalnhưsau: chet(X) Đếnđây,trongcâuhỏicủachúngtacómộtbiến:X(nhắclại:mọidanhhiệumởđầulàkýtự hoađềulàbiến).Khitrongcâuhỏicủachúngtachứamột(hoặcnhiều)biến,hệthốngsẽtìm cácgiátrịcóthểcócủabiếnđểchocâuphátbiểucủatalàđúng.Hiểuởmứcýniệm,câuhỏi củachúngtalà:ailàngười?Kếtquảtrảlờicủacâuhỏi(ai)sẽđượcchứatrongbiếnX. Câutrảlờisẽlà:X=Socrates Tươngtựnhưtrên,hệthốngsẽdựavàocơchếsuyluậnđãđượccungcấpđểtìmralờigiải vớinhữngcâuhỏidànhchocácvịtừcócácmệnhđềtươngứnglàcácluật.N hậpvàogoal nhưsau: chet(X) Hệthốngsẽtrảlờinhưsau: X=Socrates. VD7: HoànchỉnhvàthựcthichươngtrìnhchoVD2 Chươngtrìnhhoànchỉnhnhưsau: predicates giaithua(integer,integer) clauses giaithua(0,1). giaithua(X,Y):X1=X1,giaithua(X1,Y1),Y=X*Y1. Chúngtalưuýlàkhikếtthúcmỗimệnhđềđềucókýhiệu'.' Chúngtacóthểđặtchohệthốnggoaldạngnghivấnnhưsau: giaithua(3,6) Hiểutheongônngữtựnhiênsẽlà:cóphảigiaithừacủa3là6haykhông? Câutrảlờilà:Yes Hoặcchúngtacóthểđặtcâuhỏi: giaithua(3,8) Gv:TrịnhHuyHoàng Trang64
8. GiáotrìnhLogicToán Câutrảlờisẽlà:N o. Chúngtasẽđặtcâuhỏitheodạngtìmlờigiải: giaithua(3,X) CâutrảlờisẽlàX=6 Chúngtacũngcóthểđặtcâuhỏingược: giaithua(X,6) Ýtưởngcủacâuhỏisẽlà:giaithừacủasốnàosẽbằng6. Tuynhiênchúngtakhôngcungcấpchohệthốngcơchếsuyluậnđểtrảlờicâuhỏinày.Hệ thốngsẽtrảlời:N oSolution. Tấtnhiênchúngtacóthểđặtcâuhỏinhưsau: giaithua(X,Y) Cảhaithôngsốđềulàbiến.N hưvậycâuhỏicóthểhiểulà:sốnào(X)giaithừathìthànhmột sốkhác(Y).Câuhỏigầnnhưvônghĩavànhữngcâutrảlờicủahệthốngcũngsẽchẳngmang mộtýnghĩathựcsựcónghĩanào. Tómtắt:
   ChươngtrìnhPrologsẽhoạtđộngtheocơchếtươngtác.N gườisửdụngsẽcungcấp yêucầu,gọilàgoal,vàhệthốngsẽtrảlờicácyêucầunày.
   Cóhailoạigoal:goalnộivàgoalngoại.
   N ếugoalkhôngchứabiếnthìhệthốngsẽkiểmtraphátbiểucủachúngtalàđúnghoặc sai,ngượclại,hệthốngsẽtìmcácgiátrịcủacácbiếnlàmchophátbiểucủatalàđúng. 4.PhéphợpnhấtCơchếtìmcâutrảlờicủaProlog. 4.1/Phéphpnht CôngviệcquantrọngnhấtcủaPrologtrongviệctìmcâutrảlờilàthựchiệnviệchợpnhất. Phéphợpnhấtđượcbiểudiễnbằngdấu=,vànócóhaithànhphần,tạmgọilàvếtráivếphải. Phéphợpnhấtsẽtrảvềkếtquảtruehoặcfalse. Cócáctrườnghợphợpnhấtsau: a. Cảhaivếđềulàhằnghoặcbiểuthứcchứatoànhằng.N ếugiátrịcủahaivếlàbằng nhauthìphéphợpnhấtthànhcông(đápsốlàtrue),ngượclạiphéphợpnhấtsẽthấtbại (kếtquảlàfalse) 7=7 _ true 7=8 _ false "abc"="abc" _ true "abcd"="abc" _ false Gv:TrịnhHuyHoàng Trang65
9. GiáotrìnhLogicToán 7=6+1 _ true 6=7+1 _ false b. Mộttronghaivếlàhằnghoặctrongbiểuthứcchứatoànhằng,vếkialàbiếnhoặcbiểu thứccóchứabiến. Trườnghợp1: N ếutấtcảcácbiếnđềucógiátrị(gọilàcácbiếnởtìnhtrạng bound),chúngtaquayvềtrườnghợpa 7=X _ falsenếuXđãcógiátrịlà6 7=X+1 _ truenếuXđãcógiátrịlà6 Y="Socrates" _ truenếyYđãcógiátrịlà"Socrates" Trườnghợp2: N ếucóbiếnchưacógiátrị(gọilàbiếnởtìnhtrạngunbound),Prologsẽ gángiátrịchobiếnsauchohaivếcógiátrịnhưnhauvàtrảvềkếtquảlàtrue.N ếukhông tìmgiátrịnhưvậy,phéphợpnhấtsẽchokếtquảlàfalse. 7=X _ truenếuXchưacógiátrị,sauphéphợpnhấtnày,Xsẽcógiátrịlà71=X*X _ falsevìkhôngthểtìmchoXgiátrịnàolàmchogiátrịhaivếlànhưnhau. c. Cảhaivếđềulàbiếnhoặccácbiểuthứccóchứabiến Trườnghợp1: tấtcảcácbiếnđềucóchứagiátrị,chúngtasẽquayvềtrườnghợpa X=Y _ truenếucảXvàYđềuđãcógiátrịvànhữnggiátrịnàybằngnhauX1=Y _ falsenếuXvàYđềuđãcógiátrịvàXnhỏhơnY. Trườnghợp2: tấtcảcácbiếncủamộtvếđềuđãcógiátrị,chúngtasẽquayvềvềtrường hợpb X=Y _ truenếuXchưacógiátrịvàYđãcógiátrị,sauphéphợpnhất,Xsẽnhậngiátrị củaY X1=Y _ truenếuXchưacógiátrị,Yđãcógiátrị.Sauphéphợpnhất,Xsẽcógiátrị bằnggY+1 Trườnghợp3: cảhaivếđềucònchứabiếnởtìnhtrạngunbound _ hợpnhấtthấtbại X=Y _ falsenếucảXvàYđềuchưagángiátrị X1=Y _ falsenếucảXvàYđềuchưagángiátrị 4.2/CơchtìmcâutrlicaProlog N ếuchúngtađặtrachoPrologmộtcâuhỏi,Prologsẽthựchiệncôngviệcsotrùng(match), tứclàtìmmệnhđềđầutiênđềcậpđếnkháiniệmmàchúngtamuốnhỏi. TrởlạiVD6,saukhiđãhoàntấtchươngtrình,chúngtađặtraGoalnhưsau: nguoi("Socrates") Prologsẽtìmmệnhđềđầutiêncóliênquanđếnkháiniệm nguoi .Hiểnnhiên,mệnhđềđầu tiên(vàduynhấtcóliênquanđếnkháiniệmnàylà: nguoi("Socrates") Gv:TrịnhHuyHoàng Trang66
10. GiáotrìnhLogicToán N hư vậy, khi đã có goal ( nguoi("Socrates") ) và tìm thấy mệnh đề liên quan (nguoi("Socrates") ),Prologsẽtiếnhànhtìmkiếmlờigiải,côngviệcnàytiếnhànhbằngcách tạomốiliênkếtgiữacácthôngsốởphầngoalvàcácthôngsốởphầnmệnhđề.Cócáctrường hợpsau: a. Cảhaithôngsốnàyđềulàcácbiếnunbound,trongtrườnghợpnàyPrologsẽxemcả haithôngsốlà1. b. Ởtấtcảcáctrườnghợpkhác,Prologsẽtiếnhànhphéphợpnhấtgiữahailoạithôngsố. Saukhiđãtạomốiquanhệgiữacácthôngsốởphầngoalvàphầnclause,Prologsẽtiếnhành cácsubclause(nếumệnhđềnàymộtluật).N ếutấtcảcácsubclausethànhcôngvàcácbiến ởphầngoalđãởtìnhtrạngbound(tứclàđãcógiátrị),Prologsẽthôngbáolờigiải.N ếulà câuhỏithuộcdạngYes/N onhưvídụtrên,tứclàcâuhỏikhôngchứabiến,Prologsẽtrảlời Yesnếucôngviệchợpnhấtnhưđãnóiởphầnbthànhcôngvàcácsubclauseđềuthànhcông (nếumệnhđềsotrùnglàmộtluật). Quaytrởlạivớivídụcủachúngta,ởđâythôngsốcủaGoallàmộthằng("Socrates),vàthông sốcủamệnhđềtươngứngcũnglàmộthằng("Socrates),haihằngnàyhợpnhấtthànhcông, vàkếtquảtrảlờilàYes. N ếuchúngtađặtracâuhỏikhác: nguoi("Xeda") Prologcũngchỉtìmthấymộtmệnhđềliênquanđếnkhainiệmnày( nguoi("Socrates") ),vàvì sựhợpnhấtgiữahaihằng"Socrates"và"Xeda"thấtbại,đápsốsẽtrảlờilàN o. Chúngtaxéttrườnghợpcâuhỏicủachúngtacóchứabiến: nguoi(X) Hệthốngsẽtìmthấymệnhđềcóliênquanđếnvấnđềnày( nguoi("Socrates") ),vàtiếnhành hợpnhấtgiữaXvà"Socrates",vàvìXchưacógiátrị(unbound)nênphéphợpnhấtthành công,Xcógiátrịlà"Socrates". Vìviệchợpnhấtgiữacácthôngsốgiữaphầngoalvàphầnclauseđãthànhcông,đâylàmột sựkiệnnênkhôngcầnphảithựchiệnphầnsubclause,vàsaukhihợpnhất,tấtcảcácbiếncần tìmđãcógiátrị(ởđâychỉcómộtbiếnlàX),nênhệthốngsẽcôngbốđãtìmralờigiảivàin ragiátrịcủaX(X="Socrates") Chúngtaxéttrườnghợpkhiởcâuhỏiphầngoalsotrùngvớimộtluật: chet(Y) Chúngtahoàntoàncóthểđặtcâuhỏilà chet(X) ,nhưngchúngtasẽđặttênbiếnkhácđểtiện phânbiệtgiữabiếntrongcâuhỏicủagoalvàthôngsốcụcbộởmệnhđề. Câuhỏitronggoalđượcsotrùngvớimệnhđềsau: chet(X):nguoi(X). Gv:TrịnhHuyHoàng Trang67
11. GiáotrìnhLogicToán VìhaibiếnX(thôngsốcủamệnhđề)vàY(thôngsốcủagoal)đềuchưachứagiátrị,hệthống sẽxemcảhaibiếnlàmột,tứclà,khiXcóđượcgiátrịthìYcũngcógiátrịđóvàngượclại. Dođâylàmộtluật,nênhệthốngsẽtiếnhànhthựchiệncácsubclause.Hệthốngsẽthựchiện subclauseđầutiên nguoi(X) . Quátrìnhthựchiệncácsubclauseởvếphảisẽđượcthựchiệnnhưsau: a. N ếusubclausenàycóthôngsốlàbiếnunbound,Prologsẽtìmgiátrịcủa biếnnàyđểsubclausecógiátrịYes,nếukhôngtìmđượcgiátrịnhưvậy,subclause sẽthấtbại. b. N ếusubclausecóthôngsốđềulàbiếnbound(đãcógiátrị)hoặclàhằng, Prolog sẽ kiểm tra xem subclause có trả về giá trị Yes hay không, nếu không, subclausesẽthấtbại. Cácsubclausesẽđượctiếnhànhtừtráiquaphải,vànếucómộtsubclausethấtbại,mệnhđề đượcsotrùngsẽthấtbại. Trongtrườnghợptrên,khitiếnhànhsubclause nguoi(X) ,dobiếnXlàunbound,nênchúngta rơivàotrườnghợpa,hệthốngsẽtìmgiátrịcủaXchosubclausetrênlàđúng.Cáchtìmkiếm câutrảlờichosubclausenàyhòantòangiốngnhưcáchhệthốngtìmcâutrảlờikhichúngta đặtcâuhỏinàytrongphầngoal,vànhưvậyXsẽcógiátrịlà"Socrates"saukhisubclause nàythựchiệnxong. DoXvàYđượcxemnhưmột,nênkhiXcógiátrịlà"Socrates"thìYcũngcógiátrịnày. Dotấtcảcácsubclauseđãthựchiệnxong,vàYđãcógiátrị,nênPrologcôngbốlàđãtìmra lờigiảivàinragiátrịcủaY. Tómtắt:
    PhéphợpnhấtlànềntảngcủamọihoạtđộngcủaPrologđểtìmralờigiải.Đểtrảlời câuhỏi,Prologsotrùngcâuhỏivớimệnhđềvàtạomốiliênquangiữacácthôngsố.
    Prologtìmralờigiảikhithựchiệnthànhcôngmộtmệnhđềvàtấtcảcácbiếnnếucó trongcácthôngsốcủagoalđềuđãcógiátrị. 5.SựquayluiKhốngchếsốlượnglờigiảiVịtừnhátcắtvàfail Goalnộivàgoalngoại(internalgoalvàexternalgoal) KhichúngtasửdụngAltRđểchuyểnsangcửasổgiaotiếpvànhậpvàogoal,goalnàygọilà goalngoại.Chúngtacóthểthêmphầngoalnàyhẳntrongphầnsoạnthảochươngtrình,goal nàygọilàgoalnội. VD8: ViếtlạichươngtrìnhgiảiquyếtVD6sửdụnggoalnội Gv:TrịnhHuyHoàng Trang68
12. GiáotrìnhLogicToán Chươngtrìnhđượcviếtlạinhưsau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). chet(X):nguoi(X). goal nguoi(X),write(X) Trongvídụnày,chúngtađãthêmphầngoalvàotrongchươngtrình.Khithựcthi,hệthốngsẽ khônghỏigoalnữa,vàtựđộngthựchiệncácyêucầutrongphầngoal.Tuynhiênkhithực hiệngoalnội,hệthốngsẽkhôngtựđộnginkếtquảnữa.Chúngtaphảigọivịtừwrite đểlàm điềunày.Vịtừnàysẽchokếtquảlàđúngnếucácthôngsốnhậpvàolàđềulàbiếnởtrạng tháiboundhoặclàhằng. Sựquaylui(backtracing)trênProlog HợpnhấtlàhònđánềntảngchocơchếsuyluậncủaProlog,tuynhiên,đểtìmralờigiải đúng,Prologphảisửdụngcơchếquaylui,khigiátrịđầutiênđượcgánchothôngsốkhông phảilàlờigiải. Chúngtaxétvídụsau: VD9: predicates nguoi(symbol) 20 vua(symbol) sungsuong(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). vua("Xeda). sungsuong(X):nguoi(X),vua(X). N hưvậytrongvídụnày,ngoàikháiniệmvềngười,chúngtađưarakháiniệmvềvuavàsự sungsướng.Diễngiảinhữngthôngtintrongcácdữkiệntrênthànhngônngữtựnhiên,chúng tacóđượccácđiềusau:"ThếgiớimàchúngtasốngcóhaingườilàSocratesvàXeda.Chúng tacómộtvualaXeda,vàmộtthựcthểnàođóchỉsungsướngnếuthựcthểđóvừangườivừa làvua."Lưuýrằngtrongvídụtrên,cácmệnhđềliênquanđếncùngmộtvịtừphảiviếtliên tiếpnhau. Xétkhihệthốngtrảlờicâuhỏisau: sungsuong(X) Gv:TrịnhHuyHoàng Trang69
13. GiáotrìnhLogicToán Trướctiênhệthốngsẽsotrùnggoaltrênvớimệnhđề sungsuong(X):nguoi(X),vua(X). Lưuý rằngvàolúcnàychúngtacóhaibiếnX:mộtbiếnXlàthôngsốcủagoalvàmộtbiếnXlà thôngsốcủamệnhđề.Vềnguyêntắc, haibiếnXnàyhoàntoànkhácnhau . Tuynhiên,khisotrùnggoalvớimệnhđề,docảhaibiếnXlúcnàyđềuchưachứagiátrị,nên chúngsẽđượcxemnhưmột.N hưngcầnchúýrằng biếnXsửdụngtrongcácsubclauselà biếnXthôngsốcủamệnhđề. SauđóPrologsẽtiếnhànhcácsubclause.Ởsubclause đầu tiên, nguoi(X) , tương tự như VD6,PrologsẽtìmđượccâutrảlờilàX=Socrates.Khithựchiệnsubclausethứhai, vua(X) , doXđãcógiátrị(Socrates),Prologsẽkiểmtraxemgiátrịnàycólàmgiátrịcủamệnhđềlà truehaykhông. N hưcácvídụtrên,việctiếnhànhtrảlờimộtsubclausecũngtươngtựnhưkhitrảlờimột goal,Prologlạisotrùngsubclausevớimộtmệnhđềcùngtên.Prologtìmthấymộtmệnhđề liênquanđến vua là vua("Xeda") vàtiếnhànhhợpnhấtgiữaXvàXeda.DoXđãcógiátrịlà Socrates,việchợpnhấtthấtbại. Tuynhiênkhisubclausenàythấtbại,khôngcónghĩarằngPrologsẽvộikếtluậnrằngmệnh đềnàythấtbại.ỞđâycôngviệctìmkiếmcâutrảlờithấtbạisaukhibiếnXđượcgángiátrị vàchuyểntừtrạngtháiboundsangunbound.HệthốngsẽquaylạithờiđiểmbiếnXđượcgán giátrị(khitrảlờisubclause nguoi(X) ),Xđượcchuyểnlạisangtìnhtrạngunbound,vàcố gắngtìmkiếmmộtgiátrịkháccủaXđểchomệnhđềconnàyvNnđúng.Côngviệcnàyđược gọilàbacktracing. Doviệcsotrùngsubclausenàyvớimệnhđề nguoi("Socrates") thấtbại,hệthốngsẽsotrùng vớimệnhđềkhác. ếukhôngcònmệnhđềnàokhácliênquanđếnsubclause,việcthựchiện mệnhđềmớithậtsựthấtbại ,tuynhiênởđâyhệthốngtìmthấymộtmệnhđềkhácliênquan đếnkháiniệmnàylà nguoi("Xeda") .ViệchợpnhấtgiữaXvà"Xeda"lạiđượcthựchiện,Xsẽ cógiátrịlàXedavàsauđó,khilạitiếptụcthựchiệnsubclause vua(X) thìchúngtasẽdễ dàngthấyrằngsubclauselầnnàyđượcthựchiệnthànhcông.Prologđãtìmralờigiải,tuy nhiên,ởtrườnghợpnày,ngoàisựhợpnhất,Prologcònsửdụngthêmmột"vũkhí"mới,đólà sựquaylui. Khốngchếsốlượnglờigiải Chúngtaxétvídụsau VD10: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). chet(X):nguoi(X). Gv:TrịnhHuyHoàng Trang70
14. GiáotrìnhLogicToán Vídụkhôngcógìphứctạp,sovớiVD6,chúngtachỉthêmmộtngườimớilàXeda. Khisửdụnggoalngoại,vớicâuhỏi nguoi(X) Chúngtacóhailờigiải: X=Socrates X=Xeda. Chúngtacảmthấyhaiđápsốnàylàhiểnnhiên.Tuynhiênnếuchúngtadùnggoalnộitương tựVD8,chúngtachỉcómộtđápsốlàSocrates. Đâylàmộttrongnhữngđiểmkhácbiệtcănbảncủagoalnộivàgoalngoại. Goalnộichỉtìm câutrảlờiđầutiêncòngoalngoạitìmtấtcảcáccâutrảlờicóthể. Đểkhốngchếsốlượng lờigiảitheoýmình,chúngtasửdụnghaivịtừđặcbiệtlànhátcắt(cut)vàfail,nhưcácvídụ sau: VD11: ViếtlạiVD10,sửdụngvịtừfailđểinratấtcảcáclờigiảitrongtrườnghợpdùnggoal nội. Chươngtrìnhsẽđượcviếtlạinhưsau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). chet(X):nguoi(X). goal nguoi(X),nl,write(X),fail nl: làvịtừđặcbiệt,luôntrảvềkếtquảlàđúng,vàchỉđơngiảnlàxuốngdòngtrướckhiin thôngtinmớiracửasổgiaotiếp. Fail:làmộtvịtừđặcbiệt,luônluôntrảvềkếtquảlàsai. N hưvậyđểinratấtcảcáckếtquả,chúngtadùngmộtthủthuật(trick)thườnggặpkhilập trìnhtrênProlog:saukhiđãtìmthấylờigiảichosubgoal nguoi(X) vàingiátrịnàyrabằng lờigọivịtừ write(X) ,chúngtagọivịtừfailđểnhậnđượckếtquảlàsai.Docơchếback tracingđãnóiởtrên,Prologlạiquaylạithờiđiểmgọisubgoal nguoi(X) đểtìmlờigiảikhác vàinra.Quátrìnhnàycứtiếptụcchođếnkhikhôngthểtìmthấythêmmộtlờigiảinàokhác. Bằngcáchnày,chúngtađãinratấtcảcáclờigiảichocâuhỏi nguoi(X) ,tuynhiênlưuýrằng vớigoalchínhthìkhôngtìmralờigiải(dochúngtaluôngọivịtừfailchosubgoalcuốicùng) VD12: ViếtlạiVD10,dùngvịtừnhátcắtđểđểinramộtlờigiảichocâuhỏi chet(X) cho trườnghợpdùnggoalngoại. Vịtừnhátcắtđượcviếtlà!,làvịtừđặcbiệt,sẽtrảlờiđúngkhigoalchưatìmthấylờigiải nào,ngượclạisẽbáolàsai. Gv:TrịnhHuyHoàng Trang71
15. GiáotrìnhLogicToán Chươngtrìnhsẽđượcviếtlạinhưsau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). chet(X):nguoi(X),!. Khisửdụnggoalngoạilà chet(X) ,khitrảlờisubclause nguoi(X) ,hệthốngtìmrađápsốlàX =Socrates,vàvìlúcnàymệnhđềđượcsotrùng chet(X) chưacóđápsốnào,vịtừ!tiếptheo sẽtrảlờilàthànhcông. Dochúngtađangsửdụnggoalngoại,Prologsẽtìmtấtcảcáccâutrảlờicóthểcó,nênhệ thốngsẽtìmmộtcâutrảlờikhác.Đểlàmđiềuđó,hệthốngsẽtìmxemsubclause nguoi(X) có đápsốnàokháckhông.Chúngtasẽdễdàngnhậnthấyrằnghệthốngtìmthấymộtđápsố kháclàX=Xeda.Tuynhiêndogoalđãcómộtlờigiải,nênsubclausetiếptheolà!sẽbáolà thấtbại,vàlờigiảithứhaikhôngđượcchấpnhận. Tómtắt
    Goalnộisẽtìmlờigiảiđầutiên,vàgoalngoạisẽtìmtấtcảcáclờigiảicóthểcó.
    Prologsẽsửdụngcơchếquayluikhimộtbiếnkhichuyểntừtrạngtháiunboundsang boundsẽdNnđếnsựthấtbạitrongviệctruytìmlờigiải
    Vịtừfailluôntrảlờilàsai,sửdụngkhichúngtamuốnintấtcảcáclờigiảivớigoal nội.
    Vịtừ!sẽtrảlờiđúngkhigoalchưacólờigiảivàngượclại. 6.LậptrìnhđệquyvớiProlog ChúngtanhớlạirằngvớiVD2,chúngtađãcốgắngnétránhcáchđặtvấnđềđểgiảibàitoán giaithừatheocáchnhândồncácsốtừ1đếnsốcầntínhgiátrịgiaithừa.Điềunàysẽdẫnđến mộtđiểmyếucủaProlog:khôngcungcấpcáccấutrúcđiềuhiểncầnthiết,dNnđếnviệckhó khănkhithựchiệnphéplặp.uynhiênvídụnàycũngchothấymộtkỹthuậtlậptrìnhtạonên sứcmạnhchủyếucủaProlog:lậptrìnhđệquy.Kỹthuậtnàycũngphùhợpvớisuynghĩcủa conngườikhitiếpcậngiảiquyếtvấnđềvàkhiếnchoviệclậptrìnhtrênPrologcómộtsự uyểnchuyểnvànhẹnhàngtrongviệcviếtmã.Tuyvậy,nótạoramộtsựkhókhănvớinhững ngườiquenlậptrìnhthủtục.Chúngtasẽxemxétlạitừngbướctrongviệcgọiđệquyđểtìm ralờigiải. VD13: XéttừngbướcquátrìnhgọiđệquyvàhợpnhấtcủaVD7vớigoallàgiaithua(2,X) N hắclại,chúngtađãcóđoạnchươngtrìnhnhưsau: predicates giaithua(integer,integer) Gv:TrịnhHuyHoàng Trang72
16. GiáotrìnhLogicToán clauses giaithua(0,1):!. giaithua(X,Y):X1=X1,giaithua(X1,Y1),Y=X*Y1 Ởđâycómộtsựthayđổinhỏ:chúngtađặtnhátcắtđểchuyểnsựkiệnđầuthànhluật.Chúng tamuốnkhẳngđịnh:nếusốcầntìmgiaithừalà0thìgiaithừacủanólà1, vàkếtquảnàylà duy nhất ,khôngcầnphảitiếptụctìmcáctrườnghợpkhác. Với goal là giaithua(2,X) , hệ thốngsẽsotrùngvớimệnhđề giaithua(0,1) làmệnhđềđầutiêntìmthấycóliênquanđến kháiniệm giaithua. Hệthốngsẽhợpnhấtcácthôngsốtheothứtự,2hợpnhấtvới0vàXhợpnhấtvới1. CôngviệchợpnhấtXvới1thànhcông,Xcógiátrịlà1,nhưng2hợpnhấtvới0thấtbại. Hệthốngsẽtiếptụctìmkiếmlờigiảikhácbằngcáchsotrùngvớimệnhđềkhác.Lầnnàyhệ thốngsotrùnggoalvớimệnhđề giaithua(X,Y). Khitạomốiliênquangiữacácthôngsố,hệ thốnghợpnhất2vớiXcủamệnhđềvàYvớiXcủagoal.ChúngtasẽkýhiệuXGlàXthông sốcủagoal.DoYvàXGđềuchưacógiátrị,Prologsẽxemhaibiếnnàylàmột. Sauđóhệthốngbắtđầuthựchiệntừngsubclause:X1=X2 X1làbiếnmới,vàchưacógiátrị.Xđãcógiátrịlà2,nênX1cógiátrịlà1.HợpnhấtX1 với1tasẽcógiátrịcủaX1là1. giaithua(X1,Y1) Ởđâymệnhđềgiaithừađượcgọiđệquy.LưuýlúcnàyX1đãcógiátrịlà1,Y1làbiếnmới chưa có giá trị, vì vậy nhiệm vụ của hệ thống là tìm giá trị của Y1 sao cho subclause giaithua(X1,Y1) chogiátrịlàđúng.Vàcũngnhưcácvídụtrên,cáchthứcPrologtrảlờimột subclausecũngtươngtựnhưkhitrảlờicâuhỏitừgoal,tứclàlạisotrùngcâuhỏivớicác mệnhđềđãbiết
    Sotrùngvới giaithua(0,1) ,PrologtiếnhànhhợpnhấtX1với0,Y1với1,doX1đãcó giátrịlà1,việchợpnhấtvới0thấtbại,Prologphảisotrùngvớimệnhđềkhác.
    Sotrùngvới giaithua(X,Y) ,PrologtiếnhànhhợpnhấtX1vớiXđồngnhấtY1vớiY. ChúngtakýhiệuXvàYởlầngọiđệquynàylàX2vàY2,vàsửdụngcáchkýhiệu tươngtựnhưvậychocácbiếncònlạiởlầngọiđệquynàycũngnhưcáclầngọiđệquy tiếptheo.N hưvậyX2sẽcógiátrịlà1vàY1sẽcógiátrịmàY2sẽcó.Tươngtựởlần gọithứnhất,cácsubclausecủamệnhđềtrênởlầngọithứhainàysẽlầnlượtđược gọi: - X12=X21 ,hợpnhấtX12vớiX21,tacóX12cógiátrịlà0. - giaithua(X12,Y12) ,X12đãcógiátrịlà0,PrologsẽtìmgiátrịcủaY12bằngviệc tiếptụcsotrùng giaithua(X12,Y12) vớicácmệnhđềcóliênquan:
    Sotrùng giaithua(X12,Y12) với giaithua(0,1) .DoX12đãcógiátrịlà0,Prologtiến hành hợp nhất X12 với 0 và Y12 với 1. Thực hiện tiếp subclause !, do câu hỏi giaithua(X12,Y12) chưatìmđượccâutrảlờinào,nênsubclausenàytrảlờilàđúng. Việcthựchiệnmệnhđềgiaithua(0,1) thànhcông,vàY12đãcógiátrịlà1nêncâuhỏi giaithua(X12,Y12) đãcóđápsố.Vịtừ!sẽngănchặnviệctìmcácđápsốkhác, vìvậy trongtrườnghợpnày,Prologkhôngtiếptụcsotrùngtiếpvớimệnhđềgiaithua(X,Y). - Y2=X2*Y12 ,lúcnàyY2chưacógiátrị,X2vàY12đãcógiátrịlà1và1nên PrologsẽhợpnhấtY2và1.KếtquảsẽlàY2cógiátrịlà1.N hưvậyđếnđâycác Gv:TrịnhHuyHoàng Trang73
17. GiáotrìnhLogicToán subclausecủamệnhđềgiaithua(X2,Y2) đãthựcthithànhcông,vàY2đãcógiátrị là1,vàvìY1đượcđồngnhấtvớiY2,nênY1cũngsẽcógiátrịlà1.
    Y=X*Y1 ,lúcnàyYchưacógiátrị,XvàY1đãlầnlượtcógiátrịlà2và1,nên ProloghợpnhấtYvà2*1,kếtquảYsẽcógiátrịlà2. N hưvậyđếnđâycácsubclausecủamệnhđềgiaithua(X,Y) đãthựcthithànhcông,vàYđã cógiátrịlà2,vàvìXGđượcđồngnhấtvớiY,nênXGcũngsẽcógiátrịlaø2,vàlờigiảicủa bàitoánđãđượctìmthấy. Tómtắt:
    ĐệquylàsứcmạnhlậptrìnhchủyếutrênProlog
    Mỗilầngọiđệquy,cácthôngsốvàbiếncụcbộtrongmỗimệnhđềsẽđượctạomới tươngứngvớilầngọiđệquydó.
    Cóthểdùngnhátcắtđểngănchặncáclầngọiđệquythừakhiđãtìmrađápsố 7.DanhsáchtrênProlog DanhsáchlàkiểudữliệucấutrúcđặcbiệttrênProlog.Cóthểhiểudanhsáchnhưmộtkiểu dãymộtchiều,vàphầntửcủadanhsáchcóthểthuộcvềkiểudữliệubấtkỳ,tuynhiêncác phầntửtrongcùngmộtdanhsáchphảicùngkiểu. Địnhnghĩakiểudanhsách Kiểudanhsáchlàmộtkiểudữliệu(userdefinedtype)dongườidùngđịnhnghĩatrênProlog. Chúngtacầnphảiđịnhnghĩamộtkiểudữliệudanhsáchtrướckhisửdụng.Phầnđịnhnghĩa kiểudữliệumớisẽđượckhaibáosautừkhoá domains vàđặtởđầuchươngtrình. VD14: KhaibáomộtkiểudữliệumớilàmộtdanhsáchsốnguyêntrênPrologcótênlàlist. domains list=integer* Kýhiệu*biểuhiệnchodanhsách. list sẽlàkiểudữliệudanhsáchcóphầntửthuộckiểu integer . Cấutrúccủadanhsách MộtdanhsáchtrênPrologbaogồmhaiphần:phầnđầu(head)làphầntửđầutiêncủadanh sáchvàphầnđuôi(tail)làdanhsáchcácphầntửcònlạicủadanhsách. Mộtdanhsáchcóthểmôtảtheohaicách: - Liệtkêcácphầntửcủadanhsách,vídụ:[1,2,3,4,5] - Môtảphầnđầuvàphầnđuôicủadanhsách,ngăncáchbởidấu|,vídụ[1|[2,3,4,5]] VD15: Môtảmộtdanhsáchbaogồm5sốnguyênlà1,2,3,4,5 Gv:TrịnhHuyHoàng Trang74
18. GiáotrìnhLogicToán Danhsáchtrêncóthểmôtảtheocáccáchsau: [1,2,3,4,5] [1|[2,3,4,5]] [1|[2|[3,4,5]]] [1|[2|[3|[4,5]]]] [1|[2|[3|[4|[5]]]]] [1|[2|[3|[4|[5|[]]]]]] Lưuý:danhsáchrỗngcóthểđượcmôtảnhưsau:[] VD16: Viếtchươngtrìnhinraphầnđầuvàphầnđuôicủamộtdanhsách. Chươngtrìnhnàythựcchấtchỉgiúpchúngtanhìnrõhơnkháiniệmvềdanhsách. Chươngtrìnhđượcviếtnhưsau: domains list=integer* predicates indanhsach(list,integer,list) clauses indanhsach(L,H,T):L=[H|T]. Xétkhichúngtanhậpgoalvàonhưsau: indanhsach([1,2,3,4,5],X,Y) Prologsẽsotrùnggoalvớimệnhđềindanhsach(L,H,T) ,Lđượchợpnhấtvới[1,2,3,4,5],X đượcđồngnhấtvớiH,YđượcđồngnhấtvớiT.Khithựchiệnsubclause L=[H|T] ,Lđược hợpnhấtvới[H|T],nhưvậyphầnđầucủaLsẽhợpnhấtvớiH,phầnđuôisẽhợpnhấtvớiT. DoLđãcógiátrịlà[1,2,3,4,5],phầnđầucủaLsẽcógiátrịlà1,phầnđuôisẽcógiátrịlà [2,3,4,5],vậysaukhihợpnhất,Hsẽcógiátrịlà1vàLsẽcógiátrịlà[2,3,4,5].CũngtứclàX sẽcógiátrịlà1vàYcógiátrịlà[2,3,4,5].Prologđãtìmthấylờigiảivàsẽinralờigiảinày. Lưuý:
    Chươngtrìnhtrênsẽchạysainếudanhsáchnhậpvàolàrỗng([])dolờigiảicủachúng tachưaxửlýtrườnghợpnày
    Phầnmệnhđềchovịtừindanhsach cóthểviếtlạilà indanhsach([H|T],H,T). Tómtắt
    DanhsáchlàkiểudữliệucấutrúcđặcbiệtdongườidùngđịnhnghĩatrênProlog
    Mộtdanhsáchbaogồmhaiphần:phầnđầulàphầntửđầu,phầnđuôilàdanhsáchcác phầntửcònlạicủadanhsách.
    Trongtrườnghợpdanhsáchrỗng,phầnđầucủadanhsáchsẽkhôngcó. 8.LậptrìnhđệquyvớidanhsáchtrênProlog KhixửlýdanhsáchtrênProlog,ngườilậptrìnhphảitừbỏphongcáchdùngvònglặpđểxửlý dãymàphảitậndụngkỹthuậtđệquyđểtìmralờigiải.Chúngtaxétmộtsốvídụsauđây: Gv:TrịnhHuyHoàng Trang75
19. GiáotrìnhLogicToán VD17: Viếtvịtừđếmxemmộtdanhsáchcóbaonhiêuphầntử. Đầutiênchúngtaphảiđịnhnghĩađượccôngviệcmàchúngtađịnhlàm. Chúngtasẽviếtmộtvịtừnhưsau: dem(list,integer) Chúngtađếmtrongmộtdanhsáchcóbaonhiêuphầntử.Vídụkhigọigoaldem([1,2,3,4],X), đápsốsẽlàX=4 TiếptheochúngtaphảixácđịnhmộtthuậtgiảiphùhợpvớitinhthầncủaProlog. Khôngthểdùngvònglặp,chúngtaphảixâydựngmộtgiảithuậtđệquy. Mộtgiảithuậtđệquysẽbaogồmhaiphần:điềukiệndừngvàlờigọiđệquy. Điềukiệndừngchobàitoánnàyrấtdễdàng:khidanhsáchkhôngcóphầntửnào,thìhiển nhiênsốphầntửcủanólà0.Vậyđiềukiệndừngsẽđượcviếtnhưsau: dem([],0):!. Khitrườnghợpdanhsáchkhôngcóphầntửnào,đápsố0làduynhất,vậychúngtacóthể dùngnhátcắtđểyêucầuPrologkhôngtìmthêmlờigiảinàokhác. PhầnđệquyhơikhóđốivớinhữngaichưaquenvớidanhsáchtrênProlog.Prologchỉcung cấpchochúngtacơchếchiadanhsáchthànhhaiphần:phầntửđầuvàphầnđuôidanhsách cácphầntửcònlại.N hưvậylờigiảigầnnhưđãtựnóhiệnra:chúngtasẽgọiđệquyđểđếm phầnđuôicóbaonhiêuphầntửrồicộngnóvới1(phầntửđầu)sẽrasốphầntửtrongmột danhsách. Phầnnàysẽđượcviếtnhưsau: dem([H|T],X):dem(T,X1),X=X1+1. Tưtưởngđệquyđãđượcthểhiệnrấtrõràng:đếmphầnđuôiTcủadanhsáchđểcóđược tổngX1,hợpnhấtXvớiX1+1sẽchođápsốcầntìm.TuynhiênchúngtathấyởđâybiếnH hòantòankhôngcầndùngtrongvếphảicủamệnhđề.Prologkhôngcoiđâylàlỗi,nhưngsẽ "phànnàn"vềviệcnày.Xétvềhiệuquảlậptrình,hòantòankhôngcầnkhaibáotênbiếnmới chothànhphầnHtrongtrườnghợpnày.Cómộtnguyêntắcđểnhậnranhữngbiến"vôdụng" nhưvậy:đólànhữngbiếnchỉxuấthiện1lầntrongsuốtmệnhđề.Đốivớitrườnghợpnày,ta nêndùngkýhiệu'_'thaychotênbiếnđểbiểudiễnbiếnnàykhôngcầndùngtrongthuậtgiải. Vậyphầnđệquysẽđược"tinhchế"nhưsau: dem([_|T],X):dem(T,X1),X=X1+1. N hưvậytoànbộchươngtrìnhhoànchỉnhsẽnhưsau: domains list=integer* predicates dem(list,integer) clauses dem([],0):!. dem([_|T],X):dem(T,X1),X=X1+1. VD18:Viếtvịtừtínhtổngcácphầntửtrongmộtdanhsách domains list=integer* predicates Gv:TrịnhHuyHoàng Trang76
20. GiáotrìnhLogicToán tong(list,integer) clauses tong([],0):!. tong([H|T],X):tong(T,X1),X=X1+H. Tưduyđệquyởđâylà:chúngtatínhtổngphầnđuôicủadanhsách,rồicộngnóvớiphầntử đầuđểtínhtổngdanhsách. VD19: Viếtvịtừkiểmtramộtsốnguyêncónằmtrongdanhsáchhaykhông. Xácđịnhvấnđề:chúngtasẽviếtvịtừptu(integer,list) ,khigọi ptu(2,[1,3,5]) kếtquảsẽlà N o,ngượclạikhigọi ptu(3,[1,3,5]), kếtquảsẽlàYes.Ởđâychúngtaphảixácđịnhđượccác trườnghợpmộtphầntửnằmtrongmộtdanhsách.Vàchúngtaphảitrìnhbàyđượccáckhái niệmnàymộtcáchđệquy. Sauđâylàýtưởngcủathuậtgiải: cóhaitrườnghợpđểmộtsốnguyênlàphầntửcủamột danhsách:sốnguyênnàylàphầntửđầucủadanhsáchhoặcnólàphầntửcủaphầnđuôidanh sách. Saukhixácđịnhđượcýtưởng,chúngtacóbàigiảinhưsau: domains list=integer* predicates ptu(integer,list) clauses ptu(H,[H|_]):!. ptu(H,[_|T]):ptu(H,T). Lưuý:
    Chúngtađãthaythếcácbiếnchỉxuấthiệnmộtlầntrongmộtmệnhđềbằngkýhiệu'_' nhưđãnói.
    Ởmệnhđềđầuđãcókýhiệunhátcắt,nênnếumệnhđềnàyđúng,bàitoánđãcólời giảivàkhôngsotrùngđếnmệnhđềthứhai. hưvậymệnhđềthứhaichỉđượcso trùngkhimệnhđềthứnhấtthấybại,vàvìmệnhđềthứnhấtứngvớitrườnghợpsố nguyêncầntìmbằngvớiphầntửđầucủadanhsách,nênkhimệnhđềthứnhấtthấtbại, tứclàsốnguyêncầntìmkhôngbằngvớiphầntửđầucủadanhsách,nêntrongmệnhđề thứhai, chúngtakhôngcầnquantâmđếnphầntửđầucủadanhsách . VD20: Xácđịnhphầntửthứncủadanhsách Khitagọiptn([1, 3,5,7,9], 2,X) _ X=3(phầntửthứ2củadanhsách).VìPrologchỉcho chúngtatruyxuấtphầntửđầutiêncủadanhsách,nênchúngtaphảixâydựngthuậtgiảiđệ quydựatrêncơsởnày:nếunbằng1thìphầntửcầntìmlàphầntửđầucủadanhsách,ngược lạithìđósẽlàphầntửthứn1củaphầnđuôidanhsách. domains list=integer* Gv:TrịnhHuyHoàng Trang77
21. GiáotrìnhLogicToán predicates ptn(list,integer,integer) clauses ptn([H|_],1,H):!. ptn([_|T],,X):1=1,ptn(T,1,X). VD21: Tạoramộtdanhsáchbaogồmchỉcácphầntửlẻcủadanhsáchbanđầu. Goalkhigọisẽcódạngptle([1,2,3,4,5,6],L) _ L=[1,3,5] Điềukiệndừngcủabàitoánrấtđơngiản:khidanhsáchlàrỗngthìdanhsáchđượctạora cũnglàrỗng.Vàphầnđệquycủabàitoánphảidựatrênviệctruyxuấttừphầntửđầutiêncủa danhsáchvàgọiđệquychophầnđuôi.Chúngtaphảixétcáctrườnghợpkhácnhaucủaphần tửđầu. domains list=integer* predicates ptle(list,list) clauses ptle([],[]):!. ptle([H|T],[H|T1]):Hmod2=1,ptle(T,T1),!. ptle([_|T],T1):ptle(T,T1) . Ởđâychúngtalưuýđếnmệnhđềthứba:dohaimệnhđềtrênđềucónhátcắt,nênmệnhđề thứbachỉđượcsotrùngkhihaimệnhđềtrênđềusai.Mệnhđềthứhaiđãxéttrườnghợpkhi Hlẻ,vìvậyởmệnhđềthứbachắcchắnHkhôngphảilàsốlẻ,vàvìvậykhôngcầnphảixét đến. Tómtắt:
    ĐệquylàcôngcụchủyếuđểxửlýdanhsáchtrênProlog
    Việcgọiđệquytrêndanhsáchthườngdựatrêncơsởchiadanhsáchthànhphầnđầu vàphầnđuôi.
    Sửdụngvịtừnhátcắthợplýsẽkhiếncácmệnhđềtrởnêngọnnhẹvàlogichơn. 9.Danhsáchhaichiều Danhsáchhaichiềulàmộttrườnghợpđặcbiệtcủadanhsách.Phầntửcủadanhsáchlúcnày cũnglàmộtdanhsách.TaxétmộtvídụvềkhaibáodanhsáchhaichiềutrênProlog: VD22: KhaibáodanhsáchhaichiềutrênProlog domains list=integer* list2d=list* N hưvậykiểudữliệulist2dlàkiểudữliệudanhsáchmàphầntửcủanóthuộckiểulist,tứclà mộtdanhsáchkhác.Việclậptrìnhvớidanhsáchhaihaynhiềuchiều,vềcơbản, hòantòan khôngkhácvớiviệclậptrìnhdanhsáchmộtchiều,tứccũngsửdụngcácgiảithuậtxửlýdanh Gv:TrịnhHuyHoàng Trang78
22. GiáotrìnhLogicToán sáchbìnhthường.Tuynhiênchúngtacầnchúýrằngphầntửcủadanhsáchnàycũnglàmột danhsách. VD23: ViếtchươngtrìnhđếmtrênmộtdanhsáchhaichiềucủacácsốnguyênLcóbao nhiêuphầntửconcótổngcácphầntửlàsốchẳn. Vớibàitoánnày,chúngtaphảiviếtthêmmộtvịtừphụđểcóđượclờigiải: domains list=integer* list2d=list* predicates tong(list,integer) dem(list2d,integer) clauses tong([],0):!. tong([H|T],X):tong(T,X1),X=H+X1. dem([],0):!. dem([H|T],X):tong(H,),mod2=0,dem(T,X1),X=X1+1,!. dem([_|T],X):dem(T1,X). Tómtắt
    Danhsáchnhiềuchiềulàmộtdanhsáchtrongđócácphầntửcũnglàdanhsách
    Vềmặttưduy,lậptrìnhđểxửlýtrêndanhsáchnhiềuchiềukhôngkhácnhiềuvớixử lýdanhsáchmộtchiều.
    Cácphầntửcủadanhsáchnhiềuchiềucũnglàdanhsách,nêncóthểápdụngcácgiải thuậtxửlýdanhsáchđểxửlýcácphầntửnày. BàitậpThựchànhProlog Viếtcácchươngtrìnhgiảiquyếtcáccôngviệcsau: 1. Viếtchươngtrìnhđểđếmsốphầntửlàsốchẵntrênmộtdanhsách. 2. Viếtchươngtrìnhđểđếmsốphầntửlàsốchẵntrênmộtdanhsáchnhưngphầntử trướcnóphảilàmộtsốlẻ. 3. Viếtchươngtrìnhlấyphầntửchínhgiữamộtdanhsách(trườnghợpsốphầntửcủa danhsáchlàsốchẵnthìtrảvềsố0) 4. Viếtchươngtrìnhxửlýgiữahaidanhsách:lấycácphầngiao,hội,hiệucủahaidanh sách. 5. Viếtchươngtrìnhđểlấymộtdanhsáchchỉbaogồmcácphầntửcóchỉsốchẳntrên mộtdanhsáchkhác. 6. Viếtchươngtrìnhnhằmchiadanhsáchthànhhaiphần.Phầnđầugồmn.aphầnđầucủa danhsáchđượcsắpxếptheothứtựtăngdần,phầnsaugồmn.asaudanhsáchđượcsắp xếptheothứtựgiảmdần. 7. Vídụ:chia([3,52,7,312,25,66,34,45],X,Y)
    X=[3,7,52,312],Y=[25,34,45,66] 8. Sinhviênnghĩracáchgiảiquyếtchotrườnghợpsốphầntửcủadanhsáchlàsốlẻ. Gv:TrịnhHuyHoàng Trang79
23. GiáotrìnhLogicToán 9. Viếtchươngtrìnhđểchiamộtdanhsáchthànhnphần(nlàthôngsốnhập),trongđó từngphầnlầnlượtđượcsắptheothứtựtăngdầnrồiđếngiảmdần. 10.Viếtchươngtrìnhđểsắpxếpcácphầntửcủamộtdanhsáchtheothứtựphầndưcủa cácphầntửnàychomộtsốnguyênN . 11.Viếtchươngtrìnhxóađisựxuấthiệnđầutiêncủamộtphầntửtrongmộtdanhsách. 12.Viếtchươngtrìnhxóađitấtcảsựxuấthiệncủamộtphầntửtrongmộtdanhsách. 13.Viếtchươngtrìnhtìmkiếmmộtdanhsáchcontrongmộtdanhsách. 14.Viếtchươngtrìnhxóađisựxuấthiệnđầutiêncủamộtdanhsáchcontrongmộtdanh sách 15.Viếtchươngtrìnhxóađitoànbộsựxuấthiệncủamộtdanhsáchcontrongmộtdanh sách. 16.Viếtchươngtrìnhđểtạoramộttậphợptừmộtdanhsáchcácsốnguyên(trongmộttập hợpthìmộtphầntửxuấthiệnnhiềunhấtlàmộtlần.) 17.ViếtmộtchươngtrìnhđểtạoramộtdanhsáchbaogồmN phầntửnhỏnhấttừmột danhsách. 18.Viếtmộtchươngtrìnhtạoramộtdanhsáchcácướcsốcủamộtsốnguyên. 19.Viếtchươngtrìnhtínhtoántầnsuấtxuấthiệncủamộtdanhsáchtrongmộtdanhsách khác. 20.Vídụ:tansuat([1,2,3],[1,2,3,4,1,2,3,5],X)
    X=2. tansuat([2,2],[1,2,2,2,2,2],X)
    X=4. 21.Viếtchươngtrìnhkiểmtraxemmộtdanhsáchcóđốixứnghaykhông. 22.Viếtchươngtrìnhđảongượcmộtdanhsách. 23.Viếtchươngtrìnhsosánhhaidanhsáchxemchúngcólàhaitậphợpbằngnhauhay không. 24.ViếtchươngtrìnhloạibỏnhữngsốnguyênnàoxuấthiệnđúngN lầntrongmộtdanh sách. Gv:TrịnhHuyHoàng Trang80
24. GiáotrìnhLogicToán BÀI7:LOGICMỜ 1.Mộtsốkháiniệm 1.1/Tậpmờ(FuzzySets) a. Địnhnghĩatậpmờ • Tậprõ(crispsets) ChotậphợpAlàconcủatậpvũtrụUvàxlàmộtphầntử.Khiđóhàmthànhviên (x) códạngnhưsau: 1 x ∈ A A (x) =  (1.1) 0 x ∉ A Rõrànghàmthànhviên Achỉnhậnmộttronghaigiátrịlà0hay1.N hậngiátrị0khi x∉A vànhậngiátrị1khi x∈A.Vìthế A (x) ∈{0,1}. Vídụ:ChotậphợpU={ x1,x 2,x 3,x 4,x 5}vàA={ x2,x 3,x 5}thìchỉcó3trong5phầntử thuộcvềA.Tacó: A (x 1)=0, A(x 2)=1, A (x 3)=1 A (x4) =0, A (x 5)=1 VìthếhàmđặctrưngcủaAnhưsau:  1,x=x 2 x, 3 x, 5 A =  (1.2) 0,x=x1 x, 4 • Tậpmờ XéttậphợpAlàconcủatậpvũtrụU.MộttậpmờAđượcđịnhnghĩabởimộttậphợp hoặccáccặpxóthứtự(mộtquanhệnhịphân)nhưsau: A={(x, A (x)) | x∈A , A (x ∈[ 1,0) ] trongđóA(x) làmộthàmgọilàhàmthànhviênchỉđịnhmứcđộmàphầntửxthuộc vềtậpmờA ĐịnhnghĩatrêngắnkếtmỗiphầntửxtrongtậpAvớimộtsốthựcA(x) trongkhoảng [0,1].Giátrị A(x) cànglớnthìmứcđộ xthuộcvề Acàngcao. Xemxétcôngthức(1.2)tathấycácphầntửxcủacặp( x, A(x) )chobiếtsốlượngcác phầntửtrongtậpcổđiểnA,chúngthoảmộtsốđiềukiện(P) nàođóvàhàmthànhviên A(x) Gv:TrịnhHuyHoàng Trang81
25. GiáotrìnhLogicToán cómiềngiátrịtrongkhoảng[0,1]vàđólàviệcmởrộngmứcđộmàcácphầntửxthoảmã điềukiệnP.Hàmthànhviênđượcxemxétcóthểlàmộthàmliêntụchoặcmộthàmrờirạc. TậpmờAtheođịnhnghĩa(1.2)thườngtươngđươngvớihàmthànhviên A(x) .Dođó chúngtacóthểnhậnbiếtđượctậpmờthôngquahàmthànhviênvàcóthểdùnghaikháiniệm nàythaythếchonhau.Vìthếchúngtacóthểxemmộttậpmờtrênmiền Alàmộtánhxạtừ tậpAvàođoạn[0,1]. Cáctậpmờthườngđượckýhiệubằngcácchữcáiinhoa A,B,C vàcáchàmthành viêntươngứngđượckýhiệubằng A(x), B(x), C(x) , Cácphầntửvớihàmthànhviênchỉ mứcđộbằngkhôngthườngkhôngđượcliệtkêvàotậpmờ. Cáctậprõcóthểđượcxemnhưlàmộttrườnghợpđặtbiệtcủatậpmờvớicáchàm thànhviênchỉmứcđộbằng1. Mộttậpmờ AđượcgọilàđượcchuNnhoá( normalized )khicóítnhấtmộtphầntử x ∈ Amàtạiđóhàmthànhviêntại A(x)=1.N gượclạitậpmờ Ađượcgọilàtậpkhôngđược chuNnhoá. GiảsửtậphợpAlàtậpchưađượcchuNnhoá,khiđómax(A(x) )<1.ĐểchuNnhoátập AcónghĩalàchuNnhoáhàmthànhviêntachỉviệclấyhàmthànhviênđóchiachomax A (x) (A(x) ),tađượccácgiátrị max ( A (x)) Tập Ađượcgọilàtậprỗngkýhiệulà ∅nếu A(x) =0vớimọi x ∈A. Tập mờ A = {(x1 , A (x1 ))}vớix1làgiátrịduynhấttrongtập A⊂Uvà A(x 1)∈ [0,1]thì Ađượcgọilàtậpmờđơn. Vídụ1 : Xéttậpmờ A={(x 1,0.1),(x 2,0.5),(x 3,0.3),(x 4,0.8),(x 5,1),(x 6,0.2)} màcóthểđượcbiểudiễnnhưsau: A=0.1/x 1+0.5/x 2+0.3/x 3+0.8/x 4+1/x 5+0.2/x 6 Đâylàtậpmờrờirạcbaogồm6cặp.Cácphầntửx i,i=1, ,6khôngcầnthiếtphải đánhsố,chúngthuộcvềtậpA={x 1,x 2,x 3,x 4,x 5,x 6}vàlàtậpconcủaU.Hàmthànhviên A(x)củaAnhậncácgiátrịsautrongkhoảng[0,1]: Vídụ2: Chúngtahãymôtảcácsốlâncận10 Trướctiênxemxéttậpmờ  1  A1 = (x, A (x)) | x ∈ ,5[ 15], A (x) = 2   1 1 1+ (x −10)  trongđó A1 (x)làmộthàmliêntụcvàđượcthểhiệntronghìnhsau: Gv:TrịnhHuyHoàng Trang82
26. GiáotrìnhLogicToán A1 (x ) x Hình1:Cácsốthựclâncận10 N hữngsốnguyênlâncận10cóthểđượcmôtảbằngmộttậpmờhữuhạncó7cặpcó thứtựnhưsau: A2={(7,0.1),(8,0.2),(9,0.5),(10,1),(11,0.5),(12,0.2),(13,0.1)} HàmthànhviêncủaA2đượcthểhiệntronghình2bằngnhữngdấuchấm.Đólàmột hàmrờirạc. 1.2 1 0.8 0.6 0.4 0.2 0 0 5 10 15 20 Hình2:hữngsốnguyênlâncận10 Chotậpmờ A,tađịnhnghĩalátcắt α( αcut)kýhiệuA αnhưlàmộttậprõcácphần tử xmànóthuộc Avớimứcđộítnhấtlà α A = { x | x ∈ R , A (x ) ≥α},α ∈ ]1,0[ Látcắttrênlàmộtngưỡngmànóchotamứcđộtincậy αtrongmộtquyếtđịnhhoặc kháiniệmtrongmộttậpmờ.Chúngtacóthểdùngngưỡngnàyđểloạibỏrakhỏitậpnhững phầntử xthuộcvề Avớimứcđộ A(x 1)< α Vídụ3: Gv:TrịnhHuyHoàng Trang83
27. GiáotrìnhLogicToán ChotậpTmiêutảđộcaocủanhữngngườiđànông.Tậpnàycóvôsốnhữngkhoảng cắtbêntrong Tαvớiαthayđổitừ0.22đến1.Chomộtvàilátcắtsauđây: T0.22 ={ x| x∈R,160≤ x≤200}, T(x) ≥0.22 T0.5 ={ x| x∈R,170≤ x≤200}, T(x) ≥0.5 T0.78 ={ x| x∈R,180≤ x≤200}, T(x) ≥0.78 Chẳnghạntachọnmộtngưỡngvớilátcắt T0.5 dođótasẽloạinhữngngườiđànông caodưới170cmrakhỏitậpcầnxemxét. Mộttậpmờ Avới U= Rlàmộttậptậplồinếuvàchỉnếunhữngkhoảngcắt Aαlàbao lồiđốivớinhữngkhoảngcắttrongkhoảng(0,1].Trongtrườnghợpnàythìcáckhoảngcắt Aα chỉgồmcómộtđoạn.N gượclạithìtập Akhôngphảilàtậplồi. b. Cácphéptoántrêntậpmờ Xéthaitậpmờ Avà Btrongtậpvũtrụ U A={(x , A (x },)) A (x) ∈ ]1,0[ B={(x , B (x },)) B (x) ∈ ]1,0[ Cácphéptoángiữa Avà BđượcthựchiệnthôngquahàmthànhviêncủanólàA(x) và B(x) •Tươngđương TậpmờAvàBđượcgọilàtươngđương,kýhiệulà A=Bnếuvàchỉnếu A (x)= B (x),∀x∈U •Baogồm(baohàm) Tậpmờ Ađượcbaohàmtrongtậpmờ B,kýhiệulàA ⊆Bnếu A (x)≤ B (x),∀x ∈U KhiđótậpAđượcgọilàtậpconcủatập B •Tậpconthựcsự Tậpmờ Ađượcgọilàtậpconthựcsựcủatậpmờ B,kýhiệulà A⊂Bkhi Alàtậpcon của Bvà A≠ B. A (x)≤ B (x),∀x ∈U   A (x)< B (x),∃x∈U  •Bù Tậpmờ Avà A đượcgọilàbùnhaunếu (x)= 1 (x),∀x ∈U (x ) + (x) = ,1∀x∈U A A hoặc A A Gv:TrịnhHuyHoàng Trang84
28. GiáotrìnhLogicToán Haihàmthànhviên A (x) và A (x) đốixứngvớinhauquatrụcđốixứnglàđường thẳng =0.5 •Giao Phépgiaocủatập Avàtập Bkýhiệulà A∩Bđượcđịnhnghĩabởi A∩B (x ) =min ( A (x), B (x)),x ∈U N ếua 1<a 2thì min (a 1,a 2)=a 1.Vídụ: min (0.5,0.7)=0.5. •Hợp Phéphợpcủatậpmờ Avàtậpmờ Bkýhiệulà A∪Bđượcđịnhnghĩa A∪B (x ) =max( A (x), B (x)),x ∈U N ếua 1<a 2thìmax (a 1,a 2)=a 2.Vídụ: max (0.5,0.7)=0.7. Vídụ: XéttậpvũtrụU={x 1,x 2,x 3,x 4,}vàhaitậpmờA,Bđượcđịnhnghĩabởibảngsau: X x1 x2 x3 x4 A(x) 0.2 0.7 1 0 B(x) 0.5 0.3 1 0.1 Khiđótacóhợpvàgiaocủa A(x)và B(x)nhưsau: X x1 x2 x3 x4 A(x) ∩ 0.2 0.3 1 0 B(x) B(x) ∪ 0.5 0.7 1 0.1 B(x) 1.2/Sốmờ(Fuzzyumbers) Mộtsốmờđượcđịnhnghĩadựatrêntậpvũtrụ RlàmộttậplồivàđãđượcchuNnhoá. Hình(2.a)và(2.b)thểhiệnhaisốlogic: Gv:TrịnhHuyHoàng Trang85
29. GiáotrìnhLogicToán Hình(2a):sốlogicvớimộtgiátrịlớnnhấtHình(2b):sốlogicvớinhiềugiátrịlớn nhất Khoảng[a1,a 2]đượcgọilàmộtkhoảngxácđịnhcủasốlogic.Chẳnghạnvớisốlogic x =a Mtronghình(2a)làmộtgiátrịlớnnhấttrongkhimộtđoạntronghình(2b)cóđộcaolớn nhấtlà1,thựcchấtđâylàmộtlátcắtvớiđộcaotincậylà1. Cácsốlogicsẽđượckýhiệubằngcácchữcáihoađượctinđậmnhư: A,B,C , và cáchàmthànhviênđượckýhiệubằngA(x), B(x), A(x), C(x), 1.3/Sốlogicdạnghìnhkhối Hàmthànhviên Acủamộtsốlogicdạnghìnhkhốithểhiệntronghình(3)códạng hìnhchuông,đốixứngquađườngthẳngx= p,xácđịnhtrongkhoảng[a1,a 2]vàđượcđặc 1 trưngbởihaithamsố p = (a + a ) và β∈ ,0( a − p) .Đỉnhchópcủahìnhchuônglàđiểm 2 1 2 2 (p,1);2pđượcgọilàbiênđộvàđượcđịnhnghĩanhưlàmộtđoạncắttạimứcαgiữahai 1 1 điểm ( p − β, ) và ( p + β , ) đượcgọilànhữngđiểmgiaonhau. 2 2 Đườngcongtronghình(3)đượcmôtảbởicácphươngtrìnhsau: Gv:TrịnhHuyHoàng Trang86
30. GiáotrìnhLogicToán  1 (x − a ) 2 ,a ≤ x ≤ p − β,  (2 p − β − a ) 2 1 1  1  1 2 − 2 (x − p) + ,1p − β ≤ x ≤ p + β, A =  2β (2.1)  1 2  2 (x − a2 ) ,p + β ≤ x ≤ a2  (2 p + β − a2 )  0 Sốlogiccủa(2.1)làmộtsốthựclâncậnp.Bởivìtừ“lâncận”làmơhồvàtrong ngữcảnhlogicnênkhôngđượcđịnhnghĩamộtcáchđơnđiệu.Điềuđóphụthuộcvàokhoảng xácđịnhđượcchọnvàbiênđộđượcdùngđểphảnánhmộttrườnghợpcụthể.Chẳnghạntập mờvềchiềucaocủanhữngngườiđànônglàmộttrườnghợpcụthểcủa(2.1)(nhánhtrái) trongkhoảng[160,200]vớia 1=140,p=200vàβ=30. Vídụ: GiásảnxuấtcủamộtsảnphNmlâncận28vàcóthểđượcmôtảbởisốlogicAtrong hình2.2nhưsautrongđóa 1=23,a 2=33,p=28vàβ=3 Hàmthànhviên A(x)của(2.1)cóthểnhậnđượctừ(2.1)bằngviệcthaythếa 1,a 2,p vàβbằngnhữnggiátrịđặcbiệtnhưsau: 1.4/Sốlogicdạngtamgiác Mộtsốlogicdạngtamgiáchoặcđơngiảnhơnlàsốlogictamgiácvớihàmthànhviên A(x) đượcđịnhnghĩatrên Rbởi:  x − a 1 ,a ≤ x ≤ a ,  a − a 1 M  M 1  x − a A= (x) = 2 ,a ≤ x ≤ a , A  M 2 (3.1) aM − a1  0  trongđó[a1,a 2]làkhoảngxácđịnhvàđiểm(a M,1)làđỉnh(xemhình) Gv:TrịnhHuyHoàng Trang87
31. GiáotrìnhLogicToán Thôngthườngtrongcácứngdụngđiểma M∈(a 1,a 2)đượcđặttạigiữacủakhoảngxác a + a định,vídụnhư a = 1 2 ,sauđóthaythếgiátrịnàyvàocôngthức(3.1)thuđược M 2  x − a a + a 2 1 ,a ≤ x ≤ 1 2 ,  a − a 1 2  2 1  x − a a + a A= (x) = 2 2 , 1 2 ≤ x ≤ a , A  2 (3.2)  a2 − a1 2  0  Tanóirằng(3.2)biểudiễnmộtsốlogictamgiácởgiữa,tươngtựnhưsốlogichình khốivàrấtdễđểdiễntảtừlâncân(lâncậntớiaM) Sốlogictamgiácrấtthườngđượcdùngtrongcácứngdụng(điềukhiểnmờ,quảnlý việcraquyếtđịnh,thươngnghiệpvàtàichính,xãhội, ).Chúngcómộthàmthànhviênbao l r gồmhaiđoạnthẳngtuyếntínhA (trái)vàA (phải)giaonhautạiđiểm(a M,1)tạonêndạng hìnhhọcvàcácphéptoántrênsốlogictamgiácrấtđơngiản. Giảsửchúngtađanggiảiquyếtvớimộtgiátrịkhôngchắcchắn,chúngtacóthểchỉ địnhgiátrịlớnnhấtvàgiátrịnhỏnhấtcóthểđượctrongkhoảng[a1,a 2].N ếuchúngtacóthể chỉđịnhmộtgiátrịa M∈[a1,a 2]đángtincậyđểthểhiệnmộtgiátrịchắcchắnthìđỉnhcủa tamgiácsẽlà(a M,1).Vìthếvớibagiátrịa 1,a 2vàa M cóthểtạolậpmộtsốtamgiácvàmôtả hàmthànhviêncủanó.Đólàtạisaosốtamgiáccònđượcviếtdướidạng: Gv:TrịnhHuyHoàng Trang88
32. GiáotrìnhLogicToán A=(a 1,a M,a 2) (3.3) Sốlogictamgiácởgiữalàđiểmđốixứngvớitrục.N ếua 1=a,a 2=athìa M=0.Do đóA=(a,0,a) N hánhphảicủaA=(a,0,a)khi0≤x≤ađượcdùngđểmôtảmộtsốdươngbévà đượckýhiệulàA r=(0,0,a).Tổngquáthơn,nhánhtráivànhánhphảicủasốtamgiáccóthể l r đượckýhiệutươngứnglàA =(a 1,a M,a M)vàA =(a M,a M,a 2)vàđượcxemlàsốtamgiác tráivàsốtamgiácphảitươngứng. 1.5/Sốlogicdạnghìnhthang Mộtsốlogiccódạnghìnhthanghaygọitắtlàsốlogichìnhthangđượcđịnhnghĩatrên Rnhưsau:  x − a1  ,a1 ≤ x ≤ b1 b1 − a1   ,1b1 ≤ x ≤ b2 A= A (x) =  x − a2  ,b2 ≤ x ≤ a2 b2 − a2  0 Sốlogichìnhthanglàmộttrườnghợpđặcbiệtcủasốlogicvớiđỉnhphẳng.Khoảng xácđịnhcủaAlà[a1,a 2]vàđoạnđỉnhphẳngvớimặtcắtα=1cógiátrịchiếulêntrụcx tươngứnglàb 1vàb 2.Với4giátrịa 1,a 2,b 1vàb 2chúngtacóthểxâydựngmộtsốlogichình thangvàđượckýhiệulà A=(a 1,b 1,b 2,a 2) N ếub 1=b 2,sốlogichìnhthangbiếnthànhsốlogictamgiácvàđượcghilà(a 1,a M, aM,a 2).VìthếmộtsốlogictamgiácA=(a 1,a M,a 2)cóthểđượcviếtdướidạngsốlogichình thanglàA=(a 1,a M,a M,a 2).Khiđó(a 1,a M,a 2)=(a 1,a M,a M,a 2) 1 N ếu[a1,b 1]=[a2,b 2]thìsốlogichìnhthanglàđốixứngquađường x = (b + b ) .Đó 2 1 2 làmộthìnhthangcântươngứngtrongkhoảng[b1,b 2]vànhữngsốthựclâncậntrongkhoảng này. Gv:TrịnhHuyHoàng Trang89
33. GiáotrìnhLogicToán Tươngtựnhưsốlogictráivàsốlogicphảicủatamgiác,chúngtacóthểđưarasố logichìnhthangtráivàsốlogichìnhthangphảilàcácphầncủasốlogichìnhthang. l A =(a 1,b 1,b 2,b 2) r A =(b 1,b 1,b 2,a 2) 2.Ápdụngcủalogicmờtrongdựđoán Việcdựđoáncungcấpnhữngkháiniệmcơsởchonhữngviệcsắpxảyra.Khảnăngdự đoánvàướclượngnhữngsựkiệntrongtươnglaiđòihỏiphảinghiêncứutrênnhữngnguồn dữliệumơhồvàxuấtpháttừnhữngthayđổinhanhchóngcủamôitrường,mộtcôngviệcmà dùnglogicmờđểgiảiquyếtphùhợphơndùngphươngphápphânloại.Việcphântíchnhững tìnhhuóngphứctạpcầnnhiềucôngsứcvànhiềuýkiếncủacácchuyêngia.N hữngýkiếncủa cácchuyêngiathườngkhôngtrùnghợpnhau,ítnhiềucũngcónhữngchỗgiốngnhauvà nhữngchỗđốilậpnhau.Chúngsẽđượckếthợplạihoặctậphợplạiđểtạoramộtquyếtđịnh. Trongphầnnàyphươngpháphọccủalogicmờtrungbìnhsẽđượcđềcậpvàđượcdùngnhư mộtcôngcụchínhđểtổphợpnhiềumôhìnhdựđoánkhácnhau(fuzzyDelphi,quảnlýdựán, dựđoántheoyêucầu). 2.1/Giátrịtrungbìnhtrongthốngkê Mộttrongnhữngkháiniệmquantrọngnhấttrongthốngkêđólàgiátrịtrungbình (average hay mean )củanphépđo,nýkiếnhoặcnđạilượngđượcbiểudiễnbởicácsốthực r1,r 2, ,r nđượcđịnhnghĩabởi n r r1 + r2 + + rn ∑i=1 i r = = ; ave n n (3.1) nhữngđạilượngnàyđượcxemcócùngmứcđộquantrọng.Giátrịtrungbìnhtiêubiểu hoặcđạidiệnchonđạilượng N ếucácđạilượngnàycómứcđộquantrọngkhácnhauđượcbiểudiễnbởicácsốthực λ1 , λ2 ,,, λn tươngứngthìkháiniệmtrọngsốtrungbìnhđượctínhtheocôngthức. Gv:TrịnhHuyHoàng Trang90
34. GiáotrìnhLogicToán n w λ1r1 + + λn rn rave = = w1r1 + + wn rn = ∑ wi ri λ1 + λn i=1 ỞđâyW iđượcgọilàtrọngsốvàđượcchobởicôngthứcsau: n λi Wi = .i = 2,1 , , n , W1 + +Wn = ∑Wi λ1 + + λn i=1 Trọngsốphảnánhtầmquantrọnghoặccườngđộcủar i Kháiniệmtrungbìnhcóthểđượctổngquáthoábằngviệcthaythếnhữngsốmờbằng nhữngconsốthựcr itrongcôngthức(1)và(2).Ởđâychúngtôigiớihạnlạithủtụctổngquát hoáđếnsốtamgiácvàsốhìnhthang. 2.2/Cácphéptoánvớisốtamgiácvásốhìnhthang a) Phépcộngtrênsốtamgiác (1) (1) (1) N gườitađãchứngminhđượcrằngtổngcủahaisốtamgiácA 1=(a 1 ,a M ,a 2 )và (2) (2) (2) A2=(a 1 ,a M ,a 2 )cũnglàmộtsốtamgiác (1) (1) (1) (2) (2) (2) A1+A 2=(a 1 ,a M ,a 2 )+(a 1 ,a M ,a 2 ) (1) (2) (1) (2) (1) (2) =(a 1 +a 1 ,a M +a M ,a 2 +a 2 ) (4) Côngthứctổngnàycóthểđượcmởrộngchonsốtamgiácvàcóthểápdụngchosố tamgiáctráihoặcsốtamgiácphải. Chẳnghạnnhư: r (1) (1) (1) (2) (2) (2) A1 +A 2=(a M ,a M ,a 2 )+(a 1 ,a M ,a 2 ) (1) (2) (1) (2) (1) (2) =(a M +a 1 ,a M +a M ,a 2 +a 2 ) l (1) (1) (1) (2) (2) (2) A1 +A 2=(a 1 ,a M ,a M )+(a 1 ,a M ,a M ) (1) (2) (1) (2) (1) (2) =(a 1 +a 1 ,a M +a M ,a M +a M ) Vídụ1 :Tínhtổngcủahaisốtamgiácsau: A1=(5,2,1), A2=(3,4,12) Dựatheocôngthức(4)tacó: A1+A 2=(5+(3),2+4,1+12)=(8,2,13) Dựavàohìnhnàytacóthểhiểunhưsau:N ếuA 1môtảcácsốthựclâncận2vàA 2mô tảcácsốthựclâncận4thìA 1+A 2sẽthểhiệncácsốthựclâncận2+4=2. b) hânsốtamgiácvới1sốthực Gv:TrịnhHuyHoàng Trang91
35. GiáotrìnhLogicToán PhépnhânmộtsốtamgiácAvớimộtsốthựcrcũnglàmộtsốtamgiác: A r = rA=r(a 1,a M,a 2)=( ra 1, ra M, ra 2) c) Chiasốtamgiácchomộtsốthực PhépchiasốtamgiácAchosốthựcrđượcxemnhưlàphépnhânsốtamgiácAvới 1 mộtsốthực vớir≠0. r A 1 a1 a M a21 = (a , a , a ) = ( , , ) r r 1 M 2 r r r Vídụ: • N hânsốtamgiácA=(2,4,5)vớisốthực2tađược: 2A=2(2,4,5)=(4,8,10) • ChiasốtamgiácA=(2,4,5)cho2tađược: A 1 = )5,4,2( = )5.2,2,1( 2 2 • Vìthế 2A ,8,4( 10) A = = A ; (2 ) = )5.2,2,1(2 = A 2 2 2 Cácphéptoántrênsốhìnhthangđượcthựchiệntươngtựnhưcácphéptoántrênsố tamgiác d) Cộnghaisốhìnhthang (1) (1) (1) (1) (2) (2) (2) PhépcộnghaisốhìnhthangA 1=(a 1 ,b 1 ,b 2 ,a 2 )vàsốA2=(a 1 ,b 1 ,b 2 , (2) a2 )cũnglàmộtsốhìnhthang. (1) (1) (1) (1) (2) (2) (2) (2) A1+A 2=(a 1 ,b 1 ,b 2 ,a 2 )+(a 1 ,b 1 ,b 2 ,a 2 ) (1) (2) (1) (2) (1) (2) (1) (2) =(a 1 +a 1 ,b 1 +b 1 ,b 2 +b 2 ,a 2 +a 2 ) (7) Côngthứctrên(3.7)cóthểđượctổngquáthoáchonsốhìnhthangvàcácsốhình thangtráivàcácsốhìnhthangphải. e) hânsốhìnhthangvớimộtsốthực Ar=rA=(ra 1,rb 1,rb 2,ra 2) (8) f) Chiasốhìnhthangvớimộtsốthực A 1 a b b a = A = ( 1 , 2 , 2 , 2 ) , r≠0 (9) r r r r r r g) Tổngsốtamgiácvớisốhìnhthang Gv:TrịnhHuyHoàng Trang92
36. GiáotrìnhLogicToán (1), (1) (1) (1) XétsốtamgiácA 1=(a 1 ,a M ,a 2 )màcóthểhiệndiệnnhưmộtsốhìnhthang(a 1 , (1) (1) (1 (2) (2) (2) (2) aM ,a M ,a 2 )vàsốhìnhthangA2=(a 1 ,b 1 ,b 2 ,a 2 ).Dùngcôngthức(7)tacó (1) (1) (1) (1 (2) (2) (2) (2) A1+A 2=(a 1 ,a M ,a M ,a 2 )+(a 1 ,b 1 ,b 2 ,a 2 ) (1) (2) (1) (2) (1) (2) (1) (2) =(a 1 +a 1 ,a M +b 1 ,a M +b 2 ,a 2 +a 2 ) (10) 2.3/Trungbìnhtronglogicmờ a) Côngthứctrungbìnhtrongtamgiác (i) (i) (i) XétnsốtamgiácA i=(a 1 ,a M ,a 2 ),I=1, ,n. Sửdụngphépcộngcácsốtamgiácvàphépchiasốtamgiácvớimộtsốthựcsẽchota sốtrungbìnhtrongtamgiácA ave A + + A A = 1 n ave n (a )1( ,a )1( ,a )1( ) + + (a(n) ,a(n) ,a(n) ) = 1 M 2 1 M 2 n n n n ( a(i) , a(i) , a(i) ) = ∑i=1 1 ∑i=1 M ∑i=1 2 n Vàcũnglàmộtsốtamgiác n n n  1 (i) 1 (i) 1 (i)  Aave = (m1, mM , m )2 =  ∑ a1 , ∑ aM , ∑ a2  (11)  n i=1 n i=1 n i=1  Vídụ: (i)ChosốtamgiácA 1vàA 2nhưtrongvídụ1.Khiđósốtrungbìnhcủahaisốđólà: A1 + A2 (− ,2,8 13) A = = = (− )5.6,1,4 ave 2 2 r l (ii)SốtamgiácA l ,A 2vàA 3 trongvídụ2cósốtrungbìnhlà: r l A1 + A2 + A3 ,9,4( 12) A = = = .1( 33 )4,3, ave 3 3 b) Côngthứctrungbìnhtrongtamgiáccótrọngsố Gv:TrịnhHuyHoàng Trang93
37. GiáotrìnhLogicToán N ếu những số thực λi biểu diễn mức độ quan trọng của các số tam giác A = (a (i) , a (i) , a (i) ) i 1 M 2 ,i=1, n.Ápdụngcôngthức(2),(3)và(11)tathuđượctrungbình trongtamgiáccótrọngsố. w λ1 A1 + + λn An Aave = λ1 + + λn = w (a )1( , a )1( , a )1( + + w (a (n) , a (n) , a (n) ) 1 1 M 2 n 1 M 2 )1( )1( )1( (n) (n) (n) = (w1a1 , w1a M , w1a2 + + (wn a1 , wn a M , wn a2 ) )1( (n) )1( (n) )1( (n) = (w1a1 + + wn a1 , w1a M + + wn a M , w1a2 + + wn a2 ) vàcóthểđượcviếtngắngọnlạinhưsau: n n n w w w w  (i) (i) (i)  Aave = (m1 , mM , m2 ) = ∑ wi a1 , ∑ wi aM , ∑ wi a2   i=1 i=1 i=1  Côngthứctrungbìnhđốivớisốhìnhthangcóthểđượcchuyểnhoátươngtựnhư(11) và(12)nhưsau: c) Côngthứctrungbìnhtronghìnhthang (i) (i) (i) (i) Giả sử Ai = (a1 ,b1 ,b2 ,a2 ),i =1, ,n là các số hình thang. Khi đó số trung bìnhlà: Aave = (m1 ,mM1 ,mM 2 ,m2 ) (a )1( ,b )1( ,b )1( ,a )1( ) + + (a (n) ,b (n) ,b (n) ,a (n) ) = 1 1 2 2 1 1 2 2 n n n n n ( a (i) , b (i) , b (i) , a (i) ) = ∑i=1 1 ∑i=1 1 ∑i=1 2 ∑i=1 2 n d) Côngthứctrungbìnhtronghìnhthangcótrọngsố w w w w w Aave = (m1 ,mM 1 ,mM 2 ,m2 ) w (a )1( ,b )1( ,b )1( ,a )1( ) + + w (a (n) ,b (n) ,b (n) ,a (n) ) = 1 1 1 2 2 n 1 1 2 2 n n n n n ( w a (i) , w b (i) , w b (i) , w a (i) ) ∑i=1 i 1 ∑i=1 i 1 ∑i=1 i 2 ∑i=1 i 2 = n Gv:TrịnhHuyHoàng Trang94
38. GiáotrìnhLogicToán 2.4/DựđoánbằngphươngphápDelphikếthợplogicmờ FuzzyDelphilàmộtcảitiếncủaphươngphápDelphicổđiểndùngđểdựđoáncácsự kiệntrongkhoahọc.Phươngphápnàyđượcđềxuấtvàothậpniên60bởiRandCorporation, Caliornia. Cácbướcchínhđểdựđoánbằngphươngphápnàynhưsau: (i) Cácchuyêngiacóuytíntronglĩnhvựccầndựbáosẽđưaradựđoánvềthời điểmdiễnracácsựkiện(khoahọc,kỹthuật,kinhtế )mộtcáchđộclập. (ii) Cácdữliệuthuthậpđượcphântíchvàtínhgiátrịtrungbình.Sauđó,cáckết quảphântíchđượcgửingượclạichocácchuyêngia. (iii) Cácchuyêngiadựatrênkếtquảnhậnđượcđểtiếnhànhdựđoánlạirồigửikết quảmớichongườitổchứcvàkếtquảphântíchmớisẽđượcgởilạichocácchuyêngia. (iv) Quátrìnhnàycóthểđượclặplạinhiềulầnchođếnkhikếtquảdựđoáncủacác chuyêngiahộitụvềmộtkếtquảmàngườitổchứcvừaýnhất.Thôngthườngthìchỉcầnlặp lại2hoặc3lần. Tuynhiên,việcdựđoáncómộtkhókhănlàcácthôngtincóđượcthườngkhôngđầy đủvàthiếutínhchínhxác.Hơnnữamứcđộchínhxáccủacácdựđoánphụthuộcrấtnhiều vàoquanđiểmchủquancũngnhưkhảnăngcủacácchuyêngia.Dođó,thayvìsửdụngcác consốchínhxáctrongquátrìnhdựđoánchúngtasẻsửdụng“sốmờ”.Sốtamphầnrấtphù hợpchoviệcđưaracácdựđoánbằngcáchcho3giátrị:giátrịnhỏnhất,giátrịlớnnhấtvà giátrịtintưởngnhất.Khiđógiátrịtrungbìnhsẽđượctínhdựatrênphươngpháptínhtrị trungbìnhcủacác“sốmờ”đãtrìnhbàybêntrên. ÝtưởngkếthợpphươngphápDelphivớilogicmờđượcKaufmanvàGuptađềxuất vàonăm1988gồmcácbướcsau: - Bước1:ChuyêngiaE iđượcyêucầudựđoánthờiđiểmxảyramộtsựkiệnbằng cáchchobiếtngàysớmnhất,ngàytrểnhấtvàngàytintưởngnhất.Thôngtincácchuyêngia cungcấpsẽcódạng: (i) (i ) (i) Ai = (a1 , aM ,a2 ),i = 1, , n - Bước2:Trướctiênchúngtasẽtínhgiátrịtrungbình Aavg (m ,1 mM , m2 )củacáckết quảthuđược.Sauđó,chúngtatiếnhànhtínhđộlệchtâmcủatừngkếtquảdựđoántươngứng củacácchuyêngiatheocôngthứcsau: (i) (i) (i) Aavg − Ai = (m1 − a1 , mM − aM ,m2 − a2 ) n n n  1 ()()i i 1 ()()i i 1 ()()i i  =  ∑ a1 − a1 , ∑ aM − aM , ∑ a2 − a2   n i=1 n i=1 n i=1  Giátrịlệchtâmcóđượcsẽđượcgửitrởlạichocácchuyêngiatươngứngđểtiếnhành dựđoánlại. - Bước3:Mỗichuyêngiasaukhinhậnđượckếtquảphảnhồisẽtiếnhànhdựđoán lạivàchomộtkếtquảmớidạng: Gv:TrịnhHuyHoàng Trang95
39. GiáotrìnhLogicToán (i) (i) (i) Bi = (b1 ,bM ,b2 ),i = 1, ,n Quátrìnhnàyđượclặplạinhiềulầnchođếnkhi2kếtquảtrungbìnhliêntiếplàtương đốigiốngnhau. - Bước4:Côngviệcdựđoáncóthểđượctiếnhànhlạinếusaukhicókếtquảlại cóthểnhữngthôngtinmớilàmảnhhưởngđếnkếtquảcóđược. Phươngphápfuzzydelphilàphươngpháptiêubiểuchocáchdựđoánbằngcáchkết hợpquanđiểmcủanhiềuchuyêngiađầungành. Bàitậpminhhọa1:Ướclượngthờiđiểmrađờisảnphmmới Kếtquảdựđoánthờiđiểmxuấthiệnmáytínhcókhảnăngsuynghĩcủa15chuyêngia máytínhđượcchotrongbảngsau(lầnthứnhất). Ei Ai Thờiđiểm Thờiđiểmcó Thờiđiểm sớmnhất khảnăngnhất muộnnhất (1) (1) (1) E1 A1 a1 = 1995 aM = 2003 a2 = 2020 (2) (2) (2) E2 A2 a1 = 1997 aM = 2004 a2 = 2010 (3) (3) (3) E3 A3 a1 = 2000 aM = 2005 a2 = 2010 (4) (4) (4) E4 A4 a1 = 1998 aM = 2003 a2 = 2008 (5) (5) (5) E5 A5 a1 = 2000 aM = 2005 a2 = 2015 (6) (6) (6) E6 A6 a1 = 1995 aM = 2010 a2 = 2015 (7) (7) (7) E7 A7 a1 = 2010 aM = 2018 a2 = 2020 (8) (8) (8) E8 A8 a1 = 1995 aM = 2007 a2 = 2013 (9) (9) (9) E9 A9 a1 = 1995 aM = 2002 a2 = 2007 (10) (10) (10) E10 A10 a1 = 2008 aM = 2009 a2 = 2020 (11) (11) (11) E11 A11 a1 = 2010 aM = 2020 a2 = 2024 (12) (12) (12) E12 A12 a1 = 1996 aM = 2002 a2 = 2006 (13) (13) (13) E13 A13 a1 = 1998 aM = 2006 a2 = 2010 (14) (14) (14) E14 A14 a1 = 1997 aM = 2005 a2 = 2012 (15) (15) (15) E15 A15 a1 = 2002 aM = 2010 a2 = 2020 Tổngcộng 29996 30109 30210 15 15 15  1 ()i 1 ()i 1 ()i  Khiđótacó: Aavg =  ∑ a1 , ∑ aM , ∑ a2  15 i=1 15 i=1 15 i=1  Gv:TrịnhHuyHoàng Trang96
40. GiáotrìnhLogicToán  29996 30109 30206  =  , ,  = ()1999 ,7. 2007 ,3. 2014  15 15 15  a haylấygầnđúngtacó: Aavg = (2000,2007,2014) Độlệchtâmcủacácdựđoáncủacácchuyêngiatínhđượcnhưtrongbảngsau. (i) (i) (i ) Ei m1 − a1 mM − aM m2 − a2 E1 5 4 6 E2 3 3 4 E3 0 2 4 E4 2 4 6 E5 0 2 1 E6 5 3 1 E7 10 11 6 E8 5 0 1 E9 5 5 7 E10 8 2 6 E11 10 13 10 E12 4 5 8 E13 2 1 4 E14 3 2 2 E15 2 3 6 Giảsửrằngngườitiếnhànhcuộcphỏngvấnchưahàilòngvớikếtquảthuđược.Khi đó,độlệchtâmtínhđượctrongbảngtrênđượcgửilạichocácchuyêngiatươngứngxemxét vàchoramộtdựđoánmớivớikếtquảnhưtrongbảngsau. Ei Bi Thờiđiểm Thờiđiểm Thờiđiểm sớmnhất cókhảnăngnhất muộnnhất (1) (1) (1) E1 B1 b1 = 1996 bM = 2004 b2 = 2018 (2) (2) (2) E2 B2 b1 = 1997 bM = 2004 b2 = 2011 (3) (3) (3) E3 B3 b1 = 2000 bM = 2005 b1 = 2011 (4) (4) (4) E4 B4 b1 = 1998 bM = 2003 b2 = 2010 Gv:TrịnhHuyHoàng Trang97
41. GiáotrìnhLogicToán (5) (5) (5) E5 B5 b1 = 2000 bM = 2005 b2 = 2015 (6) (6) (6) E6 B6 b1 = 1997 bM = 2009 a2 = 2015 (7) (7) (7) E7 B7 b1 = 2005 bM = 2015 b2 = 2016 (8) (8) (8) E8 B8 b1 = 1996 bM = 2007 b2 = 2013 (9) (9) (9) E9 B9 b1 = 1997 bM = 2004 b2 = 2010 (10) (10) (10) E10 B10 b1 = 2004 bM = 2009 b2 = 2017 (11) (11) (11) E11 B11 b1 = 2004 bM = 2015 b2 = 2016 (12) (12) (12) E12 B12 b1 = 1996 bM = 2004 b2 = 2006 (13) (13) (13) E13 B13 b1 = 1998 bM = 2006 b2 = 2010 (14) (14) (14) E14 B14 b1 = 1997 bM = 2004 b2 = 2012 (15) (15) (15) E15 B15 b1 = 2001 bM = 2009 b2 = 2015 Tổngcộng 29986 30103 30198 Khiđótacó: Bavg = (1999.07,2006 ,9. 2013 2. ) a Haygầnđúngtacó: Bavg = (1999,2007,2013) µ 1 Aavg Bavg x 1999 2000 2007 2013 2014 N hưvậytacókếtquảtrungbìnhcủa2lầnliêntiếplàtươngđốigiốngnhau.Dođó, chúngtacóthểngưngviệckhảosátvàchuyểnsanggiaiđoạndiểngiảikếtquảthuđược.Từ kếtquảthuđượcchúngtacóthểdựđoánlàsảnphNmmớicóthểxuấthiệntrongkhoảngthời giantừ1999đến2013.Hơnnữaviệcgiảimờkếtquảthuđượcchúngtacóthờiđiểmcókhả năngnhấtlàvàokhoảngnăm2007. Gv:TrịnhHuyHoàng Trang98
42. GiáotrìnhLogicToán 2.5/PhươngphápFuzzyDelphicótrọngsố: Sựthậtlàtrongcáclĩnhvựcdựđoánkhácnhau,khảnăngamhiểucủatừngchuyêngia cũngkhácnhau.Dođó,cácdựđoáncủacácchuyêngiakhácnhaukhôngthểcócùngmộtđộ tincậynhưnhau.N hưvậymứcđộảnhhưởngcủacácdựđoáncủacácchuyêngiatươngừng đốivớikếtquảcuốicùnglàhoàntoànkhácnhau.Điềunàydẫnđếnmộtcảitiếncủaphương phápFuzzyDelphibắngcáchthêmvàomộttrọngsốwichotừngchuyêngiavớiđiềukiện n ∑ wi = 1.KhiđócácbướccủaphươngphápFuzzyDelphivẫnkhôngđổi,chỉcókháclàtrước i=1 khitínhgiátrịtrungbìnhchúngtaphảinhânkểtquảdựđoáncủacácchuyêngiavớitrọngsố tươngứngcủachuyêngiađó. Bàitậpminhhọa2 :Vớikếtquảdựđoántrongbàitậptrướcnhưnggiờđâychúngta cóthêmbảngtrọngsốcủatừngchuyêngiacụthể.Khiđócáckếtquảtínhtoáncóđượcnhư trongbảngsau. (i) (i) (i) Ei wi wi × a1 wi × aM wi × a2 E1 0.1 199.5 200.3 202 E2 0.05 99.85 100.2 100.5 E3 0.5 200 200.5 201 E4 0.05 99.9 100.15 100.4 E5 0.1 200 200.5 201.5 E6 0.05 99.75 100.5 100.75 E7 0.05 100.5 100.9 101 E8 0.1 199.5 200.7 201.3 E9 0.05 99.75 100.1 100.35 E10 0.05 100.4 100.45 101 E11 0.05 100.5 101 101.2 E12 0.05 99.8 100.1 100.3 E13 0.1 199.8 200.6 201 E14 0.05 99.85 100.25 100.6 E15 0.05 100.1 100.5 101 Tổng 1 1999.2 2006.75 2013.9 w N hưvậytacó: Aavg = (1999 ,2. 2006.75,2013 9. ) = (1999,2007,2014) Gv:TrịnhHuyHoàng Trang99
43. GiáotrìnhLogicToán 2.6/ỨngdụngFuzzyPerttrongviệcquảnlýcácđềán Quảnlýđềánlàmộtcôngviệcphứctạp,đặcbiệtlàviệcxácđịnhtiếntrìnhthựchiện cáccôngviệc.Mỗiđềáncómộtthờiđiểmbắtđầuvàmộtthờiđiểmkếtthúcxácđịnh.Tương tựmỗicôngviệcbêntrongđềáncũngcómộtthờiđiểmbắtđầuvàkếtthúcxácđịnh.Các côngviệctrongđềánphảiđượcthựchiệntheođúngmộttrìnhtựnhấtđịnh.Dođó,thờiđiểm hoàntấtcủacáccôngviệccũngphảiđượcdựđoántrước. PERTvàCPMcổđiển Haikỹthuậtcổđiểndùngđểhoạchđịnhvàkiểmsoátđồáncổđiểnlà:PERT(Project EvaluationandReviewTechnique)vàCPM(CricticalPathMethod).PERTđượcđềxuấtbởi hảiquânMỹtrongquátrìnhlênkếhoạchsảnxuấttàingầmnguyêntửPolaris.CPMcũng đượcđềxuấttrongcùngthờigianbởicácnhànghiêncứuởRemingtonRandvàDuPontđể bảoquảnnhàmáyhóachất.Cóvàisựtươngđồnggiữa2kỹthuậtnàyvàchúngthườngđược dùngchungvớinhaunhưlàmộtphươngphápthốngnhất. ĐểminhhọacáchsửdụngPERTvàCPM,chúngtasẽkhảosátquamộtđềánđược thựchiệnbởiFogattyvàHoffmannvàonăm1983.Lịchtrìnhthựchiệncáccôngviệcđược chotrongbảngsau. Hành Hành Hành Hành Thời gian động động phía động đồng độngphíasau dự kiến hoàn tất trước thời (ngày) A B,C 35 B A C D 35 C A B SE 55 D B C,E F 35 E C D F 50 F D,E G 30 G F G 30 H F 10 Từnhữngthôngtintrongbảngtrên,chúngtacókếhoạchthựchiệncáccôngviệcnhư trongsơđồsau. Gv:TrịnhHuyHoàng Trang100
44. GiáotrìnhLogicToán A C E F G H 35 55 50 30 30 10 B D 35 35 Sơđồkếhoạchthựchiệncáccôngviệcchochúngtathấymộtcáchrõràngmốilệ thuộcvềthờigianthựchiệncáccôngviệctrongtoànbộđềán. Đườnggăngcủasơđồchínhlàchuổicáccáccôngviệctheotrìnhtựthờigiantừ đầuchođếnkếnthúcđềánmàcóthờigiancầnthiếtđểhoàntấtlàdàinhất.N hưvậythờigian cầnthiếtđểhoàntấtđềáncũngchínhlàtổngthờigiancủađườnggăng. Dựavàosơđồkếhoạchthựchiệncáccôngviệc,chúng ta có thể xác định đườnggăngcủađềán.Trongsơđồtrên,đườnggăngchínhlàđườngnốibởicácdấumũitên: A,C,E,F,GvàH.Khiđótacótổngthờigianđểhoàntấtđềánlà35+55+50+30+30 +10=210ngày.Chúngtacóthểthấyrằng2côngviệcBvàDkhôngnằmtrênđườnggăng. Haicôngviệcnàycóthểkhônghoànthànhđúngtiếnđộnhưngthờigiantrểkhôngquá35 ngày.N ếukhôngthìcôngviệcFtrênđườnggăngsẽbịảnhhưởng. PERTdựatrênniềmtin Chúngtakhôngthểdựđoánchínhxácthờiđiểmhoàntấtcáccôngviệc.Đểgiảiquyết vấnđềnàycácnhànghiêncứumởrộngđãtăngcườngđộchínhxáccủakỹthuậtPERTbằng cáchsửdụngxácsuấtvàthốngkê.ĐểtiếnhànhdựđoánbằngkỷthuậtPERT,cácchuyêngia phảiđưara3dựđoánvềthờiđiểmhoàntấtcáccôngviệc:thờiđiểmtốtnhấtt1nếunhưmọi chuyệndiễnratốtđẹp,thờiđiểmkhảthinhấtnếumọichuyệndiễnratheođúngkếhoạchvà thờiđiểmtrongtrườnghợpxấunhấtnếunhưcósựcốxảyra.Khiđóthờiđiểmhoàntấttừng côngviệcđượctínhtheocôngthức: t + 4t + t t = 1 M 2 (3.22) e 6 ThờigiantổngcộngđềhoàntấtcảđềánT echínhlàtổngcáct ecủacáccôngviệctrên đườnggăng.Kếtquảướclượngtínhtheocôngthức3.22sẽgầngiốngvớicácgiátrịtrongcác ôvuôngghitrênsơđồhoạchđịnnhcáccôngviệcvàthờigianướclượnghoàntấtcáccông việccũngsẽmangnhiềutínhthựctếhơn.Tiếptheochúngtasẽphảitínhđộlệchtâmchocác tevàtiếnhànhnhữnghoạtđộngphântíchthốngkêkhác. Đểđơngiản,chúngtađềxuất mộtgiảiphápkhácthaythếchoviệcsửdụngkháiniệmxácsuấttrongPERT. Cácgiátrịướclượngt 1,t M,vàt 2docácchuyêngiađưaradựatrênkinhnghiệmvà kiếnthứctuymangnhiềutínhchủquannhưngkhônghềápđặt.Chínhvìvậybảnchấtcủa việckhôngchắcchắntrongcácdựđoánlàdotínhkhôngrõràngcủasựviệchơnxácsuất xảyrasựviệc.PERTkhôngđềxuấttínhcácgiátrịt 1,t Mvàt 2màchỉphátbiểurằngcácgiátrị đócầnđượcướclượngvàkếthợplạiđểchorakếtquảcuốicùngdựavàocôngthức3.22. Gv:TrịnhHuyHoàng Trang101
45. GiáotrìnhLogicToán SửdụngPERTkếthợpvớilogicmờđểdựđoán ChúngtasẽcảitiếnPERTsửdụngFuzzyDelphiđểướclượngt 1,t Mvàt 2chotừng côngviệc.Cácchuyêngiasẽđưaradựđoánvềthờiđiểmhoànthànhcáccôngviệcdướidạng sốtamphần.Khiđóứngvớitừngcôngviệcchúngtasẽcómộtconsốtrungbìnhcũngcó dạngsốtamphần.Tiếptheochúngtasẽgiảimờconsốnàyđểđượcmộtgiátrịthựcdựđoán thờigiancầnthiếtđềhoàntấtcôngviệc. Bàitậpápdụng: ChúngtaxemxétlạivídụcủabàitậptrướcvàbỏđicácgiátrịdựđoántheoPERTcổ điển.Giảsửthờigiancầnthiếtđểthựchiệnmỗicôngviệcđượcdựđoánbởi3chuyêngia khácnhau.Mỗicôngviệctrongđềánsẽcómộtconsốướclượngdạngtriangular.Trong bảngsaulàkếtquảướclượngchocôngviệcA. A Chuyên Ti Thời Thời Thời gia giannhanh giancóthể gianlâu nhất nhất nhất A E1 T1 33 35 38 A E2 T2 33 34 37 A E3 T3 32 36 39 Tổng 3 98 105 114 T A số ∑ i i=1 Tổngkếtcáckếtquảdựđoánchúngtađượcmộtgiátrịtrungbìnhcủathờigiancần thiếtđểhoànthànhcôngviệcA A  98 105 114  Tave =  , ,  = ()()32.67,35,38 ≈ 33,35,38  3 3 3  A Đểgiảimời Tave ,chúngtasửdụngmộttrongcáccôngthứccủacôngthức3.15 32.67 + 35 + 38 t ()1 = = 35.22 max 3 32.67 + 2 *35 + 38 t ()2 = = 35.17 max 4 32.67 + 4 *35 + 38 t ()3 = = 35.11 max 6 Chúngtacóthểthấyrằngdùtínhtheocôngthứcnàochúngtacũngcógiátrịgầnvới consố35ngày. Gv:TrịnhHuyHoàng Trang102
46. GiáotrìnhLogicToán Tươngtựcácnhómchuyêngiakhácsẽcókếtquảướclượngchocáccôngviệccònlại nhưtrongbảngsau. Công Thời Thời Thời Thời việc giantrung giantốt giandự gianlâu bình nhấtt 1 kiếnt M nhấtt 2 A A Tave 33 35 38 B B Tave 32 35 38 C C Tave 51 54 58 D D Tave 32 34 36 E E Tave 46 50 53 F F Tave 27 30 33 G G Tave 27 29 32 H H Tave 7 10 12 Khigiảimờcácgiátrịtrungbìnhtrongbảngtrênchúngtacósơđồthựchoạchđịnh côngviệcnhưsau. A C E F G H 35 54 50 30 29 10 B D 35 34 i SốtamphầnTcầnthiếtđểhoàntấtdựánchínhlàtổng Tave ,i=A,C,E,F,G,H. A C E F G H T = Tave + Tave + Tave + Tave + Tave + Tave = (192,208,226) N hưvậythờigiancầnthiếtđểhoànthànhdựánkhoảngtừ192đến226ngày, mà nhiềukhảnănglà208ngàycóđượcbằngcáchgiảimờsốT. Lênlịchcấppháttàinguyên Khoảngthờigiancầnthiếtđểhoàntấtcôngviệccóảnhhưởngmậtthiếtđếncôngviệc phâncôngnhânvậtlực.Tấtcảmọngườiđềucócảmnhậnrằngcầnphảixácđịnhđườnggăng củasơđồhoạchđịnhcôngviệctrướckhitiếnhànhphâncôngtàinguyênthựchiệncáccông việc.Việcdựđoánthờigiancầnthiếtđểhoànthànhdựánđượcthựchiệnvớigiảthuyếtlà Gv:TrịnhHuyHoàng Trang103
47. GiáotrìnhLogicToán cáctàinguyêncầnthiếtluônluônsẵnsàncấpphátkhicôngviệccầnđến.Tuynhiêntrong thựctếcórấtnhiềuvấnđềphứctạpnảysinh.Thôngthườngngườiquảnlýdựáncóthểtrang bịthêmcáctàinguyêncầnthiếtđểrútngắnthờigianhoàntấtdựán.Songđiềuđóđồngnghĩa vớiviệctăngchiphíthựchiệndựán.N hưvậyphươngcáchtốtnhấtlàchúngtatìmcáchđể rútngắnthờigiantiếnhànhdựán. Bàitậpápdụng(Phần2) Trướckhitiếnhànhthựchiệnviệcrútngắnthờigian,chúngtacócácquyướcnhưsau. tn:thờigiandựđịnhđểhoàntấtcôngviệc tc:thờigianngắnnhấtcóthểhoàntấtcôngviệc Cn:chiphídựkiếnđểhoàntấtcôngviệc Cc:chiphíthấpnhấtcóthể Đểrútngắnthờigianhoàntấtdựánthựcchấtlàđirútngắnđườnggăngcủasơđồ hoạchđịnhcáccôngviệc.ViệcrútngắnthờigianthựchiệncáccôngviệcBvàDhoàntoàn khônglàmgiảmthờigianhoàntấtdựán.Song,chúngtacóthểsửdụngmộtphầntàinguyên đểthựchiệnBvàDdùngchoviệcthựchiệncôngviệcCvàE.Tuynhiênởđâychúngtagiả sửkhôngthựchiệngiảiphápnày. Giảsửrằngkếtquảdựđoánthòigianhoàntấttừngcôngviệcđãđượcthựchiệnvàcó kếtquảnhưtrongbàitậptrên. N hưvậychúngtacònphảitiếnhànhdựđoánthờigianngắnnhấtcóthểt c,chiphídự kiếnC nvàchiphíthấpnhấtC ccủatừngcôngviệctươngbằngcáchsửdụngFuzzyDelphi. Giátrịsaukhiđãgiảimờchocácđạilượngtrênlầnlượtlà t , t , C vàC nmax cmax nmax cmax TiếptheochúngtaxétquavídụvềướclượnggiátrịC nchohànhđộngA.Cácgíatrị cònlạiđượcướclượngbằngcáchtươngtự. ViệcướclượnggiátrịC nđượctiếnhànhbỡi3chuyêngia.Kếtquảướclượngcủatừng chuyêngialàmộtconsốdạngtriangularC n=(C n1 ,C nM ,C n2 ).TrongđóC n1 làchiphícho trườnghợptốtnhất,C nM làchiphítrongtrườnghợpbìnhthườngvàC n2 làchiphíchotrường hợpxấunhất. Chuyên Cn1 CnM Cn2 gia E1 18000 20000 22000 E2 19500 21000 22000 E3 17000 19500 21000 Tổng 54500 60500 65000 Khiđótacó: C A = (18166.67,20166.67,21166.67) ≈ (18000,20000,21500) nave Gv:TrịnhHuyHoàng Trang104
48. GiáotrìnhLogicToán Tiếnhànhgiảimờconsốtrêntađượcchiphíướctínhkhoảng20000. Cácnhómchuyêngiakhácsẽướclượngcácgiátrịcònlạichotấtcảcáccôngviệctrên đườnggăngcủasơđồhoạchđịnhcôngviệcvớikếtquảnhưtrongbảngbêndưới. Đểtiếnhànhrútngắnthờigiancủađườnggăng,PERTđưarakháiniệmđộtrượtgiá đượctínhnhưtrongcôngthứcsau C − C k = n max c max tn max − tc max Tronghìnhbêndưới,chúngtacóthểthấyrõrằngkhigiátrịt nmax giảmvềt cmax thìgiá trịC nmax sẽtănglêngiátrịC cmax chi ph í Ccmax Cnmax thời gian tcmax tnmax Giảsửrằngviệckếtquảướclượngcủacácchuyêngiavàhệsốktươngứngcủacác côngviệctrongdựánnhưtrongbảngsau Cô tn tc Cnmax Ccmax Hệsốk ngviệc max max ($/ngày) A 35 25 20000 26000 600 C 54 30 30500 40500 417 E 50 32 28000 35000 389 F 30 22 18500 25000 813 G 29 20 15000 19000 444 H 10 8 7000 8000 500 N óichungviệctrangbịthêmtàinguyênđểrútngắnthờigianhoàntấtdựánnênđược bắtđầuvớinhữngcôngviệccóhệsốtrượtgiáthấpnhất. Công Thờigian Chiphí Hệsốtrượt việc rútngắnđượct nmax vượttrộiC cmax giá($/ngày) Gv:TrịnhHuyHoàng Trang105
49. GiáotrìnhLogicToán –t cmax –C nmax E 18 7000 389 C 24 10000 417 G 9 4000 444 H 2 1000 500 A 10 6000 600 F 8 6500 813 Giảsửrằngngườiquảnlýdựánmuốnrútngắnđộidàiđườnggăngtừ208ngàyxuống còn108ngày,tứccầngiảm28ngày.Khiđóvớisốliệunhưbảngtrênchúngtathấyrằng trongsốcáccôngviệctrênđườnggăngthìcôngviệcEcóhệsốtrượtgiáthấpnhất.N hưvậy bằngcáchđầutưthêm7000$chúngtacóthểrútngắnđược18ngàydođócầnphảirútthêm 10ngàynữa.CôngviệccóhệsốkthấpnhấttiếptheolàcôngviệcCvàđểrútngắnthêm10 ngàychúngtacầnđầutưthêm10x417=4170$. BÀITẬP 1. Cho2tậpmờA,B,CtrongX={1,2,3,4,5,6,7,} X 1 2 3 4 5 6 7 A 0.4 0.1 0.8 0 0.7 1 0.9 B 0.7 0.1 0.3 0.4 0.8 0.9 0 TìmA ∪B,A ∩B,A\B, ¬A ∩ ¬B 2. Cho3tậpmờA,B,CtrongX={1,2,3,4,5,6,7,8} X 1 2 3 4 5 6 7 8 A 0.8 0.3 0.5 0 0.4 1 0.6 0.1 B 0.5 0.9 0.2 0.4 0.8 0.5 0 0.7 C 0.2 0.1 0.8 0.5 0.3 0.7 0.9 0.3 a. Kiểmchứngcôngthức (A ∪B) ∩C=(A ∩C) ∪(B∩C) (A ∩B) ∪C=(A ∪C) ∩(B∪C) Gv:TrịnhHuyHoàng Trang106
50. GiáotrìnhLogicToán b. TìmA\B, ¬A ∩B, ¬A ∩(¬B ∪ ¬C) 3. Chocáctậpmờsau:  x 0≤x ≤ 3 3  1 3≤x ≤ 5 TậpmờAđịnhnghĩadựatheohàmthànhviên: A =  7 − x  5≤x ≤ 7  2  0x ≥ 7  x 0≤x ≤ 2 2  4 − x TậpmờBđịnhnghĩadựatheohàmthànhviên: B = 2 ≤x ≤ 4  2 0x ≥ 4   a. VẽđồthịbiểudiễncáctậpmờAvàB. b. Biểudiễn AA,∩ BA , ∪ B trênđồthị. Đềthithamkhảotrắcnghiệmgiữakỳ(30%tổngđiểmmônhọc) Trắcnghiệm: 1. Phátbiểunàolàmệnhđề? a. Hômnàytrờithậtđẹpquá! b. N gàymailàthứ7,bạncóbiếtkhông? c. Mộtconngựađaucảtàubỏcỏ. d. Thôiemhãyvề,quêhươngđangchờemđó. 2. Chântrịcủamệnhđề ∀∈xRx,[( −=→ 3 0) ( xx2 − 4 += 3 0)] là: c. Đúng. b.Sai. 3. Chântrịcủamệnhđềlượngtựhóa ∃∈∃∈xRyRxy, ,[( − 2 =∧ 5) (2 xy += 4)] là: a. Đúng. b.Sai. 4. Phủđịnhcủamệnhđề ∃∈∀∈∀∈xRyRzRx, , ,[(2 = yz 2 + 2 ) →≥ ( xz )] là: a. ∀∈∀∈∃∈xRyRzRx, , ,[(2 = yz 2 + 2 ) →≥ ( xz )] b. ∃∈∃∈∃∈xRyRzRx, , ,[(2 ≠ y 2 + z 2 ) ∧≥ ( xz )] c. ∀∈∃∈∃∈xRyRzRx, , ,[(2 = y 2 + z 2 ) ∧< ( xz )] d. ∀∈∃∈∃∈xRyRzRx, , ,[(2 ≠ yz 2 + 2 ) →< ( xz )] e. Tấtcảđềusai 5. Phủđịnhcủabiểuthứcmệnhđề xz∨[( y ∨ z ) → xy ] a. xz∨[( y ∨ z ) → xy ] b. xz∧[( y ∧ z ) ↔ xy ] Gv:TrịnhHuyHoàng Trang107
51. GiáotrìnhLogicToán c. xz→[( y ∧ z ) ∧ xy ] d. xz→[( yz ∨ ) →∧ xy ] e.Tấtcảđềusai 6. F= xy→[ y z ∨ yx )] ,biểudiễnFdướidạngchuNnhộihoàntoànlà: a. f=( x ∨∨ yzxyzxyz )( ∨∨ )( ∨∨ ) b. f=( xyzxyz ∨∨ )( ∨∨ ) c. f=( xyzxyz ∨∨ )( ∨∨ ) d. f=( x ∨∨ yzxyzxyz )( ∨∨ )( ∨∨ ) e.Tấtcảđềusai 7. F= xz∨( yz → yz ) ,biểudiễnFdướidạngchuNntuyểnhoàntoànlà: a. f= xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz b. f= xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz c. f= xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz d. f= xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz e.Tấtcảđềusai 8. F= xyz∨ xz ∨ xy ,khiđócôngthứcđốingẫucủaFlà: a. F *= xyz∨ xz ∨ xy b. F *= (x∨∨ yzxzx )( ∨ )( ∨ y ) c. F *= (x∨∨ yzxzx )( ∨ )( ∨ y ) d. F *= (x∨∨ yzxzx )( ∨ )( ∨ y ) e.Tấtcảđềusai 9. Côngthứclà [x→∨ ( yx )] ∧ [( xz ∨→ ) ( xy )] ∧→ ( xz ) a. Côngthứchằngđúng. b. Côngthứchằngsai c. Côngthứckhảđúng/sai 10.Côngthứclà (x→∧ y )( xz → xy )( ∧→∧ y z ) x a. Côngthứchằngđúng. b. Côngthứchằngsai c. Côngthứckhảđúng/sai ĐỀTHITHAMKHẢOHẾTHỌCPHẦ( 90phút) Câu1(2đ). Xácđịnhchântrịcủacácmệnhđềlượngtừhóasau: a. ∀∈xRxx,[(2 − 6 +=→−< 5 0) ( x 3 2)] b. ∀∈xRyRxy, ∃∈ ,[( −= 2) ∧ ( xy +=− 3)] Gv:TrịnhHuyHoàng Trang108
52. GiáotrìnhLogicToán c. ∃∈∃∈∀∈xRyRzRx, , ,[(2 = yz 2 − 2 ) →≥ ( xz )] d. ∃∈∃∈∃∈xRyRzR, , ,[(2 x2 = 2 yz 2 − 2 )( →< xz )] Câu2(1đ): Dùngcácquitắcsuydiễnđểchứngminhkếtluậnsau: {¬p ∨q,(s ∨¬q),(r ∨¬s),p ∧u} ∴r,u Câu3(2đ):Trong1trậnthiđấuđốikhángvõthuậtVovinam,thísinhsẽđượctínhlà1 điểmnếunhưcóítnhất2trongsố3trọngtàiphấtcờ.N gườitathiếtkế1máychấmđiểm chocáctrậnđấuvớithểthứcthiđấunhưvậy. a. Tìmcôngthứclogictươngứngvớimáychấmđiểmnày. b. Hãyvẽmạchđiệntửtươngứngvớicôngthứcnày(khôngrútgọncôngthức). Câu4(1đ):Cho Gn=→ [ m →∨∨( mnp )] ,hãyđưaGvềdạngthứcchỉdùngphép toánhộivàphủđịnhđểbiểudiễnchocôngthứctrên. 2(x+ y ) Câu5(1đ): Hàmmờ F( x , y ) = tronglogicmờlàhàmchuNnhayhàmđốichuNn 2− xy chuNn? Câu6(3đ): Chocáctậpmờsau: A={(x1,0.3),(x2,0.3),(x3,0.1),(x4,1),(x5,0),(x6,0.3),(x7,0.6)} B={(x1,0.4),(x2,0,6),(x3,0.5),(x4,0.8),(x5,0.2),(x6,0.9),(x7,0.3)} C={(x1,0),(x2,0.2),(x3,0.6),(x4,1),(x5,0.7),(x6,0),(x7,1)} a. TậpmờnàođượcgọilàđạtchuNn? b. Tìmhgt,supp,core,cardcủacáctậpmờtrên. c. Tìm ACABC∪,( ∩∩ ),( AB ∪∩ ) C . Gv:TrịnhHuyHoàng Trang109
53. GiáotrìnhLogicToán ĐỀTÀICỘGĐIỂMCUỐIKỲ 1. HãytìmhiểuvềcáccôngcụđểvẽmạchđiệntrongphầnmềmMS.Visiovàthựchiện vẻtấtcảcáccôngthứchàmlogicsau: a.F= xyz ∨ xz b.F= xyz ⊕ xyz c.F= xy ↔( yz ⊕ xy ) d.F= xy zt ⊕ x yz ⊕ z t e.F= yz ⊕ xy ∨ xyz f. F= xyzt ∨∨ xy xzt ∨ xy t 2. Tìmhiểuvềsựpháttriểnvàcácthànhtựucủangànhtoánứngdụngtrongtinhọc. 3. Tìmhiểuvềhìnhthànhvàpháttriểncủangônngữlậptrìnhprolog. 4. Tìmhiểuvềhìnhthànhvàpháttriểncủangônngữlậptrìnhlisp. 5. Tìmhiểunhữngthànhtựucóđượctừviệcứngdụnglogicmờtrongthờigiangầnđây. 6. Lậptrìnhtrênngônngữprologtấtcảcácbàitậpvềdanhsáchtrongbàihọcsố6. Gv:TrịnhHuyHoàng Trang110
54. GiáotrìnhLogicToán TÀILIỆUTHAMKHẢO 1. Toánhọcrờirạcứngdụngtrongtinhọc–KennethH.Rosen. 2. Toánrờirạc–ĐHKHTN –GSTS.N guyễnHữuAnh. 3. Logictoán–N guyễnVănVĩnh,N guyễnĐứcĐồng,N XBThanhHóa2001. 4. BàigiảngmônPhươngpháptoántrongtinhọc(phầnlogic)–ĐHKHTN 2004củaGS. TSKHHoàngKiếm 5. Hướngdẫngiảibàitậptoánrờirạc–ĐỗĐứcGiáo Gv:TrịnhHuyHoàng Trang111