هوش مصنوعی: استنتاج در منطق مرتبه اول

صفحه 1:
استنتاج در منطو مر تبه اول ایمان مختاری فرد. دانشگاه پیام نور شهرکرد. 

صفحه 2:
استنتاج مرتيدى اول 5 ۲ * بحسب مطالب فصل ۷. برای استنتاج در منطق مرتبه اول ؛ ابتدا بايد عبارت منتطق مرتبه اول را به كزاره ای تبدیل کنیم و سپس عبارت گزاره ای را با تابع ۳1۲۵5۵۱0۴1۵8 استنتاج کنیم * در روند كزاره اى كردن عبارت ۴001 باید سورها و... حذف شوند چون عبارت گزاره ای سور ندارد مراحل تبدیل مرتبه اول به کزاره ای (مهع] ۲,2۶ ۷2) 2 ۸ )۷ ‎١‏ حذف دو شرطی و شرطی ۲ اعمال نقیض (طبق قوانین دمورکان) ۳ انتقال سورها به اول عبارت ‎Vx (Ay (Vz (P(x) A qcy,2))))‏ ۴ _ حذف سور وجودی و جایگزین کردن اسکلم ‎١‏ اكر متغير سور وجودى به صورت (7)5) "3 باشد متغير اسكلم 3 جایگزین و سور حذف ‎Plo)‏ ‏۲ اگر سور وجودر در یک سور عمومی باشد از تابع اسکلم_برای حذف استفاده می كنيى راو )۷ نكن ون 0۵2 ۵۵۵۸ ۷2) ۷ ‎D‏ حذف ضمنی سور عمومی(بدون جایگزین کردن) ‎(POX) A 002‏ ع تبدیل به شکل نرمال عطفی 

صفحه 3:
استنتاج مرتیه‌ی اول * هدف از استنتاج در منطق مرتبه اول . یافتن الگوریتمی است که بتواند به هر سوالی قابل پاسخ گویی با کند که آیا استلزام و ایجاب به وجود می آید يا خیر؟ منطق مرتبه اول . پاسخ دهد و تعیب حدق سورها 3 روش اول براى استنتاج در منطق مرتبه اول حذف سور و تيديل پایگاه دانش به منطق گزاره ای و استفاده از قوان ناج ده بزاره ای است.لذا روشهای زیر به عنوان الگوریتمهای استنتاج در منطق مرتبه و ‎١‏ نمونه‌سازی عمومی (حذف سور عمومی با (4)) مت ‎Doiversel‏ ( ۴ نمونه‌سازی وجودی (حذف سور وجودی با ‎)٩(‏ موی لس ) ۷« نمونه‌سازی عمومی هر نمونه از یک جمله دارای سور عمومی, توسط آن جمله قابل استلزام نمونه‌سازی عمومی برای هر متغیّر ۷ و اصطلاح زمینه ب». به‌صورت زیر 5-2 می‌شود: ‎Va‏ ‏که در آن (90,0) نتیجه اعمال جایگزینی 0 به جای 7 است. ‎Svast{y gh a)‏ نوان مثال جملات نت 1 ‎King Richard Greedy Richard Evil Rickards‏ Xing Father John)” Greedy (Father Jon) = Evil Father Jofn)) از نمونه‌ساز جمله از نمونه‌سازی عمومی ج ‎Evil.‏ > صما يفم مره "مدا و« توعد با جایگزینی های ۰/1۱ ال و ((جل) بهددست مى ليد. 

