प्रीनेक्स सामान्य रूप

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

मौलिक तर्क में प्रत्येक सूत्र तार्किक रूप से प्रीनेक्स सामान्य रूप में सूत्र के सामान्तर है। उदाहरण के लिए, यदि $\phi (y)$, $\psi (z)$, और $\rho (x)$ तब दिखाए गए मुक्त चर के साथ क्वांटिफायर-मुक्त सूत्र हैं

$\forall x\exists y\forall z(\phi (y)\lor (\psi (z)\rightarrow \rho (x)))$

आव्युह के साथ प्रीनेक्स सामान्य रूप में है $\phi (y)\lor (\psi (z)\rightarrow \rho (x))$, जबकि

$\forall x((\exists y\phi (y))\lor ((\exists z\psi (z))\rightarrow \rho (x)))$

तार्किक रूप से समतुल्य है किन्तु प्रीनेक्स सामान्य रूप में नहीं।

प्रीनेक्स फॉर्म में रूपांतरण

प्रत्येक प्रथम-क्रम विधेय कलन|प्रथम-क्रम सूत्र तार्किक रूप से (मौलिक तर्क में) प्रीनेक्स सामान्य रूप में कुछ सूत्र के सामान्तर है। ऐसे अनेक रूपांतरण नियम हैं जिन्हें किसी सूत्र को प्रीनेक्स सामान्य रूप में परिवर्तित करने के लिए पुनरावर्ती रूप से क्रियान्वित किया जा सकता है। नियम इस पर निर्भर करते हैं कि सूत्र में कौन से तार्किक संयोजक दिखाई देते हैं।

संधि और विच्छेद

तार्किक संयोजन और तार्किक वियोजन के नियम यही कहते हैं

$(\forall x\phi )\land \psi$ के सामान्तर है $\forall x(\phi \land \psi )$ (हल्के) अतिरिक्त शर्त के अनुसार $\exists x\top$, या, समकक्ष, $\lnot \forall x\bot$ (कारणकि कम से कम व्यक्ति उपस्तिथ है),

$(\forall x\phi )\lor \psi$ के सामान्तर है $\forall x(\phi \lor \psi )$;

और

$(\exists x\phi )\land \psi$ के सामान्तर है $\exists x(\phi \land \psi )$,

$(\exists x\phi )\lor \psi$ के सामान्तर है $\exists x(\phi \lor \psi )$ अतिरिक्त शर्त के अनुसार $\exists x\top$.

समतुल्यताएँ तब मान्य होती हैं जब $x$ के मुक्त चर के रूप में प्रकट नहीं होता है $\psi$; यदि $x$ में मुक्त दिखाई देता है $\psi$, कोई बाउंड का नाम बदल सकता है $x$ में $(\exists x\phi )$ और समतुल्य प्राप्त करें $(\exists x'\phi [x/x'])$.

उदाहरण के लिए, रिंग (गणित) की भाषा में,

$(\exists x(x^{2}=1))\land (0=y)$ के सामान्तर है $\exists x(x^{2}=1\land 0=y)$,

किन्तु

$(\exists x(x^{2}=1))\land (0=x)$ के सामान्तर नहीं है $\exists x(x^{2}=1\land 0=x)$

क्योंकि बाईं ओर का सूत्र किसी भी रिंग में सत्य है जब मुक्त चर x 0 के सामान्तर है, जबकि दाईं ओर के सूत्र में कोई मुक्त चर नहीं है और किसी भी गैर-तुच्छ रिंग में गलत है। इसलिए $(\exists x(x^{2}=1))\land (0=x)$ पहले के रूप में पुनः लिखा जाएगा $(\exists x'(x'^{2}=1))\land (0=x)$ और फिर प्रीनेक्स को सामान्य रूप में डाल दें $\exists x'(x'^{2}=1\land 0=x)$.

निषेध

निषेध के नियम यही कहते हैं

$\lnot \exists x\phi$ के सामान्तर है $\forall x\lnot \phi$ और

