विधेय फ़ंक्टर तर्क

From Vigyanwiki

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

प्रेरणा

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

क्विन ने अपने मित्र रुडोल्फ कार्नाप के लेखन से फ़नक्टर लिया था, जो इसे दर्शन और गणितीय तर्क में नियोजित करने वाले पहले व्यक्ति थे, और इसे इस प्रकार परिभाषित किया था:

फ़ंक्टर शब्द, आयात में व्याकरणिक किन्तु निवास समिष्ट में तार्किक... संकेत है जो किसी दिए गए व्याकरणिक प्रकार की अभिव्यक्ति उत्पन्न करने के लिए दिए गए व्याकरणिक प्रकार के या अधिक अभिव्यक्तियों से जुड़ता है। (क्वीन 1982:129)प्रथम-क्रम तर्क को बीजगणित करने के पीएफएल के अतिरिक्त अन्य विधियों में सम्मिलित हैं:

  • अल्फ्रेड टार्स्की और उनके अमेरिकी छात्रों द्वारा बेलनाकार बीजगणित बर्नेज़ (1959) में प्रस्तावित सरलीकृत बेलनाकार बीजगणित ने क्विन को विधेय फ़ंक्टर वाक्यांश के पहले उपयोग वाले पेपर को लिखने के लिए प्रेरित किया था;
  • पॉल हेल्मोस का बहुपद बीजगणित अपने प्रभावकारी मौलिक और सिद्धांतों के आधार पर, यह बीजगणित पीएफएल से सबसे अधिक मिलता जुलता है;
  • संबंध बीजगणित प्रथम-क्रम तर्क के टुकड़े को बीजगणित करता है जिसमें तीन से अधिक परिमाणक (तर्क) के सीमा में कोई परमाणु सूत्र नहीं होने वाले सूत्र सम्मिलित होते हैं। चूँकि, वह टुकड़ा डोमेन अंकगणित और स्वयंसिद्ध समुच्चय सिद्धांत जेडएफसी के लिए पर्याप्त है; इसलिए संबंध बीजगणित, पीएफएल के विपरीत, गोडेल की अपूर्णता प्रमेय है। इस प्रकार 1920 के बाद से संबंध बीजगणित पर अधिकांश कार्य टार्स्की और उनके अमेरिकी छात्रों द्वारा किया गया है। संबंध बीजगणित की शक्ति तब तक प्रकट नहीं हुई जब तक कि पीएफएल पर आधारित तीन महत्वपूर्ण पत्रों, अर्थात् बेकन (1985), कुह्न (1983), और क्वीन (1976) के बाद प्रकाशित मोनोग्राफ टार्स्की और गिवंत (1987) द्वारा प्रस्तुत किया गया था;
  • संयोजक लॉजिक कॉम्बिनेटर्स पर बनता है, उच्च क्रम के फ़ंक्शन जिनके फ़ंक्शन का डोमेन अन्य कॉम्बिनेटर या फ़ंक्शन होता है, और जिनके फ़ंक्शन की सीमा और कॉम्बिनेटर होती है। इसलिए संयोजनात्मक तर्क समुच्चय सिद्धांत की अभिव्यंजक शक्ति के कारण प्रथम-क्रम तर्क से आगे निकल जाता है, जो संयोजनात्मक तर्क को विरोधाभास के प्रति संवेदनशील बनाता है। दूसरी ओर, विधेय फ़ंक्टर, केवल विधेय (जिसे टर्म (तर्क) भी कहा जाता है) को विधेय में बदल देता है।

पीएफएल वास्तविक इन औपचारिकताओं में सबसे सरल है, फिर भी ऐसा भी है जिसके बारे में सबसे कम लिखा गया है।

क्विन का संयोजनात्मक तर्क के प्रति आजीवन आकर्षण था, जिसका प्रमाण रूसी तर्कशास्त्री मोसेस शॉनफिंकेल द्वारा संयोजनात्मक तर्क की स्थापना करने वाले पेपर के वान हेजेनॉर्ट (1967) में अनुवाद के उनके परिचय से मिलता है। जब क्विन ने 1959 में पीएफएल पर गंभीरता से कार्य करना प्रारंभ किया था, जिससे संयोजन तर्क को सामान्यतः निम्नलिखित कारणों से विफल माना गया था:

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

कुह्न की निर्दिष्टीकरण

इस खंड में वर्णित पीएफएल वाक्यविन्यास, मौलिक और सिद्धांत अधिक सीमा तक स्टीवन कुह्न (1983) के हैं। इस प्रकार फ़ंक्शनलर्स के शब्दार्थ क्विन (1982) के हैं। इस प्रविष्टि के शेष भाग में बेकन (1985) की कुछ शब्दावली सम्मिलित है।

सिंटेक्स

