Prolog

‫برنامه نويسی‬ ‫پرولوگ‬ ‫& ‪Fol‬‬

‫صابر اميرنوين‬

‫مقدمه‬ ‫• اشياء داده ای ساده‬ ‫– اتم ها ( ثابت های غير عددی)‬ ‫– اعداد‬ ‫– متغيرها‬

‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫‪2‬‬

‫اشياء ساخت يافته‬ ‫تطابق‬ ‫معنای توصيفی يک برنامه‬ ‫معنای رويه ای يک برنامه‬ ‫ارتباط معنای توصيفی و رويه ای يک برنامه‬ ‫تغيي ر معنای روي ه ای توس ط تغيي ر دادن ترتيب‬ ‫فراکردها و اهداف‬

‫مقدمه‬ ‫• مکانيزم های پايه ای در پرولوگ‬ ‫– فراکردهای پرولوگ (‪)Clauses‬‬ ‫– حقايق (‪)Facts‬‬ ‫– قوانين(‪)Rules‬‬ ‫– رويه ها (‪)procedures‬‬

‫• مکانيزم عقبگرد در پرولوگ (‪)backtracking‬‬ ‫• تفاوت معنای توصيفی و رويه ای يک برنامه‬

‫تعريف روابط بوسيله حقايق‬ ‫• پرولوگ يک زبان برنامه نويسی برای محاسبات نمادين و‬ ‫غير عددی می باشد‪.‬‬ ‫• پرولوگ برای حل مسائلی که شامل اشياء و روابط ميان‬ ‫آنها می باشند بسيار مناسب می باشد‪.‬‬ ‫• مثال ‪ :‬روابط خانوادگی‬ ‫– اين حقيقت که ‪ Tom‬پدر ‪ Bob‬است را در پرولوگ به صورت‬ ‫زير نمايش می دهيم‪:‬‬

‫‪parent(tom, bob).‬‬ ‫در اينجا ‪ parent‬نام رابطه و ‪ Tom‬و ‪ Bob‬آرگومانهای رابطه می‬ ‫باشند‪.‬‬ ‫توجه‪ :‬اسامی خاص مانند ‪ tom‬بايد با يک حرف کوچک الفبا نوشته‬ ‫شوند‪.‬‬

