💻 computer science

Inductive Satisfiability Certification for Universal Quantifiers and Uninterpreted Function Symbols

تقدم هذه الورقة طريقة استنتاجية لإثبات قابلية الإرضاء للصيغ التي تجمع بين المكممات الكلية ورموز الدوال غير المفسرة، والتي تنجح في إثبات قابلية الإرضاء في الحالات التي تفشل فيها أدوات حل مسائل المنطق الرياضي (SMT) الحالية بسبب عدم القدرة على بناء نماذج صريحة.

المؤلفون الأصليون: Stefan Ratschan, Anggha Nugraha, Mikoláš Janota, Marek Dančo

نُشر 2026-02-19

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Stefan Ratschan, Anggha Nugraha, Mikoláš Janota, Marek Dančo

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك محقق يحاول حل لغز: هل تسمح مجموعة محددة من القواعد بوجود حل بالفعل؟

في عالم علوم الحاسوب، يُسمى هذا "مشكلة القابلية للإرضاء" (Satisfiability). لديك لغز منطقي (صيغة رياضية) يتضمن متغيرات، وعمليات حسابية، و"دوال الصندوق الأسود" الغامضة (مثل آلة تأخذ رقماً وتخرج رقماً آخر، لكنك لا تعرف كيف تعمل من الداخل). تريد أن تعرف: هل هناك أي طريقة لضبط الأرقام بحيث تكون جميع القواعد راضية في نفس الوقت؟

المشكلة: فخ "اللانهاية"

المحققون الحاسوبيون الحاليون (يُطلق عليهم SMT Solvers) بارعون للغاية في إثبات أن اللغز مستحيل (غير قابل للإرضاء). يمكنهم بسرعة العثور على تناقض، مثل "هذه القاعدة تقول إن X تساوي 5، لكن تلك القاعدة تقول إن X تساوي 6".

ومع ذلك، هم يواجهون صعوبة عندما تكون الإجابة هي نعم (قابلة للإرضاء)، خاصة إذا كان الحل يتطلب عدداً لانهائياً من الخطوات أو نمطاً يستمر إلى الأبد.

الطريقة القديمة: لإثبات وجود حل، يحاول هؤلاء المحققون بناء نموذج مادي للإجابة. يحاولون كتابة قيمة كل رقم على حدة.
الفشل: إذا كان الحل يتطلب نمطاً لانهائياً (مثل دالة تعمل لكل الأعداد الصحيحة من سالب ما لا نهاية إلى موجب ما لا نهاية)، فإن الحاسوب ينفد منه الذاكرة. الأمر يشبه محاولة كتابة قيمة كل حبة رمل على الشاطئ لإثبات وجود الشاطئ. إذا كان الشاطئ لانهائياً، فلن تنتهي أبداً من الكتابة.

الفكرة الجديدة: "شهادة الاستقراء"

يقترح مؤلفو هذه الورقة البحثية طريقة أذكى. بدلاً من محاولة كتابة الشاطئ بأكمله، يريدون كتابة خريطة أو وصفة تثبت وجود الشاطئ.

يسمون هذا "شهادة القابلية للإرضاء" (Satisfiability Certificate).

فكر في الأمر مثل تأثير الدومينو:

الحالة الأساسية: تثبت أن القواعد تعمل لمجموعة صغيرة ومحدودة من الأرقام (مثلاً: 0، 1، و2).
خطوة الاستقراء: تثبت قاعدة تقول: "إذا كانت القواعد تعمل للرقم N، فإنها ستعمل تلقائياً للرقم N+1".

إذا امتلكت كليهما، فلن تحتاج إلى فحص كل رقم. كل ما عليك فعله هو فحص نقطة البداية وقاعدة الانتقال للأمام. هذا هو الاستقراء الرياضي (Mathematical Induction).

كيف يعمل الأمر (الاستعارة)

تخيل أنك تبني جسراً فوق نهر عريض بشكل لا نهائي.