एक परमाणु शब्द अपर केस लैटिन अक्षर है, I और S को छोड़कर, इसके बाद संख्यात्मक सुपरस्क्रिप्ट होती है जिसे इसकी डिग्री कहा जाता है, या संक्षिप्त लोअर केस वेरिएबल्स द्वारा, जिसे सामूहिक रूप से तर्क सूची के रूप में जाना जाता है। किसी पद की डिग्री विधेय अक्षर के बाद चरों की संख्या के समान ही जानकारी देती है। इस प्रकार डिग्री 0 का परमाणु शब्द बूलियन चर या सत्य मान को दर्शाता है। इस प्रकार I की डिग्री सदैव 2 होती है और इसलिए इसे दर्शाया नहीं गया है।

कॉम्बिनेटरी (शब्द क्वीन का है) विधेय फ़ैक्टर, पीएफएल के सभी मोनैडिक और विशिष्ट, 'इनव', 'इनव', '∃', '+' और 'p' हैं। शब्द या तो परमाणु शब्द है, या निम्नलिखित पुनरावर्ती नियम द्वारा निर्मित है। यदि τ पद है, तो 'Inv'τ, 'inv'τ, '∃'τ, '+'τ, और 'p'τ पद हैं। सुपरस्क्रिप्ट n, n प्राकृतिक संख्या > 1 वाला फ़ैक्टर, उस फ़ैक्टर के n निरंतर अनुप्रयोगों (पुनरावृत्तियों) को दर्शाता है।

सूत्र या तो शब्द है या पुनरावर्ती नियम द्वारा परिभाषित है: यदि α और β सूत्र हैं, तो αβ और ~(α) भी इसी तरह सूत्र हैं। इसलिए ~ अन्य मोनैडिक फ़ंक्टर है, और कॉन्सटेनेशन एकमात्र डायडिक विधेय फ़ैक्टर है। क्विन ने इन फ़ैक्टर्स को एलेथिक कहा ~ की स्वाभाविक व्याख्या निषेध है; संयोजन कोई भी तार्किक संयोजक है, जो निषेध के साथ संयुक्त होने पर संयोजकों का कार्यात्मक पूर्णता समुच्चय बनाता है। क्विन का रोचक कार्यात्मक पूर्ण समुच्चय तार्किक संयोजन और निषेध था। इस प्रकार संयोजित पदों को संयुक्त माना जाता है। अंकन '+' बेकन (1985) का है; अन्य सभी संकेतन क्वीन (1976; 1982) के हैं। पीएफएल का एलेथिक भाग क्वीन (1982) के बूलियन शब्द स्कीमाटा के समान है।

जैसा कि सर्वविदित है, दो एलेथिक फ़ंक्टर को निम्नलिखित सिंटैक्स और शब्दार्थ के साथ एकल डायडिक फ़ैक्टर द्वारा प्रतिस्थापित किया जा सकता है: यदि α और β सूत्र हैं, तो (αβ) ऐसा सूत्र है जिसका शब्दार्थ (α और/या β) नहीं है ( शेफ़र लाइन और लॉजिकल NOR देखें)।

सिद्धांत और शब्दार्थ

क्विन ने पीएफएल के लिए न तो स्वयंसिद्धीकरण और न ही प्रमाण प्रक्रिया निर्धारित की थी। पीएफएल का निम्नलिखित स्वयंसिद्धीकरण, कुह्न (1983) में प्रस्तावित दो में से एक, संक्षिप्त और वर्णन करने में सरल है, किन्तु मुक्त चर का व्यापक उपयोग करता है और इसलिए पीएफएल की भावना के साथ पूर्ण न्याय नहीं करता है। कुह्न मुक्त चर के साथ और स्वयंसिद्धीकरण प्रदान करता है, किन्तु इसका वर्णन करना कठिन है और यह परिभाषित फ़ंक्शनलर्स का व्यापक उपयोग करता है। कुह्न ने अपने पीएफएल स्वयंसिद्धीकरण स्थिरता प्रमाण और पूर्णता (तर्क) दोनों को सिद्ध किया था।

यह खंड मौलिक विधेय फ़ैक्टर और कुछ परिभाषित फ़ैक्टरों के आसपास बनाया गया है। एलेथिक फ़ैक्टर्स को भावनात्मक तर्क के लिए सिद्धांतों के किसी भी समुच्चय द्वारा स्वयंसिद्ध किया जा सकता है जिनके मौलिक निषेध हैं और ∧ या ∨ में से हैं। समान रूप से, भावनात्मक तर्क की सभी तनातनी (तर्क) को स्वयंसिद्धों के रूप में लिया जा सकता है।

