अच्छी तरह से गठित सूत्र

गणितीय तर्क में, प्रस्तावपरक तर्क और विधेय तर्क, एक अच्छी तरह से गठित सूत्र, संक्षिप्त WFF या wff, अक्सर बस सूत्र, एक दिए गए वर्णमाला (कंप्यूटर विज्ञान) से प्रतीक (औपचारिक) का एक परिमित अनुक्रम है जो एक औपचारिक भाषा का हिस्सा है।^[1] भाषा में सूत्रों के सेट के साथ एक औपचारिक भाषा की पहचान की जा सकती है।

एक सूत्र एक वाक्यविन्यास (तर्क) वस्तु है जिसे एक व्याख्या (तर्क) के माध्यम से एक शब्दार्थ औपचारिक शब्दार्थ (तर्क) दिया जा सकता है। सूत्रों के दो प्रमुख उपयोग प्रस्तावात्मक तर्क और विधेय तर्क में हैं।

परिचय

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

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

सूत्र स्वयं वाक्यात्मक वस्तुएँ हैं। उन्हें व्याख्याओं द्वारा अर्थ दिया जाता है। उदाहरण के लिए, एक तर्कवाक्य सूत्र में, प्रत्येक साध्यात्मक चर को एक ठोस तर्कवाक्य के रूप में व्याख्यायित किया जा सकता है, ताकि समग्र सूत्र इन तर्कवाक्यों के बीच संबंध को व्यक्त करे। हालांकि, एक सूत्र को केवल एक सूत्र के रूप में माना जाना चाहिए, इसकी व्याख्या करने की आवश्यकता नहीं है।

प्रस्तावित कलन

प्रस्तावक कलन के सूत्र, जिसे प्रस्तावक सूत्र भी कहा जाता है,^[3] जैसे भाव हैं $(A\land (B\lor C))$ . उनकी परिभाषा प्रस्तावित चर के एक सेट वी के मनमाना विकल्प के साथ शुरू होती है। वर्णमाला में तार्किक संयोजकों और कोष्ठकों ( और ) के प्रतीकों के साथ V में अक्षर होते हैं, जिनमें से सभी को V में नहीं माना जाता है। सूत्र इस वर्णमाला पर कुछ भाव (अर्थात, प्रतीकों के तार) होंगे। .

सूत्र आगमनात्मक परिभाषाएँ निम्नानुसार परिभाषित हैं:

प्रत्येक प्रस्ताव चर, अपने आप में, एक सूत्र है।
यदि φ एक सूत्र है, तो ¬φ एक सूत्र है।
यदि φ और ψ सूत्र हैं, और • कोई द्विआधारी संयोजक है, तो ( φ • ψ) एक सूत्र है। यहां • सामान्य ऑपरेटर्स ∨, ∧, →, या ↔ हो सकते हैं (लेकिन इन्हीं तक सीमित नहीं हैं)।

इस परिभाषा को बैकस-नौर रूप में एक औपचारिक व्याकरण के रूप में भी लिखा जा सकता है, बशर्ते चर का सेट परिमित हो:

<alpha set> ::= p | q | r | s | t | u | ... (the arbitrary finite set of propositional variables)
<form> ::= <alpha set> | ¬<form> | (<form>∧<form>) | (<form>∨<form>) | (<form>→<form>) | (<form>↔<form>)

इस व्याकरण के प्रयोग से प्रतीकों का क्रम

(((पी → क्यू) ∧ (आर → एस)) ∨ (¬q ∧ ¬s))

एक सूत्र है, क्योंकि यह व्याकरणिक रूप से सही है। प्रतीकों का क्रम

((पी → क्यू)→(क्यूक्यू))पी))

सूत्र नहीं है, क्योंकि यह व्याकरण के अनुरूप नहीं है।

एक जटिल सूत्र को पढ़ना मुश्किल हो सकता है, उदाहरण के लिए, कोष्ठकों के प्रसार के कारण। इस अंतिम घटना को कम करने के लिए, ऑपरेटरों के बीच पूर्वता नियम (संचालन के मानक गणितीय क्रम के समान) मान लिए जाते हैं, जिससे कुछ ऑपरेटर दूसरों की तुलना में अधिक बाध्यकारी हो जाते हैं। उदाहरण के लिए, पूर्वता मानते हुए (अधिकतम बाध्यकारी से कम से कम बाध्यकारी) 1. ¬ 2. → 3. ∧ 4. ∨. फिर सूत्र