صفحه 4:
۲- نمو نه‌سازی وجودی *_ در مورد 01761(3/] ,۸۱۵۷۷5 (50۳1096610 ,1/۷65/۳00 : ۷ ما می دانیم که لاقل یک شی ۰ درست باشد . بیایید این شی را بنامیم ؛ داریم ۰ ‎Livesin(k, Springfield) A‏ (۲/۵۲6۲ ,60۵۷۷5۲۸ که در این مورد. یک ثابت اسگولم نامیده می شود. *_پس برای هر عبارت 0 و متغیر ۷ و سمبل ثابت 6 که در جای دیگری در پایگاه دانش وجود ندارد داریم ‎Ava‏ ‎Sussk {vy Kj cx)‏ es Oroun(Ol) A On ecd(Oddloba) 3 910 4 xOnawulx) A Oo/Weud (x, lobaJA 5 apa: Jie ‏تواند باشد که 0() به وجود آمده از یک سمبل ثابت جدید به نام ثابت اسکلم می باشد.‎ ن باید برای مخالی دیگر :از ۰3 2 رل /( 67۷ : »ما نتيجه مى كيريم , <, ست ت ره( سل بی که به وجود آمده است یک سمیل ثابت جدید می باشد) گزاره بغدی ما می تواتیم هر عبارت دارای سور وجودی را با یک نوع اسکلمایز شده جایگزین نماییم . برای عبارت های با سور عمومی . می توانید هر جایگزین ممکن را جایگزین نمایید ؛ که اين کار به ما اجازه می دهد که از قانون های استنتاج گزاره ای استفاده نماییم . البته اين کار خیلی ناکارآمد می باشد ؛ تا سال ۱۹۲۰ از همین روش استفاده می ‎BIS‏ 

صفحه 5:
ساده سازی به استنتاج گزاره ای السا پایگاه دانش مقابل را در نظر بگیرید: 0111-5 ‎Xing John)‏ ‎Greedy John)‏ ‎Brother (Richard John)‏ با اعمال تمامی جایگزینی های ممکن به اوّلین جمله. داریم: (پایگاه دانش گزاره‌ای شده)(الا) ((010۳[] و ‎(b</Richard}‏ img" Greedy Jobin) 20 John) KingRihare "Greedy Richard ‏ف جمقم له عامط‎ 0 جديد گزارد لی‌سازی‌شده لست سیمبول‌هاینمادها) گزاره لیعبارتند از: ام , انلس : ‎rr(tobs) , Breed {lola‏ هر پایگاه دانش با منطق مرتبه اول را می توان گزاره ای کرد به گونه‌ای که ایجاب در آن حفظ شود. یعنی هر جمله زمینه‌ای که از پایگاه دانش جدید به دست می آید. اگر و فقط اگر از پایگاه دانش جدید نیز حاصل شود. یک روش برای استنتاج: پایگاه دانش و پرس‌وجوی مرتبه‌ی اوّل را گزاره‌ای نمود. و از الگوریتمهای استنتاج گزاره ای برای استنتاج استفاده کرد. * مشکل: در مورد سیمیول های تابعی(دارای خروجی) تعداد نامحدودی ترم زمینی وجود دارد. ‎Sika‏ (Pak (Pusher (Pathe (lebs))) 

صفحه 6:
قضیه هرپراند ‎)۱٩۳۰(‏ : اثباث با یک زیر مجموعد.. ل قضیه هربراند (۱8۳۰): اگر جمله‌ای به وسیله پایگاهدانش مرتبه‌ی اوّل اصلی ایجاب شود. آنگاه یک اثبات با زیرمجموعه‌ی متناهی از پایگاه دانش گزاره‌ای شده, وجود دارد. می‌باشد. می‌توان ابتدا زیرمجموعه‌ای با استفاده از تمامی نمونه‌سازیهای نمادهای ثابت (0۳۸۷ و «ل) را تولید کنیم. سپس, با تمامی اصطلاحات با عمق \ ‎Pater)‏ ‏() و ‎Shans 9 (Paber (ek)‏ آن تمامی اصطلاحات با عمق ۲و ... را بیابیم تا زمانی که قادر به گزاره‌ای جمله ایجاب شده بشو؛ با توجه به متناهی بودن زیرمجموعه, یک مقدار حداکثر برای عمق تودرتو بودن اصطلاحات زمینه موجود شیری 1181011008 (۱۹۳۰:اگر جمله 4 توسط باه داش_001 ال اتزام اش آنگاه این جمله توسط زیرمجموعه محدودی از پایگاه داش گزاره ای سازی ‎Hoe‏ ‏استلزام اسلت مل مد 16 0 دير وو ‎create a propositional KB by instantatina with depih-Sn$ teens‏ ‎soe fis entiled by this KB.‏ مشكل: اكر ‎pw KB‏ باشد كار مى كنده در غير أبنصورت در حلقه بى ثضیه ی تورینگ و چورج (۱۹۳۶): فقط بلی مي تواند بگوید قضیه تورینگ و چرچ (۱۹۳۶): مسأله ایجاب در منطق مرتبه‌ی ارّل. یک مسأله‌ی نیمه‌تصمیم‌پذیر است, یعنی الگوریتمهایی وجود دارد که به هر جمله ایجاب شونده پاسخ مثبت می‌دهد. اما هیچ الگوریتمی وجود ندارد که به هر جمله ایجاب‌ناپذیر پاسخ منفی بدهد. 

صفحه 7:
مشکلات گزاره ای سازی نمودن * به نظر می رسد که گزاره ای سازی کردن جملات نامربوط زیادی تولید می کند. برای مثال از جملات زیر ‎Vie crc) A Breech) = Brae)‏ ‎rm(loks)‏ ‎rater (Retard soko)‏ حاصل 0 است » اما گزاره ای ‎SAS gs als Greed)(Richord) ails als Gilda Go 8 spl‏ تامربوط می باشند یکسان سازي ‎Unification)‏ ( : حل مشکل کزاره سازی:سازکار بودن دو چمله * اگر یک جایگزینی ۵ وجود داشته باشد که مقدم استلزام را با جملات موجود در پایگاه دانش, یکسان‌سازی کند. یا به عبارتی یکسان سازی. این است که ما فقط می خواهیم جایگزین هایی برای عباراتی که به ما کمک می چیزهایی را ثابت نماییم ‎oe‏ كنع آنگاه می‌توان با اعمال 8. تالی استلزام را اظهار نمود. مانند جایگزینی (0/0۳[ / 12 در پایگاه دانش, (0]00[) |۴۷ را نتيجه می‌دهد. ۱ King john) Greedy (john) Brother (Richard, John) ابتدا بايد بتوان روشى برای انتخاب مناسب 6 پیدا کرد (یکسان سازی). Unify(a,B) = @ if a8 = BO ‏م0 در ترم ج و ؛ لصطلاحاً یی هستند لگر یبکجانشینی ماننم‎ 09 -0)8 . ‏وجود داشته باشد به طوری که‎ ۲ 9 8 Knows(John,x) [Knows(John,Jane) ‏ا( ل‎ Knows(John,x) Knows(y,0J) {Od yobs} ( رتالاب ‎Knows(John,x) Knows(y,Mother(y))‏ عدم استاترارريه طاطر تیب و لا ‎‘Knows(John,x) Knows(x,0J)‏ 

صفحه 8:
آیام‌توان در پیگا انش با نتخاب مقدارى برا >ز . یک دفعه یک واقعیت را استنتاج کرد؟ ‎vx King (x) * Greedy (x) = Evil (x)‏ ‎King (john)‏ ‎vy Greedy (y)‏ ‎Brother (Richard, John)‏ براى اين كار بايد قانون ‎(Dy Pa" Dy =)‏ لوه عع نوه نيه ‎Subst(8,q)‏ ‎p,' is Kingohn) p, is King(x)‏ ‎p,'is Greedyly) p,is Greedy(x)‏ ‎is {x/John,y/John} qis Evikx)‏ 8 ‎q 8 is Evil(fohn)‏ در اين قانون اگر جمله هایی به صورت * با هم ترکیب شوند و جمله ی دیگری را ایجاد کنند. در را الزام می کرد با وجود چند جمله به تعداد جملات ترکیبی می توان جایگزاری مقادیر0 در © را طبق شرط یکسان سازی نتیجه گرفت که به آن قیاس استثنایی توسعه یافته مى گویند 

صفحه 9:
ذخیره و بازیلبی * توابع ابتدايى »8516 و۲61 و با استفاده از نسخه ابتدایی تر مثل 51076 و ‎Fetch‏ * يرس و جوها (8516) ) از طريق يك شبكه شمول به دست مى آيند. در اين شبکه هر گره در شبكه تنها با یک جابجایی از والد خود بدست می آید(شکل صفحه ۱۳۰) 

صفحه 10:
ذخیرد و بازیابی قانون می گوید که برای یک آمریکایی. فروش ات به ملل متخاصم جرم است.کشور نونو که دشمن آمریکا است. تعدادی موشک دارد و تمامی موشکهایش را از سرهنگ وست که یک آمریکایی است. خریده است. لد سرهنگ وست مجرم است. 

صفحه 11:
مثالى از یک پایگاه دانش فروش تسلیحات به ملل متخاصم برای یک آمریکایی جرم است ‎Q American(x) * Weapon(y) * Sells(x,y,z) * Hostile(z) > Criminal(x)‏ لا نونو تعدادی موشک دارد.. (55160 * ‎3x Owns(Nono,x)‏ ‎Q Owns(Nono,M,) and Missile(M,)‏ لا سرهنگ وست تمامی موشک ها را را به نونو فروخته بود ‎Q Missile(x) * Owns(Nono,x) = Sells(West,x,Nono)‏ لا موشک ها جزو تسلیحات هستند ‎O Missile(x) = Weapon(x)‏ لا هر دشمن آمریکا به عنوان متخاصم تلقی می شود ‎Q Enemy(x,America) = Hostile(x)‏ ما وست یک آمریکایی است ‎Q American(West)‏ لا کشور نونو دشمن آمریکاست ‎Q Enemy(Nono,America)‏ 

صفحه 12:
مثالى از یک پایگاه دانش فروش تسلیحات به ملل متخاصم برای یک آمریکایی جرم است ‎Q American(x) * Weapon(y) * Sells(x,y,z) * Hostile(z) > Criminal(x)‏ لا نونو تعدادی موشک دارد.. (55160 * ‎3x Owns(Nono,x)‏ ‎Q Owns(Nono,M,) and Missile(M,)‏ لا سرهنگ وست تمامی موشک ها را را به نونو فروخته بود ‎Q Missile(x) * Owns(Nono,x) = Sells(West,x,Nono)‏ لا موشک ها جزو تسلیحات هستند ‎O Missile(x) = Weapon(x)‏ لا هر دشمن آمریکا به عنوان متخاصم تلقی می شود ‎Q Enemy(x,America) = Hostile(x)‏ ما وست یک آمریکایی است ‎Q American(West)‏ لا کشور نونو دشمن آمریکاست ‎Q Enemy(Nono,America)‏ 

صفحه 13:
الکوریتم زنجیره ای پیش رو از جملات بسیط حرکت می کند و مبتنی بر داده هاست function FOL-FC-Ask(KB,a) returns a substitution or false repeat until new is empty newe-{} for each sentence rin KB do (Dy A...A Pa = Gg) + STANDARDIZE-APART(r) for cach such that (—1 A... A pal = (pi A... A phe for some pj,...,p/,in KB ¢ —Sunst(6, q) if q is not a renaming of a sentence already in KB or new then do add q' to new 6+ UNIFY(y’,a) ‏وز ف كذ‎ not fail then return 6 add new to KB return false 

صفحه 14:
[Enemy Nono.America) الگوریتم زنجیره ای پیش رو ‘Owns(Nono,MI) ‘Missile(M1) ‘American( West) 

صفحه 15:
[Hestile(Nono) [Enemy Nono.America) الگوریتم زنجیره ای پیش رو ‘Selis( West.M1,Nono) ‘Owns(Nono,MI) Weapon(M1) ‘Missile(M1) ‘American( West) 

صفحه 16:
الگوریتم زنجیره ای پیش رو (Criminal West) Weapon(M1) ‘Sells( West.M1,Nono) [Hostite(Nono) ‘American( West) ‘Missile(M1) ‘Owns(Nono,MI) [Enemy Nono.America) 

صفحه 17:
ویژکی های الکوریتم زنجیره ای پیش رو * این الگوریتم صحیح است به دلیل آنکه هر استنتاج از به کارگیری قیاس استثنائی تعمیم يافته ناشی می شود که آن نیز به نوبه خود صحیح می باشد. این الگوریتم در مورد پایگاه های دانش با بندهای معین کامل است. 

صفحه 18:
الکوریتم زنجیره ای پس رو از هدف حرکت می کند تا به داده ها برسد یعنی هدف گراست function FOL-BC-Ask(KB, goals, 9) returns a set of substitutions inputs: KB, a knowledge base goals, a list of conjuncts forming a query 0, the current substitution, initially th local variables: ans, a set of substitutions, pty substitution { } lly empty if goals is empty then return {6} q+ Sups7(6, Finst(goals)) for each rin KB where STANDARDIZE-APARI(T) = (pi A. A ta = 4) and 6! — UNIFY(«, q') succeeds 6) U ans ans FOL-BC-ASk(KB, ‏رس ...رت‎ REST goals)), Compose, return ans 

صفحه 19:
مثالی از الگوریتم زنجیره ای پس رو [Criminal West) 

صفحه 20:
مثالی از الگوریتم زنجیره ای پس رو ان تسس [Americants) Weaportv) ۳ ۵5/6/2 

صفحه 21:
مثالی از الگوریتم زنجیره ای پس رو ۵5/6/2 ان تسس ۳ Weaponty) American West) ۱1 

صفحه 22:
مثالی از الگوریتم زنجیره ای پس رو ۵5/6/2 ان تسس ۳ Weaporty) Missilely) American West) ۱1 

صفحه 23:
مثالی از الگوریتم زنجیره ای پس رو (est, ‏لق‎ | ۵5/6/2 تسس ۳ Weaporty) Missile(y) ۳ American West) ۱1 

صفحه 24:
مثالی از الگوریتم زنجیره ای پس رو fest, yiM, /Nono } [Criminall West) Swe ۳7 [Nore] 77777 ( Ty Weaporty) Missile(y) {yaaa} American West) ۱1 

صفحه 25:
مثالی از الگوریتم زنجیره ای پس رو fest, yiM, /Nono } [HostilerNono) ‘Enemy Nona, America) ۱۱ 7 ۱1 ‘Sells(West. ML) [Criminall West) [Nore] issileiMT) لك ۵ 2 {yaaa} American West) ۱1 