प्रत्येक विधेय फ़ैक्टर के लिए क्विन (1982) के शब्दार्थ को अमूर्तन (सेट बिल्डर नोटेशन) के संदर्भ में नीचे बताया गया है, इसके बाद या तो कुह्न (1983) से संबंधित स्वयंसिद्ध कथन, या क्विन (1976) से परिभाषा दी गई है। संकेतन परमाणु सूत्र को संतुष्ट करने वाले n-ट्यूपल के समुच्चय को दर्शाता है

  • पहचान, I, परिभाषित किया जाता है:

पहचान प्रतिवर्ती संबंध है (Ixx), सममित (IxyIyx), सकर्मक संबंध ((IxyIyz) → Ixz), और प्रतिस्थापन गुण का पालन करता है:

  • पैडिंग, '+', किसी भी तर्क सूची के बाईं ओर वेरिएबल जोड़ता है।
  • क्रॉपिंग, '∃', किसी भी तर्क सूची में सबसे बाएं वेरिएबल को मिटा देता है।

क्रॉपिंग दो उपयोगी परिभाषित फ़ंक्शनलर्स को सक्षम बनाता है:

  • प्रतिबिंब, 'एस':

एस 2 से अधिक किसी भी परिमित डिग्री के सभी शब्दों के प्रति संवेदनशीलता की धारणा को सामान्यीकृत करता है। एन.बी.: एस को संयोजन तर्क के संयोजन तर्क एस के साथ भ्रमित नहीं किया जाना चाहिए।

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

संयोजित तर्क सूची को पुन: व्यवस्थित करें जिससे डुप्लिकेट चर की जोड़ी को सबसे बाईं ओर समिष्टांतरित किया जा सकता है, फिर डुप्लिकेशन को समाप्त करने के लिए एस को आमंत्रित करें। इसे आवश्यकतानुसार कई बार दोहराने से अधिकतम लंबाई (m,n) की तर्क सूची प्राप्त होती है।

अगले तीन फ़ैक्टर इच्छानुसार तर्क सूचियों को पुन: व्यवस्थित करने में सक्षम बनाते हैं।

  • प्रमुख व्युत्क्रम, इनव, तर्क सूची में चरों को दाईं ओर घुमाता है, जिससे अंतिम चर पहला बन जाए।
  • लघु व्युत्क्रम, 'इनव', तर्क सूची में पहले दो चरों की अदला-बदली करता है।
  • क्रमपरिवर्तन, 'p', तर्क सूची में दूसरे से अंतिम चर को बाईं ओर घुमाता है, जिससे दूसरा चर अंतिम बन जाता है।

n चरों से युक्त तर्क सूची को देखते हुए, 'p' स्पष्ट रूप से अंतिम n−1 चर को साइकिल श्रृंखला की तरह मानता है, जिसमें प्रत्येक चर श्रृंखला में लिंक बनाता है। 'p' का अनुप्रयोग श्रृंखला को लिंक से आगे बढ़ाता है। k से F तक 'pn' का निरंतर अनुप्रयोग k+1 वेरिएबल को F में दूसरे तर्क समिष्ट पर ले जाता है।

जब n=2, 'Inv' और 'inv' केवल x1 और x2 का आदान-प्रदान करते हैं. जब n=1, उनका कोई प्रभाव नहीं पड़ता है। अतः n <3 होने पर 'p' का कोई प्रभाव नहीं पड़ता है।

कुह्न (1983) प्रमुख व्युत्क्रम और लघु व्युत्क्रम को मौलिक मानते हैं। कुह्न में अंकन 'p' 'inv' से मेल खाता है; उसके पास क्रमपरिवर्तन का कोई एनालॉग नहीं है और इसलिए उसके पास इसके लिए कोई सिद्धांत नहीं है। यदि, क्वीन (1976) के बाद, 'p' को मौलिक के रूप में लिया जाता है, तो 'इनव' और 'इनव' को '+', '∃' और पुनरावृत्त 'p' के सामान्य संयोजन के रूप में परिभाषित किया जा सकता है।

निम्न तालिका सारांशित करती है कि फ़ंक्शनलर्स अपने तर्कों की डिग्री को कैसे प्रभावित करते हैं।

अभिव्यक्ति डिग्री
no change
n
max(m, n)

नियम

वैधता को प्रभावित किए बिना, विधेय पत्र के सभी उदाहरणों को उसी डिग्री के किसी अन्य विधेय पत्र द्वारा प्रतिस्थापित किया जा सकता है। प्रथम-क्रम तर्क हैं:

  • एक वैध, सरल तर्क और निष्कर्ष के नियम के रूप;
  • मान लीजिए α और β पीएफएल सूत्र हैं जिनमें प्रकट नहीं होता है। तो यदि तो फिर, यह पीएफएल प्रमेय है इसी तरह पीएफएल प्रमेय है।

कुछ उपयोगी परिणाम

