दो-चर तर्क: Difference between revisions
No edit summary |
No edit summary |
||
| Line 13: | Line 13: | ||
बिना फ़ंक्शन प्रतीकों वाले प्रथम-क्रम तर्क के दो-चर खंड को गणना परिमाणकों को जोड़ने के साथ भी निर्णय लेने योग्य माना जाता है,<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>n</math> निकटतम के साथ एक नोड है, अर्थात् <math>\Phi = \exists x \exists^{\geq n} y E(x,y) | ||
</math> परिमाणकों की गिनती के बिना समान सूत्र के लिए '''<math>n+1</math>''' चर की आवश्यकता होती है। | </math> परिमाणकों की गिनती के बिना समान सूत्र के लिए '''<math>n+1</math>''' चर की आवश्यकता होती है। | ||
| Line 19: | Line 19: | ||
== वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन == | == वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन == | ||
दो-चर तर्क और वीस्फ़ीलर-लेमन (या रंग शोधन) एल्गोरिदम के बीच एक शक्तिशाली | दो-चर तर्क और वीस्फ़ीलर-लेमन (या रंग शोधन) एल्गोरिदम के बीच एक शक्तिशाली संबंध है। दो ग्राफ़ दिए गए हैं, तो किन्हीं दो नोड्स में रंग परिशोधन में एक ही स्थिर रंग होता है यदि और केवल यदि उनके पास समान <math>C^2</math> प्रकार है, अर्थात् वे गिनती के साथ दो-चर तर्क में समान सूत्रों को संतुष्ट करते हैं।<ref>Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.</ref> | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 11:10, 20 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.
