پاورپوینت استنتاج در منطق مرتبه اول

بخشی از پاورپوینت

اسلاید 1 :

فصل نهم استنتاج در منطق مرتبه اول

اسلاید 2 :

قواعد استنتاج سورها
نمونه سازی عمومی (تخصیص عمومی): هر متغیر سور عمومی را میتوان با هر ترم (بدون متغیر) درون پایگاه دانش، جایگزین کرد.

نمونه سازی وجودی (تخصیص وجودی): هر متغیر سور وجودی را میتوان با یک k که هیچ جای دیگر در پایگاه دانش ظاهر نشده باشد جایگزین کرد.

اسلاید 3 :

استنتاج از طریق کاهش به استنتاج گزاره ای
اگر همه سورها را با دو قاعده نمونه سازی جایگزین کنیم، پایگاه دانش منطق مرتبه اول ما تبدیل به یک پایگاه دانش گزاره ای میشود و میتوان از همان الگوریتمهای استنتاج گزاره ای برای استنتاج استفاده کرد.
اما کافی است یک نماد تابعی داشته باشیم تا تعداد جایگزینیهای ممکن برای یک سور عمومی نامتناهی شود.
john, Father(john), Father(Father(john), ….
اما این مشکل قابل حل است: اگر جمله ای توسط پایگاه دانش مرتبه اول قابل استنتاج باشد توسط زیرمجموعه ای متناهی از پایگاه دانش معادل نیز قابل استنتاج است.
قاعدتاً این زیر مجموعه دارای عمق تودرتویی محدودی است. (باقی در اسلاید بعد)

اسلاید 4 :

کاهش به استنتاج گزاره ای - ادامه
اگر گزاره ای در پایگاه دانش منطق مرتبه اول قابل اثبات باشد، ابتدا با نمادهای ثابت اصلی شروع میکنیم و در صورت عدم موفقیت در اثبات ترمهای مرتبه اول را به آنها اضافه میکنیم و به همین صورت به عمقهای بیشتر میرویم تا اثبات به دست آید.
اما در شروع ما نمیدانیم گزاره قابل اثبات است یا خیر!
تا چه عمقی جلو برویم؟
پرسش در مورد نتیجه گیری یک گزاره در منطق مرتبه اول تا حدودی قابل تصمیم گیری است ( از جنبه نظریه محاسبات، غیر قابل تصمیم گیری است)

اسلاید 5 :

قیاس استثنایی (modus ponens) توسعه یافته
برای جملات اتمیک pi، p’i و q که جایگزینی θ وجود دارد به طوریکه SUBST(θ, p’i)=SUBST(θ, pi) میتوان استنتاج زیر را داشت:

اسلاید 6 :

یکسان سازی
یکسان سازی: یافتن یک لیست جایگزینی که از طریق آن عبارات منطقی متفاوت یکسان به نظر بیایند.
Unify(p,q)=θ اگر SUBST(θ,p)=SUBST(θ,q)
θ: یکسان ساز

استاندارد کردن متغیرها

اسلاید 8 :

عبارات معین منطق مرتبه اول
عبارات معین منطق مرتبه اول: یک عبارت اتمیک یا یک عبارت شرطی که مقدم آن ترکیب عطفی لیترالهای مثبت و تالی آن یک لیترال مثبت باشد.
میتوانند شامل متغیرهایی با سور عمومی هم باشند. (سور را دیگر نمینویسیم)
اما شامل سور وجودی نیستند. (سور وجودی را نمونه سازی وجودی میکنیم)
مثال: فروش تسلیحات توسط یک آمریکایی به کشورهای دشمن جرم محسوب میشود، کشور نونو که دشمن آمریکاست، تعدادی موشک دارد که از سرهنگ وست خریداری کرده است.
datalog: پایگاه دانش بدون نماد تابعی

اسلاید 9 :

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

اسلاید 10 :

مثال: الگوریتم زنجیره پیشروی ساده

اسلاید 11 :

زنجیره پیشروی کارآمد
سه چالش زنجیره پیشرو ساده:
تطبیق الگو: یافتن تمام یکسانسازهایی که مقدم یک قانون را با برخی حقایق پایگاه دانش یکسانسازی میکنند. تطبیق الگو ارتباط تنگاتنگی با CSP دارد و CSP هم در حالت کلی یک مساله NP هارد است.
الگوریتم در هر دور خود تمام قوانین را بررسی میکند تا ببیند آیا مقدم آنها ارضا شده است یا خیر، حتی اگر حقایق زیادی به پایگاه دانش اضافه نشده باشند.
تولید حقایق نامرتبط با پرس و جو
این چالشها در زنجیره پیشروی کارآمد حل میشوند.

اسلاید 12 :

زنجیره عقبگرد
همه کلازهای پایگاه دانش به شکل lhsrhs میتوانند در نظر گرفته شوند، حتی گزاره های اتمیک مثل American(West) به عنوان کلازی در نظر گرفته میشوند که سمت چپشان خالی است.
اثبات به روش زنجیره عقبگرد در واقع نوعی جستجوی AND-OR است، گره های OR به این خاطر که پرس و جوی هدف با هر یک از قوانین میتواند اثبات شود، و گره های AND به این دلیل که برای فعال سازی یک قانون باید تمام عطفهای موجود در سمت چپ آن اثبات شوند.

اسلاید 13 :

مثال: زنجیره عقبگرد

اسلاید 14 :

برنامه نویسی منطقی با پرولوگ
برنامه نویسی منطقی فناوری است که بر اساس ایده بیان اعلانی (declarative) ساخته شده است:
یک سیستم باید بتواند با بیان دانش در یک زبان رسمی ساخته شود و مسایل باید بتوانند از طریق فرآیند استنتاج روی دانش حل شوند.
پرولوگ پرکاربردترین زبان برنامه نویسی منطقی است.
برنامه های پرولوگ مجموعه ای از کلازهای معین است.
ثابتها با حروف کوچک و متغیرها با حروف بزرگ شروع میشوند.
عبارت معین A ∧ B ⇒ C به صورت C :- A, B. نوشته میشود.
criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z)