المحللون القدامى: يحاولون وضع كل طوبة من البداية حتى النهاية. يصابون بالتعب ويستسلمون لأن النهر طويل جداً.
هذه الطريقة الجديدة:
1. يضعون أساساً متيناً للأمتار القليلة الأولى (وهي شهادة ما قبل القابلية للإرضاء).
2. يصممون آلة (تسمى المُنتِج - Propagator) يمكنها أخذ أي قسم موجود من الجسر وتمديده تلقائياً بمتر واحد، مع ضمان أن الجزء الجديد يتناسب تماماً مع الجزء القديم.
3. يثبتون أن هذه الآلة تعمل لأي اتجاه (للأمام أو للخلف).

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

شرط "ReqPivot"

هناك عقبة. هذه "الآلة" (خطوة الاستقراء) لا تعمل إلا إذا كانت قواعد اللغز "منضبطة" أو "سلسة".
تقدم الورقة شرطاً يسمى ReqPivot.

التشبيه: تخيل أنك تحاول تمديد نمط ما. إذا كان النمط فوضوياً (مثلاً: "إذا كنت في الخطوة 1، اذهب إلى 100؛ وإذا كنت في الخطوة 2، اذهب إلى 3")، فلن تتمكن بسهولة من التنبؤ بالخطوة التالية.
يضمن شرط ReqPivot أن النمط "سلس" بما يكفي لكي تتمكن الآلة من التنبؤ بالخطوة التالية بشكل موثوق. إنه يتحقق مما إذا كانت "أقصى" و"أدنى" قيم في النمط يمكن التعامل معها باستمرار.

لماذا هذا مهم؟

اختبر المؤلفون طريقتهم على مشكلات استعصت على أفضل المحللين الحاليين في العالم (مثل Z3 وCVC5).

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

الملخص

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

هذا يسمح للحواسيب بأن تقول بثقة: "نعم، يوجد حل"، حتى عندما يكون هذا الحل كبيراً جداً بحيث لا يمكن كتابته أبداً.

إليك ملخص تقني مفصل لورقة البحث بعنوان "التحقق من القابلية للإرضاء الاستقرائي للمسورات الكلية ورموز الدوال غير المفسرة" من قبل Ratschan وآخرون.

1. بيان المشكلة

تعالج الورقة البحثية قصوراً حرجاً في أدوات حل مسائل "الرضا مع نظريات إضافية" (SMT) الحالية: وهو عدم القدرة على إثبات القابلية للإرضاء (satisfiability) بكفاءة للمعادلات التي تحتوي على مسورات كلية (universal quantifiers) ورموز دوال غير مفسرة (uninterpreted function symbols - UFS)، لا سيما عند دمجها مع الحساب الخطي للأعداد الصحيحة (LIA).

السياق: يتوافق هذا المزيج مع منطق SMTLIB المعروف بـ UFLIA (الدوال غير المفسرة مع الحساب الخطي للأعداد الصحيحة)، وهو منطق غير قابل للتقرير (undecidable) بشكل عام.
القيود الحالية:
- أدوات حل SMT محسنة للغاية لإثبات عدم القابلية للإرضاء (unsatisfiability) (التفنيد).
- لإثبات القابلية للإرضاء، تعتمد الأدوات عادةً على بناء نموذج صريح (إيجاد نموذج محدود).
- يفشل هذا النهج في المعادلات التي يكون فيها أصغر نموذج لها لانهائياً (مثل $f(0)=0 \land \forall x. f(x+1) = f(x)+1$ ) أو حيث يكون أصغر نموذج محدود ضخماً بشكل يعجز معه الحساب.
- تعاني الاستدلالات (heuristics) الحالية غالباً مع الاستنتاج الخاص بالمصفوفات والقيود القائمة على الإزاحة (مثل $a[i+c]$ ).

2. المنهجية

