پاورپوینت هوش مصنوعی فصل نهم استنتاج در منطق مرتبه اول (pptx) 33 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 33 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
2
هوش مصنوعی
فصل نهم
استنتاج در منطق مرتبه اول
استنتاج مرتبه‌ي اول
مراحل تبدیل مرتبه اول به گزاره ای (مهم)
بر حسب مطالب فصل 7 ، برای استنتاج در منطق مرتبه اول ، ابتدا باید عبارت منطق مرتبه اول را به گزاره ای تبدیل کنیم و سپس عبارت گزاره ای را با تابع Pl_resolution استنتاج کنیم
در روند گزاره ای کردن عبارت FOL باید سورها و.... حذف شوند چون عبارت گزاره ای سور ندارد
حذف دو شرطی و شرطی
اعمال نقیض (طبق قوانین دمورگان)
انتقال سورها به اول عبارت
حذف سور وجودی و جایگزین کردن اسکلم
اگر متغیر سور وجودی به صورت باشد متغیر اسکلم a جایگزین و سور حذف
اگر سور وجودر در یک سور عمومی باشد از تابع اسکلم برای حذف استفاده می کنیم
حذف ضمنی سور عمومی(بدون جایگزین کردن)
تبدیل به شکل نرمال عطفی
x P(x)
x (P(x) ᴧ y (z ( q(y,z))))
x (y (z (P(x) ᴧ q(y,z))))
P(a)
x (y q(y,z))
x (q(f(x),z))
x (z (P(x) ᴧ q(f(x),z)))
(P(x) ᴧ q(f(x),z))
استنتاج مرتبه‌ي اول
هدف از استنتاج در منطق مرتبه اول ، یافتن الگوریتمی است که بتواند به هر سوالی قابل پاسخ گویی با منطق مرتبه اول ، پاسخ دهد و تعیین کند که آیا استلزام و ایجاب به وجود می آید یا خیر؟
روش اول برای استنتاج در منطق مرتبه اول حذف سور و تبدیل پایگاه دانش به منطق گزاره ای و استفاده از قوانین استنتاج در منطق گزاره ای است.لذا روشهای زیر به عنوان الگوریتمهای استنتاج در منطق مرتبه اول ارائه شده اند :
نمونه‌سازي عمومی (حذف سور عمومی یا Universal instantiation (UI) )
نمونه‌سازي وجودی (حذف سور وجودی یا Existential instantiation (EI) )
حدف سورها
1- نمونه‌سازي عمومی
هر نمونه از يك جمله داراي سور عمومي، توسط آن جمله قابل استلزام است.
نمونه‌سازي عمومی براي هر متغيّر و اصطلاح زمينه g، به‌صورت زیر نوشته مي‌شود:
که در آن Subst(,) نتيجه اعمال جايگزيني به جاي است.
به عنوان مثال جملات
King (John) Greedy (John) Evil (John)
King (Richard) Greedy (Richard) Evil (Richard)
King (Father (John)) Greedy (Father (John)) Evil (Father (John))
از نمونه‌سازی عمومی جمله
x King (x) Greedy (x) Evil (x)
با جايگزيني هاي {x John}، {x Richard} و {x Father (John)} به‌دست‌مي‌آيد.
در مورد ∃x : LivesIn(x, Springfield) ∧ knows(x, Homer) ما مي دانيم كه اين بايد براي لااقل يك شي ، درست باشد . بياييد اين شي را K بناميم ؛ داريم ، LivesIn(k, Springfield) ∧ knows(k, Homer) که در این مورد،K يك ثابت اسكُولِم ناميده مي شود.
پس ، براي هر عبارت α و متغیر v و سمبل ثابت k كه در جاي ديگري در پايگاه دانش وجود ندارد داريم :
2- نمونه‌سازي وجودی
مثال : نتيجه ي ∃xCrown(x) ∧ OnHead (x, John) به صورت Crown(C1) ∧ OnHead(C1,John) مي تواند باشد كه C1 به وجود آمده از يك سمبل ثابت جديد به نام ثابت اسكلم می باشد.
مثالي ديگر : از ∃x : d(x y ) / dy = x y ما نتيجه مي گيريم ، d(ey ) / dy = ey ، e ای که به وجود آمده است يك سمبل ثابت جديد مي باشد)
گزاره بندي
ما مي توانيم هر عبارت داراي سور وجودي را با يك نوع اسكلمايز شده جايگزين نماييم . براي عبارت هاي با سور عمومي ، مي توانيد هر جايگزين ممكن را جايگزين نماييد ؛ كه اين كار به ما اجازه مي دهد كه از قانون هاي استنتاج گزاره اي استفاده نماييم . البتّه اين كار خيلي ناكارآمد مي باشد ؛ تا سال 1960 از همين روش استفاده مي كردند .
پایگاه دانش مقابل را در نظر بگیرید:
x King (x) Greedy (x) Evil (x)
King (John)
Greedy (John)
Brother (Richard, John)
با اعمال تمامی جايگزيني هاي ممکن به اوّلین جمله، داریم:
(پایگاه دانش گزاره‌ای شده) (UI) ({x/John} و {x/Richard})
King (John) Greedy (John) Evil (John)
King (Richard) Greedy (Richard) Evil (Richard)
ساده سازی به استنتاج گزاره ای
KB جدید گزاره اي سازي شده است. سيمبول هاي(نمادها) گزاره اي عبارتند از:
King(John) , Greedy(John) , Evil(John) , King(Richard)
هر پایگاه دانش با منطق مرتبه اول را می توان گزاره ای کرد به گونه‌ای که ایجاب در آن حفظ شود، یعنی هر جمله زمینه‌ای که از پایگاه دانش جدید به دست می آید، اگر و فقط اگر از پایگاه دانش جدید نیز حاصل شود.
یک روش برای استنتاج: پایگاه دانش و پرس‌وجوي مرتبه‌ي اوّل را گزاره‌اي نمود، و از الگوریتمهای استنتاج گزاره ای برای استنتاج استفاده کرد.
• مشكل: در مورد سيمبول هاي تابعي(دارای خروجی) تعداد نامحدودي ترم زميني وجود دارد، مثلاً:
Father(Father(Father(John)))
قضیه هربراند (1930): اگر جمله‌اي به وسیله پایگاه دانش مرتبه‌ي اوّل اصلی ایجاب شود، آنگاه یک اثبات با زيرمجموعه‌ي متناهی از پایگاه دانش گزاره‌اي شده، وجود دارد.
با توجه به متناهی بودن زيرمجموعه، يك مقدار حداکثر براي عمق تودرتو بودن اصطلاحات زمینه موجود مي‌باشد.
قضیه هربراند (1930) : اثبات با یک زیر مجموعه...
قضیه ي تورينگ و چورچ (1936) : فقط بلی می تواند بگوید
مي‌توان ابتدا زيرمجموعه‌اي با استفاده از تمامی نمونه‌سازيهاي نمادهای ثابت (Richard و John) را توليد كنيم. سپس، با تمامی اصطلاحات با عمق 1 (Father (Richard) و Father (john))، و بعد از آن تمامي اصطلاحات با عمق 2 و ... را بيابيم تا زمانی كه قادر به اثبات گزاره‌اي جمله ایجاب شده بشویم.
قضیه تورینگ و چرچ (1936): مسأله ايجاب در منطق مرتبه‌ي اوّل، يك مسأله‌ي نيمه‌تصميم‌پذير است، يعني الگوريتمهايي وجود دارد كه به هر جمله ايجاب شونده پاسخ مثبت مي‌دهد. امّا هيچ الگوريتمي وجود ندارد كه به هر جمله ايجاب‌ناپذير پاسخ منفي بدهد.
مشكلات گزاره اي سازي نمودن
• به نظر مي رسد كه گزاره اي سازي كردن جملات نامربوط زيادي توليد مي كند. براي مثال از جملات زير:
∀x King(x) ∧ Greedy(x) ⇒ Evil(x)
King(John)
Brother(Richard,John)
حاصل Evil(John) است ، اما گزاره اي سازي كردن حقايق زيادي مانند Greedy(Richard) توليد مي كند كه نامربوط مي باشند
يكسان سازي (Unification ) : حل مشکل گزاره سازی:سازگار بودن دو جمله
اگر يک جایگزینی θ وجود داشته باشد كه مقدم استلزام را با جملات موجود در پایگاه دانش، يكسان‌سازي كند، یا به عبارتی يكسان سازی، اين است كه ما فقط مي خواهيم جايگزين هايي براي عباراتي كه به ما كمك مي كنند چيزهايي را ثابت نماييم پيدا كنيم .آنگاه مي‌توان با اعمال θ، تالي استلزام را اظهار نمود. مانند جايگزيني{x / John} در پایگاه دانش، Evil (John) را نتیجه می‌دهد.
x King (x) Greedy (x) Evil (x)
King (John) Greedy (John) Brother (Richard, John)
ابتدا باید بتوان روشی برای انتخاب مناسب x پیدا کرد (یکسان سازی).
Unify(α,β) = θ if αθ = βθ
{y/John,x/Mother(John)}}
{fail}
{x/OJ,y/John}}
{x/Jane}}
Unification: دو ترم s و t اصطلاحاً unifiable هستند اگر يک جانشينی مانند
وجود داشته باشد به طوری که .
.
قیاس استثنائی تعمیم یافته
آیا می‌توان در پایگاه دانش با انتخاب مقداری برای x ، یک دفعه یک واقعیت را استنتاج کرد؟
x King (x) Greedy (x) Evil (x)
King (John)
y Greedy (y)
Brother (Richard, John)
برای این کار باید قانون
p1', p2', … , pn', ( p1 p2 … pn q)
Subst(θ,q)
p1' is King(John) p1 is King(x)
p2' is Greedy(y) p2 is Greedy(x)
θ is {x/John,y/John} q is Evil(x)
q θ is Evil(John)
در این قانون اگر جمله هایی به صورت ^ با هم ترکیب شوند و جمله ی دیگری را ایجاد کنند. در را الزام می کرد با وجود چند جمله به تعداد جملات ترکیبی می توان جایگزاری مقادیرθ در q را طبق شرط یکسان سازی نتیجه گرفت که به آن قیاس استثنایی توسعه یافته می گویند
