परिधि (तर्क)

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$, तीसरा true निर्दिष्ट करता है $c$ बजाय। इसलिए, सीमाबद्ध प्रतिरूप $T$ सूची के दूसरे और तीसरे प्रतिरूप हैं। वास्तव में इन दो प्रतिरूपों वाले एक प्रस्तावनात्मक सूत्र निम्नलिखित में से एक है:

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

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

फिक्स्ड और अलग-अलग विधेय

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

अलग-अलग

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

निश्चित

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

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

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