🔢 mathematics

Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof

यह शोध पत्र एक लोडिंग तंत्र वाले चक्रीय टेब्लो सिस्टम और इंटरपुलेंट्स की गणना के लिए एक संशोधित माएहारा विधि का उपयोग करते हुए यह रचनात्मक प्रमाण प्रदान करता है कि प्रपोजिशनल डायनेमिक लॉजिक (PDL) में क्रेग इंटरपोलेशन प्रॉपर्टी (Craig Interpolation Property) विद्यमान है, जिससे पिछले प्रयासों के वापस लिए जाने या आलोचना किए जाने के बाद एक लंबे समय से चले आ रहे खुले प्रश्न का समाधान होता है।

मूल लेखक: Manfred Borzechowski, Malvin Gattinger, Helle Hvid Hansen, Revantha Ramanayake, Francisco Trucco Dalmas, Yde Venema

प्रकाशित 2026-08-12

📖 4 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Manfred Borzechowski, Malvin Gattinger, Helle Hvid Hansen, Revantha Ramanayake, Francisco Trucco Dalmas, Yde Venema

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य को सुलझाने की कोशिश कर रहे हैं, लेकिन आपको केवल सुरागों के एक विशिष्ट सेट का उपयोग करने की अनुमति है। आपके पास एक गवाह (मान लीजिए कि वे "द एक्यूज़र" या "आरोपी" हैं) से एक लंबी, जटिल रिपोर्ट है और दूसरे ("द डिफेंडर" या "बचावकर्ता") से एक जवाबी रिपोर्ट है। आपका काम एक एकल, छोटा वाक्य खोजना है जो उनके बीच के संघर्ष को स्पष्ट करता हो। यह वाक्य "मध्य मार्ग" होना चाहिए: यह तब सत्य होगा जब आरोपी सही हो, और यह तब असत्य होगा यदि बचावकर्ता सही हो। महत्वपूर्ण रूप से, इस वाक्य में केवल उन्हीं शब्दों का उपयोग किया जा सकता है जो दोनों रिपोर्टों में दिखाई देते हैं। यदि आरोपी "बिल्लियों" और "चूहों" के बारे में बात करता है और बचावकर्ता "कुत्तों" और "हड्डियों" के बारे में बात करता है, तो आपका मध्य वाक्य "बिल्लियों" या "हड्डियों" का उल्लेख नहीं कर सकता; यह केवल उन शब्दों जैसे "जानवर" या "पीछा करना" का उपयोग कर सकता है यदि वे शब्द दोनों कहानियों में मौजूद हैं। कंप्यूटर विज्ञान की दुनिया में, इस जासूसी खेल को क्रेग इंटरपोलेशन प्रॉपर्टी (Craig Interpolation Property) कहा जाता है। यह एक सुपरपावर है जो कंप्यूटरों को यह समझने में मदद करती है कि सिस्टम के विभिन्न हिस्से एक-दूसरे से कैसे संबंधित हैं, बिना अप्रासंगिक विवरणों से भ्रमित हुए।

यह शोध पत्र विशेष रूप से इस जासूसी खेल को संबोधित करता है जिसे प्रपोजिशनल डायनेमिक लॉजिक (PDL) कहा जाता है। PDL को एक भाषा के रूप में सोचें जो कंप्यूटर प्रोग्रामों के व्यवहार का वर्णन करती है। यह एक वीडियो गेम के नियम पुस्तिका की तरह है जो कहती है कि जैसे, "यदि आप 'A' दबाते हैं तो 'B' होगा, तो आप कूदेंगे," या "यदि आप 'X' दबाना जारी रखते हैं, तो आप अंततः उड़ेंगे।" "अंततः" या "इसे हमेशा के लिए करते रहना" वाला हिस्सा इसे जटिल बनाता है, जो तर्क को बहुत शक्तिशाली बनाता है। दशकों से, गणितज्ञ और कंप्यूटर वैज्ञानिक यह सिद्ध करने की कोशिश कर रहे थे कि इस विशिष्ट नियम पुस्तिका (PDL) के पास इंटरपोलेशन की सुपरपावर है। अतीत में तीन अलग-अलग टीमों ने इस पहेली को हल करने की कोशिश की थी, लेकिन उनके समाधानों में कमियां पाई गईं, जिससे यह प्रश्न अनसुलझा और निराशाजनक बना रहा।