يقترح المؤلفون نهجاً بديلاً: التحقق من القابلية للإرضاء الاستقرائي (Inductive Satisfiability Certification). بدلاً من بناء نموذج كامل، تقوم الخوارزمية بتوليد شهادة (certificate) تثبت القابلية للإرضاء عبر حجج استقرائية.

المفاهيم الأساسية

شهادة القابلية للإرضاء: كائن يتكون من:
1. شهادة ما قبل الإرضاء (I): تفسير جزئي (تفسير الخلايا) يخصص قيمًا لمصطلحات أرضية محددة ومعاملات الدوال غير المفسرة لتحقيق الجزء الخالي من المسورات ( $F$ ) ومعاملات الجزء المسور ( $Q$ ).
2. ترتيب جيد ( $\preceq$ ): يحدد اتجاه الاستقراء على نطاق المتغيرات المسورة.
3. الخلايا المنتشرة ( $X_z$ ): لكل حالة تحقق $z$ للمتغير المسور، هناك مجموعة من الخلايا الجديدة التي تُحدد قيمها بواسطة ناشر الإرضاء (Satisfiability Propagator).
4. ناشر الإرضاء: آلية تثبت أنه لأي حالة تحقق $z$ ، يمكن تخصيص قيم للخلايا المنتشرة بحيث يتحقق الشرط $Q$ ، دون التعارض مع القيم المخصصة مسبقاً.

الخوارزمية (جزء UFLIA)

تركز الورقة على جزء محدد من UFLIA مع هذه القيود:

الدوال غير المفسرة لها رتبة (arity) 1.
متغير مسور واحد فقط ( $x$ ).
معاملات موحدة للمتغير المسور في معاملات الدوال (على سبيل المثال، $f(2x+3)$ مسموح به، ولكن $f(2x+3) = f(x+1)$ ليس كذلك).

الخوارزمية (الخوارزمية 1):

التهيئة: ابدأ بفاصل أساسي $B = [0, 0]$ .
فحص الأساس: تحقق مما إذا كانت المعادلة قابلة للإرضاء لجميع حالات التحقق $x \in B$ .
فحص الانتشار (شرط ReqPivot):
- تتحقق الخوارزمية مما إذا كانت المعادلة تحقق شرط ReqPivot. يتضمن ذلك إيجاد مجموعات فرعية من المصطلحات ( $S$ ) التي تكون "متطرفة" (على سبيل المثال، أصغر أو أكبر المعاملات) بحيث يمكن نشر القيم للخارج من الفاصل $B$ إلى اللانهاية في كلا الاتجاهين الموجب ( $+$ ) والسالب ($-$).
- تتحقق من قابلية الانتشار (Propagability): هل يمكن تخصيص قيم للمعاملات المتطرفة لتحقيق $Q$ بغض النظر عن قيم المعاملات غير المتطرفة؟
- تتحقق من شروط التصادم (Clash Conditions): التأكد من أن الخلايا المنتشرة لا تتصادم مع المصطلحات الأرضية المعرفة في الجزء الخالي من المسورات $F$ .
التكرار: إذا تم استيفاء الفاصل الأساسي وشروط الانتشار، فإنه يتم إرجاع Sat (قابل للإرضاء). إذا لم يكن الأمر كذلك، قم بتوسيع الفاصل $B$ بشكل متماثل وكرر العملية.
الإنهاء: تضمن الخوارزمية الإنهاء وإرجاع Sat إذا كانت المعادلة المدخلة قابلة للإرضاء وتستوفي شرط ReqPivot.

الترميز القضايا (Propositional Encoding)

لتجنب التضخم الأسي الناتج عن التحقق من جميع المجموعات الفرعية $S$ صراحةً، قدم المؤلفون ترميز CNF مدمجاً. يستخدمون متغيرات بولينية مساعدة لتمثيل العضوية في المجموعات المتطرفة، مما يسمح بالتحقق من الشروط بكفاءة بواسطة أدوات حل SAT/SMT القياسية.

3. المساهمات الرئيسية

