परिधि (तर्क)

Not to be confused with परिसीमन.

परिधि एक गैर-एकदिष्ट तर्क है जो जॉन मैक्कार्थी द्वारा सामान्य ज्ञान धारणा को औपचारिक रूप देने के लिए बनाई गई है कि जब तक अन्यथा निर्दिष्ट नहीं किया जाता है तब तक चीजें अपेक्षित होती हैं। प्रधार समस्या को हल करने के प्रयास में बाद में मैक्कार्थी द्वारा परिधि का उपयोग किया गया था। अपने प्रारंभिक सूत्रीकरण में परिधि को अनुप्रयुक्त करने के लिए, मैक्कार्थी ने कुछ विधेय के विस्तार को कम करने की अनुमति देने के लिए प्रथम-क्रम तर्क को बढ़ाया, जहां विधेय का विस्तार मानों के टपल का समुच्चय है, जिस पर विधेय सत्य है। यह न्यूनीकरण संवृत्त-विश्व धारणा के समान है कि जो सत्य नहीं है वह असत्य है।

मैक्कार्थी द्वारा मानी गई मूल समस्या मिशनरियों और नरभक्षी की थी: नदी के एक किनारे पर तीन मिशनरी और तीन नरभक्षी हैं; उन्हें एक नौका का उपयोग करके नदी पार करनी होती है जो केवल दो लोगों को ले जा सकती है, इस अतिरिक्त बाधा के साथ कि नरभक्षी को किसी भी किनारे पर मिशनरियों से अधिक नहीं होना चाहिए (अन्यथा मिशनरियों को मार दिया जाएगा और संभवतः खाया जाएगा)। मैक्कार्थी द्वारा विचार की गई समस्या लक्ष्य तक पहुँचने के लिए चरणों के अनुक्रम को खोजने की नहीं थी (मिशनरियों और नरभक्षी समस्या पर लेख में ऐसा एक समाधान सम्मिलित है), बल्कि उन स्थितियों को बाहर करने की है जो स्पष्ट रूप से नहीं बताई गई हैं। उदाहरण के लिए, समाधान "आधा मील दक्षिण में जाएं और सेतु पर नदी पार करें" सहज रूप से मान्य नहीं है क्योंकि समस्या के विवरण में ऐसे सेतु का उल्लेख नहीं है। दूसरी ओर, इस सेतु के अस्तित्व को भी समस्या के विवरण से बाहर नहीं किया गया है। यह कि सेतु का अस्तित्व नहीं है, निहित धारणा का परिणाम है कि समस्या के विवरण में वह सब कुछ है जो इसके समाधान के लिए प्रासंगिक है। स्पष्ट रूप से यह कहना कि एक सेतु उपस्थित नहीं है, इस समस्या का समाधान नहीं है, क्योंकि कई अन्य असाधारण स्थितियां हैं जिन्हें बाहर रखा जाना चाहिए (जैसे कि नरभक्षी को बन्धन के लिए रज्‍जु की उपस्थिति, पास में एक बड़ी नौका की उपस्थिति, आदि)।

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

प्रस्तावात्मक स्थिति

जबकि परिधि को प्रारंभ में प्रथम-क्रम तर्क स्थिति में परिभाषित किया गया था, प्रस्तावात्मक स्थिति की विशिष्टता को परिभाषित करना सरल है। एक प्रस्तावक सूत्र $T$ दिया गया है, इसकी परिधि केवल $T$ संरचना वाले सूत्र है, जब तक आवश्यक न हो, एक चर को सत्य पर निर्दिष्ट न करें।

औपचारिक रूप से, प्रस्तावात्मक प्रतिरूप को प्रस्तावात्मक चर के समुच्चय द्वारा दर्शाया जा सकता है; अर्थात्, प्रत्येक प्रतिरूप को प्रस्तावक चर के समुच्चय द्वारा दर्शाया जाता है जो सत्य को निर्दिष्ट करता है। उदाहरण के लिए, सही निर्दिष्ट करने वाला प्रतिरूप $a$, असत्य $b$, और सत्य $c$ को समुच्चय $\{a,c\}$ द्वारा दर्शाया गया है, क्योंकि $a$ और $c$ वास्तव में वे चर हैं जो इस प्रतिरूप द्वारा सत्य को सौंपे गए हैं।

दिए गए दो प्रतिरूपों $M$ और $N$ ने इस तरह से स्थिति का प्रतिनिधित्व किया कि $N\subseteq M$ के समान है। $M$ प्रत्येक चर को सत्य पर समायोजित करता है, $N$ सत्य पर व्यवस्थित होता है। दूसरे शब्दों में, $\subseteq$ "सत्य न्यून चरो के समायोजन" के संबंध को प्रतिरूप करता है। $N\subset M$ का अर्थ है कि $N\subseteq M$ परन्तु ये दोनों प्रतिरूप मेल नहीं खाते हैं।