$\lnot \forall x\phi$ के सामान्तर है $\exists x\lnot \phi$.

निहितार्थ

भौतिक सशर्त के लिए चार नियम हैं: दो जो पूर्ववर्ती से परिमाणक हटाते हैं और दो जो परिणामी से परिमाणवाचक हटाते हैं। इन नियमों को निहितार्थ #तर्क को पुनः लिखकर प्राप्त किया जा सकता है $\phi \rightarrow \psi$ जैसा $\lnot \phi \lor \psi$ और उपरोक्त विच्छेद और निषेध के नियमों को क्रियान्वित करना। विच्छेदन के नियमों की तरह, इन नियमों के लिए आवश्यक है कि उपसूत्र में परिमाणित चर दूसरे उपसूत्र में मुक्त दिखाई न दे।

पूर्ववर्ती से परिमाणकों को हटाने के नियम हैं (परिमाणकों के परिवर्तन पर ध्यान दें):

$(\forall x\phi )\rightarrow \psi$ के सामान्तर है $\exists x(\phi \rightarrow \psi )$ (इस धारणा के अनुसार $\exists x\top$),

$(\exists x\phi )\rightarrow \psi$ के सामान्तर है $\forall x(\phi \rightarrow \psi )$.

परिणामी से परिमाणक हटाने के नियम हैं:

$\phi \rightarrow (\exists x\psi )$ के सामान्तर है $\exists x(\phi \rightarrow \psi )$ (इस धारणा के अनुसार $\exists x\top$),

$\phi \rightarrow (\forall x\psi )$ के सामान्तर है $\forall x(\phi \rightarrow \psi )$.

उदाहरण के लिए, जब परिमाणीकरण की सीमा गैर-ऋणात्मक प्राकृतिक संख्या है (अर्थात। $n\in \mathbb {N}$), कथन

$[\forall n\in \mathbb {N} (x<n)]\rightarrow (x<0)$

तार्किक रूप से कथन के समतुल्य है

$\exists n\in \mathbb {N} [(x<n)\rightarrow (x<0)]$

पहला कथन कहता है कि यदि x किसी प्राकृत संख्या से कम है, तब x शून्य से भी कम है। पश्चात् वाला कथन कहता है कि कुछ प्राकृतिक संख्या n उपस्तिथ है जैसे कि यदि x, n से कम है, तब x शून्य से भी कम है। दोनों कथन सत्य हैं। पहला कथन सत्य है क्योंकि यदि x किसी प्राकृत संख्या से कम है, तब उसे सबसे छोटी प्राकृत संख्या (शून्य) से भी कम होना चाहिए। पश्चात् वाला कथन सत्य है क्योंकि n=0 निहितार्थ को टॉटोलॉजी (तर्क) बनाता है।

ध्यान दें कि कोष्ठक का स्थान स्कोप (तर्क) को दर्शाता है, जो सूत्र के अर्थ के लिए बहुत महत्वपूर्ण है। निम्नलिखित दो कथनों पर विचार करें:

$\forall n\in \mathbb {N} [(x<n)\rightarrow (x<0)]$

और इसका तार्किक रूप से समतुल्य कथन

$[\exists n\in \mathbb {N} (x<n)]\rightarrow (x<0)$

पहला कथन कहता है कि किसी भी प्राकृतिक संख्या n के लिए, यदि x, n से कम है तब x शून्य से कम है। पश्चात् वाला कथन कहता है कि यदि कोई प्राकृतिक संख्या n उपस्तिथ है जैसे कि x, n से कम है, तब x शून्य से कम है। दोनों कथन झूठे हैं. पहला कथन n=2 के लिए मान्य नहीं है, क्योंकि x=1 n से कम है, किन्तु शून्य से कम नहीं है। पश्चात् वाला कथन x=1 के लिए मान्य नहीं है, क्योंकि प्राकृतिक संख्या n=2 x<n को संतुष्ट करती है, किन्तु x=1 शून्य से कम नहीं है।