إطار التحقق الاستقرائي: تقديم تعريف رسمي لـ "شهادة القابلية للإرضاء" الذي يستبدل بناء النموذج الصريح بالبراهين الاستقرائية. هذا يسمح بإثبات القابلية للإرضاء للمعادلات ذات النماذج اللانهائية.
شرط ReqPivot: تحديد شرط دلالي يضمن وجود استراتيجية انتشار استقرائية صالحة لمعادلات UFLIA.
خوارزمية لـ UFLIA: تطوير خوارزمية ملموسة تبحث عن فاصل صالح واستراتيجية انتشار، مما يثبت سلامة (soundness) واكتمالاً نسبياً (الكمال تحت فرضية ReqPivot).
الترميز الفعال: توفير ترميز CNF لجعل اختيار المجموعات الفرعية للانتشار ممكناً من الناحية الحسابية.
استخراج النموذج: توضيح كيفية استخراج نموذج حسابي (قيم للرموز الدالية) من الشهادة باستخدام دالة تقييم عودي (recursive evaluation function).

4. النتائج التجريبية

قام المؤلفون بتنفيذ الخوارزمية باستخدام لغة Python وواجهة برمجة تطبيقات Z3 وقارنوها بأدوات الحل المتطورة Z3 و CVC5 (بما في ذلك وضع SyGuS الخاص بـ CVC5).

مجموعة الاختبار: 28 مسألة قابلة للإرضاء تم تصميمها يدوياً تتضمن UFS و LIA، مع تباين في حجم النموذج (يتم التحكم فيه بواسطة المعامل $c$ ).
الأداء:
- الخوارزمية المقترحة: حلت جميع المسائل الـ 28 في وقت مهمل، بغض النظر عن معامل حجم النموذج $c$ . كان وقت التشغيل مستقراً لأن المنطق الاستقرائي يجرد حجم النطاق.
- Z3: عانى بشكل كبير. بالنسبة لقيم $c$ الأكبر، غالباً ما أعاد نتيجة "Unknown" (غير معروف) أو انتهى الوقت المخصص. حل 4 فقط من المسائل غير المحدودة.
- CVC5 (القياسي): انتهى الوقت أو فشل مع زيادة قيمة $c$ .
- CVC5 (SyGuS): حل 15 مسألة بسرعة ولكنه فشل في المعادلات التي تتطلب دوال خارج قواعد النحو الافتراضية الخاصة به (مثل $f(x+1) = 2f(x)$ ).
النتيجة الرئيسية: النهج الاستقرائي يتفوق في المعادلات التي يكون فيها النموذج لانهائياً أو ضخماً جداً للبناء الصريح، وهو سيناريو تفشل فيه أدوات حل SMT الحالية.

5. الأهمية والعمل المستقبلي

سد الفجوة: يعمل هذا العمل على سد فجوة كبيرة في الاستدلال الآلي من خلال توفير طريقة موثوقة لإثبات القابلية للإرضاء لفئة من المسائل غير القابلة للتقرير والتي تشيع في التحقق من البرامج (مثل خصائص المصفوفات).
ما وراء النماذج المحدودة: يتيح التحقق من الأنظمة التي تكون مساحة الحالة فيها لانهائية، وهي مهمة كانت مستحيلة لأدوات حل SMT القياسية.
الاتجاهات المستقبلية: يهدف المؤلفون إلى تخفيف القيود النحوية (مثل التعامل مع متغيرات مسورة متعددة بمعاملات غير موحدة) وشرط ReqPivot الدلالي، ربما من خلال استخدام أشكال أقوى من الاستقراء أو تعميم دعم النظرية.

باختاً، تقدم هذه الورقة تحولاً في النموذج من "إيجاد نموذج" إلى "التحقق من وجود نموذج عبر الاستقراء"، مما يوفر حلاً قوياً لفئة من المسائل التي تعجز عنها أفضل أدوات حل SMT حالياً.