💻 computer science

Interpolation in Proof Theory

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

المؤلفون الأصليون: Iris van der Giessen, Raheleh Jalali, Roman Kuznets

نُشر 2026-02-19

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Iris van der Giessen, Raheleh Jalali, Roman Kuznets

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

تخيل أنك محقق يحاول حل لغز ما. لديك مقدمة (الأدلة التي وجدتها، ولنسمّها A) ونتيجة (الحكم الذي توصلت إليه، ولنسمّها B). وأنت تعلم أنه إذا كانت A صحيحة، فلا بد أن تكون B صحيحة.

الآن، تخيل شخصًا ثالثًا، وهو الوسيط (Mediator)، الذي يحتاج إلى شرح لماذا تؤدي A إلى B، لكن هذا الوسيط مسموح له فقط باستخدام الكلمات التي تظهر في كل من A و B. لا يمكنه استخدام أي مصطلحات سرية من A ليست موجودة في B، ولا يمكنه استخدام أي مصطلحات قانونية من B ليست موجود في A.

المُستنتِج (Interpolant) هو ذلك التفسير المثالي، "الحلقة الوسطى" التي تربط بين الجانبين باستخدام المفردات المشتركة فقط.

هذه الورقة هي دليل تعليمات ضخم لبناء الجسور. فهي تعلم المنطقيين (المحققين) كيفية بناء هذه الجسور باستخدام أنواع مختلفة من أنظمة الإثبات (أدوات المهنة).

إليك تفصيل الأفكية الرئيسية لهذه الورقة باستخدام تشبيهات بسيطة:

1. فرق البناء الرئيسيتان

تركز الورقة على فريقين مشهورين من البنائين لديهم طرق مختلفة في بناء هذه الجسور.

فريق ماهارا (فريق "التقسيم"):
- كيف يعملون: ينظرون إلى البرهان بأك-مله (الرحلة من A إلى B) ويقسمونه من المنتصف تمامًا. يتتبعون كل خطوة في الرحلة، باحثين عن الأدلة على اليسار والنتيجة على اليمين.
- الخدعة السحرية: بينما يسيرون عائدين من النتيجة إلى الأدلة، يبنون الجسر قطعة قطعة. إذا كانت الخطوة تستخدم كلمة موجودة فقط في اليسار، فإنهم يستبعدونها. وإذا كانت تستخدم كلمة موجودة فقط في اليمين، فإنهم يستبعدونها أيضًا. أما إذا كانت تستخدم كلمة مشتركة، فإنهم يحتفظون بها.
- النتيجة: ينتجون جسرًا يعمل لأي حالة محددة (استكمال كرايج - Craig Interpolation).
- التطوير: أحيانًا، يمكنهم أيضًا إخبارك ما إذا كانت الكلمات المشتركة تُستخدم بشكل إيجابي (كقوة) أو سلبي (كنقطة ضعف). وهذا ما يسمى استكمال ليندون (Lyndon Interpolation).
فريق بيتس (الفريق "العالمي"):
- كيف يعملون: هم أكثر طموحًا. لا يريدون فقط بناء جسر لـ A و B محددين، بل يريدون بناء جسر عالمي يعمل لأي B، طالما ظلت A كما هي.
- الخدعة السحرية: يعملون كمهندس معماري بارع يمكنه "حذف" متغير معين (كلمة معينة) من صيغة واستبداله بصيغة جديدة مبسطة تلخص كل ما يمكن أن تعنيه تلك الكلمة.
- النتيجة: هذا ما يسمى الاستكمال الموحد (Uniform Interpolation). إنه يشبه وجود محول "وصل وشغل" (plug-and-play) يناسب أي مقبس.

2. المشكلة: الأدوات القديمة لا تناسب دائمًا

لفترة طويلة، امتلك المنطقيون نوعًا واحدًا فقط من الأدوات: حساب المتواليات القياسي (Standard Sequent Calculus). فكر في هذا كقطعة ورق مسطحة قياسية حيث تكتب الصيغ في صفوف.

المشكلة: بالنسبة لبعض المنطقيات المعقدة (مثل بعض المنطق الجهي أو المنطق الضبابي)، يكون محاولة بناء جسر على ورقة مسطحة أمرًا مستحيلاً. الورقة تستمر في التمزق، أو ينهار الجسر.
حل الورقة: يقول المؤلفون: "لنقم بترقية أدواتنا!"، حيث قدموا حسابات المتواليات المعممة (Generalized Sequent Calculi).

