النماذج والاستلزام

معظم هذا الموقع يقدّر كميات غير يقينية. أما هذا المسار فيطرح سؤالاً مختلفاً: بمعلومية ما يعرفه النظام أصلاً، ما الذي يجب أن يكون صادقاً؟ ولهذا السؤال جواب محدّد، والآلية التي تحسبه هي المنطق.

ثلاثة تعريفات

قاعدة المعرفة (KB) مجموعة عبارات مُثبَتة صادقةً. والنموذج إسناد كامل لقيم الصدق لكل رمز - أي عالم ممكن محدَّد بتمامه. وبكتابة $M(\alpha)$ لمجموعة النماذج التي تصدق فيها $\alpha$، تكون العلاقة المركزية هي الاستلزام:

$$\text{KB} \models \alpha \quad\text{iff}\quad M(\text{KB}) \subseteq M(\alpha).$$

أي أن $\alpha$ تصدق في كل نموذج تصدق فيه قاعدة المعرفة. وصورة راسل ونورفيغ تستحق الحفظ: تصوّر لوازم قاعدة المعرفة كومةَ قشّ و$\alpha$ إبرة، فـالاستلزام هو أن الإبرة في الكومة؛ والاستنتاج هو الإجراء الذي يجدها فيها. الأول واقعة تتعلّق بالمعنى، والثاني خوارزمية، ويمكن الحديث عنهما منفصلين.

البتّ فيه بالعدّ

قد تحوي ثلاث خانات حفرةً كلٌّ منها، فهناك $2^3 = 8$ عوالم ممكنة. وتقول قاعدة المعرفة أمرين: لا نسيم عند $[1,1]$، فجارتها $[1,2]$ خالية؛ وهناك نسيم عند $[2,1]$، فواحدة على الأقل من $[2,2]$ و$[3,1]$ تحوي حفرة.

ينجو ثلاثة نماذج. والآن اقرأ منها الاستنتاجات:

• «لا حفرة في $[1,2]$» صادقة في الثلاثة جميعاً، فهي مستلزَمة؛
• و«لا حفرة في $[2,2]$» كاذبة في اثنين منها، فهي غير مستلزَمة؛
• ولا نفيها كذلك، لأنها صادقة في الثالث.

عدم استلزام $\alpha$ ليس استلزاماً لـ$\lnot\alpha$. فنموذجان من الثلاثة يضعان حفرة في $[2,2]$ وواحد لا يضع، فالقرائن ببساطة لا تحسم تلك الخانة. والقول بـ«لا حفرة» أو بـ«حفرة» كلاهما دعوى لا تسندها قاعدة المعرفة - والجواب الأمين أن الأمر غير محسوم.

جرّبه مباشرةً. عُدّ العوالم الثمانية ودَع تعريف الاستلزام يجيب عن الأسئلة الثلاثة عنك:

وهذا الإجراء - عدّ كل نموذج، والتحقّق من أن $\alpha$ تصدق حيثما تصدق قاعدة المعرفة - هو فحص النماذج، وهو نقل مباشر للتعريف.

العوالم الثمانية كلها في الشكل أدناه، والثلاثة الناجية من قاعدة المعرفة معلَّمة. اختر نتيجةً يعلّم لك الجدول ما هو أنفع من ذلك: كلَّ عالم ناجٍ تكذب فيه تلك النتيجة. ففي حالة «لا حفرة في [2,2]» هناك عالمان، وكلٌّ منهما عالم متّسق تمامًا مع كل ما نعرفه، وهذا هو معنى «غير مستلزَمة»، ولهذا يكون تأكيد العكس بلا سند بالقدر نفسه. أوقِف إحدى قضايا القاعدة وراقب المجموعة الناجية تتّسع.

سليم ومكتمل ومكلف

ما إن يصير الاستنتاج إجراءً لا تعريفاً، تصير خاصيتان مهمّتين. فالإجراء سليم (ويسمّيه راسل ونورفيغ أيضاً حافظاً للصدق) إذا كان كل ما يشتقّه مستلزَماً فعلاً: فلا يعلن قط اكتشاف إبرة غير موجودة. وهو مكتمل إذا اشتقّ كل ما هو مستلزَم: فلا يفوّت شيئاً.

وفحص النماذج سليم ومكتمل معاً - سليم لأنه ينفّذ التعريف، ومكتمل لأنه يفحص كل نموذج. والمشكلة في الكلفة: فـ$n$ رمزاً تعطي $2^n$ نموذجاً، ويسجّل راسل ونورفيغ أن الاستلزام القضوي co-NP-كامل، فالسلوك الأسّي في أسوأ الحالات ذاتيّ لا ضعف في هذه الخوارزمية بعينها. وقد أعطتنا رموزنا الثلاثة ثمانية صفوف؛ وثلاثون منها تعطي أكثر من مليار.

وذلك هو دافع الدرس التالي. فالمبرهِن بالحلّ لا يعدّ العوالم إطلاقاً - بل يعالج العبارات نحوياً، مشتقّاً استنتاجات بقاعدة استنتاج واحدة. وأما ما لا يفعله أي مُستدِلّ عملي فهو بناء الجدول كلّه: إذ حلّالات SAT من نمط DPLL تبحث في إسنادات الصدق فعلاً، لكن إسناداً جزئياً واحداً في كل مرة.

قبل الاختبار

كن قادراً على صوغ الاستلزام علاقةَ احتواء بين مجموعتي نماذج، وتنفيذ عدّ صغير وقراءة ما يحسمه وما لا يحسمه، وتعريف السلامة والاكتمال كلٍّ على حدة، وقول لماذا يكون فحص النماذج دقيقاً وغير عملي في آن. وتغطّي مقالة المنطق وتمثيل المعرفة الأرضَ نفسها بإسهاب أكبر.