(((पी → क्यू) ∧ (आर → एस)) ∨ (¬q ∧ ¬s))

के रूप में संक्षिप्त किया जा सकता है

p → q ∧ r → s ∨ ¬q ∧ ¬s

हालाँकि, यह केवल एक सूत्र के लिखित प्रतिनिधित्व को सरल बनाने के लिए उपयोग की जाने वाली एक प्रथा है। यदि अग्रता मान ली गई थी, उदाहरण के लिए, बाएं-दाएं सहयोगी होने के लिए, निम्नलिखित क्रम में: 1. ¬ 2. ∧ 3. ∨ 4. →, तो उपरोक्त समान सूत्र (कोष्ठकों के बिना) को इस रूप में फिर से लिखा जाएगा

(p → (q ∧ r)) → (s ∨ (¬q ∧ ¬s))

विधेय तर्क

प्रथम क्रम तर्क में एक सूत्र की परिभाषा ${\mathcal {QS}}$ हाथ में सिद्धांत के हस्ताक्षर (गणितीय तर्क) के सापेक्ष है। यह हस्ताक्षर निरंतर प्रतीकों, विधेय प्रतीकों, और सिद्धांत के कार्य प्रतीकों के साथ-साथ कार्य और विधेय प्रतीकों की शुद्धता को निर्दिष्ट करता है।

सूत्र की परिभाषा कई भागों में आती है। सबसे पहले, टर्म (तर्क) के सेट को पुनरावर्ती रूप से परिभाषित किया गया है। शर्तें, अनौपचारिक रूप से, ऐसे भाव हैं जो प्रवचन के क्षेत्र से वस्तुओं का प्रतिनिधित्व करते हैं।

कोई भी चर एक पद है।
हस्ताक्षर से कोई भी स्थिर प्रतीक एक शब्द है
an रूप की अभिव्यक्ति f(t₁,…,टी_n), जहां f एक n-आर्य फ़ंक्शन प्रतीक है, और t₁,…,टी_n शर्तें हैं, फिर से एक शब्द है।

अगला कदम परमाणु सूत्रों को परिभाषित करना है।

अगर टी₁ और टी₂ शर्तें हैं तो टी₁= टी₂ एक परमाणु सूत्र है
यदि R एक n-ary विधेय प्रतीक है, और t₁,…,टी_n पद हैं, तो R(t₁,…,टी_n) एक परमाणु सूत्र है

अंत में, सूत्रों के सेट को सबसे छोटे सेट के रूप में परिभाषित किया जाता है जिसमें परमाणु सूत्रों का सेट होता है जैसे कि निम्नलिखित धारण करता है:

$\neg \phi$ एक सूत्र है जब $\phi$ एक सूत्र है
$(\phi \land \psi )$ और $(\phi \lor \psi )$ सूत्र हैं जब $\phi$ और $\psi$ सूत्र हैं;
$\exists x\,\phi$ एक सूत्र है जब $x$ एक चर है और $\phi$ सूत्र है;
$\forall x\,\phi$ एक सूत्र है जब $x$ एक चर है और $\phi$ एक सूत्र है (वैकल्पिक रूप से, $\forall x\,\phi$ के संक्षिप्त रूप के रूप में परिभाषित किया जा सकता है $\neg \exists x\,\neg \phi$ ).

