Read in English

المنطق والمعرفة

مليون بند، أم واحد وستّون

تحويل صيغة قصيرة إلى الصورة العطفيّة النظاميّة بالتوزيع يعطي 1,048,576 بندًا و20,971,520 حرفًا؛ وتسمية الصيغ الجزئيّة تعطي 61 بندًا و160 حرفًا، أي بعامل 131,072 في الأحرف، ولا يضيع بذلك شيء البتّة: فعدد نماذج الصيغتين واحد، وقد فُحص ذلك استقصاءً. فالترميز، لا الحلّال، هو موضع الكسب أو الخسارة في مسألة القابليّة للإرضاء.

14 سبتمبر 2026قراءة 3 دقيقةKudos AI

المتطلبات المسبقة: المنطق وتمثيل المعرفة

الذكاء الاصطناعي الرياضيات

اسأل المعلّم الذكي عن هذا المقال

صيغة تُعاد كتابتها بنودًا، وبندان يحملان زوجًا متتامًّا ينزلقان معًا فينتج مُحلَّلهما، ثم تنغلق السلسلة على البند الفارغ.

للتحليل قاعدة استدلال واحدة، وهو يشترط أن يكون دخله في الصورة العطفيّة النظاميّة: عطفُ فصولٍ من الأحرف. ولكل صيغة قضويّة مكافئٌ في تلك الصورة، وهو ما يُقال عادةً كأنّه يحسم الأمر.

وإليك صيغةً تفرّق بين «له مكافئ» و«تستطيع تحمّل كلفته».

\varphi \;=\; (x_1 \wedge y_1) \vee (x_2 \wedge y_2) \vee \dots \vee (x_{20} \wedge y_{20}).

عشرون عطفًا، وأربعون متغيّرًا، وسطر واحد.

أ. بالتوزيع

التحويل المدرسي يوزّع $\vee$ على $\wedge$ . فكلٌّ من الفصول العشرين يسهم إمّا بـ $x$ وإمّا بـ $y$ في كل بند، مستقلًّا عن غيره، فيكون في الناتج بندٌ لكل اختيار:

2^{20} = 1{,}048{,}576

بندًا، طول كلٍّ منها عشرون حرفًا: أي 20,971,520 حرفًا جملةً. ولثلاثين فصلًا تصير 1,073,741,824 بندًا. فالتحويل صحيح، ومنتهٍ، وعديم النفع.

ب. بتسمية الصيغ الجزئيّة

البديل أن تُسمّي كل عطف. أدخِل $t_i$ وأكِّد $t_i \leftrightarrow (x_i \wedge y_i)$ ، وهو ثلاثة بنود:

(\neg t_i \vee x_i), \qquad (\neg t_i \vee y_i), \qquad (t_i \vee \neg x_i \vee \neg y_i),

ثم قل إنّ واحدًا منها على الأقلّ يصدق: $(t_1 \vee \dots \vee t_{20})$ .

وهذا $3 \times 20 + 1 = \mathbf{61}$ بندًا و160 حرفًا، مقابل 20,971,520. أي بعامل 131,072 في الأحرف، من قاعدة إعادة كتابة لا من حلّال أفضل. وهذا هو تحويل تسيتين، وهو ما تفعله واجهة كل حلّال SAT.

ج. ما الثمن

الخلاصة المعتادة أنّ الناتج مُرضًى معه لا مكافئ، وهو ما يبدو تنازلًا. ويحسن التدقيق في ضآلة هذا التنازل.

للصيغة الجديدة عشرون متغيّرًا زائدًا، فهي إذن صيغة على مفردات أخرى ولا يمكن أن تكافئ $\varphi$ بالمعنى الصارم. لكنّ كل $t_i$ مقيَّد: فالبنود الثلاثة تثبّته على قيمة صدق $x_i \wedge y_i$ بلا حرّيّة متبقّية. ومن ثَمّ يمتدّ كل نموذج لـ $\varphi$ إلى نموذج واحد بالضبط للترميز، والعدّ يؤكّد ذلك:

$n$	نماذج $\varphi$	نماذج الترميز
1	1	1
2	7	7
3	37	37
4	175	175