3. الأدوات الجديدة: الطباعة ثلاثية الأبعاد والخرائط المسمّاة

لبناء جسور لأصعب أنواع المنطق، تقترح الورقة ثلاث طرق بناء متقدمة:

المتواليات المسمّاة (طريقة "الخريطة"):
- تخيل بدلًا من مجرد كتابة الصيغ، أنك ترفق إحداثيات GPS (تسمية/Label) بكل جملة.
- تشبيه: بدلًا من قول "إنها تمطر"، تقول "في الموقع 1، إنها تمطر".
- هذا يساعد البنائين على تتبع أين تتحقق الحقيقة بالضبط. إذا كان المنطق يتضمن "الإمكانية" أو "الضرورة" (مثل "قد تمطر غدًا")، فإن التسميات تعمل كخريطة توضح العوالم الممكنة المختلفة. هذا يجعل بناء الجسر أسهل بكثير لأنك تستطيع رؤية التضاريس بوضوح.
المتواليات الفائقة (طريقة "الصفحات المتعددة"):
- تخيل أن لديك كومة من الأوراق بدلًا من ورقة واحدة. يمكنك كتابة أجزاء مختلفة من الحجة في صفحات مختلفة وربطها ببعضها.
- تشبيه: يشبه الأمر امتلاك جدول بيانات بتبويبات متعددة. إذا أصبح أحد التبويبات مزدحمًا جدًا، تنقل الفائض إلى التبويب التالي. هذه المرونة تسمح لك ببناء جسور لمنطق أكثر تعقيدًا من صفحة واحدة.
المتواليات المتداخلة (طريقة "دمية الماتريوشكا"):
- تخيل وضع برهان داخل صندوق، وهذا الصندوق داخل صندوق آخر.
- تشبيه: مثل دمى الماتريوشكا (الدمى الروسية المتداخلة). يمكنك أن تملك عبارة عن عالم، داخل عبارة عن عالم داخل ذلك العالم. هذا مثالي للتعامل مع طبقات عميقة من سيناريوهات "ماذا لو".

4. "نظرية البرهان العالمية" (فحص المخطط الهيكلي)

تناقش الورقة أيضًا مفهومًا رفيع المستوى وهو نظرية البرهان العالمية (Universal Proof Theory).

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

5. لماذا يهم هذا؟

قد تسأل: "لماذا نهتم ببناء هذه الجسور المنطقية؟"

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

ملخص

هذه الورقة هي دليل شامل للمنطقيين. وهي تقول:

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

إنها تحول العمل المجرد والممل للمنطق الرياضي إلى مهمة هندسية عملية وبنائية.

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

تتناول الورقة البحثية تحدي إثبات خصائص الاستيفاء (وتحديداً استيفاء كريج - CIP، واستيفاء ليندون - LIP، والاستيفاء الموحد - UIP) عبر طيف واسع من المنطق غير الكلاسيكي، بما في ذلك المنطق الكلاسيكي، والحدسي، والمنطقي (modal)، والمنطق تحت البنيوي (substructural).

بينما توجد طرق دلالية (semantic)، إلا أنها غالباً ما تفتقر إلى البنائية. تركز الورقة على الطرق النظرية للبرهان (proof-theoretic methods)، وهي طرق بنائية وخوارزمية. ومع ذلك، تواجه الطرق التقليدية قيوداً:

