परिधि (तर्क): Difference between revisions
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
जबकि परिधि को प्रारंभ में प्रथम-क्रम तर्क स्थिति में परिभाषित किया गया था, प्रस्तावात्मक स्थिति की विशिष्टता को परिभाषित करना सरल है।<ref>Cadoli, M.; Lenzerini, M. (April 1994). "The complexity of propositional closed world reasoning and circumscription". Journal of Computer and System Sciences. 48 (2): 255–310. doi:10.1016/S0022-0000(05)80004-2.</ref> एक [[प्रस्तावक सूत्र]] <math>T</math> दिया गया है, इसकी परिधि केवल <math>T</math> [[संरचना (गणितीय तर्क)|संरचना]] वाले सूत्र है, जब तक आवश्यक न हो, एक चर को सत्य पर निर्दिष्ट न करें। | जबकि परिधि को प्रारंभ में प्रथम-क्रम तर्क स्थिति में परिभाषित किया गया था, प्रस्तावात्मक स्थिति की विशिष्टता को परिभाषित करना सरल है।<ref>Cadoli, M.; Lenzerini, M. (April 1994). "The complexity of propositional closed world reasoning and circumscription". Journal of Computer and System Sciences. 48 (2): 255–310. doi:10.1016/S0022-0000(05)80004-2.</ref> एक [[प्रस्तावक सूत्र]] <math>T</math> दिया गया है, इसकी परिधि केवल <math>T</math> [[संरचना (गणितीय तर्क)|संरचना]] वाले सूत्र है, जब तक आवश्यक न हो, एक चर को सत्य पर निर्दिष्ट न करें। | ||
औपचारिक रूप से, प्रस्तावात्मक प्रतिरूप को प्रस्तावात्मक चर के समुच्चय द्वारा दर्शाया जा सकता है; अर्थात्, प्रत्येक प्रतिरूप को [[प्रस्तावक चर]] के समुच्चय द्वारा दर्शाया जाता है जो | औपचारिक रूप से, प्रस्तावात्मक प्रतिरूप को प्रस्तावात्मक चर के समुच्चय द्वारा दर्शाया जा सकता है; अर्थात्, प्रत्येक प्रतिरूप को [[प्रस्तावक चर]] के समुच्चय द्वारा दर्शाया जाता है जो सत्य को निर्दिष्ट करता है। उदाहरण के लिए, सही निर्दिष्ट करने वाला प्रतिरूप <math>a</math>, असत्य <math>b</math>, और सत्य <math>c</math> को समुच्चय <math>\{a, c\}</math> द्वारा दर्शाया गया है, क्योंकि <math>a</math> और <math>c</math> वास्तव में वे चर हैं जो इस प्रतिरूप द्वारा सत्य को सौंपे गए हैं। | ||
दिए गए दो प्रतिरूपों <math>M</math> और <math>N</math> ने इस तरह से स्थिति का प्रतिनिधित्व किया कि <math>N \subseteq M</math> के समान है। <math>M</math> प्रत्येक चर को सत्य पर | दिए गए दो प्रतिरूपों <math>M</math> और <math>N</math> ने इस तरह से स्थिति का प्रतिनिधित्व किया कि <math>N \subseteq M</math> के समान है। <math>M</math> प्रत्येक चर को सत्य पर समायोजित करता है, <math>N</math> सत्य पर व्यवस्थित होता है। दूसरे शब्दों में, <math>\subseteq</math> "सत्य न्यून चरो के समायोजन" के संबंध को प्रतिरूप करता है। <math>N \subset M</math> का अर्थ है कि <math>N \subseteq M</math> परन्तु ये दोनों प्रतिरूप मेल नहीं खाते हैं। | ||
यह हमें उन प्रतिरूपों को परिभाषित करने देता है जो आवश्यक होने तक सत्य को चर निर्दिष्ट नहीं करते हैं। एक प्रतिरूप <math>M</math> को सिद्धांत <math>T</math> का न्यूनतम कहा जाता है, यदि और केवल यदि कोई प्रतिरूप <math>N</math> के <math>T</math>,<math>N \subset M</math> के लिए नहीं है। | यह हमें उन प्रतिरूपों को परिभाषित करने देता है जो आवश्यक होने तक सत्य को चर निर्दिष्ट नहीं करते हैं। एक प्रतिरूप <math>M</math> को सिद्धांत <math>T</math> का न्यूनतम कहा जाता है, यदि और केवल यदि कोई प्रतिरूप <math>N</math> के <math>T</math>,<math>N \subset M</math> के लिए नहीं है। | ||
| Line 29: | Line 29: | ||
# <math>a</math> और <math>c</math> सत्य, <math>b</math> असत्य है, अर्थात् <math>\{a,c\}</math> हैं; | # <math>a</math> और <math>c</math> सत्य, <math>b</math> असत्य है, अर्थात् <math>\{a,c\}</math> हैं; | ||
पहला प्रतिरूप चर के समुच्चय में न्यूनतम नहीं है जो इसे सत्य करता है। वास्तव में, | पहला प्रतिरूप चर के समुच्चय में न्यूनतम नहीं है जो इसे सत्य करता है। वास्तव में, <math>c</math> को छोड़कर दूसरा प्रतिरूप समान कार्य करता है, जिसे असत्य को सौंपा गया है न कि सत्य को। इसलिए, पहला प्रतिरूप न्यूनतम नहीं है। दूसरा और तीसरा प्रतिरूप अतुलनीय हैं: जबकि दूसरा <math>b</math> सत्य है, तीसरा <math>c</math> के बजाय सत्य निर्दिष्ट करता है। इसलिए, सीमाबद्ध प्रतिरूप <math>T</math> सूची के दूसरे और तीसरे प्रतिरूप हैं। वास्तव में इन दो प्रतिरूपों वाले एक प्रस्तावनात्मक सूत्र निम्नलिखित में से एक है: | ||
:<math>a \land \neg (b \leftrightarrow c)</math> | :<math>a \land \neg (b \leftrightarrow c)</math> | ||
सहजता से, परिधि में एक चर को केवल तभी निर्दिष्ट किया जाता है जब यह आवश्यक हो। दोहरी रूप से, यदि कोई चर असत्य हो सकता है, तो यह असत्य होना चाहिए। उदाहरण के लिए, कम से कम | सहजता से, परिधि में एक चर को केवल तभी निर्दिष्ट किया जाता है जब यह आवश्यक हो। दोहरी रूप से, यदि कोई चर असत्य हो सकता है, तो यह असत्य होना चाहिए। उदाहरण के लिए, कम-से-कम <math>b</math> और <math>c</math>, <math>T</math> के अनुसार सत्य को समुनदेशित किया जाना चाहिए; परिधि में दो चरों में से एक सत्य होना चाहिए। चर <math>a</math> के किसी भी प्रतिरूप में <math>T</math> और न ही सीमा असत्य नहीं हो सकती है। | ||
== निश्चित और परिवर्तनीय विधेय == | == निश्चित और परिवर्तनीय विधेय == | ||
| Line 60: | Line 60: | ||
:<math>\text{change open}_0 \equiv (\text{open}_0 \not\equiv \text{open}_1)</math> | :<math>\text{change open}_0 \equiv (\text{open}_0 \not\equiv \text{open}_1)</math> | ||
:<math>\text{change open}_1 \equiv (\text{open}_1 \not\equiv \text{open}_2)</math> | :<math>\text{change open}_1 \equiv (\text{open}_1 \not\equiv \text{open}_2)</math> | ||
: | : | ||
जैसा कि येल प्रक्षेपण समस्या द्वारा दर्शाया गया है, इस प्रकार का समाधान कार्य नहीं करता है। उदाहरण के लिए, <math>\neg \text{open}_1</math>अभी तक उपरोक्त सूत्रों की परिधि में सम्मिलित नहीं है: वह प्रतिरूप जिसमें <math>\text{change open}_0</math>सत्य और <math>\text{change open}_1</math>असत्य है, विपरीत मानों वाले प्रतिरूपों के साथ अतुलनीय है। इसलिए, जिस स्थिति में द्वार 1 समय पर विवृत हो जाता है और फिर क्रिया के परिणामस्वरूप विवृत रहता है, उसे परिसीमन द्वारा बाहर नहीं किया जाता है। | |||
ऐसी समस्याओं से ग्रसित नहीं गतिशील कार्यक्षेत्र के कई अन्य औपचारिकताओं को विकसित किया गया है (एक संक्षिप्त विवरण के लिए प्रधार समस्या देखें)। कई लोग सीमा का उपयोग एक अलग तरीके से करते हैं। | |||
ऐसी समस्याओं से ग्रसित नहीं गतिशील कार्यक्षेत्र के कई अन्य औपचारिकताओं को विकसित किया गया है (एक संक्षिप्त विवरण के लिए प्रधार समस्या देखें)। कई लोग सीमा का उपयोग | |||
== विधेय परिधि == | == विधेय परिधि == | ||
| Line 103: | Line 102: | ||
परिधि सदैव वियोगात्मक सूचना को सही ढंग से नियंत्रित नहीं करता है। [[रेमंड राइटर|रे रेइटर]] ने निम्नलिखित उदाहरण प्रदान किया: एक चेकबोर्ड पर एक सिक्का उछाला जाता है और परिणाम यह होता है कि सिक्का या तो एक काले क्षेत्र पर, या एक सफेद क्षेत्र पर, या दोनों पर होता है। हालाँकि, बड़ी संख्या में अन्य संभावित स्थान हैं जहाँ सिक्का नहीं होना चाहिए; उदाहरण के लिए, यह निहित है कि सिक्का भूतल पर, या प्रशीतित्र पर, या चंद्रमा की सतह पर नहीं है। इसलिए परिधि <math>On</math> विधेय का उपयोग विस्तारण को कम करने के लिए किया जा सकता है, ताकि <math>On(\text{coin},\text{moon})</math> असत्य है भले ही यह स्पष्ट रूप से नहीं कहा गया हो। | परिधि सदैव वियोगात्मक सूचना को सही ढंग से नियंत्रित नहीं करता है। [[रेमंड राइटर|रे रेइटर]] ने निम्नलिखित उदाहरण प्रदान किया: एक चेकबोर्ड पर एक सिक्का उछाला जाता है और परिणाम यह होता है कि सिक्का या तो एक काले क्षेत्र पर, या एक सफेद क्षेत्र पर, या दोनों पर होता है। हालाँकि, बड़ी संख्या में अन्य संभावित स्थान हैं जहाँ सिक्का नहीं होना चाहिए; उदाहरण के लिए, यह निहित है कि सिक्का भूतल पर, या प्रशीतित्र पर, या चंद्रमा की सतह पर नहीं है। इसलिए परिधि <math>On</math> विधेय का उपयोग विस्तारण को कम करने के लिए किया जा सकता है, ताकि <math>On(\text{coin},\text{moon})</math> असत्य है भले ही यह स्पष्ट रूप से नहीं कहा गया हो। | ||
दूसरी ओर, <math>On</math> का न्यूनतमकरण विधेय पर गलत परिणाम होता है कि सिक्का या तो काले क्षेत्र पर या सफेद क्षेत्र पर है, परन्तु दोनों पर नहीं है। ऐसा इसलिए है क्योंकि जिन प्रतिरूपों में <math>On</math> पर ही सत्य है, <math>(\text{coin},\text{white area})</math> और केवल <math>On</math> पर <math>(\text{coin},\text{black area})</math> का न्यूनतम विस्तारण है, जबकि प्रतिरूप जिसमें <math>On</math> का विस्तारण दोनों युग्मों से बना है, न्यूनतम नहीं है। | दूसरी ओर, <math>On</math> का न्यूनतमकरण विधेय पर गलत परिणाम होता है कि सिक्का या तो काले क्षेत्र पर या सफेद क्षेत्र पर है, परन्तु दोनों पर नहीं है। ऐसा इसलिए है क्योंकि जिन प्रतिरूपों में <math>On</math> पर ही सत्य है, <math>(\text{coin},\text{white area})</math> और केवल <math>On</math> पर <math>(\text{coin},\text{black area})</math> का न्यूनतम विस्तारण है, जबकि प्रतिरूप जिसमें <math>On</math> का विस्तारण दोनों युग्मों से बना है, जो न्यूनतम नहीं है। | ||
सिद्धान्त अंकुश [[थॉमस ईटर]], [[जॉर्ज गोटलोब]] और [[यूरी गुरेविच]] द्वारा प्रस्तावित एक समाधान है।<ref>Eiter, T.; Gottlob, G.; Gurevich, Y. (1993). "CURB your theory!". In Bajcsy, Ruzena. IJCAI-93: proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, Chambéry, France, August 28–September 3, 1993. IJCAII. pp. 634–9. {{ISBN|155860300X}}.</ref> विचार यह है कि जिस प्रतिरूप में परिधि का चयन करने में विफल रहता है, वह एक जिसमें दोनों<math>On(\text{coin},\text{white area})</math> और <math>On(\text{coin},\text{black area})</math> सत्य हैं, सूत्र का एक प्रतिरूप है जो ( | सिद्धान्त अंकुश [[थॉमस ईटर]], [[जॉर्ज गोटलोब]] और [[यूरी गुरेविच]] द्वारा प्रस्तावित एक समाधान है।<ref>Eiter, T.; Gottlob, G.; Gurevich, Y. (1993). "CURB your theory!". In Bajcsy, Ruzena. IJCAI-93: proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, Chambéry, France, August 28–September 3, 1993. IJCAII. pp. 634–9. {{ISBN|155860300X}}.</ref> विचार यह है कि जिस प्रतिरूप में परिधि का चयन करने में विफल रहता है, वह एक जिसमें दोनों<math>On(\text{coin},\text{white area})</math> और <math>On(\text{coin},\text{black area})</math> सत्य हैं, सूत्र का एक प्रतिरूप है जो (<math>On</math> का डब्ल्यू .आर. टी विस्तारण) चुने गए दोनों प्रतिरूपों की तुलना में अधिक है। अधिक विशेष रूप से, सूत्र के प्रतिरूपों में, बहिष्कृत प्रतिरूप दो चयनित प्रतिरूपों की सबसे कम ऊपरी सीमा है। सिद्धान्त अंकुश इस तरह के कम-से-कम ऊपरी सीमा प्रतिरूप का चयन करता है, इसके अतिरिक्त परिधि द्वारा चुना जाता है। यह समावेशन तब तक किया जाता है जब तक प्रतिरूप का समुच्चय संवृत्त नहीं हो जाता है, इस अर्थ में कि इसमें प्रतिरूप के सभी समुच्चयों की कम से कम ऊपरी सीमाएं सम्मिलित हैं। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 11:21, 26 May 2023
परिधि एक गैर-एकदिष्ट तर्क है जो जॉन मैक्कार्थी द्वारा सामान्य ज्ञान धारणा को औपचारिक रूप देने के लिए बनाई गई है कि जब तक अन्यथा निर्दिष्ट नहीं किया जाता है तब तक चीजें अपेक्षित होती हैं।[1][2] प्रधार समस्या को हल करने के प्रयास में बाद में मैक्कार्थी द्वारा परिधि का उपयोग किया गया था। अपने प्रारंभिक सूत्रीकरण में परिधि को अनुप्रयुक्त करने के लिए, मैक्कार्थी ने कुछ विधेय के विस्तार को कम करने की अनुमति देने के लिए प्रथम-क्रम तर्क को बढ़ाया, जहां विधेय का विस्तार मानों के टपल का समुच्चय है, जिस पर विधेय सत्य है। यह न्यूनीकरण संवृत्त-विश्व धारणा के समान है कि जो सत्य नहीं है वह असत्य है।[3]
मैक्कार्थी द्वारा मानी गई मूल समस्या मिशनरियों और नरभक्षी की थी: नदी के एक किनारे पर तीन मिशनरी और तीन नरभक्षी हैं; उन्हें एक नौका का उपयोग करके नदी पार करनी होती है जो केवल दो लोगों को ले जा सकती है, इस अतिरिक्त बाधा के साथ कि नरभक्षी को किसी भी किनारे पर मिशनरियों से अधिक नहीं होना चाहिए (अन्यथा मिशनरियों को मार दिया जाएगा और संभवतः खाया जाएगा)। मैक्कार्थी द्वारा विचार की गई समस्या लक्ष्य तक पहुँचने के लिए चरणों के अनुक्रम को खोजने की नहीं थी (मिशनरियों और नरभक्षी समस्या पर लेख में ऐसा एक समाधान सम्मिलित है), बल्कि उन स्थितियों को बाहर करने की है जो स्पष्ट रूप से नहीं बताई गई हैं। उदाहरण के लिए, समाधान "आधा मील दक्षिण में जाएं और सेतु पर नदी पार करें" सहज रूप से मान्य नहीं है क्योंकि समस्या के विवरण में ऐसे सेतु का उल्लेख नहीं है। दूसरी ओर, इस सेतु के अस्तित्व को भी समस्या के विवरण से बाहर नहीं किया गया है। यह कि सेतु का अस्तित्व नहीं है, निहित धारणा का परिणाम है कि समस्या के विवरण में वह सब कुछ है जो इसके समाधान के लिए प्रासंगिक है। स्पष्ट रूप से यह कहना कि एक सेतु उपस्थित नहीं है, इस समस्या का समाधान नहीं है, क्योंकि कई अन्य असाधारण स्थितियां हैं जिन्हें बाहर रखा जाना चाहिए (जैसे कि नरभक्षी को बन्धन के लिए रज्जु की उपस्थिति, पास में एक बड़ी नौका की उपस्थिति, आदि)।
जड़ता की अंतर्निहित धारणा को औपचारिक रूप देने के लिए बाद में मैक्कार्थी द्वारा परिधि का उपयोग किया गया था: जब तक अन्यथा निर्दिष्ट नहीं किया जाता तब तक चीजें परिवर्तित होती नहीं हैं। परिसीमन यह निर्दिष्ट करने से बचने के लिए उपयोगी प्रतीत होता है कि प्रतिबंधों को परिवर्तित करने के लिए स्पष्ट रूप से ज्ञात को छोड़कर सभी क्रियाओं द्वारा स्थिति नहीं परिवर्तित की जाती है; इसे प्रधार समस्या के रूप में जाना जाता है। हालांकि, बाद में मैक्कार्थी द्वारा प्रस्तावित समाधान को कुछ स्थितियों में असत्य परिणामों के लिए अग्रणी दर्शाया गया, जैसे येल प्रक्षेपण समस्या परिदृश्य में है। प्रधार समस्या के अन्य समाधान जो येल प्रक्षेपण समस्या को सही ढंग से औपचारिक रूप प्रदान करते हैं, जो उपस्थित हैं; कुछ परिधि का उपयोग एक अलग तरीके से करते हैं।
प्रस्तावात्मक स्थिति
जबकि परिधि को प्रारंभ में प्रथम-क्रम तर्क स्थिति में परिभाषित किया गया था, प्रस्तावात्मक स्थिति की विशिष्टता को परिभाषित करना सरल है।[4] एक प्रस्तावक सूत्र दिया गया है, इसकी परिधि केवल संरचना वाले सूत्र है, जब तक आवश्यक न हो, एक चर को सत्य पर निर्दिष्ट न करें।
औपचारिक रूप से, प्रस्तावात्मक प्रतिरूप को प्रस्तावात्मक चर के समुच्चय द्वारा दर्शाया जा सकता है; अर्थात्, प्रत्येक प्रतिरूप को प्रस्तावक चर के समुच्चय द्वारा दर्शाया जाता है जो सत्य को निर्दिष्ट करता है। उदाहरण के लिए, सही निर्दिष्ट करने वाला प्रतिरूप , असत्य , और सत्य को समुच्चय द्वारा दर्शाया गया है, क्योंकि और वास्तव में वे चर हैं जो इस प्रतिरूप द्वारा सत्य को सौंपे गए हैं।
दिए गए दो प्रतिरूपों और ने इस तरह से स्थिति का प्रतिनिधित्व किया कि के समान है। प्रत्येक चर को सत्य पर समायोजित करता है, सत्य पर व्यवस्थित होता है। दूसरे शब्दों में, "सत्य न्यून चरो के समायोजन" के संबंध को प्रतिरूप करता है। का अर्थ है कि परन्तु ये दोनों प्रतिरूप मेल नहीं खाते हैं।
यह हमें उन प्रतिरूपों को परिभाषित करने देता है जो आवश्यक होने तक सत्य को चर निर्दिष्ट नहीं करते हैं। एक प्रतिरूप को सिद्धांत का न्यूनतम कहा जाता है, यदि और केवल यदि कोई प्रतिरूप के , के लिए नहीं है।
परिधि केवल न्यूनतम प्रतिरूपों का चयन करके व्यक्त की जाती है। इसे इस प्रकार परिभाषित किया गया है:
वैकल्पिक रूप से, कोई प्रतिरूप के बिल्कुल उपरोक्त समुच्चय वाले सूत्र के रूप में परिभाषित कर सकता है; इसके अतिरिक्त, कोई की परिभाषा देने से भी बच सकता है और केवल न्यूनतम अनुमान को परिभाषित करता यदि है और केवल यदि प्रत्येक न्यूनतम प्रतिरूप भी एक प्रतिरूप है।
उदाहरण: सूत्र तीन प्रतिरूप हैं:
- , , सत्य, अर्थात् हैं;
- और सत्य,