परिधि (तर्क): 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>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>N</math> सत्य पर व्यवस्थित करता है। दूसरे शब्दों में, <math>\subseteq</math> ट्रू लेस चर पर समायोजन के संबंध को प्रतिरूप करता है। <math>N \subset M</math> अर्थ कि <math>N \subseteq 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> परन्तु ये दोनों प्रतिरूप मेल नहीं खाते। | ||
| Line 24: | Line 24: | ||
वैकल्पिक रूप से, कोई परिभाषित कर सकता है <math>CIRC(T)</math> प्रतिरूप के बिल्कुल उपरोक्त समुच्चय वाले सूत्र के रूप में; इसके अतिरिक्त, कोई इसकी परिभाषा देने से भी बच सकता है <math>CIRC</math> और केवल न्यूनतम अनुमान को परिभाषित करें <math>T \models_M Q</math> यदि और केवल यदि प्रत्येक न्यूनतम प्रतिरूप <math>T</math> का भी एक प्रतिरूप है <math>Q</math>. | वैकल्पिक रूप से, कोई परिभाषित कर सकता है <math>CIRC(T)</math> प्रतिरूप के बिल्कुल उपरोक्त समुच्चय वाले सूत्र के रूप में; इसके अतिरिक्त, कोई इसकी परिभाषा देने से भी बच सकता है <math>CIRC</math> और केवल न्यूनतम अनुमान को परिभाषित करें <math>T \models_M Q</math> यदि और केवल यदि प्रत्येक न्यूनतम प्रतिरूप <math>T</math> का भी एक प्रतिरूप है <math>Q</math>. | ||
उदाहरण | उदाहरण: सूत्र <math>T=a \land (b \lor c)</math> तीन प्रतिरूप हैं: | ||
# <math>a</math>, <math>b</math>, <math>c</math> सत्य | # <math>a</math>, <math>b</math>, <math>c</math> सत्य, अर्थात् <math>\{a,b,c\}</math> हैं; | ||
# <math>a</math> और <math>b</math> | # <math>a</math> और <math>b</math> सत्य, <math>c</math> असत्य है, अर्थात् <math>\{a,b\}</math> हैं; | ||
# <math>a</math> और <math>c</math> | # <math>a</math> और <math>c</math> सत्य, <math>b</math> असत्य है, अर्थात् <math>\{a,c\}</math> हैं; | ||
पहला प्रतिरूप चर के समुच्चय में न्यूनतम नहीं है जो इसे सही करता है। वास्तव में, दूसरा प्रतिरूप समान कार्य को छोड़कर करता है <math>c</math>, जिसे असत्य को सौंपा गया है न कि सत्य को। इसलिए, पहला प्रतिरूप न्यूनतम नहीं है। दूसरा और तीसरा प्रतिरूप अतुलनीय हैं: जबकि दूसरा सही है <math>b</math>, तीसरा true निर्दिष्ट करता है <math>c</math> बजाय। इसलिए, सीमाबद्ध प्रतिरूप <math>T</math> सूची के दूसरे और तीसरे प्रतिरूप हैं। वास्तव में इन दो प्रतिरूपों वाले एक प्रस्तावनात्मक सूत्र निम्नलिखित में से एक है: | पहला प्रतिरूप चर के समुच्चय में न्यूनतम नहीं है जो इसे सही करता है। वास्तव में, दूसरा प्रतिरूप समान कार्य को छोड़कर करता है <math>c</math>, जिसे असत्य को सौंपा गया है न कि सत्य को। इसलिए, पहला प्रतिरूप न्यूनतम नहीं है। दूसरा और तीसरा प्रतिरूप अतुलनीय हैं: जबकि दूसरा सही है <math>b</math>, तीसरा true निर्दिष्ट करता है <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>b</math> और <math>c</math>, <math>T</math> के अनुसार सत्य को समुनदेशित किया जाना चाहिए; परिसीमा में दो चरों में से एक सत्य होना चाहिए। चर <math>a</math> के किसी भी प्रतिरूप में <math>T</math> और न ही सीमा असत्य नहीं हो सकता। | ||
== | == निश्चित और परिवर्तनीय विधेय == | ||
निश्चित और | निश्चित और परिवर्तनीय विधेय के साथ परिसीमा का विस्तारण [[व्लादिमीर लाइफशिट्ज]] के कारण है।<ref>Lifschitz, V. (November 1985). "Closed-world databases and circumscription". Artificial Intelligence. 27: 229–235. doi:10.1016/0004-3702(85)90055-4.</ref> विचार यह है कि कुछ प्रतिबंधों को कम नहीं किया जाना चाहिए। प्रस्तावपरक तर्क के संदर्भ में, यदि संभव हो तो कुछ चर गलत नहीं होने चाहिए। विशेष रूप से, दो प्रकार के चरों पर विचार किया जा सकता है: | ||
; | ; परिवर्तनीय: ये वे चर हैं जिन्हें न्यूनीकरण के पर्यन्त तनिक भी ध्यान में नहीं रखा जाना चाहिए; | ||
; निश्चित: ये वे चर हैं जिन्हें न्यूनीकरण करते समय निश्चित माना जाता है; दूसरे शब्दों में, इन चरों के समान मानों वाले प्रतिरूपों की तुलना करके ही न्यूनीकरण किया जा सकता है। | ; निश्चित: ये वे चर हैं जिन्हें न्यूनीकरण करते समय निश्चित माना जाता है; दूसरे शब्दों में, इन चरों के समान मानों वाले प्रतिरूपों की तुलना करके ही न्यूनीकरण किया जा सकता है। | ||
अंतर यह है कि अलग-अलग स्थितियों का मान केवल मान लिया जाता है कि कोई फर्क नहीं पड़ता। इसके बजाय निश्चित स्थितियाँ एक संभावित स्थिति की विशेषता बताती हैं, इसलिए दो स्थितियों की तुलना करना जहाँ इन स्थितियों के अलग-अलग मान हैं, कोई | अंतर यह है कि अलग-अलग स्थितियों का मान केवल मान लिया जाता है कि कोई फर्क नहीं पड़ता। इसके बजाय निश्चित स्थितियाँ एक संभावित स्थिति की विशेषता बताती हैं, इसलिए दो स्थितियों की तुलना करना जहाँ इन स्थितियों के अलग-अलग मान हैं, कोई अर्थ नहीं है। | ||
औपचारिक रूप से, सीमा का विस्तारण जिसमें भिन्न और निश्चित चर सम्मिलित होते हैं, वह इस प्रकार है, जहां <math>P</math> न्यूनतम करने के लिए चर का समुच्चय है, <math>Z</math> निश्चित चर | औपचारिक रूप से, सीमा का विस्तारण जिसमें भिन्न और निश्चित चर सम्मिलित होते हैं, वह इस प्रकार है, जहां <math>P</math> न्यूनतम करने के लिए चर का समुच्चय है, <math>Z</math> निश्चित चर हैं और भिन्न चर वे हैं जो <math>P \cup Z</math> में नहीं हैं: | ||
:<math>\text{CIRC}(T;P,Z) = \{ M ~|~ M \models T \text{ and } | :<math>\text{CIRC}(T;P,Z) = \{ M ~|~ M \models T \text{ and } | ||
\not\exists N \text{ such that } N \models T ,~ N \cap P \subset M \cap P \text{ and } N \cap Z = M \cap Z \}</math> | \not\exists N \text{ such that } N \models T ,~ N \cap P \subset M \cap P \text{ and } N \cap Z = M \cap Z \}</math> | ||
शब्दों में, सत्य को सौंपे गए चरों का न्यूनीकरण केवल चरों | शब्दों में, सत्य को सौंपे गए चरों का न्यूनीकरण केवल चरों <math>P</math> के लिए किया जाता है; इसके अतिरिक्त, प्रतिरूप की तुलना केवल तभी की जाती है जब वे चर <math>Z</math> के लिए समान मान निर्दिष्ट करते हैं। प्रतिरूपों की तुलना करते समय अन्य सभी चरों को ध्यान में नहीं रखा जाता है। | ||
मैक्कार्थी द्वारा प्रस्तावित प्रधार समस्या का समाधान सीमा पर आधारित है जिसमें कोई निश्चित स्थिति नहीं है। प्रस्तावात्मक स्थिति में, इस समाधान को निम्नानुसार वर्णित किया जा सकता है: ज्ञात सूत्रों को सीधे | मैक्कार्थी द्वारा प्रस्तावित प्रधार समस्या का समाधान सीमा पर आधारित है जिसमें कोई निश्चित स्थिति नहीं है। प्रस्तावात्मक स्थिति में, इस समाधान को निम्नानुसार वर्णित किया जा सकता है: ज्ञात सूत्रों को सीधे विकोडन करने के अतिरिक्त, प्रतिबंधों के मानों में परिवर्तन का प्रतिनिधित्व करने वाले नए चर भी परिभाषित करते हैं; इन नए चरों को फिर कम किया जाता है। | ||
उदाहरण के लिए, उस कार्यक्षेत्र का जिसमें एक | उदाहरण के लिए, उस कार्यक्षेत्र का जिसमें एक द्वार है जो समय 0 पर संवृत्त होता है और जिसमें समय 2 पर द्वार विवृति की क्रिया निष्पादित होती है, जिसे स्पष्ट रूप से जाना जाता है वह दो सूत्रों द्वारा दर्शाया जाता है: | ||
:<math>\neg \text{open}_0</math> | :<math>\neg \text{open}_0</math> | ||
:<math>\text{true} \rightarrow \text{open}_2</math> | :<math>\text{true} \rightarrow \text{open}_2</math> | ||
प्रधार समस्या इस उदाहरण में समस्या | प्रधार समस्या इस उदाहरण में समस्या <math>\neg open_1</math>के रूप में दिखाई देती है। उपरोक्त सूत्रों का परिणाम नहीं है, जबकि द्वार को तब तक संवृत्त रहना चाहिए जब तक कि उसे विवृति की क्रिया न हो जाए। नए चर को परिभाषित करके प्रतिबंध का उपयोग इस उद्देश्य के लिए <math>change\_open_t</math> परिवर्तनों को प्रतिरूप करने और फिर उन्हें कम करने के लिए किया जा सकता है : | ||
:<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> | ||
Revision as of 23:28, 25 May 2023
परिसीमन जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) द्वारा बनाया गया एक गैर-मोनोटोनिक तर्क है जो सामान्य ज्ञान की धारणा को औपचारिक रूप देने के लिए है कि जब तक अन्यथा निर्दिष्ट नहीं किया जाता है तब तक चीजें अपेक्षित होती हैं।[1][2] प्रधार समस्या को हल करने के प्रयास में बाद में मैक्कार्थी द्वारा परिसीमा का उपयोग किया गया था। अपने प्रारंभिक सूत्रीकरण में परिसीमा को अनुप्रयुक्त करने के लिए, मैककार्थी ने कुछ विधेय के विस्तारण (शब्दार्थ) को कम करने की अनुमति देने के लिए प्रथम-क्रम तर्क को बढ़ाया, जहां विधेय का विस्तारण मानों के टपल का समुच्चय है, जिस पर विधेय सत्य है। यह न्यूनीकरण संवृत्त-विश्व धारणा के समान है कि जो सत्य नहीं है वह असत्य है।[3] मैक्कार्थी द्वारा मानी गई मूल समस्या मिशनरियों और नरभक्षी समस्या की थी: एक नदी के एक किनारे पर तीन मिशनरी और तीन नरभक्षी हैं; उन्हें एक नाव का उपयोग करके नदी पार करनी होती है जो केवल दो लोगों को ले जा सकती है, इस अतिरिक्त बाधा के साथ कि नरभक्षी को किसी भी किनारे पर मिशनरियों से अधिक नहीं होना चाहिए (अन्यथा मिशनरियों को मार दिया जाएगा और संभवतः खाया जाएगा)। मैक्कार्थी द्वारा विचार की गई समस्या लक्ष्य तक पहुँचने के लिए कदमों के अनुक्रम को खोजने की नहीं थी (मिशनरियों और नरभक्षी समस्या पर लेख में ऐसा एक समाधान सम्मिलित है), बल्कि उन स्थितियों को बाहर करने की है जो स्पष्ट रूप से नहीं बताई गई हैं। उदाहरण के लिए, समाधान आधा मील दक्षिण की ओर जाता है और पुल पर नदी को पार करना सहज रूप से मान्य नहीं है क्योंकि समस्या के बयान में ऐसे पुल का उल्लेख नहीं है। दूसरी ओर, इस पुल के अस्तित्व को भी समस्या के बयान से बाहर नहीं किया गया है। कि पुल उपस्थित नहीं है निहित धारणा का परिणाम है कि समस्या के बयान में वह सब कुछ है जो इसके समाधान के लिए प्रासंगिक है। स्पष्ट रूप से यह कहना कि एक पुल उपस्थित नहीं है, इस समस्या का समाधान नहीं है, क्योंकि कई अन्य असाधारण स्थितियां हैं जिन्हें बाहर रखा जाना चाहिए (जैसे कि नरभक्षी को बन्धन के लिए रस्सी की उपस्थिति, पास में एक बड़ी नाव की उपस्थिति, आदि। )
जड़ता की अंतर्निहित धारणा को औपचारिक रूप देने के लिए बाद में मैक्कार्थी द्वारा परिसीमा का उपयोग किया गया था: जब तक अन्यथा निर्दिष्ट नहीं किया जाता तब तक चीजें परिवर्तित होती नहीं हैं। परिसीमन यह निर्दिष्ट करने से बचने के लिए उपयोगी प्रतीत होता है कि प्रतिबंधों को परिवर्तित करने के लिए स्पष्ट रूप से ज्ञात को छोड़कर सभी क्रियाओं द्वारा स्थिति नहीं परिवर्तित की जाती है; इसे प्रधार समस्या के रूप में जाना जाता है। हालांकि, बाद में मैक्कार्थी द्वारा प्रस्तावित समाधान को कुछ स्थितियों में गलत परिणामों के लिए अग्रणी दिखाया गया, जैसे येल प्रक्षेपण समस्या परिदृश्य में। प्रधार समस्या के अन्य समाधान जो येल प्रक्षेपण समस्या को सही ढंग से औपचारिक रूप देते हैं, उपस्थित हैं; कुछ परिमार्जन का उपयोग करते हैं परन्तु एक अलग तरीके से।
प्रस्तावात्मक मामला
जबकि परिसीमा को प्रारंभ में प्रथम-क्रम तर्क स्थिति में परिभाषित किया गया था, प्रस्तावात्मक स्थिति की विशिष्टता को परिभाषित करना आसान है।[4] एक प्रस्तावक सूत्र दिया गया है , इसकी परिसीमा केवल संरचना (गणितीय तर्क) वाले सूत्र है जब तक आवश्यक न हो, एक चर को सत्य पर नियत न करें।
औपचारिक रूप से, प्रस्तावात्मक प्रतिरूप को प्रस्तावात्मक चर के समुच्चय द्वारा दर्शाया जा सकता है; अर्थात्, प्रत्येक प्रतिरूप को प्रस्तावक चर के समुच्चय द्वारा दर्शाया जाता है जो इसे सत्य को निर्दिष्ट करता है। उदाहरण के लिए, सही निर्दिष्ट करने वाला प्रतिरूप , असत्य , और सच है समुच्चय द्वारा दर्शाया गया है , क्योंकि और वास्तव में वे चर हैं जो इस प्रतिरूप द्वारा सत्य को सौंपे गए हैं।
दो प्रतिरूप दिए और इस तरह से प्रतिनिधित्व किया, स्थिति के समान है प्रत्येक चर को सत्य पर व्यवस्थित करना सत्य पर व्यवस्थित करता है। दूसरे शब्दों में, ट्रू लेस चर पर समायोजन के संबंध को प्रतिरूप करता है। अर्थ कि परन्तु ये दोनों प्रतिरूप मेल नहीं खाते।
यह हमें उन प्रतिरूपों को परिभाषित करने देता है जो आवश्यक होने तक सत्य को चर निर्दिष्ट नहीं करते हैं। एक प्रतिमा एक सिद्धांत का (तर्क) न्यूनतम कहा जाता है, यदि और केवल यदि कोई प्रतिरूप नहीं है का जिसके लिए .
परिसीमा केवल न्यूनतम प्रतिरूपों का चयन करके व्यक्त की जाती है। इसे इस प्रकार परिभाषित किया गया है:
वैकल्पिक रूप से, कोई परिभाषित कर सकता है प्रतिरूप के बिल्कुल उपरोक्त समुच्चय वाले सूत्र के रूप में; इसके अतिरिक्त, कोई इसकी परिभाषा देने से भी बच सकता है और केवल न्यूनतम अनुमान को परिभाषित करें यदि और केवल यदि प्रत्येक न्यूनतम प्रतिरूप का भी एक प्रतिरूप है .
उदाहरण: सूत्र तीन प्रतिरूप हैं:
- , ,