صفحه 26:
مثالی از الگوریتم زنجیره ای پس رو fest, yiM, /Nono } [HostilerNono) ‘Enemy Nona, America) ۱۱ 7 ۱1 ‘Sells(West. ML) [Criminall West) [Nore] issileiMT) لك ۵ 2 {yaaa} American West) ۱1 

صفحه 27:
برنامه نویسی منطقی ( اثبات استلزام و ...) - پرولوک * الگوریتم - منطق + کنترل * بر اساس : الگوریتم زنجیره ای پس گرد با استفاده از عبارت های هورن * برنامه- مجموعه ای از عبارات ,الا ... ,رات -: مب pricotd(X) 3+ oericon(), weapon’), sebs(X,7,L), hostle(L) 

صفحه 28:
یک برنامه بسیار ساده پرولورگ یک برنامه بسیار ساده پرولوگ را در نظر می گیریم. این برنامه شامل چهار کلاز است که در یک دیتابیس ذخیره شده اند 2 ‏حم احلا , (ا ریما اسلا‎ X). و6 که در لنتهاآمده می‌سرسد که آیا حسیز‌چیزیرا دوستدارد که نسعیم‌همآنرا دیستدارد؟ پرولوگاولیرتسرم از ‎query‏ را می‌گیرد (2۲ ,۳ )او تاش‌می‌ک ند که آنرا ببایککا( در دیتابیس ۱6 کند. يرولوكبا توليد ‎thes( hossrist, Pood) alex 59 «Soy Lig food tile‏ 5 )0 رخ )لا را بایکدیگر ( کند سپس يرول وكجانشينىبه دستلمدم را به تمامىتسرم هائ/1هم اعط میک ند سیسسه سرلغ دومیرتسرم رود ‎OFSLAS‏ ‏(ل ,ممم )حصا شده لستلین‌جمله با هیچ جمله دیگریدر دیتابیس ۱/۷ ن_می‌شود. بعد از هر شکست. پرولوگ اه می کند. یعنی به تم قیلی باز می گردد. که در اين مورد مر كردن (2 ,یی )لا با (لس ,مضه )حصلا است. اکنون پرولوگ تلاش می کند که اولین ترم ‎TUE‏ رابا یک کلاز دیگر در دیتابیس ۶ کند. که («مجها رخیعیا )حلا است. اين دو ترم با جانشیتی ۳۹۲ لیگ ز لهس می شوند. که به ترم دوم بصب يعنى ( ,صم )دصلا هم اعمال مى شود تا (ممسسسها رحس )حصلا را ایجاد کند. ترم جدید با سومین کلاز دیتابیس قابل #7 شدن است. بعد از تمام شدن کار با تمامی ترم های 7ج پرولوگ جانشینی های به دست آمده را خروجی می دهد. که در این جا و2( است. 

صفحه 29:
یکی از مسائل کلاسیکی که معمولاً در ابتدای آموزش پرولوگ مطرح می کنند مساله شجره نامه خانوادگی می باشد. برای مثال شجره نامه زیر را درنظر بگیرید: jamshid Se ‏و‎ mina 6 | ‏ود‎ javad ‏ود‎ 4 را اختيار مى كنيم و با یک ‎comes Prete g rare‏ این شجره نامه را به زیان پرولوگ توصیف می تماييم. براى اين كار سه محمول بابه يعنى .سرى درخت را نمايش مى دهيم sande (fem). sande (or). srde(fannl). en ee Belibledinienen ‏سسسب‎ ‎bs ‏.دهیم‎ ‎he pret oP axed?‏ تما وا ی ‎Quen’: poredi( hossud, sured).‏ )سوم( ‎prea jexoohtd, sored). Who ‏سمدم والسجدد عا‎ ‎parr fresh, cokra). Quen): porei( XG sured). ‎poral sad, faved). sho were the ohio P xed? ‎poral eared, zchra). Query: paral seed, X). ‏سم ,لس ‎poreul‏ ‎poreul wots, 1210).‏ ها رو )نس 