यदि किसी सूत्र की कोई घटना नहीं है $\exists x$ या $\forall x$ , किसी भी चर के लिए $x$ , तो कहा जाता है {{Anchor|Quantifier-free formula}क्वांटिफायर मुक्त। एक 'अस्तित्ववादी सूत्र' एक ऐसा सूत्र है जो अस्तित्वगत परिमाणीकरण के अनुक्रम से शुरू होता है जिसके बाद परिमाणक-मुक्त सूत्र होता है।

परमाणु और खुले सूत्र

एक परमाणु सूत्र एक ऐसा सूत्र है जिसमें कोई तार्किक संबंध नहीं होता है और न ही परिमाणीकरण (तर्क) होता है, या समकक्ष रूप से एक ऐसा सूत्र होता है जिसमें कोई सख्त उपसूत्र नहीं होता है। परमाणु सूत्रों का सटीक रूप विचाराधीन औपचारिक प्रणाली पर निर्भर करता है; प्रस्तावपरक तर्क के लिए, उदाहरण के लिए, परमाणु सूत्र प्रस्तावात्मक चर हैं। विधेय तर्क के लिए, परमाणु अपने तर्कों के साथ विधेय प्रतीक हैं, प्रत्येक तर्क एक गठन नियम है।

कुछ शब्दावली के अनुसार, केवल तार्किक संयोजकों का उपयोग करके परमाणु सूत्रों के संयोजन से एक खुला सूत्र बनता है, क्वांटिफायर के बहिष्करण के लिए।^[4] इसे ऐसे सूत्र से भ्रमित नहीं होना है जो बंद नहीं है।

बंद सूत्र

एक बंद सूत्र, जमीनी अभिव्यक्ति फॉर्मूला या वाक्य भी एक ऐसा फॉर्मूला है जिसमें किसी भी चर (गणित) के मुक्त और बाध्य चर नहीं होते हैं। यदि 'A' किसी प्रथम कोटि की भाषा का सूत्र है जिसमें चर $v 1, \dots, v n$ मुक्त घटनाएँ हैं, फिर A से पहले $\forall v 1 \dots \forall v n$ ए का समापन है।

सूत्रों पर लागू गुण

एक भाषा में एक सूत्र ए ${\mathcal {Q}}$ संतुष्टि और वैधता है अगर यह हर व्याख्या (तर्क) के लिए सही है ${\mathcal {Q}}$ .
एक भाषा में एक सूत्र ए ${\mathcal {Q}}$ संतुष्टि और वैधता है अगर यह कुछ व्याख्या (तर्क) के लिए सही है ${\mathcal {Q}}$ .
पीनो अंकगणित की भाषा का एक सूत्र 'निर्णायक' है यदि यह एक निर्णायक सेट का प्रतिनिधित्व करता है, यानी यदि कोई प्रभावी तरीका है, जो ए के मुक्त चर के चर के प्रतिस्थापन को देखते हुए कहता है कि या तो परिणामी उदाहरण A का साध्य है या इसका निषेध है।

शब्दावली का प्रयोग

गणितीय तर्क पर पहले के कार्यों में (उदाहरण के लिए अलोंजो चर्च द्वारा^[5]), सूत्र प्रतीकों के किसी भी तार को संदर्भित करते हैं और इन तारों के बीच, अच्छी तरह से गठित सूत्र वे तार थे जो (सही) सूत्रों के गठन नियमों का पालन करते थे।

कई लेखक केवल सूत्र कहते हैं।^[6]^[7]^[8]^[9] आधुनिक उपयोग (विशेष रूप से गणितीय सॉफ़्टवेयर के साथ कंप्यूटर विज्ञान के संदर्भ में जैसे कि मॉडल जाँच उपकरणों की सूची, स्वचालित प्रमेय सिद्ध करने वाले, इंटरएक्टिव प्रमेय साबित करने वाले) सूत्र की धारणा को केवल बीजगणितीय अवधारणा को बनाए रखने और अच्छी तरह से गठित प्रश्न को छोड़ने के लिए करते हैं , यानी सूत्रों के ठोस स्ट्रिंग प्रतिनिधित्व (कनेक्टिव्स और क्वांटिफायर के लिए इस या उस प्रतीक का उपयोग करके, ऑपरेशन के इस या उस क्रम का उपयोग करके, पोलिश संकेतन या इंफिक्स नोटेशन नोटेशन आदि का उपयोग करके) केवल नोटेशनल समस्या के रूप में।

जबकि अभिव्यक्ति सुव्यवस्थित सूत्र अभी भी उपयोग में है,^[10]^[11]^[12] ये लेखक जरूरी नहीं हैं^{[weasel words]} इसे सूत्र के पुराने अर्थ के विपरीत उपयोग करें, जो अब गणितीय तर्क में सामान्य नहीं है।^{[citation needed]}

अभिव्यक्ति अच्छी तरह से बनाई गई सूत्र (डब्ल्यूएफएफ) भी लोकप्रिय संस्कृति में शामिल हो गई। WFF अकादमिक गेम WFF 'N PROOF: द गेम ऑफ मॉडर्न लॉजिक के नाम पर इस्तेमाल होने वाले एक गूढ़ वाक्य का हिस्सा है, लेमन एलन द्वारा,^[13] विकसित हुआ जब वह येल लॉ स्कूल में था (वह बाद में मिशिगन विश्वविद्यालय में प्रोफेसर था)। खेलों के सुइट को बच्चों को प्रतीकात्मक तर्क के सिद्धांतों (पोलिश संकेतन में) सिखाने के लिए डिज़ाइन किया गया है।^[14] इसका नाम wiffenpoof की एक प्रतिध्वनि है, येल विश्वविद्यालय में जयकार के रूप में इस्तेमाल किया जाने वाला एक बकवास शब्द द व्हिफेनपोफ सॉन्ग और द व्हिफेनपोफ्स में लोकप्रिय हुआ।^[15]

यह भी देखें

ग्राउंड एक्सप्रेशन
बेहतरीन अभिव्यक्ति

↑ Formulas are a standard topic in introductory logic, and are covered by all introductory textbooks, including Enderton (2001), Gamut (1990), and Kleene (1967)
↑ W. Dean, S. Walsh, The Prehistory of the Subsystems of Second-order Arithmetic (2016), p.6
↑ First-order logic and automated theorem proving, Melvin Fitting, Springer, 1996 [1]
↑ Handbook of the history of logic, (Vol 5, Logic from Russell to Church), Tarski's logic by Keith Simmons, D. Gabbay and J. Woods Eds, p568 [2].
↑ Alonzo Church, [1996] (1944), Introduction to mathematical logic, page 49
↑ Hilbert, David; Ackermann, Wilhelm (1950) [1937], Principles of Mathematical Logic, New York: Chelsea
↑ Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 978-0-521-58713-6
↑ Barwise, Jon, ed. (1982), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
↑ Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3
↑ Enderton, Herbert [2001] (1972), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
↑ R. L. Simpson (1999), Essentials of Symbolic Logic, page 12
↑ Mendelson, Elliott [2010] (1964), An Introduction to Mathematical Logic (5th ed.), London: Chapman & Hall
↑ Ehrenburg 2002
↑ More technically, propositional logic using the Fitch-style calculus.
↑ Allen (1965) acknowledges the pun.

संदर्भ

Allen, Layman E. (1965), "Toward Autotelic Learning of Mathematical Logic by the WFF 'N PROOF Games", Mathematical Learning: Report of a Conference Sponsored by the Committee on Intellective Processes Research of the Social Science Research Council, Monographs of the Society for Research in Child Development, 30 (1): 29–41
Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4th ed.), Cambridge University Press, ISBN 978-0-521-00758-0
Ehrenberg, Rachel (Spring 2002). "He's Positively Logical". Michigan Today. University of Michigan. Archived from the original on 2009-02-08. Retrieved 2007-08-19.
Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
Gamut, L.T.F. (1990), Logic, Language, and Meaning, Volume 1: Introduction to Logic, University Of Chicago Press, ISBN 0-226-28085-3
Hodges, Wilfrid (2001), "Classical Logic I: First-Order Logic", in Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic, Blackwell, ISBN 978-0-631-20692-7
Hofstadter, Douglas (1980), Gödel, Escher, Bach: An Eternal Golden Braid, Penguin Books, ISBN 978-0-14-005579-5
Kleene, Stephen Cole (2002) [1967], Mathematical logic, New York: Dover Publications, ISBN 978-0-486-42533-7, MR 1950307
Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6

