दो-चर तर्क

गणितीय तर्क और कंप्यूटर विज्ञान में, दो-चर तर्क प्रथम-क्रम तर्क का टुकड़ा (तर्क) है जहां सूत्र (तर्क) केवल दो अलग-अलग चर (तर्क) का उपयोग करके लिखा जा सकता है। इस टुकड़े का अध्ययन आमतौर पर फ़ंक्शन प्रतीकों के बिना किया जाता है।

निर्णायकता

दो-चर तर्क के बारे में कुछ महत्वपूर्ण समस्याएं, जैसे संतुष्टिशीलता (तर्क) और [[परिमित संतुष्टि (तर्क)]], निर्णायकता (कंप्यूटर विज्ञान) हैं। यह परिणाम दो-चर तर्क के टुकड़ों की निर्णायकता के बारे में परिणामों को सामान्यीकृत करता है, जैसे कि कुछ विवरण तर्क; हालाँकि, दो-चर तर्क के कुछ टुकड़े उनकी संतुष्टि समस्याओं के लिए बहुत कम कम्प्यूटेशनल जटिलता सिद्धांत का आनंद लेते हैं।

इसके विपरीत, फ़ंक्शन प्रतीकों के बिना प्रथम-क्रम तर्क के तीन-चर खंड के लिए, संतुष्टि अनिर्णीत है।

परिमाणकों की गणना

बिना फ़ंक्शन प्रतीकों वाले प्रथम-क्रम तर्क के दो-चर खंड को गणना क्वांटिफायर के अतिरिक्त होने पर भी निर्णय लेने योग्य माना जाता है, और इस प्रकार विशिष्टता मात्रा का ठहराव। यह एक अधिक शक्तिशाली परिणाम है, क्योंकि उच्च संख्यात्मक मानों के लिए गणना परिमाणक उस तर्क में व्यक्त नहीं किए जा सकते हैं।

गणना परिमाणक वास्तव में परिमित-परिवर्तनीय तर्क की अभिव्यक्ति में सुधार करते हैं क्योंकि वे यह कहने की अनुमति देते हैं कि एक नोड है $n$ पड़ोसी, अर्थात् $\Phi =\exists x\exists ^{\geq n}yE(x,y)$. परिमाणकों की गिनती के बिना $n+1$ समान सूत्र के लिए चर की आवश्यकता होती है।

वीस्फ़ीलर-लेमन एल्गोरिथम से कनेक्शन

दो-चर तर्क और वीस्फ़ीलर-लेमन (या रंग शोधन एल्गोरिदम) एल्गोरिदम के बीच एक मजबूत संबंध है। दो ग्राफ़ दिए गए हैं, तो किन्हीं दो नोड्स का रंग परिशोधन में समान स्थिर रंग होता है यदि और केवल यदि उनका रंग समान हो $C^{2}$ प्रकार, अर्थात्, वे गिनती के साथ दो-चर तर्क में समान सूत्रों को संतुष्ट करते हैं।