परिधि (तर्क)

From Vigyanwiki
Revision as of 11:30, 15 May 2023 by alpha>Indicwiki (Created page with "{{short description|Non-monotonic logic created by John McCarthy}} {{distinguish|circumscribe}} सर्कमस्क्रिप्शन जॉन मैक्कार...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

प्रस्तावात्मक मामला

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

औपचारिक रूप से, प्रस्तावात्मक मॉडल को प्रस्तावात्मक चर के सेट द्वारा दर्शाया जा सकता है; अर्थात्, प्रत्येक मॉडल को प्रस्तावक चर के सेट द्वारा दर्शाया जाता है जो इसे सत्य को निर्दिष्ट करता है। उदाहरण के लिए, सही असाइन करने वाला मॉडल , झूठा , और सच है सेट द्वारा दर्शाया गया है , क्योंकि और वास्तव में वे चर हैं जो इस मॉडल द्वारा सत्य को सौंपे गए हैं।

दो मॉडल दिए और इस तरह से प्रतिनिधित्व किया, स्थिति के बराबर है प्रत्येक चर को सत्य पर सेट करना सत्य पर सेट करता है। दूसरे शब्दों में, ट्रू लेस वेरिएबल्स पर सेटिंग के संबंध को मॉडल करता है। मतलब कि लेकिन ये दोनों मॉडल मेल नहीं खाते।

यह हमें उन मॉडलों को परिभाषित करने देता है जो आवश्यक होने तक सत्य को चर निर्दिष्ट नहीं करते हैं। एक प्रतिमा एक सिद्धांत का (तर्क) न्यूनतम कहा जाता है, अगर और केवल अगर कोई मॉडल नहीं है का जिसके लिए .

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

वैकल्पिक रूप से, कोई परिभाषित कर सकता है मॉडल के बिल्कुल उपरोक्त सेट वाले सूत्र के रूप में; इसके अलावा, कोई इसकी परिभाषा देने से भी बच सकता है और केवल न्यूनतम अनुमान को परिभाषित करें यदि और केवल यदि प्रत्येक न्यूनतम मॉडल का भी एक मॉडल है .

उदाहरण के तौर पर सूत्र तीन मॉडल हैं:

  1. , , सत्य हैं, अर्थात् ;
  2. और सच हैं, असत्य है, अर्थात् ;
  3. और सच हैं, असत्य है, अर्थात् .

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

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

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

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

अलग-अलग
ये वे चर हैं जिन्हें न्यूनीकरण के दौरान बिल्कुल भी ध्यान में नहीं रखा जाना चाहिए;
निश्चित
ये वे चर हैं जिन्हें न्यूनीकरण करते समय निश्चित माना जाता है; दूसरे शब्दों में, इन चरों के समान मूल्यों वाले मॉडलों की तुलना करके ही न्यूनीकरण किया जा सकता है।

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

औपचारिक रूप से, सीमा का विस्तार जिसमें भिन्न और निश्चित चर शामिल होते हैं, वह इस प्रकार है, जहां न्यूनतम करने के लिए चर का सेट है, निश्चित चर, और अलग-अलग चर वे हैं जो अंदर नहीं हैं :

शब्दों में, सत्य को सौंपे गए चरों का न्यूनीकरण केवल चरों के लिए किया जाता है ; इसके अलावा, मॉडल की तुलना केवल तभी की जाती है जब वे चर के लिए समान मान निर्दिष्ट करते हैं . मॉडलों की तुलना करते समय अन्य सभी चरों को ध्यान में नहीं रखा जाता है।

मैक्कार्थी द्वारा प्रस्तावित फ्रेम समस्या का समाधान सीमा पर आधारित है जिसमें कोई निश्चित स्थिति नहीं है। प्रस्तावात्मक मामले में, इस समाधान को निम्नानुसार वर्णित किया जा सकता है: ज्ञात सूत्रों को सीधे एन्कोडिंग करने के अलावा, शर्तों के मूल्यों में परिवर्तन का प्रतिनिधित्व करने वाले नए चर भी परिभाषित करते हैं; इन नए चरों को फिर कम किया जाता है।

उदाहरण के लिए, उस डोमेन का जिसमें एक दरवाजा है जो समय 0 पर बंद होता है और जिसमें समय 2 पर दरवाजा खोलने की क्रिया निष्पादित होती है, जिसे स्पष्ट रूप से जाना जाता है वह दो सूत्रों द्वारा दर्शाया जाता है:

फ़्रेम समस्या इस उदाहरण में समस्या के रूप में दिखाई देती है उपरोक्त सूत्रों का परिणाम नहीं है, जबकि द्वार को तब तक बंद रहना चाहिए जब तक कि उसे खोलने की क्रिया न हो जाए। नए वेरिएबल्स को परिभाषित करके सर्कमस्क्रिप्शन का उपयोग इस उद्देश्य के लिए किया जा सकता है परिवर्तनों को मॉडल करने और फिर उन्हें कम करने के लिए:

...

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

ऐसी समस्याओं से पीड़ित नहीं गतिशील डोमेन के कई अन्य औपचारिकताओं को विकसित किया गया है (एक सिंहावलोकन के लिए फ्रेम समस्या देखें)। कई लोग सीमा का उपयोग करते हैं लेकिन एक अलग तरीके से।

विधेय परिधि

मैककार्थी द्वारा प्रस्तावित परिचलन की मूल परिभाषा प्रथम-क्रम तर्क के बारे में है। प्रस्तावपरक तर्क (कुछ ऐसा जो सत्य या असत्य हो सकता है) में चर की भूमिका पहले क्रम के तर्क में विधेय द्वारा निभाई जाती है। अर्थात्, एक तर्कवाक्य सूत्र को पहले क्रम के तर्क में व्यक्त किया जा सकता है, जिसमें प्रत्येक प्रस्तावक चर को शून्य arity के विधेय के साथ प्रतिस्थापित किया जा सकता है (अर्थात, बिना किसी तर्क के विधेय)। इसलिए, परिधि के पहले क्रम के तर्क संस्करण में विधेय पर न्यूनीकरण किया जाता है: जब भी संभव हो, विधेय को गलत होने के लिए एक सूत्र का परिधि प्राप्त किया जाता है।[6] प्रथम-क्रम तर्क सूत्र दिया गया है एक विधेय (तर्क) युक्त , इस विधेय मात्रा का परिसीमन केवल के मॉडल का चयन करने के लिए जिसमें मूल्यों के टुपल्स के न्यूनतम सेट पर सत्य को असाइन किया गया है।

औपचारिक रूप से, प्रथम-क्रम मॉडल में एक विधेय का विस्तार मूल्यों के टुपल्स का सेट है जो मॉडल में सत्य को निर्दिष्ट करता है। प्रथम-क्रम के मॉडल में वास्तव में प्रत्येक विधेय प्रतीक का मूल्यांकन शामिल है; ऐसा मूल्यांकन बताता है कि विधेय अपने तर्कों के किसी भी संभावित मूल्य के लिए सही है या गलत।[7] चूंकि विधेय का प्रत्येक तर्क एक शब्द होना चाहिए, और प्रत्येक शब्द एक मूल्य का मूल्यांकन करता है, मॉडल बताता है कि क्या मानों के किसी भी संभावित टपल के लिए सत्य है . का विस्तार एक मॉडल में शब्दों के टुपल्स का सेट होता है जैसे कि मॉडल में सत्य है।

एक विधेय की परिधि एक सूत्र में के केवल मॉडलों का चयन करके प्राप्त किया जाता है न्यूनतम विस्तार के साथ . उदाहरण के लिए, यदि किसी सूत्र में केवल दो मॉडल हैं, केवल इसलिए भिन्न हैं एक में सत्य और दूसरे में असत्य है, तभी दूसरा प्रतिरूप चुना जाता है। यह है क्योंकि के विस्तार में है पहले मॉडल में लेकिन दूसरे में नहीं।

मैककार्थी द्वारा मूल परिभाषा शब्दार्थ के बजाय वाक्य-विन्यास थी। एक सूत्र दिया और एक विधेय , परिधि में निम्नलिखित द्वितीय क्रम सूत्र है:

इस सूत्र में के रूप में एक ही arity की एक विधेय है . यह एक दूसरे क्रम का सूत्र है क्योंकि इसमें एक विधेय पर मात्रा का ठहराव होता है। उपसूत्र के लिए एक आशुलिपि है:

इस सूत्र में, शब्दों का एक n-tuple है, जहाँ n की arity है . यह सूत्र बताता है कि विस्तार न्यूनीकरण किया जाना है: पर सत्य मूल्यांकन के लिए एक मॉडल पर विचार किया जा रहा है, यह मामला होना चाहिए कि कोई अन्य विधेय नहीं है हर ट्यूपल को झूठा असाइन कर सकता है असत्य को असाइन करता है और फिर भी इससे भिन्न होता है .

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

बिंदुवार सीमारेखा

प्वाइंटवाइज सरकमस्क्रिप्शन, फर्स्ट-ऑर्डर सर्कमस्क्रिप्शन का एक प्रकार है जिसे व्लादिमीर लाइफशिट्ज द्वारा पेश किया गया है।[8] प्रस्तावात्मक मामले में, बिंदुवार और विधेय परिधि मेल खाते हैं। बिंदुवार परिधि का तर्क यह है कि यह विधेय के विस्तार को कम करने के बजाय अलग-अलग मानों के प्रत्येक टपल के लिए एक विधेय के मान को कम करता है। उदाहरण के लिए, के दो मॉडल हैं डोमेन के साथ , एक सेटिंग और दूसरी सेटिंग . के विस्तार के बाद से पहले मॉडल में है जबकि दूसरे का एक्सटेंशन है , परिधि केवल पहले मॉडल का चयन करती है।

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

डोमेन और सूत्र परिवर्णन

मैककार्थी द्वारा परिधि का एक पूर्व सूत्रीकरण विधेय के विस्तार के बजाय प्रथम-क्रम मॉडल के प्रवचन के डोमेन को कम करने पर आधारित है। अर्थात्, एक मॉडल को दूसरे से कम माना जाता है यदि इसका एक छोटा डोमेन है और दो मॉडल मूल्यों के सामान्य टपल्स के मूल्यांकन पर मेल खाते हैं। परिधि के इस संस्करण को विधेय परिधि में घटाया जा सकता है।

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

सिद्धांत पर अंकुश

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

दूसरी ओर, का न्यूनतमकरण विधेय सुराग गलत परिणाम के लिए कि सिक्का या तो काले क्षेत्र पर है या सफेद क्षेत्र पर है, लेकिन दोनों नहीं। ऐसा इसलिए है क्योंकि जिन मॉडलों में पर ही सत्य है और केवल पर का न्यूनतम विस्तार है , जबकि मॉडल जिसमें का विस्तार दोनों जोड़ियों से बना है न्यूनतम नहीं है।

थ्योरी कर्बिंग थॉमस ईटर, जॉर्ज गोटलोब और यूरी गुरेविच द्वारा प्रस्तावित एक समाधान है।[9] विचार यह है कि जिस मॉडल में परिसीमा का चयन करने में विफल रहता है, वह एक जिसमें दोनों और सत्य हैं, सूत्र का एक मॉडल है जो अधिक है (w.r.t. का विस्तार ) चुने गए दोनों मॉडलों की तुलना में। अधिक विशेष रूप से, सूत्र के मॉडलों में, बहिष्कृत मॉडल दो चयनित मॉडलों की सबसे कम ऊपरी सीमा है। थ्योरी कर्बिंग इस तरह के कम से कम ऊपरी सीमा मॉडल का चयन करता है, इसके अलावा परिधि द्वारा चुना जाता है। यह समावेशन तब तक किया जाता है जब तक मॉडल का सेट बंद नहीं हो जाता है, इस अर्थ में कि इसमें मॉडल के सभी सेटों की कम से कम ऊपरी सीमाएं शामिल हैं।

यह भी देखें

संदर्भ

  1. McCarthy, J. (February 1986). "Applications of circumscription to formalizing common-sense knowledge". Artificial Intelligence. 28 (1): 89–116. doi:10.1016/0004-3702(86)90032-9.
  2. McCarthy, J. (April 1980). "Circumscription – A form of non-monotonic reasoning". Artificial Intelligence. 13: 27–39. doi:10.1016/0004-3702(80)90011-9.
  3. Eiter, T.; Gottlob, G. (June 1993). "Propositional circumscription and extended closed world reasoning are \Pi^p_2-complete". Theoretical Computer Science. 114 (2): 231–245. doi:10.1016/0304-3975(93)90073-3.
  4. 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.
  5. Lifschitz, V. (November 1985). "Closed-world databases and circumscription". Artificial Intelligence. 27: 229–235. doi:10.1016/0004-3702(85)90055-4.
  6. Lifschitz, V. (1994). "Circumscription". In Gabbay, D.M.; Hogger, C.J.; Robinson, J.A. Nonmonotonic Reasoning and Uncertain Reasoning. Handbooks of Logic in Computer Science and Artificial Intelligence and Logic Programming. 3. Oxford University Press. pp. 297–352. ISBN 0198537476.
  7. Cadoli, M. (November 1992). "The complexity of model checking for circumscriptive formulae". Information Processing Letters. 44 (3): 113–8. doi:10.1016/0020-0190(92)90049-2.
  8. Lifschitz, V. (1986). "Pointwise circumscription". Proceedings AAAI-86 Fifth National Conference on Artificial Intelligence, August 11-15, 1986, Philadelphia, PA. pp. 406–410. ISBN 0934613133.
  9. 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.


बाहरी संबंध