दो-चर तर्क

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

निर्णायकता

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

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

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

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

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

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

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