‫تعريف روابط بوسيله حقايق‬ .‫• اين برنامه از شش فراکرد تشکيل شده است‬ .‫ می باشد‬parent ‫• هر فراکرد يک نمونه از رابطه‬ parent)tom, bob(.

pam

tom

parent)pam, bob(. bob

parent)tom, liz(.

liz

parent)bob, ann(. parent)bob, pat(. parent)pat, jim(.

ann

pat

jim

‫تعريف روابط بوسيله حقايق‬ ‫آيا ‪ Bob‬پدر ‪ Pat‬می باشد؟‬ ‫‪?- parent)bob, pat(.‬‬ ‫‪yes‬‬ ‫اين به صورت يک حقيقت در برنامه ذکر شده است‪.‬‬ ‫‪?- parent)liz, pat(.‬‬ ‫‪no‬‬ ‫در برنامه چنين رابطه ای بيان نشده است‪.‬‬ ‫‪?- parent)tom, ben(.‬‬ ‫‪no‬‬ ‫برنامه نام ‪ Ben‬را نشنيده است‪.‬‬

‫تعريف روابط بوسيله حقايق‬ ‫چه کسی والد ‪ Liz‬می باشد؟‬ ‫‪?- parent)X, liz(.‬‬ ‫پرولوگ در پاسخ به اين پرسش سعی می کند برای ‪X‬‬ ‫مقداری بيابد که عبارت بال درست باشد‪.‬‬ ‫‪X = tom‬‬ ‫فرزندان ‪ Bob‬چه کسانی می باشند؟‬ ‫‪?- parent)bob, X(.‬‬ ‫;‪X = ann‬‬ ‫مکانيزمی برای درخواست‬ ‫;‪X = pat‬‬ ‫پاسخهای بيشتر‬ ‫‪no‬‬

‫تعريف روابط بوسيله حقايق‬ ‫چه کسانی والد چه کسانی می باشند؟‬ ‫‪?- parent)X, Y(.‬‬ ‫‪X = pam‬‬ ‫;‪Y = bob‬‬ ‫‪X = tom‬‬ ‫;‪Y = bob‬‬ ‫‪X = tom‬‬ ‫;‪Y = liz‬‬ ‫…‬

‫تعريف روابط بوسيله حقايق‬ ‫جد ‪ Jim‬چه کسی است؟‬

‫‪?- parent)Y, jim(, parent)X, Y(.‬‬ ‫‪X = bob‬‬ ‫‪Y = pat‬‬ ‫اگر ترتيب دو درخواست را در پرسش بال عوض کنيم‬ ‫معنای منطقی ثابت باقی می ماند و بنابراين پرسش‬ ‫زير همان پاسخ بال را توليد می کند‪.‬‬ ‫‪?- parent)X, Y(, parent)Y, jim(.‬‬

‫تعريف روابط بوسيله حقايق‬ ‫نوه های ‪ Tom‬چه کسانی هستند؟‬ ‫‪?- parent)tom, X(, parent)X, Y(.‬‬ ‫‪X = bob‬‬ ‫;‪Y = ann‬‬ ‫‪X = bob‬‬ ‫‪Y = pat‬‬

‫تعريف روابط بوسيله حقايق‬ ‫آيا ‪ Ann‬و ‪ Pat‬والد مشترکی دارند؟‬ ‫کنيم ‪ X‬باشد)‬ ‫‪?- parent)X, ann(, parent)X, pat(.‬‬ ‫‪X = bob‬‬

‫تعريف روابط بوسيله حقايق‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬

‫در پرولوگ تعريف روابط به سادگی توسط يک ‪-n‬تايي‬ ‫از اشياء که رابطه را ارضاء می کنند‪،‬انجام می شود‪.‬‬ ‫کاربر به سادگی می تواند از پرولوگ در باره روابط‬ ‫تعريف شده در برنامه پرس و جو کند‪.‬‬ ‫يک برنامه پرولوگ از فراکردها تشکيل می شود‪.‬‬ ‫پرسش ها شامل يک يا چند هدف می باشند‪ ،‬مانند‪:‬‬ ‫(‪parent)X, ann(, parent)X, pat‬‬ ‫اگر پاسخ پرولوگ به يک پرسش مثبت باشد در اين‬ ‫صورت می گوييم پرسش قابل ارضاء و گرنه غير‬ ‫قابل ارضاء می باشد‪.‬‬ ‫اگر پرسشی دارای پاسخهای متعددی باشد‪ ،‬پرولوگ‬ ‫هر تعداد پاسخی را که کاربر بخواهد پيدا می کند‪.‬‬

‫تعريف روابط بوسيله قوانين‬ ‫برنام ه رواب ط خانوادگ ی را ب ا افزودن اطلعاتی مثل‬ ‫درباره جنسيت افراد می توان تعميم داد‪:‬‬ ‫‪female)pam(.‬‬ ‫‪male)tom(.‬‬ ‫‪male)bob(.‬‬ ‫‪female)liz(.‬‬ ‫‪female)pat(.‬‬ ‫‪female)ann(.‬‬ ‫‪male)jim(.‬‬ ‫روابط يکتايي و دوتايي‪.‬‬

‫تعريف روابط بوسيله قوانين‬ ‫• تعريف رابطه ‪ ( offspring‬عکس رابطه ‪)parent‬‬ ‫اضافه کنيم‪ :‬مثل‬ ‫‪offspring)liz, tom(.‬‬ ‫‪offspring)Y, X( :- parent)X, Y(.‬‬ ‫يعنی بازاء هر ‪ X‬و ‪ ، Y‬اگر ‪ X‬والد ‪ Y‬باشد‪ ،‬آنگاه‬ ‫‪ Y‬فرزند ‪ X‬می باشد‪.‬‬

‫تعريف روابط بوسيله قوانين‬ ‫• تفاوت ميان حقايق و قوانين‪:‬‬ ‫– ي ک حقيق ت چيزی اس ت ک ه همواره و بدون هي چ قيد و‬ ‫شرطی درست می باشد‪.‬‬ ‫– از طرف ديگر يک قانون چيزهايی را بيان می کند که برای‬ ‫درستی آنها بايد برخی از شرايط ارضاء شوند‪.‬‬

‫• بنابراين قوانين از دوقسمت تشکيل می شوند‪:‬‬ ‫– بخش شرط (‪ )condition part‬و‬ ‫– بخش نتيجه (‪.)conclusion part‬‬ ‫‪offspring)Y, X( :- parent)X, Y(.‬‬ ‫‪head‬‬ ‫‪body‬‬

‫تعريف روابط بوسيله قوانين‬ ‫آيا ‪ Liz‬فرزند ‪ Tom‬است؟‬ ‫‪?- offspring) liz, tom(.‬‬ ‫نحوه پاسخ دهی پرولوگ‪:‬‬ ‫چون قانون اسليد قبل بازاء هر ‪ X‬و ‪ Y‬قابل اعمال است‪ ،‬پس بر‬ ‫اشياء خاص ‪ Liz‬و ‪ Tom‬نيز قابل اعمال می باشد‪ .‬برای اعمال‬ ‫اين قانون بر اين اشياء خاص‪ ،‬بايد ‪ Y‬را با ‪ Liz‬و ‪ X‬را با ‪Tom‬‬ ‫در قانون فوق جايگزين کنيم( نمونه دهی)‬ ‫‪X = tom , Y = liz‬‬ ‫پس از جايگذاری‪ ،‬ي ک نمون ه خاص از قانون را ب ه شک ل زير‬ ‫بدست می آوريم‪:‬‬ ‫(‪offspring)liz, tom( :- parent)tom, liz‬‬ ‫اکنون پرولوگ سعی می کند که دريابد آيا بخش شرط قانون بال‬ ‫درست است يا خير‪ .‬چون بخش شرط درست است ( با توجه‬ ‫به حقايق موجود در برنامه)‪ ،‬بنابراين پاسخ پرولوگ ‪ yes‬خواهد‬ ‫بود‪.‬‬

‫تعريف روابط بوسيله قوانين‬ :‫تعريف رابطه مادری‬ mother)X, Y( :- parent)X, Y(, female)X(. ‫ در قانون فوق علمت ويرگول به معنای ترکيب‬:‫توجه‬ .‫) شرايط می باشد‬And( ‫عطفی‬ female

parent

offspring Y

X

X

X

parent

mother

parent Y

Y

parent grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Z

grandparent

‫تعريف روابط بوسيله قوانين‬ ‫نحوه قالب بندی برنامه ها‬ ‫‪grandparent(X, Z) :- parent(X, Y), parent(Y, Z).‬‬

‫نحوه مناسب نوشتن قوانين‪:‬‬ ‫‪grandparent(X, Z) :‬‬‫‪parent(X, Y),‬‬ ‫‪parent(Y, Z).‬‬

‫تعريف روابط بوسيله قوانين‬ )sister(‫تعريف رابطه خواهری‬ sister)X, Y( :parent)Z, X(, parent)Z, Y(, female)X(.

Z

female

?- sister)ann, pat(. yes ?- sister)X, pat(. X = ann; X = pat

parent

parent X

sister

Y

‫تعريف روابط بوسيله قوانين‬ ‫تصحيح رابطه خواهری‬ sister)X, Y( :parent)Z, X(, parent)Z, Y(, female)X(, different(X, Y).

‫تعريف روابط بوسيله قوانين‬ ‫• نکات مهم‪:‬‬ ‫– تعميم برنامه های پرولوگ با افزودن فراکردهای جديد‪.‬‬ ‫– انواع فراکردها‪:‬‬ ‫• حقاي ق ‪ :‬بيانگ ر چيزهاي ي ک ه همواره و بدون شرط درس ت می‬ ‫باشند‪.‬‬ ‫• قوانين‪ :‬بيانگر چيزهايي که درستی آنها بستگی به برخی شرايط‬ ‫دارد‪.‬‬ ‫• پرسش ها‪ :‬وسيله ای که کاربر با آن می تواند از برنامه بپرسد چه‬ ‫چيزهايي درست هستند‪.‬‬

‫– فراکردها از دوقسمت تشکيل می شوند ( سرآيند و بدنه)‬ ‫• حقايق‪ :‬قسمت بدنه آنها تهی‬ ‫• پرسش ها‪ :‬فقط دارای بدنه‬ ‫• قوانين‪ :‬دارای هر دو قسمت‬

‫قوانين بازگشتی‬ )predecessor( ‫تعريف رابطه اجدادی‬ X

X

parent

predecessor

parent

Z

parent

predecessor

parent Z

‫قوانين بازگشتی‬ :predecessor ‫تعريف رابطه‬ predecessor)X, Z( :parent)X, Z(. predecessor)X, Z( :parent)X, Y(, parent)Y, Z(. predecessor)X, Z( :parent)X, Y1(, parent)Y1, Y2(, parent)Y2, Z(. …

‫قوانين بازگشتی‬ :‫ به صورت بازگشتی‬predecessor ‫تعريف‬ predecessor)X, Z( :parent)X, Z(.

%pr1

predecessor)X, Z( :parent)X, Y(, predecessor)Y, Z(.

%pr2

?- predecessor)pam, X(. X = bob; X = ann; X = pat; X = jim

‫قوانين بازگشتی‬ ‫تعريف رويه (‪:)procedure‬‬ ‫مانن د رابط ه ‪ predecessor‬در مثال روابط‬ ‫خانوادگ ی ک ه توس ط دو فراکرد تعريف شده‬ ‫است‪.‬‬ ‫انواع توضيحات (‪ )comment‬در پرولوگ‪:‬‬ ‫‪/* this is a comment */‬‬ ‫‪% this is also a comment‬‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫در پرولوگ ه ر پرس ش شام ل ي ک ي ا چن د هدف می‬ ‫باشد‪.‬‬ ‫پرولوگ برای پاسخ گويی به پرسشها سعی می کند اين‬ ‫اهداف را ارضاء کند‪.‬‬ ‫ارضاء هدف يعنی اينکه نشان دهيم هدف درست است‬ ‫( با اين فرض که روابط موجود در برنامه درست می‬ ‫باشند)‪.‬‬ ‫ارضاء هدف يعنی اينکه نشان دهيم هدف مورد نظر به‬ ‫طور منطق ی از حقاي ق و قواني ن موجود در برنامه‬ ‫می کند‪.‬‬ ‫اگر پرسشی شامل متغير باشد‪ ،‬پرولوگ بايد دريابد که‬ ‫کدام اشياء خاص ( به جای متغيرها) اهداف را برآورده‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ :‫مثال‬ fallible)X( :- man)X(. man)socrates(. ?- fallible)socrates(. yes

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫(‪predecessor)tom, pat‬‬ ‫‪predecessor)X, Z( :- parent)X, Z(.‬‬ ‫‪X = tom, Z= pat‬‬ ‫هدف جديد‪:‬‬ ‫(‪parent)tom, pat‬‬ ‫چون هي چ فراکردی در برنام ه وجود ندارد ک ه بخش‬ ‫سرآيند آن با اين هدف تطابق (‪ )match‬داشته باشد‪،‬‬ ‫بنابراين اين هدف مردود می شود‪.‬‬ ‫اکنون پرولوگ به سمت هدف اول عقبگرد می کند تا‬ ‫روش ديگری برای ارضای آن پيدا کند‪ .‬بنابراين قانون‬ ‫دوم ‪ predecessor‬را امتحان می کند‪.‬‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫‪predecessor)X, Z( :‬‬‫‪parent)X, Y(,‬‬ ‫‪predecessor)Y, Z(.‬‬ ‫مانند قبل متغيرهای ‪ X‬و ‪ Z‬با ‪ tom‬و ‪ pat‬نمونه دهی می شوند‪:‬‬ ‫‪X = tom, Z = pat‬‬ ‫اکنون هدف اص لی يعن ی ‪ )predecessor)tom, pat‬با دوهدف جديد‬ ‫زير جايگزين می شود‪:‬‬ ‫‪parent)tom, Y(,‬‬ ‫(‪predecessor)Y, pat‬‬ ‫اکنون پرولوگ سعی می کند اين دو هدف را به ترتيب نوشتن‬ ‫آنها ارضاء کند‪.‬‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫هدف اول يعنی ‪ )parent)tom, Y‬به راحتی با يک حقيقت برنامه‬ ‫يعن ی ‪ )parent)tom, bob‬تطاب ق م ی ياب د‪ ،‬بنابراين هدف اول‬ ‫بانمونه دهی ‪ Y=bob‬ارضاء می شود و هدف دوم به هدف زير‬ ‫تبديل می شود‪:‬‬ ‫(‪predecessor)bob, pat‬‬ ‫دوباره برای ارضاء اين هدف قانون اول ‪ predecessor‬امتحان می‬ ‫شود‪ ،‬يعنی قانون زير‪:‬‬ ‫‪predecessor)X’, Z’( :‬‬‫‪parent)X’, Z’(.‬‬ ‫از تطابق هدف و بخش سرآيند اين قانون نمونه دهی زير بدست‬ ‫می آيد‪:‬‬ ‫‪X’ = bob, Z’ = pat‬‬ ‫و هدف فعلی با هدف جديد زير جايگزين می شود‪:‬‬ ‫(‪parent)bob, pat‬‬ ‫اين هدف بلفاصله قابل ارضاء می باشد‪ .‬و بنابراين هدف اصلی‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ predecessor(tom, pat) by rule pr1 parent(tom, pat) no

by rule pr2 parent(tom, Y) predecessor(Y, pat) Y = bob

by fact parent(tom, bob)

predecessor(bob, pat) by rule pr1 parent(bob, pat) yes

‫اشياء داده ای‬ data objects

simple objects

constants

atoms

structures

variables

numbers 32

‫اشياء داده ای‬ ‫• در پرولوگ نوع يک شيء توسط ساختار گرامری آن‬ ‫مشخص می شود‪.‬‬ ‫– متغيرها با يک حرف الفبايی بزرگ شروع می شوند‪.‬‬ ‫– اتم ها با يک حرف الفبايی کوچک شروع می شوند‪.‬‬

‫• در پرولوگ ات م ه ا و متغي ر ه ا رشت ه هايي از‬ ‫کاراکترهای زير می باشند‪:‬‬ ‫–‬ ‫–‬ ‫–‬ ‫–‬ ‫‪33‬‬

‫حروف بزرگ ‪A ،B ، ... ،Z‬‬ ‫حروف کوچک ‪a ،b ، ... ،z‬‬ ‫ارقام ‪9 ، ... ،1 ،0‬‬ ‫کاراکتر های خاص مانند ‪~ _ & . : = > < / * - +‬‬

‫ساختارها‬ P1 = point)1, 1( P2 = point)2, 3( S = seg)P1, P2( = seg)point)1, 1(, point)2, 3( ( T = triangle)point)4, 2(, point)6, 4(, point)7, 1( ( triangle

point

point

4

2

6

point

4

7

1

34

‫تطابق‬ ‫• عم ل تطاب ق مهمتري ن عمل ی اس ت ک ه برروی عبارت ها در‬ ‫پرولوگ انجام می گيرد‪.‬‬ ‫• گوييم دو عبارت داده شده‪ ،‬باهم تطابق دارند اگر‪:‬‬

‫شوند که بعد از جايگزينیعبارت ها با هم يکسان شوند‪ .‬مثل‪:‬‬ ‫‪date)D, M, 2001( ,‬‬ ‫(‪date)D1, may, Y1‬‬ ‫‪D = D1‬‬ ‫دو عبارت بال با هم تطابق دارند اگر‪:‬‬ ‫‪M = may‬‬ ‫‪Y1 = 2001‬‬ ‫‪35‬‬

‫تطابق‬ ‫• توججه ‪ :‬عم ل تطاب ق در پرولوگ هميش ه منج ر به‬ ‫می شود‪.‬‬ ‫عمومی ترين نمونه دهی ها‬ ‫‪?- date)D, M, 2001( = date)D1, may, Y1(,‬‬ ‫‪date)D, M, 2001( = date)15, M, Y(.‬‬ ‫‪D = 15‬‬ ‫‪M = may‬‬ ‫‪D1 = 15‬‬ ‫‪Y1 = 2001‬‬ ‫‪Y = 2001‬‬ ‫‪36‬‬

‫تطابق‬ ‫• الگوريتم تطابق دو عبارت ‪:S, T‬‬ ‫تطابق هستند که هر دو شیء يکسانی باشند‪.‬‬ ‫انطباق هستند و ‪ S‬با ‪ T‬نمونه دهی می شود و‬ ‫برعکس‪.‬‬ ‫تطابق می يابند که‪:‬‬ ‫‪ 37‬و‬

‫تطابق‬ ‫ تعريف خاصيت عمودی و افقی برای پاره خط ها‬: ‫مثال‬ vertical(seg(point(X, Y), point(X, Y1) ) ). horizontal(seg(point(X, Y), point(X1, Y) ) ).

•

?- vertical)seg)point)1, 1(, point)1, 2( ( (. yes ?- vertical)seg)point)1, 1(, point)2, Y( ( (. no ?- horizontal)seg)point)1, 1(, point)2, Y( ( (. Y=1 ?- vertical)seg)point)2, 3(, P(. P = point)2, H53( ?- vertical)S(, horizontal)S(. S = seg)point)X, Y(, point)X, Y( ( 38

‫معنای توصيفی برنامه ها‬ ‫‪• P :- Q, R.‬‬ ‫معنای توص يفی‪ P :‬درس ت اس ت اگر ‪ Q‬و ‪R‬‬ ‫درست باشند‪.‬‬ ‫معنای رويه ای‪:‬‬

‫زير مسأله ‪ R‬را حل کن‪.‬‬ ‫بنابراين تفاوت در اهميت ترتيب بخش شرايط‬ ‫‪ 39‬می باشد‪.‬‬

‫معنای توصيفی برنامه ها‬ ‫‪• P :- Q; R.‬‬ ‫معنای توصيفی‪ P :‬درست است اگر ‪ Q‬درست باشد يا ‪ R‬درست‬ ‫باشد‪.‬‬ ‫معادل با‪:‬‬ ‫‪P :- Q.‬‬ ‫‪P :- R.‬‬ ‫اولويت کاما از سمی کالن بيشتر است‪:‬‬ ‫‪P :- Q, R; S, T, U.‬‬ ‫معادل است با‪:‬‬ ‫‪P :- )Q, R(; )S, T, U(.‬‬ ‫يا‪:‬‬ ‫‪P :- Q, R.‬‬ ‫‪P :- S, T, U.‬‬ ‫‪40‬‬

‫معنای رويه ای برنامه ها‬ ‫• معنای رويه ای چگونگی پاسخ گويی پرولوگ‬ ‫به پرسشها را مشخص می کند‪.‬‬ ‫• بنابراين معنای رويه ای پرولوگ‪ ،‬يک رويه برای‬ ‫اجرای ليستی از اهداف ( پرسش) در رابطه با‬ ‫‪.‬‬ ‫باشد‬ ‫می‬ ‫برنامه‬ ‫يک‬ ‫‪program‬‬ ‫‪failure\success indicator‬‬

‫‪execute‬‬ ‫‪instantiation of variables‬‬ ‫‪41‬‬

‫‪goal list‬‬

‫مسأله ميمون و موز‬ ‫• مسجأله ‪ :‬يک ميمون در کنار در ورودی اتاقی قرار‬ ‫دارد‪ .‬در وس ط اتاق ي ک موز از سقف آويزان‬ ‫است‪.‬ميمون گرسنه است و می خواهد خودش را به‬ ‫موز برس اند‪ ،‬ام ا دس تش ب ه آ ن نم ی رسد‪ .‬در کنار‬ ‫پنجره يک جعبه وجود دارد که ميمون می تواند از آن‬ ‫اس تفاده کند‪ .‬ميمون م ی توان د اعمال زير را انجام‬ ‫دهد‪:‬‬ ‫–‬ ‫–‬ ‫–‬ ‫–‬

‫کف اتاق راه برود‪.‬‬ ‫از جعبه بال برود‪.‬‬ ‫جعبه را به اين طرف و آن طرف جابجا کند‪.‬‬ ‫موز رابگيرد به شرطی که روی جعبه باشد و جعبه نيز در‬ ‫وسط اتاق و زير موز باشد‪.‬‬

‫• سوال اي ن ا ست ک ه آي ا ميمون م ی توان د به موزش‬ ‫برسد يا خير و اگر می تواند کدام دنباله از اعمال را‬ ‫بايد انجام دهد؟‬

‫مسأله ميمون و موز‬ ‫• فرموله سازی مسأله ‪ :‬در اين مسأله می توان دنيا را در‬ ‫هر لحظ ه توس ط حالت ی بيان کرد ک ه درآ ن موقعيت اشياء‬ ‫مشخ ص شده باشند‪ .‬حال ت م ی توان د ب ا زمان ( انجام عمل)‬ ‫تغيير کند‪.‬‬ ‫(‪state)P1, P2, P3, H‬‬ ‫موقعيت جعبه موقعيت عمودی موقعيت افقی ميمون‬ ‫داشتن‪/‬نداشتن موز‬ ‫ميمون‬

‫• حالت اوليه‪:‬‬ ‫(‪state)atdoor, onfloor, atwindow, hasnot‬‬ ‫• فرموله سازی هدف‪:‬‬ ‫(‪state)_, _, _, has‬‬

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)middle, onbox, middle, hasnot(, grasp, state)middle, onbox, middle, has( (.

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)Pos1, onfloor, Box, Has(, walk)Pos1, Pos2(, state)Pos2, onfloor, Box, Has( (.

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)Pos1, onfloor, Pos1, Has(, push)Pos1, Pos2(, state)Pos2, onfloor, Pos2, Has( (.

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)Pos, onfloor, Pos, Has(, climb, state)Pos, onbox, Pos, Has( (.

‫مسأله ميمون و موز‬ ‫• پرسش اصلی که برنامه بايد پاسخ دهد اين است که‬ ‫آيا دنباله ای از عمليات وجود دارند که ميمون را از‬ ‫( نهايي)‬ ‫حال ت اولي ه مس أله ب ه حال ت هدف‬ ‫برسانند‪.‬‬ ‫(‪canget)State‬‬ ‫که می تواند به صورت زير بيان شود‪:‬‬ ‫‪canget)state)_, _, _, has( (.‬‬ ‫‪canget)State1( :‬‬‫‪move)State1, Move, State2(,‬‬ ‫‪canget)State2(.‬‬

‫)مسأله ميمون و موز( برنامه کامل‬ move)state)middle, onbox, middle, hasnot(, grasp, state)middle, onbox, middle, has( (. move)state)Pos, onfloor, Pos, Has(, climb, state)Pos, onbox, Pos, Has( (. move)state)Pos1, onfloor, Pos1, Has(, push)Pos1, Pos2(, state)Pos2, onfloor, Pos2, Has( (. move)state)Pos1, onfloor, Box, Has(, walk)Pos1, Pos2(, state)Pos2, onfloor, Box, Has( (. canget)state)_, _, _, has( (. canget)State1( :move)State1, Move, State2(, canget)State2(.

‫مسأله ميمون و موز‬ :‫• حل مسأله‬ ?- canget)state)atdoor, onfloor, atwindow, hasnot( (. yes :‫دنباله عمليات‬ walk)atdoor, atwindow(, push)atwindow, middle(, climb, grasp

‫ترتيب فراکردها و اهداف‬ ‫• خطر حلقه بی پايان‬ ‫‪P :- P.‬‬ ‫اي ن فراکرد از لحاظ معنای توص يفی کامل درس ت است ( ‪P‬‬ ‫درست است اگر ‪ P‬درست باشد)‪.‬‬ ‫اما از لحاظ رويه ای مشکل ايجاد می کند ( حلقه بی پايان)‬ ‫در برنام ه ميمون و موز عمليات را ب ه ترتي ب زي ر در برنامه‬ ‫نوشتيم‪:‬‬ ‫گرفتن موز‪ ،‬بالرفتن‪ ،‬جابه جا کردن جعبه و راه رفتن‬ ‫اين ترتيب اولويت اعمال مختلف را برای ميمون مشخص می‬ ‫کنند‪ ،‬يعنی مثل ميمون بين راه رفتن و گرفتن موز دومی را‬ ‫ترجيح می دهد‪ .‬اين اولويت ها به ميمون در حل مسأله کمک‬ ‫می کنند‪ .‬حال اگ ر ترتي ب عمليات را عوض کني م و عمل راه‬ ‫رفتن را بالتر از بقيه اعمال در برنامه قراردهيم ميمون تا ابد‬ ‫در اتاق قدم خواهد زد و هيچگاه به موز نمی رسد ( اگر زنده‬ ‫بماند!) ‪.‬‬