निर्णायकता (तर्क)
तर्क में, एक सही/गलत निर्णय समस्या निर्णायक होती है यदि सही उत्तर प्राप्त करने के लिए कोई प्रभावी तरीका मौजूद हो। शून्य-क्रम तर्क (प्रस्तावात्मक तर्क) निर्णायक है, जबकि प्रथम-क्रम तर्क | प्रथम-क्रम तर्क और उच्च-क्रम तर्क | उच्च-क्रम तर्क नहीं हैं। औपचारिक प्रणालियाँ निर्णायक होती हैं यदि उनकी वैधता (तर्क) सूत्रों (या प्रमेय) के सेट में सदस्यता प्रभावी ढंग से निर्धारित की जा सकती है। एक सिद्धांत (गणितीय तर्क) (तार्किक परिणाम के तहत वाक्यों का सेट डिडक्टिव क्लोजर) एक निश्चित तार्किक प्रणाली में निर्णायक है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि सिद्धांत में स्वैच्छिक सूत्र शामिल हैं या नहीं। कई महत्वपूर्ण समस्याएँ अनिर्णीत समस्याएँ हैं, अर्थात्, यह सिद्ध हो चुका है कि सदस्यता निर्धारित करने के लिए कोई प्रभावी तरीका (परिमित के बाद सही उत्तर देना, हालाँकि संभवतः बहुत लंबा, सभी मामलों में समय) उनके लिए मौजूद नहीं हो सकता है।
एक तार्किक प्रणाली की निर्णायकता
प्रत्येक तार्किक प्रणाली एक सिंटेक्स (तर्क)तर्क) के साथ आती है, जो अन्य बातों के अलावा औपचारिक प्रमाण की धारणा को निर्धारित करती है, और एक औपचारिक शब्दार्थ (तर्क), जो तार्किक वैधता की धारणा को निर्धारित करता है। एक प्रणाली के तार्किक रूप से मान्य सूत्रों को कभी-कभी प्रणाली के प्रमेय कहा जाता है, विशेष रूप से प्रथम-क्रम तर्क के संदर्भ में जहां गोडेल की पूर्णता प्रमेय शब्दार्थ और वाक्य-विन्यास परिणाम की समानता स्थापित करता है। अन्य सेटिंग्स में, जैसे रैखिक तर्क, सिंटैक्टिक परिणाम (प्रिवेबिलिटी) संबंध का उपयोग सिस्टम के प्रमेयों को परिभाषित करने के लिए किया जा सकता है।
एक तार्किक प्रणाली निर्णायक होती है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि क्या मनमाने सूत्र तार्किक प्रणाली के प्रमेय हैं। उदाहरण के लिए, प्रस्तावपरक तर्क निर्णायक है, क्योंकि सत्य तालिका | सत्य-सारणी पद्धति का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि क्या एक मनमाना तर्कवाक्य सूत्र तार्किक रूप से मान्य है।
प्रथम-क्रम तर्क सामान्य रूप से निर्णायक नहीं होता है; विशेष रूप से, किसी भी हस्ताक्षर (तर्क) में तार्किक वैधताओं का सेट जिसमें समानता शामिल है और दो या अधिक तर्कों के साथ कम से कम एक अन्य विधेय निर्णायक नहीं है।[1] प्रथम-क्रम तर्क को विस्तारित करने वाली तार्किक प्रणालियाँ, जैसे कि द्वितीय-क्रम तर्क और प्रकार सिद्धांत, भी अनिर्णीत हैं।
पहचान के साथ मोनडिक विधेय कलन की वैधता, हालांकि, निर्णायक हैं। यह प्रणाली प्रथम-क्रम तर्क है जो उन हस्ताक्षरों तक सीमित है जिनके पास कोई फ़ंक्शन प्रतीक नहीं है और समानता के अलावा जिनके संबंध प्रतीक कभी भी एक से अधिक तर्क नहीं लेते हैं।
कुछ तार्किक प्रणालियाँ अकेले प्रमेयों के समुच्चय द्वारा पर्याप्त रूप से प्रदर्शित नहीं होती हैं। (उदाहरण के लिए, त्रिगुट तर्क | क्लेन के तर्क में कोई प्रमेय नहीं है।) ऐसे मामलों में, तार्किक प्रणाली की निर्णायकता की वैकल्पिक परिभाषाओं का अक्सर उपयोग किया जाता है, जो सूत्रों की वैधता की तुलना में कुछ अधिक सामान्य निर्धारित करने के लिए एक प्रभावी विधि की मांग करती हैं; उदाहरण के लिए, अनुक्रमों की वैधता, या तार्किक परिणाम {(जी, ए) | Г ⊧ A} तर्क।
एक सिद्धांत की निश्चितता
एक सिद्धांत (गणितीय तर्क) सूत्रों का एक समूह है, जिसे अक्सर तार्किक परिणाम के तहत बंद माना जाता है। एक सिद्धांत के लिए निर्णायकता इस बात से संबंधित है कि क्या कोई प्रभावी प्रक्रिया है जो यह तय करती है कि सूत्र सिद्धांत का सदस्य है या नहीं, सिद्धांत के हस्ताक्षर में एक मनमाना सूत्र दिया गया है। निर्णायकता की समस्या स्वाभाविक रूप से तब उत्पन्न होती है जब सिद्धांत को सिद्धांतों के एक निश्चित सेट के तार्किक परिणामों के सेट के रूप में परिभाषित किया जाता है।
सिद्धांतों की निर्णायकता के बारे में कई बुनियादी परिणाम हैं। प्रत्येक (गैर-परासंगत तर्क ) असंगत सिद्धांत निर्णायक है, क्योंकि सिद्धांत के हस्ताक्षर में प्रत्येक सूत्र एक तार्किक परिणाम होगा, और इस प्रकार सिद्धांत का एक सदस्य होगा। प्रत्येक पूर्ण सिद्धांत पुनरावर्ती गणना योग्य प्रथम-क्रम सिद्धांत निर्णायक है। एक निर्णायक सिद्धांत का विस्तार निर्णायक नहीं हो सकता है। उदाहरण के लिए, प्रस्तावपरक तर्क में अनिर्णीत सिद्धांत हैं, हालांकि वैधताओं का सेट (सबसे छोटा सिद्धांत) निर्णायक है।
एक सुसंगत सिद्धांत जिसमें संपत्ति है कि प्रत्येक सुसंगत विस्तार अनिर्णीत है, अनिवार्य रूप से अनिर्णीत कहा जाता है। वास्तव में, हर सुसंगत विस्तार अनिवार्य रूप से अनिर्णीत होगा। क्षेत्रों का सिद्धांत अनिर्णीत है लेकिन अनिवार्य रूप से अनिर्णीत नहीं है। रॉबिन्सन अंकगणित अनिवार्य रूप से अनिर्णीत होने के लिए जाना जाता है, और इस प्रकार हर सुसंगत सिद्धांत जिसमें रॉबिन्सन अंकगणित शामिल है या व्याख्या करता है, वह भी (अनिवार्य रूप से) अनिर्णीत है।
निर्णायक प्रथम-क्रम के सिद्धांतों के उदाहरणों में वास्तविक बंद क्षेत्रों का सिद्धांत और प्रेस्बर्गर अंकगणित शामिल हैं, जबकि समूह का सिद्धांत (गणित) और रॉबिन्सन अंकगणित अनिर्णीत सिद्धांतों के उदाहरण हैं।
कुछ निर्णायक सिद्धांत
कुछ निर्णायक सिद्धांतों में शामिल हैं (मोंक 1976, पृष्ठ 234):[2]* 1915 में लियोपोल्ड लोवेनहेम द्वारा स्थापित केवल समानता के साथ हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का सेट।
- 1959 में Ehrenfeucht द्वारा स्थापित समानता और एक एकल कार्य के साथ एक हस्ताक्षर में प्रथम-क्रम तार्किक वैधता का सेट।
- समानता और जोड़ के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे प्रेस्बर्गर अंकगणित भी कहा जाता है। पूर्णता 1929 में Mojzesz Presburger द्वारा स्थापित की गई थी।
- समानता और गुणन के साथ हस्ताक्षर में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे स्कोलेम अंकगणित भी कहा जाता है।
- 1940 में अल्फ्रेड टार्स्की द्वारा स्थापित बूलियन बीजगणित के पहले क्रम के सिद्धांत को विहित रूप से परिभाषित किया गया (1940 में पाया गया लेकिन 1949 में घोषित किया गया)।
- तर्स्की द्वारा 1949 में स्थापित दी गई विशेषता (बीजगणित) के बीजगणितीय रूप से बंद क्षेत्रों का पहला क्रम सिद्धांत।
- वास्तविक संख्या के प्रथम-क्रम सिद्धांत की निर्णायकता | वास्तविक-बंद आदेशित क्षेत्रों का प्रथम-क्रम सिद्धांत, टार्स्की-सीडेनबर्ग प्रमेय (टार्स्की की घातीय कार्य समस्या भी देखें)।
- 1949 में टार्स्की द्वारा स्थापित यूक्लिडियन ज्यामिति का प्रथम-क्रम सिद्धांत।
- एबेलियन समूहों का प्रथम-क्रम सिद्धांत, 1955 में स्ज़मील्यू द्वारा स्थापित किया गया।
- 1959 में श्वाभौसर द्वारा स्थापित अतिपरवलयिक ज्यामिति का प्रथम-क्रम सिद्धांत।
- 1980 के दशक से लेकर आज तक सेट थ्योरी की विशिष्ट निर्णायक उपभाषाओं की जांच की गई। (कैंटोन एट अल।, 2001)
- सन्यासी दूसरे क्रम का तर्क | वृक्ष का द्वित्तीय क्रम सिद्धांत (ग्राफ़ सिद्धांत) (S2S (गणित) देखें)।
निर्णायकता स्थापित करने के लिए उपयोग की जाने वाली विधियों में क्वांटिफायर उन्मूलन, मॉडल पूर्णता और लोश-वॉच टेस्ट शामिल हैं।
कुछ अनिर्णीत सिद्धांत
कुछ अनिर्णीत सिद्धांतों में शामिल हैं (मोंक 1976, पृष्ठ 279):[2]
- समानता के साथ किसी भी पहले-क्रम के हस्ताक्षर में तार्किक वैधताओं का सेट और या तो: 2 से कम नहीं, या दो यूनरी फ़ंक्शन प्रतीकों, या 2 से कम नहीं, 1953 में बोरिस ट्रेचटेनब्रॉट द्वारा स्थापित एरिटी का एक संबंध प्रतीक .
- 1949 में टार्स्की और आंद्रेज मोस्टोव्स्की द्वारा स्थापित योग, गुणन और समानता के साथ प्राकृतिक संख्याओं का पहला क्रम सिद्धांत।
- 1949 में जूलिया रॉबिन्सन द्वारा स्थापित जोड़, गुणा और समानता के साथ परिमेय संख्याओं का प्रथम-क्रम सिद्धांत।
- 1953 में अल्फ्रेड टार्स्की द्वारा स्थापित समूहों का पहला क्रम सिद्धांत।[3] उल्लेखनीय रूप से, न केवल समूहों का सामान्य सिद्धांत अनिर्णीत है, बल्कि कई और विशिष्ट सिद्धांत भी हैं, उदाहरण के लिए (जैसा कि माल्सेव 1961 द्वारा स्थापित) परिमित समूहों का सिद्धांत। मालसेव ने यह भी स्थापित किया कि अर्धसमूहों का सिद्धांत और छल्लों का सिद्धांत अनिर्णीत हैं। रॉबिन्सन ने 1949 में स्थापित किया कि क्षेत्रों का सिद्धांत अनिर्णीत है।
- रॉबिन्सन अंकगणित (और इसलिए कोई भी सुसंगत विस्तार, जैसे पीनो अंकगणित) अनिवार्य रूप से अनिर्णीत है, जैसा कि 1950 में राफेल रॉबिन्सन द्वारा स्थापित किया गया था।
- समानता और दो कार्य प्रतीकों के साथ प्रथम-क्रम सिद्धांत[4]
व्याख्यात्मकता पद्धति का उपयोग अक्सर सिद्धांतों की अनिश्चितता को स्थापित करने के लिए किया जाता है। यदि एक अनिवार्य रूप से अनिर्णीत सिद्धांत टी एक सुसंगत सिद्धांत एस में व्याख्या योग्य है, तो एस भी अनिवार्य रूप से अनिर्णीत है। यह कम्प्यूटेबिलिटी सिद्धांत में कई-एक कमी की अवधारणा से निकटता से संबंधित है।
अर्ध-अम्लता
एक सिद्धांत या तार्किक प्रणाली की एक संपत्ति जो निर्णायकता से कमजोर है, अर्ध-निर्णायकता है। एक सिद्धांत अर्धनिर्णीत होता है यदि कोई प्रभावी तरीका है, जो एक मनमाना सूत्र दिया जाता है, हमेशा सिद्धांत में सूत्र होने पर सही ढंग से बताएगा, लेकिन सिद्धांत में सूत्र नहीं होने पर या तो नकारात्मक उत्तर दे सकता है या कोई उत्तर नहीं दे सकता है। यदि प्रमेय (और केवल प्रमेय) उत्पन्न करने के लिए एक प्रभावी विधि है, तो प्रत्येक प्रमेय अंततः उत्पन्न होगा, तो एक तार्किक प्रणाली अर्ध-निर्णायक है। यह निर्णायकता से अलग है क्योंकि एक अर्धनिर्णायक प्रणाली में यह जाँचने के लिए कोई प्रभावी प्रक्रिया नहीं हो सकती है कि कोई सूत्र नहीं एक प्रमेय है।
प्रत्येक निर्णायक सिद्धांत या तार्किक प्रणाली अर्ध-निर्णायक होती है, लेकिन सामान्य तौर पर इसका विलोम सत्य नहीं होता है; एक सिद्धांत निर्णायक है अगर और केवल अगर यह और इसके पूरक दोनों अर्ध-निर्णायक हैं। उदाहरण के लिए, पहले क्रम के तर्क की तार्किक वैधता का सेट वी अर्ध-निर्णायक है, लेकिन निर्णायक नहीं है। इस मामले में, ऐसा इसलिए है क्योंकि मनमानी सूत्र ए के निर्धारण के लिए कोई प्रभावी तरीका नहीं है कि क्या ए वी में नहीं है। इसी तरह, प्रथम-क्रम के स्वयंसिद्धों के किसी भी पुनरावर्ती गणना योग्य सेट के तार्किक परिणामों का सेट अर्ध-निर्णायक है। ऊपर दिए गए अनिर्णीत प्रथम-क्रम सिद्धांतों के कई उदाहरण इस रूप के हैं।
पूर्णता से संबंध
निर्णायकता को पूर्ण सिद्धांत के साथ भ्रमित नहीं होना चाहिए। उदाहरण के लिए, बीजगणितीय रूप से बंद क्षेत्रों का सिद्धांत निर्णायक है, लेकिन अधूरा है, जबकि + और × वाली भाषा में गैर-नकारात्मक पूर्णांकों के बारे में सभी सत्य प्रथम-क्रम कथनों का सेट पूर्ण है लेकिन अनिर्णीत है। दुर्भाग्य से, एक पारिभाषिक अस्पष्टता के रूप में, अनिर्णीत कथन शब्द को कभी-कभी स्वतंत्रता (गणितीय तर्क) के पर्याय के रूप में प्रयोग किया जाता है।
कम्प्यूटेबिलिटी से संबंध
एक निर्णायक सेट की अवधारणा के साथ, एक निर्णायक सिद्धांत या तार्किक प्रणाली की परिभाषा या तो प्रभावी तरीकों या गणना योग्य कार्यों के संदर्भ में दी जा सकती है। इन्हें आम तौर पर प्रति चर्च की थीसिस के बराबर माना जाता है। वास्तव में, सबूत है कि एक तार्किक प्रणाली या सिद्धांत अनिर्णीत है, कम्प्यूटेबिलिटी की औपचारिक परिभाषा का उपयोग यह दिखाने के लिए करेगा कि एक उपयुक्त सेट एक निर्णायक सेट नहीं है, और फिर चर्च की थीसिस को यह दिखाने के लिए आमंत्रित करें कि सिद्धांत या तार्किक प्रणाली किसी भी प्रभावी द्वारा निर्णायक नहीं है। विधि (एंडर्टन 2001, पीपी। 206ff।)।
खेलों के संदर्भ में
कुछ खेलों को उनकी निर्णायकता के अनुसार वर्गीकृत किया गया है:
- शतरंज निर्णायक है।[5][6] सटीक जानकारी वाले अन्य सभी परिमित दो-खिलाड़ी खेलों के लिए भी यही है।
- अनंत शतरंज में एन में मेट (नियमों और गेमपीस पर सीमाओं के साथ) निर्णायक है।[7][8] हालांकि, ऐसे स्थान हैं (बहुत सारे टुकड़ों के साथ) जो जीतने के लिए मजबूर हैं, लेकिन किसी परिमित एन के लिए एन में दोस्त नहीं हैं।[9]
- परिमित बोर्ड (लेकिन असीमित समय के साथ) पर अपूर्ण जानकारी वाले कुछ टीम गेम अनिर्णीत हैं।[10]
यह भी देखें
संदर्भ
टिप्पणियाँ
- ↑ Trakhtenbrot, 1953 .
- ↑ 2.0 2.1 Monk, Donald (1976). गणितीय तर्क. Springer. ISBN 9780387901701.
- ↑ Tarski, A.; Mostovski, A.; Robinson, R. (1953), Undecidable Theories, Studies in Logic and the Foundation of Mathematics, North-Holland, Amsterdam, ISBN 9780444533784
- ↑ Gurevich, Yuri (1976). "मानक कक्षाओं के लिए निर्णय समस्या". J. Symb. Log. 41 (2): 460–464. CiteSeerX 10.1.1.360.1517. doi:10.1017/S0022481200051513. S2CID 798307. Retrieved 5 August 2014.
- ↑ Stack Exchange Computer Science. "Is chess game movement TM decidable?"
- ↑ Undecidable Chess Problem?
- ↑ Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board
- ↑ Brumleve, Dan; Hamkins, Joel David; Schlicht, Philipp (2012). "The Mate-in-n Problem of Infinite Chess Is Decidable". यूरोप में कम्प्यूटेबिलिटी पर सम्मेलन. Lecture Notes in Computer Science. Vol. 7318. Springer. pp. 78–88. arXiv:1201.5597. doi:10.1007/978-3-642-30870-3_9. ISBN 978-3-642-30870-3. S2CID 8998263.
- ↑ "Lo.logic – Checkmate in $\omega$ moves?".
- ↑ Poonen, Bjorn (2014). "10. Undecidable Problems: A Sampler: §14.1 Abstract Games". In Kennedy, Juliette (ed.). Interpreting Gödel: Critical Essays. Cambridge University Press. pp. 211–241 See p. 239. arXiv:1204.0299. CiteSeerX 10.1.1.679.3322. ISBN 9781107002661.}
ग्रन्थसूची
- Barwise, Jon (1982), "Introduction to first-order logic", in Barwise, Jon (ed.), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
- Cantone, D.; Omodeo, E. G.; Policriti, A. (2013) [2001], Set Theory for Computing. From Decision Procedures to Logic Programming with Sets, Monographs in Computer Science, Springer, ISBN 9781475734522
- Chagrov, Alexander; Zakharyaschev, Michael (1997), Modal logic, Oxford Logic Guides, vol. 35, Oxford University Press, ISBN 978-0-19-853779-3, MR 1464942
- Davis, Martin (2013) [1958], Computability and Unsolvability, Dover, ISBN 9780486151069
- Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Academic Press, ISBN 978-0-12-238452-3
- Keisler, H. J. (1982), "Fundamentals of model theory", in Barwise, Jon (ed.), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
- Monk, J. Donald (2012) [1976], Mathematical Logic, Springer-Verlag, ISBN 9781468494525