فُحص ذلك بتعداد كل إسناد، وعددها $2^{2n}$ لـ $\varphi$ و $2^{3n}$ للترميز. فالقابليّة للإرضاء محفوظة، والحلول محفوظة، وحتى عدد النماذج محفوظ. وغير المحفوظ هو قائمة المتغيّرات، وثمن ذلك خطوة إسقاط في النهاية.

تفاعلي: مليون عبارة، أو إحدى وستون

محور لوغاريتمي. يُرسم الترميزان معًا، والزر يختار أيهما يوصف.

عدد الفواصل n20

عبارات هذا الترميز: 1,048,576
حرفيات هذا الترميز: 20,971,520
النماذج، في أيٍّ منهما: 1,096,024,843,375
الموزَّع إلى Tseitin، حرفيات: 131,072x
الموزَّع إلى Tseitin، عبارات: 17,190x

العبارات الأولى: (x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5 ∨ x6 ∨ x7 ∨ x8 ∨ x9 ∨ x10 ∨ x11 ∨ x12 ∨ x13 ∨ x14 ∨ x15 ∨ x16 ∨ x17 ∨ x18 ∨ x19 ∨ x20), (y1 ∨ x2 ∨ x3 ∨ x4 ∨ x5 ∨ x6 ∨ x7 ∨ x8 ∨ x9 ∨ x10 ∨ x11 ∨ x12 ∨ x13 ∨ x14 ∨ x15 ∨ x16 ∨ x17 ∨ x18 ∨ x19 ∨ x20), (x1 ∨ y2 ∨ x3 ∨ x4 ∨ x5 ∨ x6 ∨ x7 ∨ x8 ∨ x9 ∨ x10 ∨ x11 ∨ x12 ∨ x13 ∨ x14 ∨ x15 ∨ x16 ∨ x17 ∨ x18 ∨ x19 ∨ x20), ... 1,048,576 عبارة في المجموع.

يختار التوزيع x أو y من كل فاصل من الفواصل الـ20 باستقلال، فيكتب 1,048,576 عبارة في كلٍّ منها 20 حرفية. نسبة الحرفيات 2 مرفوعًا إلى n - 3، فكل فاصل إضافي يضاعف الفجوة. وللترميزين 1,096,024,843,375 نموذجًا، أي 4 أس n ناقص 3 أس n، لأن كل متغير جديد مُجبَر على قيمة الاقتران الذي يسمّيه.

د. القاعدة نفسها

يأخذ التحليل بندين يحملان زوجًا متتامًّا وينتج مُحلَّلهما:

\frac{(\alpha \vee \ell) \qquad (\beta \vee \neg \ell)}{(\alpha \vee \beta)}.

وهو ليس تامًّا لاشتقاق اللوازم كيفما كانت - فمن $P$ لن يشتقّ أبدًا $P \vee Q$ وهو لازم - لكنّه تامٌّ للنقض: إن كانت مجموعة بنود غير قابلة للإرضاء فإنّ التحليل المتكرّر يشتقّ البند الفارغ. وهذا يكفي، لأنّ $\text{KB} \models \alpha$ يصدق بالضبط حين تكون $\text{KB} \wedge \neg\alpha$ غير قابلة للإرضاء.

وعلى البنود $\{P \vee Q,\; \neg P \vee R,\; \neg Q \vee R,\; \neg R\}$ يوجد نقض من أربع خطوات:

$\neg R$ مع $\neg P \vee R$ يعطي $\neg P$
$\neg R$ مع $\neg Q \vee R$ يعطي $\neg Q$
$P \vee Q$ مع $\neg P$ يعطي $Q$
$Q$ مع $\neg Q$ يعطي البند الفارغ.

أمّا الإشباع الأعمى - بتحليل كل زوج حتى لا يظهر جديد - فيشتقّ 8 بنود جديدة ويبلغ انغلاقًا من 12 قبل أن يصل. وعلى أربعة بنود لا فرق يُذكر. وهو الفرق نفسه الذي يفصل حلّالًا حديثًا مسوقًا بالتعارضات عن الخوارزميّة كما تُكتب في كتاب، وهو على النطاق الكبير كلُّ شيء.

