स्कोलेम सामान्य रूप: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Formalism of first-order logic}} गणितीय तर्क में, प्रथम-क्रम तर्क का एक सुगठि...")
 
 
(12 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Formalism of first-order logic}}
{{Short description|Formalism of first-order logic}}
[[गणितीय तर्क]] में, [[प्रथम-क्रम तर्क]] का एक सुगठित_सूत्र स्कोलेम सामान्य रूप में होता है यदि यह केवल [[सार्वभौमिक परिमाणीकरण]]|सार्वभौमिक प्रथम-क्रम परिमाणकों के साथ [[प्रीनेक्स सामान्य रूप]] में होता है।
[[गणितीय तर्क]] में, [[प्रथम-क्रम तर्क]] का सुगठित सूत्र '''स्कोलेम सामान्य रूप''' में होता है यदि यह केवल [[सार्वभौमिक परिमाणीकरण|सार्वभौमिक प्रथम-क्रम परिमाणकों]] के साथ [[प्रीनेक्स सामान्य रूप]] में होता है।


प्रत्येक प्रथम-क्रम [[सुगठित सूत्र]] को स्कोलेमाइज़ेशन (कभी-कभी स्कोलेमनाइज़ेशन लिखा जाता है) नामक प्रक्रिया के माध्यम से इसकी [[संतुष्टि]] को बदले बिना स्कोलेम सामान्य रूप में परिवर्तित किया जा सकता है। परिणामी सूत्र आवश्यक रूप से मूल सूत्र के साथ [[तार्किक तुल्यता]] नहीं है, लेकिन इसके साथ समतुल्य है: यह तभी संतोषजनक है जब मूल सूत्र संतोषजनक है।<ref>{{cite web|title=सामान्य रूप और स्कोलेमाइज़ेशन|url=http://www.mpi-inf.mpg.de/departments/rg1/teaching/autrea-ss10/script/lecture10.pdf|publisher=max planck institut informatik|accessdate=15 December 2012}}</ref>
प्रत्येक प्रथम-क्रम [[सुगठित सूत्र]] को '''स्कोलेमाइज़ेशन''' (कभी-कभी '''स्कोलेमनाइज़ेशन''' लिखा जाता है) नामक प्रक्रिया के माध्यम से इसकी [[संतुष्टि]] को बदले बिना स्कोलेम सामान्य रूप में परिवर्तित किया जा सकता है। परिणामी सूत्र आवश्यक रूप से मूल सूत्र के साथ [[तार्किक तुल्यता]] नहीं है, किन्तु इसके साथ समतुल्य है: यह तभी संतोषजनक है जब मूल सूत्र संतोषजनक है।<ref>{{cite web|title=सामान्य रूप और स्कोलेमाइज़ेशन|url=http://www.mpi-inf.mpg.de/departments/rg1/teaching/autrea-ss10/script/lecture10.pdf|publisher=max planck institut informatik|accessdate=15 December 2012}}</ref>
स्कोलेम सामान्य रूप में कमी [[औपचारिक तर्क]] कथनों से [[अस्तित्वगत परिमाणीकरण]] को हटाने की एक विधि है, जिसे अक्सर [[स्वचालित प्रमेय कहावत]] में पहले चरण के रूप में निष्पादित किया जाता है।
 
स्कोलेम सामान्य रूप में कमी [[औपचारिक तर्क]] कथनों से [[अस्तित्वगत परिमाणीकरण|अस्तित्व संबंधी परिमाणकों]] को हटाने की एक विधि है, जिसे अधिकांश [[स्वचालित प्रमेय कहावत|स्वचालित प्रमेय लोकोक्ति]] में पहले वेरिएबलण के रूप में निष्पादित किया जाता है।


== उदाहरण ==
== उदाहरण ==


स्कोलेमाइज़ेशन का सबसे सरल रूप अस्तित्वगत रूप से परिमाणित चर के लिए है जो एक सार्वभौमिक परिमाणक के दायरे (तर्क) के अंदर नहीं हैं। इन्हें केवल नए स्थिरांक बनाकर प्रतिस्थापित किया जा सकता है। उदाहरण के लिए, <math>\exists x P(x)</math> में बदला जा सकता है <math>P(c)</math>, कहाँ <math>c</math> एक नया स्थिरांक है (सूत्र में कहीं और नहीं होता है)
स्कोलेमाइज़ेशन का सबसे सरल रूप अस्तित्वगत रूप से परिमाणित वेरिएबल के लिए है जो सार्वभौमिक परिमाणक के सीमा (तर्क) के अंदर नहीं हैं। इन्हें केवल नए स्थिरांक बनाकर प्रतिस्थापित किया जा सकता है। उदाहरण के लिए, <math>\exists x P(x)</math> को <math>P(c)</math> में बदला जा सकता है, जहाँ <math>c</math> नया स्थिरांक (सूत्र में कहीं और नहीं होता है) है।


अधिक सामान्यतः, स्कोलेमाइज़ेशन प्रत्येक अस्तित्वगत परिमाणित चर को प्रतिस्थापित करके किया जाता है <math>y</math> एक शब्द के साथ <math>f(x_1,\ldots,x_n)</math> जिसका कार्य चिह्न <math>f</math> नया है। इस पद के चर इस प्रकार हैं. यदि सूत्र प्रीनेक्स सामान्य रूप में है, तो <math>x_1,\ldots,x_n</math> वे चर हैं जो सार्वभौमिक रूप से परिमाणित हैं और जिनके परिमाणक उससे पहले हैं <math>y</math>. सामान्य तौर पर, वे ऐसे चर होते हैं जिन्हें सार्वभौमिक रूप से परिमाणित किया जाता है (हम मानते हैं कि हम क्रम में अस्तित्व संबंधी परिमाणकों से छुटकारा पा लेते हैं, इसलिए पहले सभी अस्तित्वगत परिमाणकों <math>\exists y</math> हटा दिए गए हैं) और ऐसे <math>\exists y</math> उनके परिमाणकों के दायरे में होता है। कार्यक्रम <math>f</math> इस प्रक्रिया में पेश किए गए को स्कोलेम फ़ंक्शन कहा जाता है (या स्कोलेम स्थिरांक यदि यह शून्य एरिटी का है) और शब्द को स्कोलेम शब्द कहा जाता है।
सामान्यतः, स्कोलेमाइज़ेशन प्रत्येक अस्तित्वगत रूप से परिमाणित वेरिएबल <math>y</math> को एक शब्द <math>f(x_1,\ldots,x_n)</math> के साथ प्रतिस्थापित करके किया जाता है जिसका फ़ंक्शन प्रतीक <math>f</math> नया है। इस पद के वेरिएबल इस प्रकार है। यदि सूत्र प्रीनेक्स सामान्य रूप में है, तो <math>x_1,\ldots,x_n</math> वे वेरिएबल हैं जो सार्वभौमिक रूप से परिमाणित हैं और जिनके परिमाणक <math>y</math> से पहले हैं। सामान्यतः, वे ऐसे वेरिएबल होते हैं जिन्हें सार्वभौमिक रूप से परिमाणित (हम मानते हैं कि हमें क्रम में अस्तित्वगत परिमाणकों से छुटकारा मिल गया है, इसलिए <math>\exists y</math> से पहले के सभी अस्तित्वगत परिमाणकों को हटा दिया गया है) किया जाता है और जैसे कि <math>\exists y</math> उनके परिमाणकों के सीमा में होता है। इस प्रक्रिया में प्रस्तुत किए गए फ़ंक्शन <math>f</math> को स्कोलेम फ़ंक्शन (या स्कोलेम स्थिरांक यदि यह शून्य एरिटी का है) कहा जाता है और शब्द को स्कोलेम शब्द कहा जाता है।
उदाहरण के तौर पर सूत्र <math>\forall x \exists y \forall z. P(x,y,z)</math> स्कोलेम सामान्य रूप में नहीं है क्योंकि इसमें अस्तित्वगत परिमाणक शामिल है <math>\exists y</math>. स्कोलेमाइजेशन प्रतिस्थापित करता है <math>y</math> साथ <math>f(x)</math>, कहाँ <math>f</math> एक नया फ़ंक्शन प्रतीक है, और परिमाणीकरण को हटा देता है {{nowrap|<math>y</math>.}} परिणामी सूत्र है <math>\forall x \forall z . P(x,f(x),z)</math>. स्कोलेम शब्द <math>f(x)</math> रोकना <math>x</math>, लेकिन नहीं <math>z</math>, क्योंकि क्वांटिफायर को हटाया जाना है <math>\exists y</math> के दायरे में है <math>\forall x</math>, लेकिन उसमें नहीं <math>\forall z</math>; चूँकि यह सूत्र प्रीनेक्स सामान्य रूप में है, यह कहने के बराबर है कि, परिमाणकों की सूची में, <math>x</math> पछाड़ <math>y</math> जबकि <math>z</math> नहीं करता। इस परिवर्तन द्वारा प्राप्त सूत्र तभी संतोषजनक है जब मूल सूत्र हो।


उदाहरण के तौर पर सूत्र <math>\forall x \exists y \forall z. P(x,y,z)</math> स्कोलेम सामान्य रूप में नहीं है क्योंकि इसमें अस्तित्वगत परिमाणक <math>\exists y</math> सम्मिलित है। स्कोलेमाइज़ेशन <math>y</math> को <math>f(x)</math> से प्रतिस्थापित करता है, जहाँ <math>f</math> एक नया फ़ंक्शन प्रतीक है, और {{nowrap|<math>y</math>.}} पर परिमाणीकरण को हटा देता है। परिणामी सूत्र <math>\forall x \forall z . P(x,f(x),z)</math> है। स्कोलेम शब्द <math>f(x)</math> में <math>x</math> सम्मिलित है, किन्तु <math>z</math> नहीं, क्योंकि हटाया जाने वाला क्वांटिफायर <math>\exists y</math> <math>\forall x</math> के सीमा में है, किन्तु <math>\forall z</math> के सीमा में नहीं है; चूँकि यह सूत्र प्रीनेक्स सामान्य रूप में है, यह कहने के बराबर है कि, क्वांटिफायर की सूची में, <math>x</math>, <math>y</math> से पहले आता है जबकि <math>z</math> नहीं। इस परिवर्तन द्वारा प्राप्त सूत्र तभी संतोषजनक है जब मूल सूत्र हो।
==स्कोलेमाइज़ेशन कैसे काम करता है==
==स्कोलेमाइज़ेशन कैसे काम करता है==


स्कोलेमाइज़ेशन प्रथम-क्रम संतुष्टि की परिभाषा के साथ दूसरे-क्रम तर्क|दूसरे-क्रम तुल्यता को लागू करके काम करता है। तुल्यता एक अस्तित्वगत परिमाणक को सार्वभौमिक परिमाणक से पहले ले जाने का एक तरीका प्रदान करती है।
स्कोलेमाइज़ेशन प्रथम-क्रम संतुष्टि की परिभाषा के साथ-साथ दूसरे-क्रम तुल्यता को लागू करके काम करता है। तुल्यता एक सार्वभौमिक परिमाणक से पहले एक अस्तित्वगत परिमाणक को "स्थानांतरित" करने का एक विधि प्रदान करती है।


:<math>\forall x  \exists y  R(x,y)  \iff \exists f \forall x  R(x,f(x)) </math>
:<math>\forall x  \exists y  R(x,y)  \iff \exists f \forall x  R(x,f(x)) </math>
कहाँ
जहाँ
:<math>f(x)</math> एक फ़ंक्शन है जो मैप करता है <math>x</math> को <math>y</math>.
:<math>f(x)</math> एक फ़ंक्शन है जो <math>x</math> को <math>y</math> पर मैप करता है।


सहज रूप से, प्रत्येक के लिए वाक्य <math>x</math> वहाँ एक मौजूद है <math>y</math> ऐसा है कि <math>R(x,y)</math>समतुल्य रूप में परिवर्तित होने पर वहां एक फ़ंक्शन मौजूद होता है <math>f</math> हर मैपिंग <math>x</math> में <math>y</math> ऐसा कि, हर किसी के लिए <math>x</math> उसके पास होता है <math>R(x,f(x))</math>.
सहज रूप से, वाक्य "प्रत्येक <math>x</math> के लिए एक <math>y</math> उपस्थित होता है जैसे कि <math>R(x,y)</math>" को समतुल्य रूप में परिवर्तित किया जाता है "प्रत्येक <math>x</math> को <math>y</math> में मैप करने वाला एक फ़ंक्शन <math>f</math> उपस्थित होता है जैसे कि प्रत्येक <math>x</math> के लिए यह <math>R(x,f(x))</math> रखता है"।


यह तुल्यता उपयोगी है क्योंकि प्रथम-क्रम संतुष्टि की परिभाषा अंतर्निहित रूप से फ़ंक्शन प्रतीकों के मूल्यांकन पर परिमाण निर्धारित करती है। विशेष रूप से, प्रथम-क्रम सूत्र <math>\Phi</math> यदि कोई मॉडल मौजूद है तो यह संतोषजनक है <math>M</math> और एक मूल्यांकन <math>\mu</math> सूत्र के मुक्त चर जो सूत्र का सही मूल्यांकन करते हैं। मॉडल में सभी फ़ंक्शन प्रतीकों का मूल्यांकन शामिल है; इसलिए, स्कोलेम फ़ंक्शन अंतर्निहित रूप से अस्तित्वगत रूप से परिमाणित हैं। उपरोक्त उदाहरण में, <math>\forall x . R(x,f(x))</math> यह तभी संतोषजनक है जब कोई मॉडल मौजूद हो <math>M</math>, जिसमें एक मूल्यांकन शामिल है <math>f</math>, ऐसा है कि <math>\forall x . R(x,f(x))</math> इसके मुक्त चर के कुछ मूल्यांकन के लिए सत्य है (इस मामले में कोई नहीं)इसे दूसरे क्रम में इस प्रकार व्यक्त किया जा सकता है <math>\exists f \forall x . R(x,f(x))</math>. उपरोक्त तुल्यता से, यह की संतुष्टि के समान है <math>\forall x \exists y . R(x,y)</math>.
यह तुल्यता उपयोगी है क्योंकि प्रथम-क्रम संतुष्टि की परिभाषा अंतर्निहित रूप से फ़ंक्शन प्रतीकों के मूल्यांकन पर परिमाण निर्धारित करती है। विशेष रूप से, प्रथम-क्रम सूत्र <math>\Phi</math> संतोषजनक है यदि कोई मॉडल <math>M</math> उपस्थित है और सूत्र के मुक्त वेरिएबल का मूल्यांकन <math>\mu</math> है जो सूत्र का सही मूल्यांकन करता है। मॉडल में सभी फ़ंक्शन प्रतीकों का मूल्यांकन सम्मिलित है; इसलिए, स्कोलेम फ़ंक्शन अंतर्निहित रूप से अस्तित्वगत रूप से परिमाणित हैं। उपरोक्त उदाहरण में, <math>\forall x . R(x,f(x))</math> यह तभी संतोषजनक है जब कोई मॉडल <math>M</math> उपस्थित हो, जिसमें <math>f</math> के लिए मूल्यांकन सम्मिलित हो, जैसे कि <math>\forall x . R(x,f(x))</math> अपने मुक्त वेरिएबल (इस स्थिति में कोई नहीं) के कुछ मूल्यांकन के लिए सही है। इसे दूसरे क्रम में <math>\exists f \forall x . R(x,f(x))</math> के रूप में व्यक्त किया जा सकता है। उपरोक्त तुल्यता के अनुसार, यह <math>\forall x \exists y . R(x,y)</math> की संतुष्टि के समान है।


मेटा-स्तर पर, प्रथम-क्रम तर्क#शब्दार्थ|किसी सूत्र की प्रथम-क्रम संतुष्टि <math>\Phi</math> संकेतन के थोड़े दुरुपयोग के साथ लिखा जा सकता है <math>\exists M \exists \mu ~.~ ( M,\mu \models \Phi)</math>, कहाँ <math>M</math> एक मॉडल है, <math>\mu</math> मुक्त चर का मूल्यांकन है, और <math>\models</math> मतलब कि <math>\Phi</math> में सच है <math>M</math> अंतर्गत <math>\mu</math>. चूँकि प्रथम-क्रम मॉडल में सभी फ़ंक्शन प्रतीकों का मूल्यांकन होता है, कोई भी स्कोलेम फ़ंक्शन <math>\Phi</math> इसमें निहित रूप से अस्तित्वगत रूप से परिमाणित किया गया है <math>\exists M</math>. परिणामस्वरूप, सूत्र के सामने के कार्यों पर अस्तित्वगत परिमाणकों को चर के स्थान पर अस्तित्वगत परिमाणकों से बदलने के बाद, इन अस्तित्वगत परिमाणकों को हटाकर सूत्र को अभी भी प्रथम-क्रम वाले के रूप में माना जा सकता है। इलाज का यह अंतिम चरण <math>\exists f \forall x . R(x,f(x))</math> जैसा <math>\forall x . R(x,f(x))</math> पूरा किया जा सकता है क्योंकि कार्यों को अंतर्निहित रूप से अस्तित्वगत रूप से परिमाणित किया जाता है <math>\exists M</math> प्रथम-क्रम संतुष्टि की परिभाषा में।
मेटा-स्तर पर, सूत्र <math>\Phi</math> की प्रथम-क्रम संतुष्टि को <math>\exists M \exists \mu ~.~ ( M,\mu \models \Phi)</math> के रूप में अंकन के थोड़े दुरुपयोग के साथ लिखा जा सकता है। जहां <math>M</math> एक मॉडल है, <math>\mu</math> मुक्त वेरिएबल का मूल्यांकन है, और <math>\models</math> का अर्थ है कि <math>\mu</math> के अनुसार <math>M</math> में <math>\Phi</math> सत्य है। चूँकि प्रथम-क्रम मॉडल में सभी फ़ंक्शन प्रतीकों का मूल्यांकन होता है, कोई भी स्कोलेम फ़ंक्शन जिसमें <math>\Phi</math> सम्मिलित होता है, उसे अंतर्निहित रूप से <math>\exists M</math> द्वारा परिमाणित किया जाता है। परिणामस्वरूप, सूत्र के सामने के कार्यों पर अस्तित्वगत परिमाणकों को वेरिएबल के स्थान पर अस्तित्वगत परिमाणकों से प्रतिस्थापित करने के बाद भी इन अस्तित्वगत परिमाणकों को हटाकर सूत्र को प्रथम-क्रम वाले परिमाणकों के रूप में माना जा सकता है। <math>\exists f \forall x . R(x,f(x))</math> को <math>\forall x . R(x,f(x))</math> मानने का यह अंतिम चरण पूरा किया जा सकता है क्योंकि प्रथम-क्रम संतुष्टि की परिभाषा में कार्यों को अंतर्निहित रूप से <math>\exists M</math> द्वारा परिमाणित किया गया है।


स्कोलेमाइज़ेशन की शुद्धता को उदाहरण सूत्र पर दिखाया जा सकता है <math>F_1 = \forall x_1 \dots \forall x_n \exists y R(x_1,\dots,x_n,y)</math> निम्नलिखित नुसार। यह सूत्र मॉडल_सिद्धांत#प्रथम-क्रम_तर्क से संतुष्ट है <math>M</math> यदि और केवल यदि, के लिए प्रत्येक संभावित मान के लिए <math>x_1,\dots,x_n</math> मॉडल के डोमेन में, के लिए एक मान मौजूद है <math>y</math> उस मॉडल के क्षेत्र में जो बनाता है <math>R(x_1,\dots,x_n,y)</math> सत्य। पसंद के सिद्धांत के अनुसार, एक फ़ंक्शन मौजूद है <math>f</math> ऐसा है कि <math>y = f(x_1,\dots,x_n)</math>. परिणामस्वरूप, सूत्र <math>F_2 = \forall x_1 \dots \forall x_n R(x_1,\dots,x_n,f(x_1,\dots,x_n))</math> संतोषजनक है, क्योंकि इसमें मूल्यांकन जोड़कर प्राप्त मॉडल है <math>f</math> को <math>M</math>. इससे पता चलता है कि <math>F_1</math> तभी संतुष्ट है जब <math>F_2</math> संतोषजनक भी है. इसके विपरीत, यदि <math>F_2</math> संतोषजनक है, तो एक मॉडल मौजूद है <math>M'</math> जो उसे संतुष्ट करता है; इस मॉडल में फ़ंक्शन के लिए मूल्यांकन शामिल है <math>f</math> ऐसा कि, के हर मूल्य के लिए <math>x_1,\dots,x_n</math>, सूत्र <math>R(x_1,\dots,x_n,f(x_1,\dots,x_n))</math> धारण करता है. नतीजतन, <math>F_1</math> एक ही मॉडल से संतुष्ट है क्योंकि कोई भी प्रत्येक मूल्य के लिए चुन सकता है <math>x_1,\ldots,x_n</math>, मूल्य <math>y=f(x_1,\dots,x_n)</math>, कहाँ <math>f</math> के अनुसार मूल्यांकन किया जाता है <math>M'</math>.
स्कोलेमाइज़ेशन की शुद्धता को उदाहरण सूत्र <math>F_1 = \forall x_1 \dots \forall x_n \exists y R(x_1,\dots,x_n,y)</math> पर निम्नानुसार दिखाया जा सकता है। यह सूत्र मॉडल <math>M</math> द्वारा संतुष्ट है यदि और केवल तभी, मॉडल के डोमेन में <math>x_1,\dots,x_n</math> के लिए प्रत्येक संभावित मान के लिए, मॉडल के डोमेन में <math>y</math> के लिए एक मान उपस्थित है जो <math>R(x_1,\dots,x_n,y)</math> को सत्य बनाता है। पसंद के सिद्धांत के अनुसार, एक फ़ंक्शन <math>f</math> उपस्थित है जैसे कि <math>y = f(x_1,\dots,x_n)</math>परिणामस्वरूप, सूत्र <math>F_2 = \forall x_1 \dots \forall x_n R(x_1,\dots,x_n,f(x_1,\dots,x_n))</math> संतोषजनक है, क्योंकि इसमें <math>f</math> से <math>M</math> के मूल्यांकन को जोड़कर प्राप्त मॉडल है। इससे पता चलता है कि <math>F_1</math> केवल संतोषजनक है यदि <math>F_2</math> भी संतोषजनक है। इसके विपरीत, यदि <math>F_2</math> संतोषजनक है, तो एक मॉडल <math>M'</math> उपस्थित है जो इसे संतुष्ट करता है; इस मॉडल में फ़ंक्शन <math>f</math> के लिए एक मूल्यांकन सम्मिलित है, इस प्रकार, <math>x_1,\dots,x_n</math> के प्रत्येक मान के लिए सूत्र <math>R(x_1,\dots,x_n,f(x_1,\dots,x_n))</math> धारण करता है। परिणामस्वरूप, <math>F_1</math> उसी मॉडल से संतुष्ट है क्योंकि कोई <math>x_1,\ldots,x_n</math> के प्रत्येक मान के लिए, मान <math>y=f(x_1,\dots,x_n)</math> चुन सकता है, जहां <math>f</math> का मूल्यांकन <math>M'</math> के अनुसार किया जाता है।


==स्कोलेमाइज़ेशन के उपयोग==
==स्कोलेमाइज़ेशन के उपयोग==
स्कोलेमाइज़ेशन के उपयोगों में से एक [[स्वचालित प्रमेय सिद्ध करना]] है। उदाहरण के लिए, [[विश्लेषणात्मक झांकी की विधि]] में, जब भी कोई सूत्र जिसका प्रमुख परिमाणक अस्तित्वगत होता है, तो स्कोलेमाइजेशन के माध्यम से उस परिमाणक को हटाकर प्राप्त सूत्र उत्पन्न किया जा सकता है। उदाहरण के लिए, यदि <math>\exists x . \Phi(x,y_1,\ldots,y_n)</math> एक झांकी में होता है, जहां <math>x,y_1,\ldots,y_n</math> के मुक्त चर हैं <math>\Phi(x,y_1,\ldots,y_n)</math>, तब <math>\Phi(f(y_1,\ldots,y_n),y_1,\ldots,y_n)</math> झांकी की उसी शाखा में जोड़ा जा सकता है। यह जोड़ झांकी की संतुष्टि में कोई बदलाव नहीं करता है: पुराने फॉर्मूले के प्रत्येक मॉडल को उपयुक्त मूल्यांकन जोड़कर बढ़ाया जा सकता है <math>f</math>, नए फॉर्मूले के एक मॉडल के लिए।
स्कोलेमाइज़ेशन के उपयोगों में से [[स्वचालित प्रमेय सिद्ध करना]] है। उदाहरण के लिए, [[विश्लेषणात्मक झांकी की विधि|विश्लेषणात्मक टेबल्यू की विधि]] में, जब भी कोई सूत्र जिसका प्रमुख परिमाणक अस्तित्वगत होता है, तो स्कोलेमाइजेशन के माध्यम से उस परिमाणक को हटाकर प्राप्त सूत्र उत्पन्न किया जा सकता है। उदाहरण के लिए, यदि <math>\exists x . \Phi(x,y_1,\ldots,y_n)</math> एक टेबल्यू में होता है, जहां <math>x,y_1,\ldots,y_n</math> <math>\Phi(x,y_1,\ldots,y_n)</math> के मुक्त वेरिएबल हैं तो <math>\Phi(f(y_1,\ldots,y_n),y_1,\ldots,y_n)</math> टेबल्यू की उसी शाखा में जोड़ा जा सकता है। यह जोड़ टेबल्यू के गुण में कोई बदलाव नहीं करता है: पुराने सूत्र के प्रत्येक मॉडल को नए सूत्र के मॉडल में <math>f</math> का उपयुक्त मूल्यांकन जोड़कर बढ़ाया जा सकता है।


स्कोलेमाइजेशन का यह रूप शास्त्रीय स्कोलेमाइजेशन की तुलना में एक सुधार है, जिसमें केवल वेरिएबल जो सूत्र में मुक्त हैं, उन्हें स्कोलेम शब्द में रखा गया है। यह एक सुधार है क्योंकि झांकी के शब्दार्थ सूत्र को कुछ सार्वभौमिक रूप से परिमाणित चर के दायरे (प्रोग्रामिंग) में अंतर्निहित रूप से रख सकते हैं जो सूत्र में ही नहीं हैं; ये चर स्कोलेम शब्द में नहीं हैं, जबकि वे स्कोलेमाइज़ेशन की मूल परिभाषा के अनुसार होंगे। एक और सुधार जिसका उपयोग किया जा सकता है वह उन सूत्रों के लिए समान स्कोलेम फ़ंक्शन प्रतीक को लागू करना है जो परिवर्तनीय नामकरण [[तक]] समान हैं।<ref>R. Hähnle. Tableaux and related methods. [[Handbook of Automated Reasoning]].</ref>
स्कोलेमाइजेशन का यह रूप "पारंपरिक" स्कोलेमाइजेशन की तुलना में एक सुधार है, जिसमें केवल वेरिएबल जो सूत्र में मुक्त हैं, उन्हें स्कोलेम शब्द में रखा गया है। यह एक सुधार है क्योंकि टेबल्यू के शब्दार्थ सूत्र को कुछ सार्वभौमिक रूप से परिमाणित वेरिएबल के सीमा में रख सकते हैं जो सूत्र में ही नहीं हैं; ये वेरिएबल स्कोलेम शब्द में नहीं हैं, जबकि वे स्कोलेमाइज़ेशन की मूल परिभाषा के अनुसार होंगे। एक और सुधार जिसका उपयोग किया जा सकता है वह उन सूत्रों के लिए समान स्कोलेम फ़ंक्शन प्रतीक को लागू करना है जो परिवर्तनीय नामकरण [[तक]] समान हैं।<ref>R. Hähnle. Tableaux and related methods. [[Handbook of Automated Reasoning]].</ref>
एक अन्य उपयोग प्रथम-क्रम तर्क के लिए Resolution_(logic)#Resolution_in_first_order_logic|resolution विधि में है, जहां सूत्रों को सार्वभौमिक रूप से परिमाणित समझे जाने वाले [[खंड (तर्क)]] के सेट के रूप में दर्शाया जाता है। (उदाहरण के लिए [[पीने वाला विरोधाभास]] देखें।)


मॉडल सिद्धांत में एक महत्वपूर्ण परिणाम लोवेनहेम-स्कोलेम प्रमेय है, जिसे सिद्धांत को स्कोलेमाइज़ करके और परिणामी स्कोलेम कार्यों के तहत बंद करके सिद्ध किया जा सकता है।<ref>S. Weinstein, [http://ozark.hendrix.edu/~yorgey/settheory/11-lowenheim-skolem.pdf The Lowenheim-Skolem Theorem], lecture notes (2009). Accessed 6 January 2023.</ref>
एक अन्य उपयोग प्रथम-क्रम तर्क के लिए रिज़ॉल्यूशन विधि में है, जहां सूत्रों को सार्वभौमिक रूप से परिमाणित समझे जाने वाले [[खंड (तर्क)|खंडों (तर्क)]] के सेट के रूप में दर्शाया जाता है। (उदाहरण के लिए [[पीने वाला विरोधाभास|ड्रिंकर पैराडॉक्स]] देखें।)
 
मॉडल सिद्धांत में महत्वपूर्ण परिणाम लोवेनहेम-स्कोलेम प्रमेय है, जिसे सिद्धांत को स्कोलेमाइज़ करके और परिणामी स्कोलेम कार्यों के अनुसार बंद करके सिद्ध किया जा सकता है।<ref>S. Weinstein, [http://ozark.hendrix.edu/~yorgey/settheory/11-lowenheim-skolem.pdf The Lowenheim-Skolem Theorem], lecture notes (2009). Accessed 6 January 2023.</ref>




==स्कोलेम सिद्धांत==
==स्कोलेम सिद्धांत==
सामान्य तौर पर, यदि <math>T</math> एक [[सिद्धांत (गणितीय तर्क)]] है और प्रत्येक सूत्र के लिए [[मुक्त चर]] हैं <math>x_1, \dots, x_n, y</math> एक फ़ंक्शन प्रतीक है <math>F</math> यह संभवतः एक स्कोलेम फ़ंक्शन है <math>y</math>, तब <math>T</math> स्कोलेम सिद्धांत कहा जाता है।<ref>[http://www.math.uu.nl/people/jvoosten/syllabi/logicasyllmoeder.pdf "Sets, Models and Proofs" (3.3) by I. Moerdijk and J. van Oosten]</ref>
सामान्यतः, यदि <math>T</math> [[सिद्धांत (गणितीय तर्क)]] है और [[मुक्त चर|मुक्त]] वेरिएबल <math>x_1, \dots, x_n, y</math>, वाले प्रत्येक सूत्र के लिए एक फ़ंक्शन प्रतीक <math>F</math> है जो कि <math>y</math> के लिए एक स्कोलेम फ़ंक्शन है, तब <math>T</math> को स्कोलेम सिद्धांत कहा जाता है।<ref>[http://www.math.uu.nl/people/jvoosten/syllabi/logicasyllmoeder.pdf "Sets, Models and Proofs" (3.3) by I. Moerdijk and J. van Oosten]</ref>
प्रत्येक स्कोलेम सिद्धांत [[मॉडल पूर्ण सिद्धांत]] है, अर्थात मॉडल की प्रत्येक [[उपसंरचना (गणित)]] एक प्रारंभिक तुल्यता है। स्कोलेम सिद्धांत टी के एक मॉडल एम को देखते हुए, एक निश्चित सेट वाले सबसे छोटे उपसंरचना को का 'स्कोलेम हल' कहा जाता है। का स्कोलेम हल ए के ऊपर एक [[परमाणु मॉडल (गणितीय तर्क)]] [[प्रमुख मॉडल]] है।
 
प्रत्येक स्कोलेम सिद्धांत [[मॉडल पूर्ण सिद्धांत]] है, अर्थात मॉडल की प्रत्येक [[उपसंरचना (गणित)]] प्रारंभिक तुल्यता है। स्कोलेम सिद्धांत T के मॉडल M को देखते हुए, निश्चित सेट A वाले सबसे छोटे उपसंरचना को A का 'स्कोलेम समाधान' कहा जाता है। A का स्कोलेम समाधान A के ऊपर [[परमाणु मॉडल (गणितीय तर्क)]] [[प्रमुख मॉडल]] है।


== इतिहास ==
== इतिहास ==
स्कोलेम सामान्य रूप का नाम दिवंगत नॉर्वेजियन गणितज्ञ [[ थोरल्फ़ स्कोलेम ]] के नाम पर रखा गया है।
स्कोलेम सामान्य रूप का नाम दिवंगत नॉर्वेजियन गणितज्ञ [[ थोरल्फ़ स्कोलेम |थोरल्फ़ स्कोलेम]] के नाम पर रखा गया है।


==यह भी देखें==
==यह भी देखें==
Line 63: Line 65:
* {{MathWorld |title=SkolemizedForm |urlname=SkolemizedForm}}
* {{MathWorld |title=SkolemizedForm |urlname=SkolemizedForm}}


{{DEFAULTSORT:Skolem Normal Form}}[[Category: सामान्य रूप (तर्क)]] [[Category: मॉडल सिद्धांत]]
{{DEFAULTSORT:Skolem Normal Form}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 07/07/2023|Skolem Normal Form]]
[[Category:Created On 07/07/2023]]
[[Category:Lua-based templates|Skolem Normal Form]]
[[Category:Machine Translated Page|Skolem Normal Form]]
[[Category:Pages with maths render errors|Skolem Normal Form]]
[[Category:Pages with script errors|Skolem Normal Form]]
[[Category:Templates Vigyan Ready|Skolem Normal Form]]
[[Category:Templates that add a tracking category|Skolem Normal Form]]
[[Category:Templates that generate short descriptions|Skolem Normal Form]]
[[Category:Templates using TemplateData|Skolem Normal Form]]
[[Category:मॉडल सिद्धांत|Skolem Normal Form]]
[[Category:सामान्य रूप (तर्क)|Skolem Normal Form]]

Latest revision as of 16:48, 12 September 2023

गणितीय तर्क में, प्रथम-क्रम तर्क का सुगठित सूत्र स्कोलेम सामान्य रूप में होता है यदि यह केवल सार्वभौमिक प्रथम-क्रम परिमाणकों के साथ प्रीनेक्स सामान्य रूप में होता है।

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

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

उदाहरण

स्कोलेमाइज़ेशन का सबसे सरल रूप अस्तित्वगत रूप से परिमाणित वेरिएबल के लिए है जो सार्वभौमिक परिमाणक के सीमा (तर्क) के अंदर नहीं हैं। इन्हें केवल नए स्थिरांक बनाकर प्रतिस्थापित किया जा सकता है। उदाहरण के लिए, को में बदला जा सकता है, जहाँ नया स्थिरांक (सूत्र में कहीं और नहीं होता है) है।

सामान्यतः, स्कोलेमाइज़ेशन प्रत्येक अस्तित्वगत रूप से परिमाणित वेरिएबल को एक शब्द के साथ प्रतिस्थापित करके किया जाता है जिसका फ़ंक्शन प्रतीक नया है। इस पद के वेरिएबल इस प्रकार है। यदि सूत्र प्रीनेक्स सामान्य रूप में है, तो वे वेरिएबल हैं जो सार्वभौमिक रूप से परिमाणित हैं और जिनके परिमाणक से पहले हैं। सामान्यतः, वे ऐसे वेरिएबल होते हैं जिन्हें सार्वभौमिक रूप से परिमाणित (हम मानते हैं कि हमें क्रम में अस्तित्वगत परिमाणकों से छुटकारा मिल गया है, इसलिए से पहले के सभी अस्तित्वगत परिमाणकों को हटा दिया गया है) किया जाता है और जैसे कि उनके परिमाणकों के सीमा में होता है। इस प्रक्रिया में प्रस्तुत किए गए फ़ंक्शन को स्कोलेम फ़ंक्शन (या स्कोलेम स्थिरांक यदि यह शून्य एरिटी का है) कहा जाता है और शब्द को स्कोलेम शब्द कहा जाता है।

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

स्कोलेमाइज़ेशन कैसे काम करता है

स्कोलेमाइज़ेशन प्रथम-क्रम संतुष्टि की परिभाषा के साथ-साथ दूसरे-क्रम तुल्यता को लागू करके काम करता है। तुल्यता एक सार्वभौमिक परिमाणक से पहले एक अस्तित्वगत परिमाणक को "स्थानांतरित" करने का एक विधि प्रदान करती है।

जहाँ

एक फ़ंक्शन है जो को पर मैप करता है।

सहज रूप से, वाक्य "प्रत्येक के लिए एक उपस्थित होता है जैसे कि " को समतुल्य रूप में परिवर्तित किया जाता है "प्रत्येक को में मैप करने वाला एक फ़ंक्शन उपस्थित होता है जैसे कि प्रत्येक के लिए यह रखता है"।

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

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

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

स्कोलेमाइज़ेशन के उपयोग

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

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

एक अन्य उपयोग प्रथम-क्रम तर्क के लिए रिज़ॉल्यूशन विधि में है, जहां सूत्रों को सार्वभौमिक रूप से परिमाणित समझे जाने वाले खंडों (तर्क) के सेट के रूप में दर्शाया जाता है। (उदाहरण के लिए ड्रिंकर पैराडॉक्स देखें।)

मॉडल सिद्धांत में महत्वपूर्ण परिणाम लोवेनहेम-स्कोलेम प्रमेय है, जिसे सिद्धांत को स्कोलेमाइज़ करके और परिणामी स्कोलेम कार्यों के अनुसार बंद करके सिद्ध किया जा सकता है।[3]


स्कोलेम सिद्धांत

सामान्यतः, यदि सिद्धांत (गणितीय तर्क) है और मुक्त वेरिएबल , वाले प्रत्येक सूत्र के लिए एक फ़ंक्शन प्रतीक है जो कि के लिए एक स्कोलेम फ़ंक्शन है, तब को स्कोलेम सिद्धांत कहा जाता है।[4]

प्रत्येक स्कोलेम सिद्धांत मॉडल पूर्ण सिद्धांत है, अर्थात मॉडल की प्रत्येक उपसंरचना (गणित) प्रारंभिक तुल्यता है। स्कोलेम सिद्धांत T के मॉडल M को देखते हुए, निश्चित सेट A वाले सबसे छोटे उपसंरचना को A का 'स्कोलेम समाधान' कहा जाता है। A का स्कोलेम समाधान A के ऊपर परमाणु मॉडल (गणितीय तर्क) प्रमुख मॉडल है।

इतिहास

स्कोलेम सामान्य रूप का नाम दिवंगत नॉर्वेजियन गणितज्ञ थोरल्फ़ स्कोलेम के नाम पर रखा गया है।

यह भी देखें

टिप्पणियाँ

  1. "सामान्य रूप और स्कोलेमाइज़ेशन" (PDF). max planck institut informatik. Retrieved 15 December 2012.
  2. R. Hähnle. Tableaux and related methods. Handbook of Automated Reasoning.
  3. S. Weinstein, The Lowenheim-Skolem Theorem, lecture notes (2009). Accessed 6 January 2023.
  4. "Sets, Models and Proofs" (3.3) by I. Moerdijk and J. van Oosten


संदर्भ


बाहरी संबंध