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

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

शास्त्रीय तर्क में प्रत्येक सूत्र तार्किक रूप से प्रीनेक्स सामान्य रूप में सूत्र के बराबर है। उदाहरण के लिए, यदि $\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). Classical Mathematical Logic: The Semantic Foundations of Logic. Princeton University Press. pp. 108–. ISBN 978-1-4008-4155-4.
• पीटर बी. एंड्रयूज (17 April 2013). An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof. Springer Science & Business Media. pp. 111–. ISBN 978-94-015-9934-4.
• इलियट मेंडेलसन (1 June 1997). Introduction to Mathematical Logic, Fourth Edition. CRC Press. pp. 109–. ISBN 978-0-412-80830-2.
• हिनमन, पीटर (2005), गणितीय तर्क के मूल सिद्धांत, ए के पीटर्स, ISBN 978-1-56881-262-5