यह शोध पत्र अंततः इस रहस्य को सुलझाता है। लेखकों ने, जो जर्मनी और नीदरलैंड के शोधकर्ताओं की एक टीम है, एक नया और कठोर प्रमाण निर्मित किया है कि प्रपोजिशनल डायनेमिक लॉजिक में वास्तव में क्रेग इंटरपोलेशन प्रॉपर्टी है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने "साइक्लिक टेबलू सिस्टम" (cyclic tableau system) नामक एक विशिष्ट उपकरण का निर्माण किया। इस सिस्टम की कल्पना एक विशाल, शाखाओं वाले पेड़ के रूप में करें जहाँ आप एक जटिल तार्किक पहेली को छोटे और छोटे टुकड़ों में तोड़ने की कोशिश करते हैं। आमतौर पर, ये पेड़ अनंत तक बढ़ते हैं, लेकिन लेखकों ने इसमें एक विशेष "लोडिंग तंत्र" जोड़ा है जो एक सुरक्षा जाल के रूप में कार्य करता है। यदि पेड़ खुद पर वापस लूप (loop) बनाने लगता है (जो तब होता है जब प्रोग्राम कार्यों को दोहराते हैं), तो यह तंत्र लूप को पहचान लेता है और विकास को रोक देता है, जिससे यह सुनिश्चित होता है कि प्रमाण सीमित और प्रबंधनीय रहे।

इस नए पेड़-निर्माण उपकरण का उपयोग करके, लेखकों ने दिखाया कि PDL में किसी भी वैध तार्किक कथन के लिए, आप हमेशा वह आदर्श "मध्य वाक्य" (इंटरपोलेंट) खोज सकते हैं जो केवल उनके साझा शब्दावली का उपयोग करके दो पक्षों के तर्क को जोड़ता है। उन्होंने केवल यह सिद्ध नहीं किया कि यह मौजूद है; उन्होंने यह भी दिखाया कि इसकी गणना बिल्कुल कैसे की जाती है। उन्होंने यहाँ तक कि 'हaskell' नामक भाषा में एक कंप्यूटर प्रोग्राम भी लिखा है जो आपके लिए यह गणना कर सकता है, और वे वर्तमान में अपने गणित को 100% सही सत्यापित करने के लिए "लीन" (Lean) नामक एक डिजिटल सहायक का उपयोग करके प्रमाण के दूसरे स्तर पर काम कर रहे हैं। हालांकि उन्होंने मुख्य पहेली को सुलझा लिया है, वे स्वीकार करते हैं कि कुछ छोटे, संबंधित प्रश्न—जैसे कि क्या यह "टेस्ट" कमांड के बिना तर्क के एक सरल संस्करण के लिए काम करता है—भविष्य के जासूसों के लिए खुले रह गए हैं। लेकिन फिलहाल, बड़े सवाल का जवाब मिल गया है: PDL के पास इंटरपोलेशन की सुपरपावर है, और अब हम जानते हैं कि इसका उपयोग ठीक से कैसे किया जाए।

तकनीकी सारांश: प्रपोजिशनल डायनेमिक लॉजिक (PDL) में क्रेग इंटरपोलेशन (Craig Interpolation) है

1. समस्या

यह शोध पत्र इस लंबे समय से चले आ रहे खुले प्रश्न को संबोधित करता है कि क्या प्रपोजिशनल डायनेमिक लॉजिक (PDL) में क्रेग इंटरपोलेशन प्रॉपर्टी (CIP) मौजूद है। CIP यह बताता है कि किसी भी वैध निहितार्थ (valid implication) $\phi \to \psi$ के लिए, एक इंटरपोलेंट $\theta$ मौजूद होता है, ऐसा कि $\phi \to \theta$ और $\theta \to \psi$ वैध हों, और $\theta$ में केवल वे प्रपोजिशनल लेटर्स और एटोमिक प्रोग्राम्स होते हैं जो $\phi$ और $\psi$ दोनों में सामान्य हैं।

यद्यपि PDL एक सुव्यवस्थित मॉडल्स लॉजिक है जिसके स्थापित निर्णय क्षमता (decidability) और पूर्णता (completeness) परिणाम हैं, फिर भी इसकी इंटरपोलेशन स्थिति दशकों तक अस्पष्ट रही है। साहित्य में इंटरपोलेशन सिद्ध करने के तीन पिछले प्रयास शामिल हैं:

लेवेंट (Leivant, 1981): एक प्रमाण का दावा किया, जिसे बाद में क्राक्ट (Kracht, 1999) द्वारा गलत कारणों से खारिज कर दिया गया, हालांकि लेवेंट के प्रमाण में एक वास्तविक कमी बनी रही।
बोर्चेकोव्स्की (Borzechowski, 1988): एक मास्टर थीसिस (Diplomarbeit) जिसमें प्रमाण का दावा किया गया था, जिसे बहुत कम ध्यान मिला और कुछ लोगों द्वारा सत्यापन योग्य न होने के कारण खारिज कर दिया गया।
कोवाल्स्की (Kowalski, 2002): एक प्रमाण का दावा किया, जिसे खारिज कर दिया गया और 2004 में आधिकारिक तौर पर वापस ले लिया गया।

कठिनाई इसलिए उत्पन्न होती है क्योंकि PDL एक मॉडल्स फिक्स्डपॉइंट लॉजिक है (इटरेशन ऑपरेटर $*$ के कारण)। जबकि पूर्ण मॉडल्स $\mu$ -कैलकुलस और इसके अल्टरनेशन-फ्री फ्रैगमेंट के लिए चक्रीय प्रमाण प्रणालियों (cyclic proof systems) के माध्यम से इंटरपोलेशन स्थापित किया जा चुका है, PDL के विशिष्ट प्रतिबंध यह सुनिश्चित करना चुनौतीपूर्ण बनाते हैं कि इंटरपोडेंट्स को चरितार्थ करने वाले फिक्स्डपॉइंट समीकरणों के समाधानों को $\mu$ -कैलकुलस की पूर्ण अभिव्यक्ति शक्ति की आवश्यकता के बजाय, स्वयं PDL के भीतर ही व्यक्त किया जा सके।

2. कार्यप्रणाली

लेखक एक चक्रीय टेब्लो सिस्टम (cyclic tableau system) और माएहारा (Maehara) की प्रमाण-सिद्धांतिक पद्धति के अनुकूलन पर आधारित एक रचनात्मक प्रमाण प्रदान करते हैं।

2.1. PDL के लिए एक चक्रीय टेब्लो सिस्टम

लेखक PDL के लिए एक नया टेब्लो सिस्टम परिभाषित करते हैं जो स्प्लिट सीक्वेंट्स (जोड़े में फॉर्मूला सेट) पर कार्य करता है। मुख्य विशेषताएं शामिल हैं:

लोकल बनाम मॉडल्स रीजनिंग: सिस्टम सिंगल स्टेट के भीतर स्थानीय तर्क (प्रपोजिशनल रीजनिंग और प्रोग्राम्स का अनफोल्डिंग) और मॉडल्स रीजनिंग (क्रिपके मॉडल में अवस्थाओं के बीच जाना) के बीच अंतर करता है।
अनफोल्डिंग तंत्र: प्रत्येक प्रोग्राम कंस्ट्रक्टर के लिए मानक रिडक्शन नियमों के बजाय, सिस्टम एक "लोडिंग" तंत्र का उपयोग करता है। $[\alpha]\psi$ (जहाँ $\alpha$ नॉन-एटोमिक है) जैसे फॉर्मूला को "टेस्ट प्रोफाइल्स" के आधार पर सीक्वेंट्स के एक परिमित सेट में अनफोल्ड किया जाता है। यह सेट, जिसे $\text{unfold}_\square(\alpha, \psi)$ कहा जाता है, उन सभी संभावित निष्पादन पथों (execution paths) के वियोजन (disjunction) का प्रतिनिधित्व करता है जहाँ विशिष्ट टेस्ट सफल होते हैं या विफल होते हैं।
इटरेशन को संभालना: $[\alpha^*]\psi$ जैसे फॉर्मूला के अनंत स्थानीय अनफोल्डिंग को रोकने के लिए, सिस्टम अनफोल्डिंग प्रक्रिया के दौरान फॉर्मूला की पुनर्जीवित (regenerated) अभिव्यक्तियों को हटा देता है। यह इस अवलोकन पर निर्भर करता है कि $[\alpha^*]\psi$ एक 'ग्रेटेस्ट फिक्स्डपॉइंट' है।
चक्रीय प्रमाण (Cyclic Proofs): सिस्टम "रिपीट्स" (ऐसे नोड्स जिनमें अपने पूर्वज/कंपैनियन के समान लेबल होते हैं) की अनुमति देता है।
- लोडेड-पाथ रिपीट्स (Loaded-path repeats): एक रिपीट जहाँ कंपैनियन से वर्तमान नोड तक का पथ पूरी तरह से लोडेड नोड्स से बना होता है। इन्हें "सफल" लीव्स (लीव्स जो एक लूप को संतुष्ट करते हैं) के रूप में माना जाता है।
- फ्री रिपीट्स (Free repeats): एक रिपीट जहाँ पथ में अनलोडेड नोड्स होते हैं। इन्हें "असफल" लीव्स के रूप में माना जाता है, जो एक संभावित काउंटर-मॉडल का संकेत देते हैं।
समाप्ति (Termination): सिस्टम यह सुनिश्चित करने के लिए कि सभी फ्री रिपीट्स और लोडेड-पाथ रिपीट्स लीव्स हैं, और फिशर-लैडनर क्लोजर (Fischer-Ladner closure) का उपयोग करके फॉर्मूला के सेट को सीमित करने के लिए, समाप्ति सुनिश्चित करता है।