पीएफएल को स्वयंसिद्ध करने के अतिरिक्त, क्वीन (1976) ने निम्नलिखित अनुमानों को उम्मीदवार स्वयंसिद्ध के रूप में प्रस्तावित किया था।

'p' का n−1 निरंतर पुनरावृत्ति यथास्थिति बहाल करता है:

+ और ∃ दूसरे को नष्ट करें:

निषेध +, ∃, और p पर वितरित होता है:

+ और p संयोजन पर वितरित करता है:

पहचान का रोचक निहितार्थ है:

क्विन ने नियम का भी अनुमान लगाया: यदि α पीएफएल प्रमेय है, तो ऐसा , +α, और ही है.

बेकन का कार्य

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

  • फ्रेडरिक फिच की शैली में प्राकृतिक कटौती सूत्रीकरण बेकन इस सूत्रीकरण को पूर्ण विस्तार से संगति प्रमाण एवं पूर्णता (तर्क) सिद्ध करते हैं।
  • एक स्वयंसिद्ध सूत्रीकरण, जिसे बेकन प्रमाणित करते हैं, किन्तु सिद्ध नहीं करते है, पिछले वाले के समान है। इनमें से कुछ स्वयंसिद्ध बातें केवल बेकन के संकेतन में दोहराए गए क्विन अनुमान हैं।

बेकन भी:

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

प्रथम-क्रम तर्क से पीएफएल तक

निम्नलिखित कलन विधि को क्वीन (1976: 300-2) से अनुकूलित किया गया है। प्रथम-क्रम तर्क के वाक्य (गणितीय तर्क) को देखते हुए, पहले निम्नलिखित कार्य करें:

अब पूर्ववर्ती परिणाम पर निम्नलिखित एल्गोरिदम प्रयुक्त करें:

  1. सबसे गहराई से निहित क्वांटिफायर के आव्यूहों का अनुवाद डिजजंक्टिव सामान्य रूप में करें, जिसमें डिजंक्ट्स के संयुक्त पद सम्मिलित हों, आवश्यकतानुसार परमाणु शब्दों को अस्वीकार। परिणामी उपसूत्र में केवल निषेध, संयोजन, विच्छेदन और अस्तित्वगत परिमाणीकरण सम्मिलित है।
  2. मार्ग के नियम का उपयोग करके आव्यूह में विच्छेदों पर अस्तित्व संबंधी परिमाणकों को वितरित करें (क्विन 1982: 119):
  3. तथ्य का उपयोग करके संयोजन को कार्टेशियन उत्पाद से बदलें:
  4. सभी परमाणु शब्दों की तर्क सूचियों को संयोजित करें, और संयोजित सूची को उपसूत्र के सबसे दाईं ओर ले जाएँ।
  5. परिमाणित चर के सभी उदाहरणों (इसे y कहें) को तर्क सूची के बाईं ओर ले जाने के लिए Inv' और inv का उपयोग करें।
  6. Y के अंतिम उदाहरण को छोड़कर सभी को हटाने के लिए जितनी बार आवश्यक हो S का उपयोग करें। के एक उदाहरण के साथ उपसूत्र को उपसर्ग करके y को हटा दें।
  7. (1)-(6) को तब तक दोहराएँ जब तक कि सभी परिमाणित चर समाप्त न हो जाएँ। समतुल्यता का आह्वान करके परिमाणक के सीमा में आने वाले किसी भी वियोजन को हटा दें:

पीएफएल से प्रथम-क्रम तर्क तक रिवर्स अनुवाद पर क्विन (1976: 302-4) में चर्चा की गई है।

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

यह भी देखें

फ़ुटनोट

  1. Johannes Stern, Toward Predicate Approaches to Modality, Springer, 2015, p. 11.
  2. Metamath axioms.

संदर्भ

  • Bacon, John, 1985, "The completeness of a predicate-functor logic," Journal of Symbolic Logic 50: 903–26.
  • Paul Bernays, 1959, "Uber eine naturliche Erweiterung des Relationenkalkuls" in Heyting, A., ed., Constructivity in Mathematics. North Holland: 1–14.
  • Kuhn, Steven T., 1983, "An Axiomatization of Predicate Functor Logic," Notre Dame Journal of Formal Logic 24: 233–41.
  • Willard Quine, 1976, "Algebraic Logic and Predicate Functors" in Ways of Paradox and Other Essays, enlarged ed. Harvard Univ. Press: 283–307.
  • Willard Quine, 1982. Methods of Logic, 4th ed. Harvard Univ. Press. Chpt. 45.
  • Sommers, Fred, 1982. The Logic of Natural Language. Oxford Univ. Press.
  • Alfred Tarski and Givant, Steven, 1987. A Formalization of Set Theory Without Variables. AMS.
  • Jean Van Heijenoort, 1967. From Frege to Gödel: A Source Book on Mathematical Logic. Harvard Univ. Press.

बाहरी संबंध