दो-चर तर्क: 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> और इस प्रकार यूनिकनेस क्कंटीफिकैसन यह एक अधिक शक्तिशाली परिणाम है, क्योंकि उच्च संख्यात्मक मानों के लिए गणना परिमाणक उस तर्क में व्यक्त नहीं किए जा सकते हैं। | |||
गणना परिमाणक वास्तव में परिमित-परिवर्तनीय तर्कों की अभिव्यक्ति में सुधार करते हैं क्योंकि वे यह कहने की अनुमति देते हैं कि <math>n</math> निकटतम के साथ एक नोड है, अर्थात् <math>\Phi = \exists x \exists^{\geq n} y E(x,y) | गणना परिमाणक वास्तव में परिमित-परिवर्तनीय तर्कों की अभिव्यक्ति में सुधार करते हैं क्योंकि वे यह कहने की अनुमति देते हैं कि <math>n</math> निकटतम के साथ एक नोड है, अर्थात् <math>\Phi = \exists x \exists^{\geq n} y E(x,y) | ||
</math> परिमाणकों की गिनती के बिना समान | </math> परिमाणकों की गिनती के बिना समान फोर्मुला के लिए '''<math>n+1</math>''' चर की आवश्यकता होती है। | ||
== वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन == | == वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन == | ||
दो-चर तर्क और वीस्फ़ीलर-लेमन (या | दो-चर तर्क और वीस्फ़ीलर-लेमन (या कलर रेफिनमेंट ) एल्गोरिदम के बीच एक शक्तिशाली संबंध है। दो ग्राफ़ दिए गए हैं, तो किन्हीं दो नोड्स में कलर रेफिनमेंट में एक ही स्थिर कलर होता है यदि और केवल यदि उनके पास समान <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 12:57, 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.