يطبّق الشكل القاعدة نفسها على قاعدة معرفة أخرى، هي قاعدة النسيم من عالم Wumpus، $B_{1,1} \Leftrightarrow (P_{1,2} \vee P_{2,1})$ مع $\neg B_{1,1}$ : أربعة بنود والاستعلام المنفيّ، ويُتحقَّق من كل جواب على العوالم الثمانية الممكنة.

تفاعلي: دحضٌ، فقرةً فقرة

الجواب مرّتين: بالحلّ، وبتعداد العوالم الثمانية.

قاعدة المعرفة بالصورة العطفية، والسؤال منفيًّا في آخرها

!B11 v P12 v P21
!P12 v B11
!P21 v B11
!B11
P12

فقرات البداية: 5
فقرات جديدة: 5
الفقرة الفارغة: نعم
تعداد النماذج يوافق: نعم

النواتج، بترتيب ما وجده البرهان

!P12 v B11 + !B11 -> !P12
!P21 v B11 + !B11 -> !P21
!P12 v B11 + P12 -> B11
!B11 v P12 v P21 + !P12 -> !B11 v P21
P12 + !P12 -> []

اسأل هل تستلزم القاعدة

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

هـ. ما نأخذه من ذلك

الترجمة جزء من الخوارزميّة. فمسألةٌ تستحيل بعد التوزيع وتصير روتينيّة بعد تسيتين لم تكن يومًا مسألةً صعبة، بل كانت مسألةً سيّئة الترميز.
عُدّ الأحرف لا البنود. فالصورة الموزَّعة أعلاه سيّئة في الاثنين، لكنّ ترميزات تبدو متقاربة بعدد البنود كثيرًا ما تختلف برتبة قدر في الأحرف، وهي ما يمشي عليه الانتشار فعلًا.
«يوجد مكافئ في الصورة النظاميّة» قولٌ عن الوجود. وكذلك «كل مسألة في NP تُردّ إلى SAT». وكلاهما صحيح، ولا يقول أيٌّ منهما شيئًا عن حجم ما تحصل عليه.

المراجع والقراءات الإضافية

Stuart Russell, Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson (3rd edition), 2010· مكتبة مراجع Kudos AI

تُذكر الأعمال المحمية بحقوق النشر للمرجعية فقط ولا تُستضاف هنا؛ يرجى الرجوع إلى الناشر للوصول إليها.

الوسوم:#logic #cnf #resolution #sat #intermediate

قراءات ذات صلة

30 أغسطس 2026قراءة 7 دقيقةالمنطق والمعرفة

المنطق وتمثيل المعرفة

الاستدلال على ما يجب أن يكون صادقاً: النماذج والاستلزام محلولةً بالعدّ الشامل، والسلامة والاكتمال، ولماذا ينفد التعبير من منطق القضايا، وأين يلتقطه منطق الرتبة الأولى.

تمثيل المعرفةالذكاء الاصطناعي

18 أغسطس 2026قراءة 6 دقيقةالبحث والألعاب

نظرية الألعاب وتوازن ناش

الاستدلال الاستراتيجي حين لا يكون اللاعبون متعارضين تعارضاً صارماً: الاستراتيجيات المهيمنة، ومعضلة السجينين محلولةً من مصفوفة عوائدها، وتوازن ناش، وأمثلية باريتو، ولماذا قد يتعارض التوازن والكفاءة.

نظرية الألعابالذكاء الاصطناعيالرياضيات

14 سبتمبر 2026قراءة 3 دقيقةأسس الاحتمالات

أيّ توزيع خاطئ تريد؟

هدفٌ ثنائي المنوال، وغاوسيّة واحدة، واتّجاهان للتباعد نفسه. تصغير KL(P||Q) يمدّ الغاوسيّة على المنوالين بلا كتلة تُذكر حيث يقيم الهدف فعلًا؛ وتصغير KL(Q||P) يضعها على منوال واحد عند 0.6931 نات، وهي ln 2 حتى أربعة أرقام عشرية لا مصادفة. وكل مواءمة يحكم عليها المعيار الآخر بالكارثة: 2.0976 مقابل 15.2799.

تعلّم الآلةالرياضيات

← العودة إلى كل المقالات