Semantics for the minimal well-determined logic
यह शोधपत्र न्यूनतम सुव्यवस्थित तर्क (minimal well-determined logic) के लिए एक महानतम तत्व और एक आंशिक निहितार्थ फलन (partial implication function) वाले निम्न अर्ध-लैटिस (lower semilattices) पर आधारित एक नवीन अर्थविज्ञान (semantics) प्रस्तुत करता है, जो इसकी सुसंगतता (soundness) और पूर्णता (completeness) को सिद्ध करते हुए यह प्रदर्शित करता है कि इसके तादात्म्यों (tautologies) का समुच्चय बहुपद समय (polynomial time) में निर्णायक (decidable) है।
मूल पेपर CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/) के तहत सार्वजनिक डोमेन को समर्पित है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
"यदि" और "और" का तर्क: सत्य की भूमि में एक जासूसी कहानी
कल्पना कीजिए कि आप एक रहस्य सुलझाने की कोशिश कर रहे एक जासूस हैं, लेकिन उंगलियों के निशान या अलबी (alibi) के बजाय, आपके सुराग वाक्य हैं। तर्क की दुनिया में, प्रपोजिशनल लॉजिक (propositional logic) नामक एक विशेष शाखा है जो यह अध्ययन करती है कि हम जटिल सत्यों को बनाने के लिए सरल कथनों को कैसे जोड़ते हैं। इसे तर्क की व्याकरण के रूप में समझें। इस व्याकरण के दो सबसे प्रसिद्ध उपकरण संयोजन (conjunction) (शब्द "और", जो दो चीजों को एक साथ जोड़ता है) और निहितार्थ (implication) (शब्द "यदि... तो", जो एक शर्त निर्धारित करता है) हैं।
आमतौर पर, जब हम तर्क करते हैं, तो हमारे पास एक स्वर्णिम नियम होता है जिसे मोडस पोमेंस (Modus Ponens) कहा जाता है। यह हमारे सोचने के इंजन के रूप में कार्य करता है: "यदि बारिश हो रही है, तो जमीन गीली है। बारिश हो रही है। इसलिए, जमीन गीली है।" यह नियम इतना स्वाभाविक लगता है कि हम अक्सर इसे बिना सोचे स्वीकार कर लेते हैं। लेकिन क्या होगा यदि हम एक ऐसा तर्क तंत्र बनाने की कोशिश करें जो यह मानकर न चले कि यह नियम स्वचालित रूप से काम करता है? क्या होगा यदि हम "और" तथा "यदि" को पूरे सिस्टम को तोड़े बिना एक साथ काम करने के लिए आवश्यक न्यूनतम नियमों को खोजना चाहते हैं? यह वह प्रश्न है जिसका समाधान इगोर गोर्बुनोव और मिखाइल रिबकोव अपने शोध पत्र में करते हैं। वे एक सुव्यवस्थित तर्क के "न्यूनतम" संस्करण की तलाश कर रहे हैं—एक ऐसा सिस्टम जो समझने के लिए पर्याप्त मजबूत हो, लेकिन इतना भी मजबूत न हो कि हमें वे चीजें स्वीकार करने के लिए मजबूर करे जिन्हें हमने इरादा नहीं किया था।
शोध पत्र की बड़ी खोज: बिना इंजन वाला एक तर्क
इस शोध पत्र में, लेखक तर्क के एक बहुत ही विशिष्ट, संक्षिप्त संस्करण की जांच करते हैं जिसे वे मिनिमल वेल-डिटरमाइंड लॉजिक (minimal well-determined logic) कहते हैं। वे इस सवाल से शुरुआत करते हैं: "हमें 'और' तथा 'यदि' के साथ एक तर्क को काम करने के लिए नियमों के सबसे छोटे सेट की आवश्यकता क्यों है?"
आमतौर पर, तर्कशास्त्री अपने सिस्टम को कई एक्सिओम्स (शुरुआती सत्य) और नियमों (जैसे मोडस पोमेंस) की सूची बनाकर बनाते हैं जो आपको एक सत्य से दूसरे सत्य तक जाने का तरीका बताते हैं। लेखकों ने इस न्यूनतम तर्क को मोडस पोमेंस को एक शुरुआती नियम के रूप में आवश्यक बनाए बिना परिभाषित करने का एक तरीका खोज निकाला। यह पता चला कि, यदि आप सिस्टम को सही तरीके से स्थापित करते हैं, तो "यदि A तो B, और A, इसलिए B" का नियम अन्य नियमों से स्वाभाविक रूप से उभरता है। यह एक कार बनाने जैसा है जहाँ इंजन चाबी घुमाते ही खुद शुरू हो जाता है, बजाय इसके कि आपको हर बार उसे धक्का देना पड़े।
इस तर्क को सिद्ध करने के लिए, लेखकों को इसे विज़ुअलाइज़ करने का एक नया तरीका विकसित करना पड़ा। उन्होंने लोअर सेमिलाटिस विद अ ग्रेटेस्ट एलीमेंट (lower semilattice with a greatest element) नामक एक गणितीय संरचना पर आधारित एक सिमेंटिक्स (semantics) (प्रतीकों की व्याख्या करने का एक तरीका) बनाया।
इसे चित्रित करने का एक तरीका यहाँ दिया गया है: कल्पना कीजिए कि ब्लॉकों से बना एक पिरामिड है।
- ब्लॉक विभिन्न कथनों या विचारों का प्रतिनिधित्व करते हैं।
- पिरामिड का आकार यह दर्शाता है कि ये विचार एक-दूसरे से कैसे संबंधित हैं। यदि आप दो ब्लॉकों को मिलाकर एक बड़ा ब्लॉक बना सकते हैं, तो वह आपका "और" (conjunction) है।
- सबसे ऊपर का ब्लॉक "ग्रेटेस्ट एलीमेंट" है, जो परम सत्य या उस स्थिति का प्रतिनिधित्व करता है जहाँ सब कुछ संतुष्ट है।
अधिकांश तर्क प्रणालियों में, "यदि... तो" (implication) एक मशीन की तरह है जो दो ब्लॉकों को लेती है और एक नया ब्लॉक निकाल देती है। लेकिन इस न्यूनतम तर्क में, लेखकों ने महसूस किया कि "यदि... तो" हमेशा उसी तरह से नया ब्लॉक नहीं बनाता है। कभी-कभी, शर्त पूरी नहीं होती है, और मशीन बस वहीं रुक जाती है। इसलिए, उन्होंने "यदि... तो" को एक पार्शियल फंक्शन (partial function) के रूप में परिभाषित किया। इसे एक वेंडिंग मशीन की तरह समझें जो केवल तभी काम करती है जब आपके पास सही सिक्का हो। यदि आप ब्लॉकों का सही संयोजन (जहाँ पहला ब्लॉक पिरामिड में दूसरे ब्लॉक के "भीतर" या "छोटा" है) डालते हैं, तो मशीन आपको शीर्ष ब्लॉक (True) देती है। यदि शर्तें पूरी नहीं होती हैं, तो मशीन कोई परिणाम नहीं देती—यह अपरिभाषित (undefined) है। यह "पार्शियल" प्रकृति ही इस तर्क को काम करने के लिए चाबी है, ताकि मोडस पोमेंस नियम को शुरुआत से वहां रखने के लिए मजबूर न होना पड़े।
चौंकाने वाला मोड़: यह तेज़ है!
यहाँ कहानी वास्तव में रोमांचक हो जाती है। आमतौर पर, जब आप किसी तर्क को उसके मूल तत्वों तक सीमित करते हैं, तो आप उम्मीद कर सकते हैं कि गणित अव्यवस्थित हो जाएगा या नियमों की जाँच करना अविश्वसनीय रूप से कठिन हो जाएगा। आप सोच सकते हैं, "यदि हम मानक नियमों को हटा देते हैं, तो यह पता लगाने में कि कोई कथन सत्य है या नहीं, इसमें अनंत समय लगेगा।"
लेकिन लेखकों ने कुछ आश्चर्यजनक खोजा: यह वास्तव में बहुत तेज़ है।
उन्होंने एक विशिष्ट एल्गोरिदम (कंप्यूटर के लिए एक चरण-दर-चरण रेसिपी) डिजाइन किया जो यह जाँचता है कि कोई भी दिया गया वाक्य इस न्यूनतम तर्क में एक "टाउटोलॉजी" (एक कथन जो हमेशा सत्य होता है) है या नहीं। उन्होंने सिद्ध किया कि यह एल्गोरिदम पॉलीनोमियल टाइम (polynomial time) में चलता है।
इसे रोजमर्रा की भाषा में कहें तो: कल्पना कीजिए कि आपके पास एक पहेली है। यदि पहेली "कठिन" है (कई जटिल तर्क समस्याओं की तरह), तो पहेली को हल करने में लगने वाला समय पहेली के बड़े होने के साथ तेजी से (exponentially) बढ़ता है—पहेली के आकार को दोगुना करने से इसे हल करने में लाखों गुना अधिक समय लग सकता है। लेकिन इस न्यूनतम तर्क के लिए, इसे हल करने में लगने वाला समय केवल एक सरल वक्र (जैसे आकार का वर्ग) की तरह बढ़ता है। यदि आप वाक्य की लंबाई को दोगुना करते हैं, तो कंप्यूटर को केवल थोड़ा सा अधिक काम करने की आवश्यकता होती है, लाखों गुना अधिक नहीं।
लेखक इस बात से हैरान थे। उन्होंने उल्लेख किया कि अधिकांश "प्राकृतिक" तर्क (जैसे कि वे जिनमें क्लासिकल लॉजिक शामिल है) कंप्यूटर के लिए जल्दी से हल करना बेहद कठिन (coNP-hard) होता है। लेकिन यह न्यूनतम, संक्षिप्त तर्क, अपने अजीब "पार्शियल" नियमों के बावजूद, कंप्यूटर द्वारा संभालने के लिए वास्तव में आसान है।
इसका क्या अर्थ है
यह शोध पत्र केवल यह नहीं कहता कि "यहाँ एक नया तर्क है।" यह एक पूर्ण टूलकिट प्रदान करता है:
- एक नई परिभाषा: उन्होंने दिखाया कि कैसे इस तर्क को मानक "यदि A तो B" नियम को माने बिना बनाया जा सकता है।
- एक नया मानचित्र: उन्होंने "पिरामिड" सिमेंटिक्स (सेमिलैटिस) बनाया ताकि यह समझाया जा सके कि तर्क कैसे व्यवहार करता है।
- एक प्रमाण: उन्होंने सिद्ध किया कि उनका मानचित्र नियमों के साथ पूरी तरह मेल खाता है (Soundness and Completeness)।
- एक गति परीक्षण: उन्होंने सिद्ध किया कि इस प्रणाली में किसी कथन की सत्यता की जाँच करना गणनात्मक रूप से आसान है (Polynomial Time)।
लेखक यह भी बताते हैं कि यह न्यूनतम तर्क एक आधार है। आप बाद में अधिक मजबूत तर्क बनाने के लिए इसमें और अधिक नियम जोड़ सकते हैं, लेकिन आप इस स्वच्छ, कुशल आधार से शुरुआत करते हैं। उन्होंने यह भी दिखाया कि यह तर्क क्लासिकल लॉजिक से मौलिक रूप से भिन्न है: इसमें वे "कठिन" समस्याएं नहीं हैं जो क्लासिकल लॉजिक को कंप्यूटरों के लिए इतना कठिन बनाती हैं।
संक्षेप में, गोर्बुनोव और रिबकोव ने एक तर्क प्रणाली ली, उसके सबसे प्रसिद्ध इंजन को हटा दिया, और पाया कि कार अभी भी पूरी तरह से चलती है—और यह पता चलता है कि यह एक स्पोर्ट्स कार है जो अविश्वसनीय रूप से तेज़ चलती है। उन्होंने हमें "यदि" और "और" के बारे में सोचने का एक नया तरीका दिया जो गणितीय रूप से सुंदर और गणनात्मक रूप से कुशल दोनों है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।