दो-चर तर्क: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
मैथमेटिकल लॉजिक और [[कंप्यूटर विज्ञान]] में, '''टू वेरिएबल लॉजिक''' [[प्रथम-क्रम तर्क|फर्स्ट आर्डर लॉजिक]] का फ्रेगमेंट है जहां फोर्मुला ( | मैथमेटिकल लॉजिक और [[कंप्यूटर विज्ञान]] में, '''टू वेरिएबल लॉजिक''' [[प्रथम-क्रम तर्क|फर्स्ट आर्डर लॉजिक]] का फ्रेगमेंट है जहां फोर्मुला (लॉजिक ) केवल दो अलग-अलग वेरिएबल (लॉजिक ) का उपयोग करके लिखा जा सकता है।<ref>L. Henkin. ''Logical systems containing only a finite number of symbols'', Report, Department of Mathematics, University of Montreal, 1967</ref> इस फ्रेगमेंट का अध्ययन सामान्यतः [[फ़ंक्शन प्रतीक|फंक्शन सिंबल]] के बिना किया जाता है। | ||
==डिसाइडेबल == | ==डिसाइडेबल == | ||
टू वेरिएबल लॉजिक के बारे में कुछ महत्वपूर्ण समस्याएं जैसे सेटीसफियाबिलिटी( | टू वेरिएबल लॉजिक के बारे में कुछ महत्वपूर्ण समस्याएं जैसे सेटीसफियाबिलिटी(लॉजिक ) और फाईनाईट सेटीसफियाबिलिटी (लॉजिक ), डिसाइडेबल (कंप्यूटर विज्ञान) हैं।<ref>E. Grädel, P.G. Kolaitis and M. Vardi, ''On the Decision Problem for Two-Variable First-Order Logic'', The Bulletin of Symbolic Logic, Vol. | ||
3, No. 1 (Mar., 1997), pp. 53-69.</ref> यह परिणाम टू वेरिएबल लॉजिक के टुकड़ों की डिसाइडेबल के बारे में परिणामों को सामान्यीकृत करता है, जैसे कि कुछ [[विवरण तर्क|डिस्क्रिप्शन लॉजिक]]; चूँकि, टू वेरिएबल लॉजिक के कुछ फ्रेगमेंट उनकी सेटीसफियाबिलिटी समस्याओं के लिए बहुत कम [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समष्टियता सिद्धांत]] का प्रयोग करते हैं। | 3, No. 1 (Mar., 1997), pp. 53-69.</ref> यह परिणाम टू वेरिएबल लॉजिक के टुकड़ों की डिसाइडेबल के बारे में परिणामों को सामान्यीकृत करता है, जैसे कि कुछ [[विवरण तर्क|डिस्क्रिप्शन लॉजिक]]; चूँकि, टू वेरिएबल लॉजिक के कुछ फ्रेगमेंट उनकी सेटीसफियाबिलिटी समस्याओं के लिए बहुत कम [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समष्टियता सिद्धांत]] का प्रयोग करते हैं। | ||
इसके विपरीत, फंक्शन सिंबल के बिना फर्स्ट आर्डर लॉजिक के तीन- | इसके विपरीत, फंक्शन सिंबल के बिना फर्स्ट आर्डर लॉजिक के तीन-वेरिएबल फ्रेगमेंट के लिए सेटीसफियाबिलिटी अनडिसाइडेबल है।<ref>A. S. Kahr, Edward F. Moore and Hao Wang. ''Entscheidungsproblem Reduced to the ∀ ∃ ∀ Case'', 1962, noting that their ∀ ∃ ∀ formulas use only three variables.</ref> | ||
== काउंटिंग क्कंटीफायर == | == काउंटिंग क्कंटीफायर == | ||
फंक्शन सिंबल वाले फर्स्ट आर्डर लॉजिक के टू वेरिएबल फ्रेगमेंट को काउंटिंग क्कंटीफायर को जोड़ने के साथ भी निर्णय लेने योग्य माना जाता है,<ref>E. Grädel, M. Otto and E. Rosen. ''Two-Variable Logic with Counting is Decidable.'', Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997.</ref> और इस प्रकार यूनिकनेस क्कंटीफिकैसन यह एक अधिक शक्तिशाली परिणाम है, क्योंकि उच्च संख्यात्मक मानों के लिए गणना परिमाणक उस | फंक्शन सिंबल वाले फर्स्ट आर्डर लॉजिक के टू वेरिएबल फ्रेगमेंट को काउंटिंग क्कंटीफायर को जोड़ने के साथ भी निर्णय लेने योग्य माना जाता है,<ref>E. Grädel, M. Otto and E. Rosen. ''Two-Variable Logic with Counting is Decidable.'', Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997.</ref> और इस प्रकार यूनिकनेस क्कंटीफिकैसन यह एक अधिक शक्तिशाली परिणाम है, क्योंकि उच्च संख्यात्मक मानों के लिए गणना परिमाणक उस लॉजिक में व्यक्त नहीं किए जा सकते हैं। | ||
गणना परिमाणक वास्तव में परिमित-परिवर्तनीय | गणना परिमाणक वास्तव में परिमित-परिवर्तनीय लॉजिक ों की अभिव्यक्ति में सुधार करते हैं क्योंकि वे यह कहने की अनुमति देते हैं कि <math>n</math> निकटतम के साथ एक नोड है, अर्थात् <math>\Phi = \exists x \exists^{\geq n} y E(x,y) | ||
</math> परिमाणकों की गिनती के बिना समान फोर्मुला के लिए '''<math>n+1</math>''' | </math> परिमाणकों की गिनती के बिना समान फोर्मुला के लिए '''<math>n+1</math>''' वेरिएबल की आवश्यकता होती है। | ||
== वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन == | == वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन == | ||
Revision as of 13:06, 21 July 2023
मैथमेटिकल लॉजिक और कंप्यूटर विज्ञान में, टू वेरिएबल लॉजिक फर्स्ट आर्डर लॉजिक का फ्रेगमेंट है जहां फोर्मुला (लॉजिक ) केवल दो अलग-अलग वेरिएबल (लॉजिक ) का उपयोग करके लिखा जा सकता है।[1] इस फ्रेगमेंट का अध्ययन सामान्यतः फंक्शन सिंबल के बिना किया जाता है।
डिसाइडेबल
टू वेरिएबल लॉजिक के बारे में कुछ महत्वपूर्ण समस्याएं जैसे सेटीसफियाबिलिटी(लॉजिक ) और फाईनाईट सेटीसफियाबिलिटी (लॉजिक ), डिसाइडेबल (कंप्यूटर विज्ञान) हैं।[2] यह परिणाम टू वेरिएबल लॉजिक के टुकड़ों की डिसाइडेबल के बारे में परिणामों को सामान्यीकृत करता है, जैसे कि कुछ डिस्क्रिप्शन लॉजिक; चूँकि, टू वेरिएबल लॉजिक के कुछ फ्रेगमेंट उनकी सेटीसफियाबिलिटी समस्याओं के लिए बहुत कम कम्प्यूटेशनल समष्टियता सिद्धांत का प्रयोग करते हैं।
इसके विपरीत, फंक्शन सिंबल के बिना फर्स्ट आर्डर लॉजिक के तीन-वेरिएबल फ्रेगमेंट के लिए सेटीसफियाबिलिटी अनडिसाइडेबल है।[3]
काउंटिंग क्कंटीफायर
फंक्शन सिंबल वाले फर्स्ट आर्डर लॉजिक के टू वेरिएबल फ्रेगमेंट को काउंटिंग क्कंटीफायर को जोड़ने के साथ भी निर्णय लेने योग्य माना जाता है,[4] और इस प्रकार यूनिकनेस क्कंटीफिकैसन यह एक अधिक शक्तिशाली परिणाम है, क्योंकि उच्च संख्यात्मक मानों के लिए गणना परिमाणक उस लॉजिक में व्यक्त नहीं किए जा सकते हैं।
गणना परिमाणक वास्तव में परिमित-परिवर्तनीय लॉजिक ों की अभिव्यक्ति में सुधार करते हैं क्योंकि वे यह कहने की अनुमति देते हैं कि निकटतम के साथ एक नोड है, अर्थात् परिमाणकों की गिनती के बिना समान फोर्मुला के लिए वेरिएबल की आवश्यकता होती है।
वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन
टू वेरिएबल लॉजिक और वीस्फ़ीलर-लेमन (या कलर रेफिनमेंट ) एल्गोरिदम के बीच एक शक्तिशाली संबंध है। दो ग्राफ़ दिए गए हैं, तो किन्हीं दो नोड्स में कलर रेफिनमेंट में एक ही स्थिर कलर होता है यदि और केवल यदि उनके पास समान प्रकार है, अर्थात् वे गिनती के साथ टू वेरिएबल लॉजिक में समान सूत्रों को संतुष्ट करते हैं।[5]
संदर्भ
- ↑ L. Henkin. Logical systems containing only a finite number of symbols, Report, Department of Mathematics, University of Montreal, 1967
- ↑ E. Grädel, P.G. Kolaitis and M. Vardi, On the Decision Problem for Two-Variable First-Order Logic, The Bulletin of Symbolic Logic, Vol. 3, No. 1 (Mar., 1997), pp. 53-69.
- ↑ A. S. Kahr, Edward F. Moore and Hao Wang. Entscheidungsproblem Reduced to the ∀ ∃ ∀ Case, 1962, noting that their ∀ ∃ ∀ formulas use only three variables.
- ↑ E. Grädel, M. Otto and E. Rosen. Two-Variable Logic with Counting is Decidable., Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997.
- ↑ Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.