2.2. क्वाजी-टेब्लो और फिक्स्डपॉइंट समीकरणों के माध्यम से इंटरपोलेशन

लेखक माएहारा की पद्धति को चक्रीय सेटिंग में अनुकूलित करते हैं:

क्लस्टर्स (Clusters): टेब्लो को रिपीट्स से कंपैनियन तक बैक-एज वाले एक ग्राफ के रूप में देखा जाता है। इस ग्राफ के स्ट्रॉन्गली कनेक्टेड कंपोनेंट्स (SCCs) को "क्लस्टर्स" कहा जाता है।
क्वाजी-टेब्लो (Quasi-Tableaux): एक उचित क्लस्टर (एक नॉन-सिंगलटन SCC) के लिए, लेखक एक "क्वाजी-टेब्लो" परिभाषित करते हैं। इस संरचना का उपयोग इंटरपोडेंट को चरितार्थ करने वाले समीकरणों के सिस्टम को सेट करने के लिए किया जाता है।
प्री-इंटरपोडेंट्स (Pre-interpolants): विधि लीफ-टू-रूट इंडक्शन के माध्यम से क्वाजी-टेब्लो के नोड्स के लिए प्री-इंटरपोडेंट्स को परिभाषित करती है।
- एग्जिट नोड्स (Exit nodes) पर: (वे लीव्स जो क्लस्टर का हिस्सा नहीं हैं), प्री-इंटरपोडेंट एग्जिट नोड का इंटरपोडेंट होता है (इंडक्शन द्वारा माना गया है)।
- रिपीट लीव्स (Repeat leaves) पर: प्री-इंटरपोडेंट एक आंतरिक प्रपोजिशनल वेरिएबल $q_x$ होता है।
- कंपैनियन नोड्स (Companion nodes) पर: प्री-इंटरपोडेंट को फिक्स्डपॉइंट समीकरण के समाधान के रूप में परिभाषित किया जाता है। विशेष रूप से, यदि एक कंपैनियन $x$ का एक चाइल्ड $y$ है जिसका प्री-इंटरपोडेंट $\iota_y \equiv \bigwedge_i [\alpha_i]q_x \wedge \bigwedge_j [\beta_j]q_{z_j} \wedge \psi$ है, तो $x$ के लिए प्री-इंटरपोडेंट $\iota_x := [(\bigcup_i \alpha_i)^*](\bigwedge_j [\beta_j]q_{z_j} \wedge \psi)$ के रूप में परिभाषित किया जाता है।
PDL में समाधान: यह महत्वपूर्ण अंतर्दृष्टि है कि यह विशिष्ट निर्माण सुनिश्चित करता है कि फिक्स्डपॉइंट समीकरणों के समाधान PDL की भाषा के भीतर ही रहें। $\iota_x$ के परिभाषा में इटरेशन ऑपरेटर $*$ का उपयोग प्रभावी रूप से PDL के भीतर समीकरण $\iota_x \equiv \iota_y\langle q_x \mapsto \iota_x \rangle$ को हल करता है।
अंतिम इंटरपोडेंट (Final Interpolant): क्लस्टर के रूट के लिए इंटरपोडेंट, रूट के प्री-इंटरपोडेंट में आंतरिक वेरिएबल्स को संबंधित रीजन फॉर्मूला (स्प्लिट सीक्वेंट्स के लेफ्ट-हैंड साइड के वियोजन) के साथ प्रतिस्थापित करके प्राप्त किया जाता है।

3. प्रमुख योगदान और परिणाम

