पूर्णता (तर्क)

Not to be confused with Complete (complexity).

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

पूर्णता से संबंधित अन्य गुण

Main articles: Soundness and Consistency

संपत्ति बातचीत (तर्क) # पूर्णता के लिए स्पष्ट बातचीत को ध्वनि कहा जाता है: एक प्रणाली एक संपत्ति के संबंध में ध्वनि है (ज्यादातर शब्दार्थ वैधता) यदि उसके प्रत्येक प्रमेय में वह संपत्ति है।

पूर्णता के रूप

अभिव्यंजक पूर्णता

एक औपचारिक भाषा अभिव्यंजक रूप से पूर्ण होती है यदि वह उस विषय वस्तु को व्यक्त कर सकती है जिसके लिए उसका इरादा है।

कार्यात्मक पूर्णता

Main article: Functional completeness

एक औपचारिक प्रणाली से जुड़े तार्किक संयोजकों का एक सेट कार्यात्मक पूर्णता है यदि यह सभी प्रस्तावित कार्यों को व्यक्त कर सकता है।

शब्दार्थ पूर्णता

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

$\models _{\mathcal {S}}\varphi \ \to \ \vdash _{\mathcal {S}}\varphi .$

उदाहरण के लिए, गोडेल की पूर्णता प्रमेय प्रथम-क्रम तर्क के लिए सिमेंटिक पूर्णता स्थापित करता है।

मजबूत पूर्णता

एक औपचारिक प्रणाली S मजबूत अर्थों में पूर्ण या पूर्ण है यदि परिसर Γ के प्रत्येक सेट के लिए, Γ से अर्थपूर्ण रूप से अनुसरण करने वाला कोई सूत्र Γ से व्युत्पन्न है। वह है:

$\Gamma \models _{\mathcal {S}}\varphi \ \to \ \Gamma \vdash _{\mathcal {S}}\varphi .$

खंडन पूर्णता

एक औपचारिक प्रणाली S खंडन-पूर्ण है यदि यह सूत्रों के प्रत्येक असंतुष्ट सेट से झूठा (तर्क) प्राप्त करने में सक्षम है। वह है,

$\Gamma \models _{\mathcal {S}}\bot \to \ \Gamma \vdash _{\mathcal {S}}\bot .$

प्रत्येक दृढ़ता से पूर्ण प्रणाली भी खंडन-पूर्ण है। सहज रूप से, मजबूत पूर्णता का अर्थ है कि, एक सूत्र सेट दिया गया है $\Gamma$, प्रत्येक शब्दार्थ परिणाम की गणना करना संभव है $\varphi$ का $\Gamma$, जबकि खंडन-पूर्णता का अर्थ है कि, एक सूत्र सेट दिया गया है $\Gamma$ और एक सूत्र $\varphi$, यह जांचना संभव है कि क्या $\varphi$ का शब्दार्थ परिणाम है $\Gamma$.

खंडन-पूर्ण प्रणालियों के उदाहरणों में शामिल हैं: हॉर्न क्लॉज पर एसएलडी संकल्प, इक्वेशनल क्लॉज़ल फ़र्स्ट-ऑर्डर लॉजिक पर सुपरपोजिशन कैलकुलस, रिज़ॉल्यूशन (तर्क) # फ़र्स्ट ऑर्डर लॉजिक में रिज़ॉल्यूशन | क्लॉज़ (लॉजिक) सेट पर रॉबिन्सन का रिज़ॉल्यूशन। उत्तरार्द्ध दृढ़ता से पूर्ण नहीं है: उदा। $\{a\}\models a\lor b$ प्रथम-क्रम तर्क के प्रस्तावनात्मक उपसमुच्चय में भी धारण करता है, परंतु $a\lor b$ से प्राप्त नहीं किया जा सकता $\{a\}$ संकल्प द्वारा। हालाँकि, $\{a,\lnot (a\lor b)\}\vdash \bot$ प्राप्त किया जा सकता है।

वाक्यात्मक पूर्णता

एक औपचारिक प्रणाली S सिंटैक्टिक रूप से पूर्ण या निगमनात्मक रूप से पूर्ण या अधिकतम पूर्ण है यदि प्रत्येक वाक्य (गणितीय तर्क) (बंद सूत्र) के लिए सिस्टम की भाषा का φ या तो φ या ¬φ का एक प्रमेय है S. इसे कम्प्लीट_थ्योरी भी कहा जाता है, और सिमेंटिक पूर्णता से अधिक मजबूत है। एक अन्य अर्थ में, एक औपचारिक प्रणाली वाक्य रचनात्मक रूप से पूर्ण होती है यदि और केवल तभी जब असंगतता को पेश किए बिना इसमें कोई अप्रमाणित वाक्य नहीं जोड़ा जा सकता है। प्रस्तावक कलन | ट्रुथ-फंक्शनल प्रोपोज़िशनल लॉजिक और फ़र्स्ट-ऑर्डर लॉजिक | फ़र्स्ट-ऑर्डर प्रेडिकेट लॉजिक सिमेंटिक रूप से पूर्ण हैं, लेकिन सिंटैक्टिक रूप से पूर्ण नहीं हैं (उदाहरण के लिए, प्रोपोज़िशनल लॉजिक स्टेटमेंट जिसमें एकल प्रोपोज़िशनल वेरिएबल A शामिल है, एक प्रमेय नहीं है, और न ही है इसका निषेध)। गोडेल की अपूर्णता प्रमेय | गोडेल की अपूर्णता प्रमेय से पता चलता है कि कोई भी पुनरावर्ती प्रणाली जो पर्याप्त रूप से शक्तिशाली है, जैसे कि पीनो अंकगणित, सुसंगत और वाक्य-विन्यास दोनों पूर्ण नहीं हो सकती है।

संरचनात्मक पूर्णता

Main article: admissible rule

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