طريقة ماهارا (Maehara's method): (المعتمدة على حسابات التتابعات - sequent calculi) هي طريقة بنائية، لكنها غالباً ما تفشل في إثبات استيفاء ليندون (الحفاظ على القطبية) للمنطق الذي يفتقر إلى حسابات تتابعية خالية من القطع (cut-free) أو حيث تؤدي القطوع القياسية إلى تعطيل القطبية.
طريقة بيتس (Pitts' method): (للاستيفاء الموحد) تتطلب خصائص إنهاء محددة تفتقر إليها العديد من الحسابات القياسية.
العديد من المنطقيات (مثل S5، وGödel-Dummett) لا تقبل حسابات تتابعية قياسية خالية من القطع، مما يجعل إثباتات الاستيفاء التقليدية صعبة أو مستحيلة.
هناك نقص في إطار عمل موحد لتحديد أي المنطقيات تمتلك خصائص الاستيفاء، ولماذا تفشل بعض الأنظمة البرهانية الجيدة في تحقيقها.

2. المنهجية

يستخدم المؤلفون نهجاً نظرياً برهانياً متعدد الأوجه، ينتقل من حسابات التتابعات القياسية إلى الهياكل المعممة وإطار عمل ميتا-نظري:

أ. طريقة ماهارا (التتابعات المنقسمة - Split Sequents)

الفكرة الجوهرية: بدلاً من الاستيفاء بين المقدم واللحاق، تقوم الطريقة بالاستيفاء بين "انقسام أيسر" و"انقسام أيمن" للتتابع ( $\Gamma; \Gamma' \Rightarrow \Delta; \Delta'$ ).
الآلية: عند إعطاء برهان لـ $\varphi \to \psi$ ، تقوم الطريقة ببناء مستوفٍ $\theta$ عن طريق الاستقراء على شجرة البرهان. يتتبع الانقسام أصل الصيغ (من $\varphi$ أو $\psi$ ) لضمان شرط المتغيرات ( $Var(\theta) \subseteq Var(\varphi) \cap Var(\psi)$ ).
التوسعات: تناقش الورقة القطوع المقيدة (التحليلية، شبه التحليلية، أحادية اللون) للتعامل مع منطقيات مثل S5 التي تفتقر إلى حسابات خالية من القطع، رغم أن هذه الأخيرة غالباً ما تفشل في الحفاظ على القطبية من أجل LIP.

ب. طريقة بيتس (الاستيفاء الموحد)

الفكرة الجوهرية: بناء مستوفيات موحدة ( $\exists p \varphi, \forall p \varphi$ ) تعمل لأي سياق، مما يفسر فعلياً التكميم الاقتراحي داخل المنطق.
الآلية: تعتمد على حسابات تتابعية ذات إنهاء قوي (strongly terminating). يتم بناء المستوفي عبر بحث برهاني من الأسفل إلى الأعلى (حتى بالنسبة للتتابعات غير المثبتة)، حيث يتم تعريف المستوفي بشكل استقرائي بناءً على القاعدة المطبقة.
القيد: تتطلب حسابات حيث تؤدي تطبيقات القواعد إلى تقليل مقياس الوزن بشكل صارم (مثل تجنب الانكماش - contraction في الصيغة الرئيسية).

ج. النظرية البرهانية الشاملة (Universal Proof Theory)

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

د. حسابات التتابعات المعممة (الموسومة، الفائقة، المتداخلة)

الدافع: للمنطقيات التي تفشل فيها التتابعات القياسية (مثل S5، GL)، يستخدم المؤلفون حسابات التتابعات الموسومة (Labelled Sequent Calculi) (التي تدمج الدلالات الكريبكية مباشرة في التركيب عبر العلامات $i: \varphi$ والعلاقات $iRj$ ).
الاستيفاء الموسوم: المستويات ليست مجرد صيغ بل هي صيغ متعددة الأشكال (تركيبات بولينية من الصيغ الموسومة).
استراتيجية الهندسة العكسية: يصنف المؤلفون القواعد إلى أنواع محلية، وتجميعية، وتشتتية بناءً على سلوكها الدلالي.
- المحلية: يتم الحفاظ على المستوفي.
- التجميعية/التشتتية: يتم دمج المستويات عبر $\land$ أو $\lor$ .
- المنطقية ( $\square$ / $\diamond$ ): تتطلب تحويلات معقدة للتعامل مع العلامات الجديدة التي يتم إدخالها في المقدمات (مثل تحويل $j:\varphi$ إلى $i:\square\varphi$ ).

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

مسح شامل وتوحيد: توحد الورقة بين طريقتي ماهارا وبيتس، وتوضح كيفية امتدادهما إلى المنطقيات المودالية وتحت البنيوية.
إطار الاستيفاء الموسوم: توفر طريقة بنائية قوية لإثبات استيفاء ليندون (LIP) باستخدام التتابعات الموسومة. يعد هذا تحسيناً كبيراً مقارنة بطرق التتابعات القياسية، التي غالباً ما تفشل في الحفاظ على القطبية لمنطق مثل S5.
نتائج النظرية البرهانية الشاملة:
- الإيجابية: تحدد أن المنطقيات التي تمتلك حسابات شبه تحليلية ونهائية بالكامل تمتلك UIP.
- السلبية: تثبت أن معظم المنطقيات الوسيطة والعديد من المنطقيات المودالية (مثل امتدادات S4، K4) لا يمكن أن تمتلك حسابات تتابعية شبه تحليلية لأنها تفتقر إلى الاستيفاء. وهذا يرسخ رابطاً عميقاً بين وجود أنظمة برهانية "جيدة" وخصائص الاستيفاء.
البناء الخوارزمي: تفصل الورقة الخوارزميات لبناء المستويات لـ:
- المنطق الكلاسيكي/الحدسي (ماهارا).
- المنطق المودالي K (بيتس).
- المنطقيات المعرفة بشروط إطار (عبر التتابعات الموسومة).
التعامل مع القواعد غير القابلة للاستيفاء: توضح أن وجود حساب خالٍ من القطع لا يضمن الاستيفاء؛ إذ قد تتطلب هياكل قواعد معينة (مثل تلك الموجودة في منطق Gödel-Dummett) حسابات أكثر تعقيداً (فائقة/متداخلة) لإثبات الاستيفاء.

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

المنطقيات المودالية:
- تم إثبات CIP وLIP لـ المكعب المودالي بأكمله (K, T, D, K4, S4, S5, إلخ) باستخدام التتابعات الموسومة.
- أثبتت أن S5 يقبل LIP عبر التتابعات الموسومة، بينما تفشل طرق ماهارا القياسية مع القطوع التحليلية في إثبات LIP لـ S5.
- أظهرت أن منطقيات مثل GL (Gödel-Löb) تمتلك CIP ولكنها تتطلب براهين دورية أو معالجات محددة لـ LIP.
المنطقيات الوسيطة:
- أكدت أن 7 منطقيات وسيطة متسقة فقط (IPC, LC, KC, Bd2, Sm, GSc, CPC) تمتلك CIP/UIP.
- استخدمت هذا لإثبات أن أي منطقية وسيطة أخرى لا تقبل حساباً تتابعياً شبه تحليلي.
المنطقيات تحت البنيوية والخطية:
- وسعت النتائج لتشمل منطقيات مثل MALL، وILL، والمنطقيات الضبابية (MTL, BL).
- حددت عائلات من المنطقيات (مثل بعض امتدادات MALL، ومنطقيات الصلة) التي تفتقر إلى CIP وبالتالي لا يمكنها امتلاك حسابات شبه تحليلية.
الاستيفاء الموحد:
- قدمت أول إثبات برهاني لـ استيفاء ليندون الموحد (ULIP) للمنطق K5.
- قامت بصياغة بناء المستويات الموحدة في Coq/Rocq لـ IPC، وK، وGL، وiSL.

5. الأهمية

الطبيعة البنائية: على عكس الإثباتات الدلالية، توفر هذه الطرق خوارزميات صريحة لحساب المستويات، وهو أمر بالغ الأهمية لتطبيقات مثل تعقيد البرهان (مثلاً NP مقابل coNP)، وفحص النماذج (model checking)، وتمثيل المعرفة.
الربط بين التركيب والدلالة: يربط نهج التتابعات الموسومة بأناقة بين النظرية البرهانية والدلالات الكريبكية، مما يسمح باشتقاق الاستيفاء للمنطقيات المعرفة حصرياً بشروط الإطار.
النتائج السلبية كأدوات: يحول تطبيق النظرية البرهانية الشاملة خصائص الاستيفاء إلى أداة لـ نتائج الاستحالة. إذا كان المنطق يفتقر إلى الاستيفاء، يمكن للمرء أن يستنتج فوراً أنه لا يمكن أن يمتلك نظاماً برهانياً "جيداً" (شبه تحليلي)، مما يوفر على الباحثين محاولات بناء مثل هذه الحسابات.
المنفعة العملية: تعمل الورقة كـ "دليل" للباحثين: لإثبات الاستيفاء لمنطق جديد، يتم التحقق مما إذا كانت قواعد حسابه تتناسب مع الأنماط "المحلية/التجميعية/التشتتية" القياسية أو ما إذا كانت تتطلب تحويلات محددة (مثل قواعد تشبه $\square$ للعلامات الجديدة).

باختصار، تثبت الورقة أن الاستيفاء ليس مجرد خاصية منطقية بل هو قيد هيكلي على الأنظمة البرهانية. فهي توفر الأدوات اللازمة لإثبات الاستيفاء بنائياً لمجموعة واسعة من المنطقيات باستخدام حسابات التتابعات المعممة، وتقدم إطاراً صارماً لفهم حدود المنهجيات النظرية البرهانية.