PDL के लिए CIP का प्रमाण: यह पेपर स्थापित करता है कि PDL में क्रेग इंटरपोलेशन प्रॉपर्टी (CIP) है।
बेथ डेफिनैबिलिटी (Beth Definability): एक परिणाम के रूप में, यह पेपर सिद्ध करता है कि PDL में बेथ डेफिनैबिलिटी प्रॉपर्टी है (क्योंकि डीडक्शन थ्योरम की उपस्थिति में CIP, बेथ डेफिनैबिलिटी को प्रेरित करता है)।
रचनात्मक एल्गोरिदम (Constructive Algorithm): प्रमाण रचनात्मक है। लेखक एक क्लोज्ड टेब्लो से इंटरपोडेंट्स की गणना करने के लिए एक स्पष्ट एल्गोरिदम प्रदान करते हैं।
औपचारिक सत्यापन (Formal Verification): लेखकों ने प्रमाण को इंटरैक्टिव थ्योरम प्रूवर Lean 4 में आंशिक रूप से औपचारिक रूप दिया है। पेपर के लेखन के समय तक, साउंडनेस (Soundness) और कम्प्लीटनेस (Completeness) थ्योरम्स, साथ ही कई सहायक लेम्मा को सत्यापित किया गया है।
कार्यान्वयन (Implementation): टेब्लो सिस्टम और इंटरपोडेंट निर्माण का एक Haskell कार्यान्वयन प्रदान किया गया है, जो वेब इंटरफेस के माध्यम से उपलब्ध है।

4. महत्व और दावे

यह पेपर PDL की इंटरपोलेशन स्थिति के संबंध में साहित्य के एक पहेली को हल करने का दावा करता है, जो पिछले प्रयासों के अंतराल को पार करने वाला पहला सत्यापित प्रमाण प्रदान करता है।

ऐतिहासिक मुद्दों का समाधान: लेखक पिछले असफल प्रयासों के इतिहास को स्पष्ट रूप से संबोधित करते हैं, यह नोट करते हुए कि उनका दृष्टिकोण बोर्चेकोव्स्की (1988) के मूल विचारों पर आधारित है, लेकिन चक्रीय प्रमाणों के प्रबंधन और इंटरपोडेंट्स के निर्माण को PDL की भाषा के भीतर कठोरता से औपचारिक रूप देता है।
पद्धतिगत नवीनता (Methodological Novelty): पेपर इस बात पर जोर देता है कि जबकि गैर-चक्रीय प्रमाणों के लिए माएहारा की पद्धति मानक है, चक्रीय प्रमाणों (फिक्स्डपॉइंट लॉजिक) पर लागू करने के लिए फिक्स्डपॉइंट समीकरणों को हल करने की आवश्यकता होती है। लेखक प्रदर्शित करते हैं कि PDL के लिए, इन समाधानों को इसके अपने इटरेशन ऑपरेटर का उपयोग करके व्यक्त किया जा सकता है, जो एक गैर-तुच्छ परिणाम है जो PDL को अन्य फ्रैगमेंट से अलग करता है जहाँ ऐसे समाधानों के लिए पूर्ण $\mu$ -कैलकुलस की आवश्यकता हो सकती है।
खुले प्रश्न (Open Questions): लेखक विनम्रतापूर्वक नोट करते हैं कि उनकी पद्धति टेस्ट प्रोग्राम्स ( $\tau?$ ) की उपस्थिति पर निर्भर करती है। फलस्वरूप, यह एक खुला प्रश्न बना हुआ है कि क्या टेस्ट-मुक्त PDL फ्रैगमेंट में इंटरपोलेशन है, क्योंकि उनका निर्माण आमतौर पर उन इंटरपोडेंट्स को भी उत्पन्न करता है जिनमें टेस्ट शामिल होते हैं, भले ही इनपुट टेस्ट-मुक्त हो। वे अपने तरीके को अन्य PDL वेरिएंट्स (जैसे कॉनवर्स या इंटरसेक्शन के साथ) तक विस्तारित करने और क्लीनी अलजेब्रा विद टेस्ट्स (KAT) पर इसके प्रभावों को भी खुला छोड़ देते हैं।

संक्षेप में, यह पेपर एक नवीन चक्रीय टेब्लो सिस्टम और एक विशेष फिक्स्डपॉइंट-सॉल्विंग तकनीक का उपयोग करके PDL के लिए क्रेग इंटरपोलेशन का एक निर्णायक, रचनात्मक प्रमाण प्रदान करता है, जिसे Haskell कार्यान्वयन और Lean में आंशिक औपचारिक सत्यापन द्वारा समर्थित किया गया है।