यह हमें उन प्रतिरूपों को परिभाषित करने देता है जो आवश्यक होने तक सत्य को चर निर्दिष्ट नहीं करते हैं। एक प्रतिरूप $M$ को सिद्धांत $T$ का न्यूनतम कहा जाता है, यदि और केवल यदि कोई प्रतिरूप $N$ के $T$,$N\subset M$ के लिए नहीं है।

परिधि केवल न्यूनतम प्रतिरूपों का चयन करके व्यक्त की जाती है। इसे इस प्रकार परिभाषित किया गया है:

$CIRC(T)=\{M~|~M{\mbox{ is a minimal model of }}T\}$

वैकल्पिक रूप से, कोई $CIRC(T)$ प्रतिरूप के बिल्कुल उपरोक्त समुच्चय वाले सूत्र के रूप में परिभाषित कर सकता है; इसके अतिरिक्त, कोई $CIRC$ की परिभाषा देने से भी बच सकता है और केवल न्यूनतम अनुमान $T\models _{M}Q$ को परिभाषित करता यदि है और केवल यदि प्रत्येक न्यूनतम प्रतिरूप $T$ भी एक प्रतिरूप $Q$ है।

उदाहरण: सूत्र $T=a\land (b\lor c)$ तीन प्रतिरूप हैं:

1. $a$, $b$, $c$ सत्य, अर्थात् $\{a,b,c\}$ हैं;
2. $a$ और $b$ सत्य, $c$ असत्य है, अर्थात् $\{a,b\}$ हैं;
3. $a$ और $c$ सत्य, $b$ असत्य है, अर्थात् $\{a,c\}$ हैं;

पहला प्रतिरूप चर के समुच्चय में न्यूनतम नहीं है जो इसे सत्य करता है। वास्तव में, $c$ को छोड़कर दूसरा प्रतिरूप समान कार्य करता है, जिसे असत्य को सौंपा गया है न कि सत्य को। इसलिए, पहला प्रतिरूप न्यूनतम नहीं है। दूसरा और तीसरा प्रतिरूप अतुलनीय हैं: जबकि दूसरा $b$ सत्य है, तीसरा $c$ के बजाय सत्य निर्दिष्ट करता है। इसलिए, सीमाबद्ध प्रतिरूप $T$ सूची के दूसरे और तीसरे प्रतिरूप हैं। वास्तव में इन दो प्रतिरूपों वाले एक प्रस्तावनात्मक सूत्र निम्नलिखित में से एक है:

$a\land \neg (b\leftrightarrow c)$

सहजता से, परिधि में एक चर को केवल तभी निर्दिष्ट किया जाता है जब यह आवश्यक हो। दोहरी रूप से, यदि कोई चर असत्य हो सकता है, तो यह असत्य होना चाहिए। उदाहरण के लिए, कम-से-कम $b$ और $c$, $T$ के अनुसार सत्य को समुनदेशित किया जाना चाहिए; परिधि में दो चरों में से एक सत्य होना चाहिए। चर $a$ के किसी भी प्रतिरूप में $T$ और न ही सीमा असत्य नहीं हो सकती है।

निश्चित और परिवर्तनीय विधेय

निश्चित और परिवर्तनीय विधेय के साथ परिधि का विस्तारण व्लादिमीर लाइफशिट्ज के कारण है। विचार यह है कि कुछ प्रतिबंधों को कम नहीं किया जाना चाहिए। प्रस्तावपरक तर्क के संदर्भ में, यदि संभव हो तो कुछ चर गलत नहीं होने चाहिए। विशेष रूप से, दो प्रकार के चरों पर विचार किया जा सकता है:

परिवर्तनीय

ये वे चर हैं जिन्हें न्यूनीकरण के पर्यन्त तनिक भी ध्यान में नहीं रखा जाना चाहिए;

निश्चित

ये वे चर हैं जिन्हें न्यूनीकरण करते समय निश्चित माना जाता है; दूसरे शब्दों में, इन चरों के समान मानों वाले प्रतिरूपों की तुलना करके ही न्यूनीकरण किया जा सकता है।

अंतर यह है कि अलग-अलग स्थितियों का मान केवल मान लिया जाता है कि कोई फर्क नहीं पड़ता। इसके बजाय निश्चित स्थितियाँ एक संभावित स्थिति की विशेषता बताती हैं, इसलिए दो स्थितियों की तुलना करना जहाँ इन स्थितियों के अलग-अलग मान हैं, कोई अर्थ नहीं है।

औपचारिक रूप से, सीमा का विस्तारण जिसमें भिन्न और निश्चित चर सम्मिलित होते हैं, वह इस प्रकार है, जहां $P$ न्यूनतम करने के लिए चर का समुच्चय है, $Z$ निश्चित चर हैं और भिन्न चर वे हैं जो $P\cup Z$ में नहीं हैं:

$\text{CIRC}(T;P,Z)=\{M|M\models <!--\; \models \; -->T\text{ and }\mathrm{\nexists }N\text{ such that }$