اسلاید 15 :

بسط (استنتاج) در برنامه های پرولوگ به وسیله زنجیره عقبگرد (عمق اول) انجام میشود.
[H|T] یک لیست است که عنصر اول آن H (سر یا head) و باقی آن T (دم یا tail) است.
مثال: تعریف معنای الحاق
append([],Y,Y).append([A|X],Y,[A|Z]) :- append(X,Y,Z).
جواب پرسش append(X,Y,[1,2]):
X=[] Y=[1,2];
X=[1] Y=[2];
X=[1,2] Y=[]

اسلاید 16 :

حلقه های بی پایان
مثال: تعریف معنای مسیر در گراف
path(X,Z) :- link(X,Z).path(X,Z) :- path(X,Y), link(Y,Z).
حالا جای دو گزاره را عوض میکنیم:
path(X,Z) :- path(X,Y), link(Y,Z).path(X,Z) :- link(X,Z).
در حلقه بینهایت گرفتار میشود:

اسلاید 17 :

استنتاج زائد
پرولوگ برای یافتن مسیری از A1 به J4 به 877 استنتاج احتیاج دارد که اغلب آنها شامل یافتن گره های تکراری است که هدف از طریق آنها قابل دسترسی است.



این مشکل مربوط به روش جستجوی عمقی است که پرولوگ به کار میبرد (بسط گره های تکراری در جستجوی عمقی گراف)
راه حل: برنامه نویسی منطقی جدولی که اهداف فرعی تکراری به یادسپاری میکند.

اسلاید 18 :

استفاده از معنای (semantic) پایگاه داده
معنای پرولوگ یک معنای پایگاه داده گونه است به این معنی که همانند پایگاه داده
چیزی که در پایگاه داده وجود ندارد، اصلاً وجود ندارد (فرض دنیای بسته)
هیچ دو ثابت مختلف با هم یکی نیستند (فرض ثابتهای یکتا)
فرض زیر در پرولوگ:
Course(CS, 101), Course(CS, 102), Course(CS, 106), Course(EE, 101)
هم ارز گزاره زیر در FOL است:
Course(d, n) ⇔ (d=CS ∧ n=101) ∨ (d=CS ∧ n=102) ∨ (d=CS ∧ n=106) ∨ (d=EE ∧ n=101)
به این گزاره دوم تکمیل گزاره پرولوگ بالا میگوییم

اسلاید 19 :

برنامه نویسی منطقی محدودیت (CLP)
مسایل CSP میتوانند به شکل کلازهای معین تعریف شوند و پرولوگ میتواند آنها را حل کند.
اما از آنجا که در زنجیره رو به عقب، الگوریتم همه دامنه یک متغیر را پویش میکند، پرولوگ استاندارد فقط قادر به حل مسایل CSP با دامنه های متناهی است. (مثلاً مساله رنگ آمیزی ایالتها، فقط با شش رنگ).
مثال:
triangle(X,Y,Z) :-X>0, Y>0, Z>0, X+Y>=Z, Y+Z>=X, X+Z>=Y.
پرولوگ به پرس و جوی triangle(3,4,5) به سادگی جواب میدهد اما در پاسخ به triangle(3,4,Z) دچار مشکل خواهد شد.
برنامه نویسی منطقی محدودیت اجازه میدهد متغیرها به جای مقدار گرفتن، محدود شوند.
جواب پرس و جوی triangle(3,4,Z) برابر با محدودیت 1<=Z<=7است.

اسلاید 20 :

قانون استنتاج تحلیل منطق مرتبه اول