उदाहरण

लगता है कि $\phi$, $\psi$, और $\rho$ क्वांटिफायर-मुक्त सूत्र हैं और इनमें से कोई भी दो सूत्र किसी भी मुक्त चर को साझा नहीं करते हैं। सूत्र पर विचार करें

$(\phi \lor \exists x\psi )\rightarrow \forall z\rho$.

अंतरतम उपसूत्रों से प्रारंभ होने वाले नियमों को पुनरावर्ती रूप से क्रियान्वित करके, तार्किक रूप से समकक्ष सूत्रों का निम्नलिखित अनुक्रम प्राप्त किया जा सकता है:

$(\phi \lor \exists x\psi )\rightarrow \forall z\rho$.

$(\exists x(\phi \lor \psi ))\rightarrow \forall z\rho$,

$\neg (\exists x(\phi \lor \psi ))\lor \forall z\rho$,

$(\forall x\neg (\phi \lor \psi ))\lor \forall z\rho$,

$\forall x(\neg (\phi \lor \psi )\lor \forall z\rho )$,

$\forall x((\phi \lor \psi )\rightarrow \forall z\rho )$,

$\forall x(\forall z((\phi \lor \psi )\rightarrow \rho ))$,

$\forall x\forall z((\phi \lor \psi )\rightarrow \rho )$.

यह मूल सूत्र के समतुल्य एकमात्र प्रीनेक्स फॉर्म नहीं है। उदाहरण के लिए, उपरोक्त उदाहरण में पूर्ववर्ती से पहले परिणामी से निपटकर, प्रीनेक्स फॉर्म

$\forall z\forall x((\phi \lor \psi )\rightarrow \rho )$

प्राप्त किया जा सकता है:

$\forall z((\phi \lor \exists x\psi )\rightarrow \rho )$

$\forall z((\exists x(\phi \lor \psi ))\rightarrow \rho )$,

$\forall z(\forall x((\phi \lor \psi )\rightarrow \rho ))$,

$\forall z\forall x((\phi \lor \psi )\rightarrow \rho )$.

क्वांटिफायर (तर्क)#समान सीमा वाले दो सार्वभौमिक क्वांटिफायर के क्वांटिफायर (नेस्टिंग) का क्रम कथन के अर्थ/सत्य मूल्य को नहीं बदलता है।

अंतर्ज्ञानवादी तर्क

किसी सूत्र को प्रीनेक्स रूप में परिवर्तित करने के नियम मौलिक तर्क का भारी उपयोग करते हैं। अंतर्ज्ञानवादी तर्क में, यह सच नहीं है कि प्रत्येक सूत्र तार्किक रूप से प्रीनेक्स सूत्र के सामान्तर है। निषेध संयोजक बाधा है, परंतु एकमात्र नहीं। निहितार्थ ऑपरेटर को मौलिक तर्क की तुलना में अंतर्ज्ञानवादी तर्क में भी भिन्न तरह से व्यवहार किया जाता है; अंतर्ज्ञानवादी तर्क में, विच्छेद और निषेध का उपयोग करके इसे परिभाषित नहीं किया जा सकता है।

बीएचके व्याख्या दर्शाती है कि क्यों कुछ सूत्रों में कोई अंतर्ज्ञान-समतुल्य प्रीनेक्स फॉर्म नहीं है। इस व्याख्या में, का प्रमाण

$(\exists x\phi )\rightarrow \exists y\psi \qquad (1)$

एक फलन है, जिसे ठोस x और प्रमाण दिया गया है $\phi (x)$, ठोस y और प्रमाण उत्पन्न करता है $\psi (y)$. इस स्थितियोंमें x के दिए गए मान से y के मान की गणना करना स्वीकार्य है। का प्रमाण

$\exists y(\exists x\phi \rightarrow \psi ),\qquad (2)$