صفحه 30:
۴ لیست ها در پرولوگ (1,17,1] )800670 احاقبا ليستخالوبرلبر باخود ليست ‎append({X|L],Y,[X|Z]) :- append(L,Y,Z)‏ * پرس و جو: ([208680)۸,8,]1,2 2 * پاسخ ها: ‎B=[1,2]‏ []عم 8-121 [1]عم ‎(rA=[1,2] B‏ 

صفحه 31:
۱۱1۴۷), 7۳0,( > © ‏زمانى كه‎ due + = Rich(x) * Unhappy(x) ب من 9 ص۱۳ 

صفحه 32:
بدیل به فر م ‎OOF‏ ‏هر کس همه حیوانات را دوست داشته باشد. توسط یک نفردوست داشته خواهد شد. ‎vx [vy Animal y) = Loves(x,y)] = [By Loves(y,x)]‏ ‎.١‏ حذف یک دوشرطی ها و یک شرطی ها ‎vx [5 Vy ~Animally) * Loves(x,y)] ‘ [ay Loves(y,x)]‏ 2. Move > inwards: > Vx p = 3x ap, 7 3x p = Vx ap vx [By 7(-Animaly) ° Loves(x,y))] ‘ [ay Loves(y,x)] ¥x [By --Animally) * =Loves(x,y)] ° [By Loves(y,x)] vx [ay Animaly) * >Loves(x,y)] ‘ [ay Loves(y,x)] ‏استاندارد ساز متغیرها‎ ۳ Vax [By Parody) * ‏[(«حعسصا ]۲ نصا‎ 4 اسکولم سازی ‎Vx [Dens Px) Levels Pn))] " bevwol B(x).x)‏ ه-حذف سورها (عمومى) (د 0 )سصصنا ". ‎[evar (x)) * Love(nsPCx))]‏ 1-توزيع " بر ‎[Pond Plx)) * Love Plx),x)] * [berver(x,Plx)) * Love P(x), x]‏ 

صفحه 33:
اثبات به روش تحلیل ‎V— Weapor(y) v Sella) Vv Mestilelz) v Criminalls) 2‏ امم عاد ‎ ‎ ‎ ‏ماهم ۷ تراک ۷ ۱ )هم۱۵ ۱ “ساسم ممح | ‎‘Are icant West)‏ ‎۹ Weapon] 0 ‏مهد ۱ لتعملا أعاامع حب ‎A Missilety)‏ لت ‎۳ ‎ ‎ ‎ ‎ ‎ ‎ ‏| مسف وه اد [ ماحم قاط ص۱9 و ‎ ‎v omatNerost V Houten)‏ 2 انس ‎ ‎ ‎ ‎ ‏0 > لا رامد صم عم 2 لصوم عم ‎ ‎ ‎- ‏اتام ااعملة ب _زمعا”عصبرممدك‎ = Hest Nono} ‎ ‎ ‎ ‎Enemy Nera,America)‏ معا رجا موق ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