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 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. 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