दूसरी ओर, y का एकल ठोस मान और फलन उत्पन्न करता है जो किसी भी प्रमाण को परिवर्तित करता है $\exists x\phi$ के प्रमाण में $\psi (y)$. यदि प्रत्येक x संतोषजनक है $\phi$ y संतोषजनक बनाने के लिए उपयोग किया जा सकता है $\psi$ किन्तु ऐसे किसी भी y का निर्माण ऐसे x के ज्ञान के बिना नहीं किया जा सकता है तब सूत्र (1) सूत्र (2) के सामान्तर नहीं होगा।

किसी सूत्र को प्रीनेक्स फॉर्म में परिवर्तित करने के नियम जो अंतर्ज्ञानवादी तर्क में विफल होते हैं:

(1) $\forall x(\phi \lor \psi )$ तात्पर्य $(\forall x\phi )\lor \psi$,

(2) $\forall x(\phi \lor \psi )$ तात्पर्य $\phi \lor (\forall x\psi )$,

(3) $(\forall x\phi )\rightarrow \psi$ तात्पर्य $\exists x(\phi \rightarrow \psi )$,

(4) $\phi \rightarrow (\exists x\psi )$ तात्पर्य $\exists x(\phi \rightarrow \psi )$,

(5) $\lnot \forall x\phi$ तात्पर्य $\exists x\lnot \phi$,

(x मुक्त चर के रूप में प्रकट नहीं होता है $\,\psi$ (1) और (3) में; x मुक्त चर के रूप में प्रकट नहीं होता है $\,\phi$ (2) और (4) में)।

प्रीनेक्स फॉर्म का उपयोग

कुछ प्रमाण गणना केवल उस सिद्धांत से निपटेंगे जिसके सूत्र प्रीनेक्स सामान्य रूप में लिखे गए हैं। अंकगणितीय पदानुक्रम और विश्लेषणात्मक पदानुक्रम विकसित करने के लिए यह अवधारणा आवश्यक है।

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

ज्यामिति के लिए टार्स्की के स्वयंसिद्ध तार्किक प्रणाली है जिसके सभी वाक्य 'सार्वभौमिक-अस्तित्ववादी रूप' में लिखे जा सकते हैं, प्रीनेक्स सामान्य रूप का विशेष मामला जिसमें किसी भी अस्तित्वगत परिमाणीकरण से पहले प्रत्येक सार्वभौमिक परिमाणीकरण होता है, जिससे कि सभी वाक्यों को इस रूप में फिर से लिखा जा सके $\forall u$ $\forall v$ $\ldots$ $\exists a$ $\exists b$ $\phi$, कहाँ $\phi$ वाक्य है जिसमें कोई परिमाणक नहीं है। इस तथ्य ने अल्फ्रेड टार्स्की को यह सिद्ध करना करने की अनुमति दी कि यूक्लिडियन ज्यामिति निर्णायकता (तर्क) है।

यह भी देखें

• अंकगणितीय पदानुक्रम
• हर्बब्रांडीकरण
• शोलेमाइजेशन

संदर्भ

• रिचर्ड एल एप्सटीन (18 December 2011). शास्त्रीय गणितीय तर्क: तर्क की अर्थ संबंधी नींव. प्रिंसटन यूनिवर्सिटी प्रेस. pp. 108–. ISBN 978-1-4008-4155-4.
• पीटर बी. एंड्रयूज (17 April 2013). गणितीय तर्क और प्रकार सिद्धांत का परिचय: प्रमाण के माध्यम से सत्य तक. स्प्रिंगर साइंस एंड बिजनेस मीडिया. pp. 111–. ISBN 978-94-015-9934-4.
• इलियट मेंडेलसन (1 June 1997). गणितीय तर्क का परिचय, चौथा संस्करण. CRC Press. pp. 109–. ISBN 978-0-412-80830-2.
• हिनमन, पीटर (2005), गणितीय तर्क के मूल सिद्धांत, ए के पीटर्स, ISBN 978-1-56881-262-5