बाहरी संबंध

Well-Formed Formula for First Order Predicate Logic - includes a short Java quiz.
Well-Formed Formula at ProvenMath

[1] Formulas are a standard topic in introductory logic, and are covered by all introductory textbooks, including Enderton (2001), Gamut (1990), and Kleene (1967)

[2] W. Dean, S. Walsh, The Prehistory of the Subsystems of Second-order Arithmetic (2016), p.6

[3] First-order logic and automated theorem proving, Melvin Fitting, Springer, 1996 [1]

[4] Handbook of the history of logic, (Vol 5, Logic from Russell to Church), Tarski's logic by Keith Simmons, D. Gabbay and J. Woods Eds, p568 [2].

[5] Alonzo Church, [1996] (1944), Introduction to mathematical logic, page 49

[6] Hilbert, David; Ackermann, Wilhelm (1950) [1937], Principles of Mathematical Logic, New York: Chelsea

[7] Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 978-0-521-58713-6

[8] Barwise, Jon, ed. (1982), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1

[9] Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3

[10] Enderton, Herbert [2001] (1972), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3

[11] R. L. Simpson (1999), Essentials of Symbolic Logic, page 12

[12] Mendelson, Elliott [2010] (1964), An Introduction to Mathematical Logic (5th ed.), London: Chapman & Hall

[13] Ehrenburg 2002

[14] More technically, propositional logic using the Fitch-style calculus.

[15] Allen (1965) acknowledges the pun.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]