संतोषप्रदता: Difference between revisions

Latest revision as of 16:15, 30 October 2023

गणितीय तर्क में, उचित रूप से निर्मित सूत्र संतोषप्रदता है यदि यह इसके चर (गणित) के मूल्यों के कुछ असाइनमेंट के अनुसार सत्य है। उदाहरण के लिए, सूत्र $x+3=y$ संतोषप्रदता है क्योंकि जब $x=3$ एवं $y=6$ , एवं सूत्र $x+1=x$ पूर्णांकों पर संतुष्ट नहीं है। संतुष्टि के लिए दोहरी अवधारणा वैधता है; सूत्र मान्य है यदि इसके चर के मानों का प्रत्येक असाइनमेंट सूत्र को सत्य बनाता है। उदाहरण के लिए, $x+3=3+x$ पूर्णांक मान्य है, किन्तु $x+3=y$ क्या पूर्णांक मान्य नहीं है।

औपचारिक रूप से, अनुमत प्रतीकों के सिंटेक्स (तर्क) को परिभाषित करने वाले निश्चित तर्क के संबंध में संतुष्टि का अध्ययन किया जाता है, जैसे प्रथम-क्रम तर्क, द्वितीय-क्रम तर्क या प्रस्तावपरक कलन चूंकि, वाक्यात्मक होने के अतिरिक्त, संतुष्टि शब्दार्थ गुण है क्योंकि यह प्रतीकों के अर्थ से संबंधित है, उदाहरण के लिए, $+$ का अर्थ, जैसे सूत्र में $x+1=x$ है। औपचारिक रूप से, हम व्याख्या (तर्क) (या प्रतिमान सिद्धांत) को परिभाषित करते हैं, जो चर के लिए मूल्यों का असाइनमेंट है एवं अन्य सभी गैर-तार्किक प्रतीकों के लिए अर्थ का असाइनमेंट है, एवं सूत्र को संतोषप्रदता कहा जाता है यदि कुछ व्याख्या स्पष्टता प्रदर्शित करती है।^[1] जबकि यह प्रतीकों की गैर-मानक व्याख्याओं की अनुमति देता है जैसे $+$ , अतिरिक्त अभिगृहीत प्रदान करके उनके अर्थ को सीमित किया जा सकता है। संतुष्टि मोडुलो में सिद्धांत (गणितीय तर्क) के संबंध में सूत्र की संतुष्टि पर विचार किया जाता है, जो स्वयंसिद्ध का (परिमित या अनंत) उपसमुच्चय है।

संतुष्टि एवं वैधता को सूत्र के लिए परिभाषित किया गया है, किन्तु सिद्धांत या सूत्रों के उपसमुच्चय के लिए सामान्यीकृत किया जा सकता है, सिद्धांत संतोषप्रदता है यदि कम से कम व्याख्या सिद्धांत में प्रत्येक सूत्र को सत्य बनाती है, एवं मान्य होते है यदि व्याख्या में प्रत्येक सूत्र सत्य है, उदाहरण के लिए, अंकगणित के सिद्धांत जैसे पीनो अभिगृहीत संतोषप्रदता हैं क्योंकि वे प्राकृतिक संख्याओं में सत्य होते हैं। यह अवधारणा सिद्धांत की संगति के निकटता से संबंधित है, एवं वास्तव में प्रथम-क्रम तर्क के लिए संगति के समान होते है, परिणाम जिसे गोडेल की पूर्णता प्रमेय के रूप में जाना जाता है। संतुष्टि की अस्वीकृति असंतोषप्रदताता है, एवं वैधता की उपेक्षा अमान्यता है। ये चार अवधारणाएं उसी प्रकार से संबंधित हैं जैसे कि अरस्तू के विरोध के वर्ग के समान हैं।

प्रस्तावपरक तर्क में कोई सूत्र संतोषप्रदता है या नहीं, यह निर्धारित करने की निर्णय समस्या ही निर्णायक समस्या है, एवं इसे बूलियन संतुष्टि समस्या या सैट के रूप में जाना जाता है। सामान्यतः, यह निर्धारित करने की समस्या हैं, कि क्या प्रथम-क्रम तर्क का वाक्य संतोषप्रदता है या निर्णायक नहीं है। सार्वभौमिक बीजगणित, समीकरण सिद्धांत एवं स्वचालित प्रमेय प्रमाणित करने में, शब्द पुनर्लेखन, सर्वांगसमता संवृत करने एवं एकीकरण (कंप्यूटर विज्ञान) की प्रविधियों का उपयोग संतोषप्रदताता निर्धारित करने के लिए किया जाता है। कोई विशेष सिद्धांत (तर्क) निर्णायक है या नहीं यह निर्भर करता है कि सिद्धांत चर-मुक्त है।^[2]

वैधता की संतुष्टि में कमी

नकारात्मकता के साथ क्लासिकल तर्क शास्त्र के लिए, सामान्यतः सूत्र की वैधता के प्रश्न को व्यक्त करना संभव है, क्योंकि विपक्ष के उपरोक्त वर्ग में व्यक्त अवधारणाओं के मध्य संबंधों के कारण संतुष्टि सम्मिलित है। विशेष रूप से φ मान्य है एवं यदि ¬φ असंतुष्ट है, जिसका अर्थ त्रुटिपूर्ण ¬φ संतोषप्रदता है। एवं यदि ¬φ अमान्य है।

निषेध के बिना तर्कशास्त्र के लिए, जैसे कि तर्क प्रणालियों की सूची सकारात्मक प्रस्तावपरक कलन, वैधता एवं संतुष्टि के प्रश्न असंबंधित हो सकते हैं। तर्क प्रणालियों की सूची के विषय में सकारात्मक प्रस्ताविक कलन, संतुष्टि की समस्या तुच्छ है, क्योंकि प्रत्येक सूत्र संतोषप्रदता है, जबकि वैधता की समस्या सह-एनपी-पूर्ण है।

क्लासिकल लॉजिक के लिए प्रस्तावित संतुष्टि

क्लासिकल प्रस्तावपरक तर्क के विषय में सूत्रों के लिए संतुष्टि निर्णायक है। विशेष रूप से, संतुष्टि एनपी-पूर्ण समस्या है, एवं कम्प्यूटेशनल जटिलता सिद्धांत में सबसे गहन अध्ययन वाली समस्याओं में से है।

प्रथम क्रम के तर्क में संतुष्टि

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

प्रतिमान सिद्धांत में संतुष्टि

प्रतिमान सिद्धांत में, परमाणु सूत्र संतोषप्रदता होता है यदि संरचना (तर्क) के तत्वों का संग्रह होता है जो सूत्र को सत्य बनाता है।^[4] यदि A संरचना है, φ सूत्र है, एवं a तत्वों का संग्रह है, जो संरचना से लिया गया है, जो φ को संतुष्ट करता है, तो सामान्यतः यह लिखा जाता है कि

A ⊧ φ [a]

यदि φ का कोई मुक्त चर नहीं है, अर्थात, यदि φ परमाणु वाक्य है, एवं यह A से संतुष्ट है, तो इस प्रकार लिखा जाता है,

A ⊧ φ

इस विषय में, यह भी कहा जाता है कि A, φ के लिए प्रतिमान में φ A में सत्य है। यदि T, A द्वारा संतुष्ट परमाणु वाक्यों का संग्रह है, तो इस प्रकार लिखा जाता है,

A ⊧ T

परिमित संतुष्टि

संतुष्टि से संबंधित समस्या परिमित संतुष्टि है, जो यह निर्धारित करने का प्रश्न है कि क्या कोई सूत्र परिमित प्रतिमान को स्वीकार करता है जो इसे सत्य बनाता है। तर्क के लिए जिसमें परिमित प्रतिमान संपत्ति है, संतुष्टि एवं परिमित संतुष्टि की समस्याएं होती हैं, क्योंकि उस तर्क के सूत्र के पास प्रतिमान है यदि केवल उसके पास परिमित प्रतिमान है, तो परिमित प्रतिमान सिद्धांत के गणितीय क्षेत्र में यह प्रश्न महत्वपूर्ण है।

परिमित संतुष्टि को सामान्य रूप से युग्मित नहीं होना चाहिए। उदाहरण के लिए, निम्नलिखित वाक्यों के तार्किक संयोजन के रूप में प्राप्त प्रथम-क्रम तर्क सूत्र पर विचार करें, जहाँ $a_{0}$ एवं $a_{1}$ तार्किक स्थिरांक हैं।

$R(a_{0},a_{1})$
$\forall xy(R(x,y)\rightarrow \exists zR(y,z))$
$\forall xyz(R(y,x)\wedge R(z,x)\rightarrow y=z))$
$\forall x\neg R(x,a_{0})$

परिणामी सूत्र में अनंत प्रतिमान $R(a_{0},a_{1}),R(a_{1},a_{2}),\ldots$ है , किन्तु यह दिखाया जा सकता है कि इसका कोई परिमित प्रतिमान नहीं है (तथ्य से प्रारम्भ $R(a_{0},a_{1})$ एवं $R$ की श्रंखला का पालन कर रहा है, परमाणु सूत्र जो दूसरे स्वयंसिद्ध द्वारा उपस्थित होना चाहिए, प्रतिमान की परिमितता के लिए लूप के अस्तित्व की आवश्यकता होगी, जो तीसरे एवं चौथे स्वयं सिद्धों का उल्लंघन करेगा, चाहे वह वापस लूप हो $a_{0}$ या भिन्न तत्व को हो।

किसी दिए गए तर्क में इनपुट सूत्र के लिए संतुष्टि का निर्णय लेने का कम्प्यूटेशनल जटिलता सिद्धांत परिमित संतुष्टि का निर्णय लेने से भिन्न हो सकता है; वास्तव में, कुछ तर्क के लिए, उनमें से केवल निर्धारणीय (तर्क) है।

क्लासिकल प्रथम-क्रम तर्क के लिए, परिमित संतुष्टि गणनात्मक रूप से गणना योग्य है (कक्षा आरई (जटिलता) में) एवं ट्रैखटेनब्रॉट के प्रमेय द्वारा अनिर्णीत समस्या सूत्र की अस्वीकृति पर प्रारम्भ होती है।

संख्यात्मक बाधाएँ

प्रायः गणितीय अनुकूलन के क्षेत्र में दिखाई देते हैं, जहां कोई सामान्यतः कुछ बाधाओं के अधीन उद्देश्य फंक्शन को अधिकतम करना चाहता है। चूंकि, वस्तुनिष्ठ फ़ंक्शन को त्यागकर, केवल यह निर्धारित करने का मूल विषय कि क्या बाधाएं संतोषप्रदता हैं, कुछ समायोजन में अनिर्णीत हो सकती हैं। निम्न तालिका मुख्य विषयो को सारांशित करती है।

प्रतिबंध	वास्तविक से अधिक	पूर्णांकों पर
रेखीय	पी.टाइम (रैखिक प्रोग्रामिंग देखें))	एनपी-पूर्ण (पूर्णांक प्रोग्रामिंग देखें)
बहुपद	उदा के माध्यम से निर्णय लेने योग्य बेलनाकार बीजगणितीय अपघटन	अनिर्णीत (हिल्बर्ट की दसवीं समस्या))

तालिका स्रोत: बॉकमायर एवं वीस्पफेनिंग।^[5]^: 754

रैखिक बाधाओं के लिए, निम्न तालिका द्वारा पूर्ण चित्र प्रदान किया गया है।

प्रतिबंध समाप्त	परिमेय	पूर्णांक	प्राकृतिक संख्या
रेखीय समीकरण	पी.टाइम	पीटाइम	एन पी-सम्पूर्ण
रैखिक असमानताएँ	पी.टाइम	एन पी-सम्पूर्ण	एन पी-सम्पूर्ण

तालिका स्रोत: बॉकमायर एवं वीस्पफेनिंग।^[5]^: 755

यह भी देखें

2-संतुष्टि
बूलियन संतुष्टि समस्या
सर्किट संतुष्टि
कार्प की 21 एनपी-पूर्ण समस्याएँ
वैधता (तर्क)
संयमित संतोष

↑ Boolos, Burgess & Jeffrey 2007, p. 120: "A set of sentences [...] is satisfiable if some interpretation [makes it true].".
↑ Franz Baader; Tobias Nipkow (1998). टर्म पुनर्लेखन और वह सब. Cambridge University Press. pp. 58–92. ISBN 0-521-77920-0.
↑ Baier, Christel (2012). "Chapter 1.3 Undecidability of FOL". Lecture Notes — Advanced Logics. Technische Universität Dresden — Institute for Technical Computer Science. pp. 28–32. Archived from the original (PDF) on 14 October 2020. Retrieved 21 July 2012.
↑ Wilifrid Hodges (1997). एक छोटा मॉडल सिद्धांत. Cambridge University Press. p. 12. ISBN 0-521-58713-1.
↑ ^5.0 ^5.1 Alexander Bockmayr; Volker Weispfenning (2001). "Solving Numerical Constraints". In John Alan Robinson; Andrei Voronkov (eds.). स्वचालित रीज़निंग वॉल्यूम I की हैंडबुक. Elsevier and MIT Press. ISBN 0-444-82949-0. (Elsevier) (MIT Press).

संदर्भ

Boolos, George; Burgess, John; Jeffrey, Richard (2007). Computability and Logic (5th ed.). Cambridge University Press.

अग्रिम पठन

Daniel Kroening; Ofer Strichman (2008). Decision Procedures: An Algorithmic Point of View. Springer Science & Business Media. ISBN 978-3-540-74104-6.
A. Biere; M. Heule; H. van Maaren; T. Walsh, eds. (2009). Handbook of Satisfiability. IOS Press. ISBN 978-1-60750-376-7.

[FOOTNOTEBoolosBurgessJeffrey2007p._120:_"A_set_of_sentences_[...]_is_''satisfiable''_if_some_interpretation_[makes_it_true]."-1] Boolos, Burgess & Jeffrey 2007, p. 120: "A set of sentences [...] is satisfiable if some interpretation [makes it true].".

[2] Franz Baader; Tobias Nipkow (1998). टर्म पुनर्लेखन और वह सब. Cambridge University Press. pp. 58–92. ISBN 0-521-77920-0.

[3] Baier, Christel (2012). "Chapter 1.3 Undecidability of FOL". Lecture Notes — Advanced Logics. Technische Universität Dresden — Institute for Technical Computer Science. pp. 28–32. Archived from the original (PDF) on 14 October 2020. Retrieved 21 July 2012.

[4] Wilifrid Hodges (1997). एक छोटा मॉडल सिद्धांत. Cambridge University Press. p. 12. ISBN 0-521-58713-1.

[BockmayrWeispfenning2001-5] 5.0 ^5.1 Alexander Bockmayr; Volker Weispfenning (2001). "Solving Numerical Constraints". In John Alan Robinson; Andrei Voronkov (eds.). स्वचालित रीज़निंग वॉल्यूम I की हैंडबुक. Elsevier and MIT Press. ISBN 0-444-82949-0. (Elsevier) (MIT Press).

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
 {{Short description|Concept in mathematical logic}}
-[[गणितीय तर्क]] में, उचित रूप से निर्मित सूत्र संतोषजनक है यदि यह इसके [[चर (गणित)]] के मूल्यों के कुछ असाइनमेंट के अनुसार सत्य है। उदाहरण के लिए, सूत्र <math>x+3=y</math> संतोषजनक है क्योंकि जब <math>x=3</math> एवं <math>y=6</math>, एवं सूत्र <math>x+1=x</math> पूर्णांकों पर संतुष्ट नहीं है। संतुष्टि के लिए दोहरी अवधारणा [[वैधता (तर्क)|वैधता]] है; सूत्र मान्य है यदि इसके चर के मानों का प्रत्येक असाइनमेंट सूत्र को सत्य बनाता है। उदाहरण के लिए, <math>x+3=3+x</math> पूर्णांक मान्य है, किन्तु <math>x+3=y</math> क्या पूर्णांक मान्य नहीं है।
+[[गणितीय तर्क]] में, उचित रूप से निर्मित सूत्र '''संतोषप्रदता''' है यदि यह इसके [[चर (गणित)]] के मूल्यों के कुछ असाइनमेंट के अनुसार सत्य है। उदाहरण के लिए, सूत्र <math>x+3=y</math> संतोषप्रदता है क्योंकि जब <math>x=3</math> एवं <math>y=6</math>, एवं सूत्र <math>x+1=x</math> पूर्णांकों पर संतुष्ट नहीं है। संतुष्टि के लिए दोहरी अवधारणा [[वैधता (तर्क)|वैधता]] है; सूत्र मान्य है यदि इसके चर के मानों का प्रत्येक असाइनमेंट सूत्र को सत्य बनाता है। उदाहरण के लिए, <math>x+3=3+x</math> पूर्णांक मान्य है, किन्तु <math>x+3=y</math> क्या पूर्णांक मान्य नहीं है।
-औपचारिक रूप से, अनुमत प्रतीकों के [[सिंटेक्स (तर्क)]] को परिभाषित करने वाले निश्चित तर्क के संबंध में संतुष्टि का अध्ययन किया जाता है, जैसे प्रथम-क्रम तर्क, द्वितीय-क्रम तर्क या प्रस्तावपरक कलन चूंकि, वाक्यात्मक होने के अतिरिक्त, संतुष्टि शब्दार्थ गुण है क्योंकि यह प्रतीकों के अर्थ से संबंधित है, उदाहरण के लिए, <math>+</math> का अर्थ, जैसे सूत्र में <math>x+1=x</math> है। औपचारिक रूप से, हम [[व्याख्या (तर्क)]] (या [[मॉडल सिद्धांत|प्रतिमान सिद्धांत]]) को परिभाषित करते हैं, जो चर के लिए मूल्यों का असाइनमेंट है एवं अन्य सभी गैर-तार्किक प्रतीकों के लिए अर्थ का असाइनमेंट है, एवं सूत्र को संतोषजनक कहा जाता है यदि कुछ व्याख्या स्पष्टता प्रदर्शित करती है।{{sfn|Boolos|Burgess|Jeffrey|2007|loc=p. 120: "A set of sentences [...] is ''satisfiable'' if some interpretation [makes it true]."}} जबकि यह प्रतीकों की गैर-मानक व्याख्याओं की अनुमति देता है जैसे <math>+</math>, अतिरिक्त अभिगृहीत प्रदान करके उनके अर्थ को सीमित किया जा सकता है। संतुष्टि मोडुलो सिद्धांतों की समस्या [[सिद्धांत (गणितीय तर्क)]] के संबंध में सूत्र की संतुष्टि पर विचार करती है, जो [[स्वयंसिद्ध]] का (परिमित या अनंत) उपसमुच्चय है।
+औपचारिक रूप से, अनुमत प्रतीकों के [[सिंटेक्स (तर्क)]] को परिभाषित करने वाले निश्चित तर्क के संबंध में संतुष्टि का अध्ययन किया जाता है, जैसे प्रथम-क्रम तर्क, द्वितीय-क्रम तर्क या प्रस्तावपरक कलन चूंकि, वाक्यात्मक होने के अतिरिक्त, संतुष्टि शब्दार्थ गुण है क्योंकि यह प्रतीकों के अर्थ से संबंधित है, उदाहरण के लिए, <math>+</math> का अर्थ, जैसे सूत्र में <math>x+1=x</math> है। औपचारिक रूप से, हम [[व्याख्या (तर्क)]] (या [[मॉडल सिद्धांत|प्रतिमान सिद्धांत]]) को परिभाषित करते हैं, जो चर के लिए मूल्यों का असाइनमेंट है एवं अन्य सभी गैर-तार्किक प्रतीकों के लिए अर्थ का असाइनमेंट है, एवं सूत्र को संतोषप्रदता कहा जाता है यदि कुछ व्याख्या स्पष्टता प्रदर्शित करती है।{{sfn|Boolos|Burgess|Jeffrey|2007|loc=p. 120: "A set of sentences [...] is ''satisfiable'' if some interpretation [makes it true]."}} जबकि यह प्रतीकों की गैर-मानक व्याख्याओं की अनुमति देता है जैसे <math>+</math>, अतिरिक्त अभिगृहीत प्रदान करके उनके अर्थ को सीमित किया जा सकता है। संतुष्टि मोडुलो में [[सिद्धांत (गणितीय तर्क)]] के संबंध में सूत्र की संतुष्टि पर विचार किया जाता है, जो [[स्वयंसिद्ध]] का (परिमित या अनंत) उपसमुच्चय है।
-संतुष्टि एवं वैधता को सूत्र के लिए परिभाषित किया गया है, किन्तु मनमाने सिद्धांत या सूत्रों के उपसमुच्चय के लिए सामान्यीकृत किया जा सकता है, सिद्धांत संतोषजनक है यदि कम से कम व्याख्या सिद्धांत में प्रत्येक सूत्र को सत्य बनाती है, एवं मान्य होते है यदि प्रत्येक व्याख्या में प्रत्येक सूत्र सत्य है, उदाहरण के लिए, अंकगणित के सिद्धांत जैसे पीनो अभिगृहीत संतोषजनक हैं क्योंकि वे प्राकृतिक संख्याओं में सत्य होते हैं। यह अवधारणा सिद्धांत की संगति से निकटता से संबंधित है, एवं वास्तव में प्रथम-क्रम तर्क के लिए संगति के समान है, परिणाम जिसे गोडेल की पूर्णता प्रमेय के रूप में जाना जाता है। संतुष्टि की अस्वीकृति असंतोषजनकता है, एवं वैधता की उपेक्षा अमान्यता है। ये चार अवधारणाएं दूसरे से ठीक उसी प्रकार से संबंधित हैं जैसे कि [[अरस्तू]] के विरोध के वर्ग के समान हैं।
+संतुष्टि एवं वैधता को सूत्र के लिए परिभाषित किया गया है, किन्तु सिद्धांत या सूत्रों के उपसमुच्चय के लिए सामान्यीकृत किया जा सकता है, सिद्धांत संतोषप्रदता है यदि कम से कम व्याख्या सिद्धांत में प्रत्येक सूत्र को सत्य बनाती है, एवं मान्य होते है यदि व्याख्या में प्रत्येक सूत्र सत्य है, उदाहरण के लिए, अंकगणित के सिद्धांत जैसे पीनो अभिगृहीत संतोषप्रदता हैं क्योंकि वे प्राकृतिक संख्याओं में सत्य होते हैं। यह अवधारणा सिद्धांत की संगति के निकटता से संबंधित है, एवं वास्तव में प्रथम-क्रम तर्क के लिए संगति के समान होते है, परिणाम जिसे गोडेल की पूर्णता प्रमेय के रूप में जाना जाता है। संतुष्टि की अस्वीकृति असंतोषप्रदताता है, एवं वैधता की उपेक्षा अमान्यता है। ये चार अवधारणाएं उसी प्रकार से संबंधित हैं जैसे कि [[अरस्तू]] के विरोध के वर्ग के समान हैं।
-प्रस्तावपरक तर्क में कोई सूत्र संतोषजनक है या नहीं, यह निर्धारित करने की [[निर्णय समस्या]] [[निर्णायक समस्या]] है, एवं इसे [[बूलियन संतुष्टि समस्या]] या SAT के रूप में जाना जाता है। सामान्यतः, यह निर्धारित करने की समस्या कि क्या प्रथम-क्रम तर्क का वाक्य संतोषजनक है, निर्णायक नहीं है। [[सार्वभौमिक बीजगणित]], [[समीकरण सिद्धांत]] एवं स्वचालित प्रमेय प्रमाणित करने में, शब्द पुनर्लेखन, सर्वांगसमता संवृत करने एवं [[एकीकरण (कंप्यूटर विज्ञान)]] की प्रविधियों का उपयोग संतोषजनकता निर्धारित करने के लिए किया जाता है। कोई विशेष [[सिद्धांत (तर्क)]] निर्णायक है या नहीं यह निर्भर करता है कि सिद्धांत चर-मुक्त है।<ref>{{cite book|author1=Franz Baader|author-link=Franz Baader|author2=Tobias Nipkow|author2-link=Tobias Nipkow|title=टर्म पुनर्लेखन और वह सब|year=1998|publisher=Cambridge University Press|isbn=0-521-77920-0|pages=58–92|url=https://books.google.com/books?id=N7BvXVUCQk8C&q=satisfiability+OR+satisfiable}}</ref>
+प्रस्तावपरक तर्क में कोई सूत्र संतोषप्रदता है या नहीं, यह निर्धारित करने की [[निर्णय समस्या]] ही [[निर्णायक समस्या]] है, एवं इसे [[बूलियन संतुष्टि समस्या]] या सैट के रूप में जाना जाता है। सामान्यतः, यह निर्धारित करने की समस्या हैं, कि क्या प्रथम-क्रम तर्क का वाक्य संतोषप्रदता है या निर्णायक नहीं है। [[सार्वभौमिक बीजगणित]], [[समीकरण सिद्धांत]] एवं स्वचालित प्रमेय प्रमाणित करने में, शब्द पुनर्लेखन, सर्वांगसमता संवृत करने एवं [[एकीकरण (कंप्यूटर विज्ञान)]] की प्रविधियों का उपयोग संतोषप्रदताता निर्धारित करने के लिए किया जाता है। कोई विशेष [[सिद्धांत (तर्क)]] निर्णायक है या नहीं यह निर्भर करता है कि सिद्धांत चर-मुक्त है।<ref>{{cite book|author1=Franz Baader|author-link=Franz Baader|author2=Tobias Nipkow|author2-link=Tobias Nipkow|title=टर्म पुनर्लेखन और वह सब|year=1998|publisher=Cambridge University Press|isbn=0-521-77920-0|pages=58–92|url=https://books.google.com/books?id=N7BvXVUCQk8C&q=satisfiability+OR+satisfiable}}</ref>
-== वैधता को संतुष्टि में कमी ==
+== वैधता की संतुष्टि में कमी ==
-नकारात्मकता के साथ [[शास्त्रीय तर्क]]शास्त्र के लिए, सामान्यतः सूत्र की वैधता के प्रश्न को व्यक्त करना संभव है, क्योंकि विपक्ष के उपरोक्त वर्ग में व्यक्त अवधारणाओं के मध्य संबंधों के कारण संतुष्टि सम्मिलित है। विशेष रूप से φ मान्य है एवं यदि ¬φ असंतुष्ट है, जिसका अर्थ है कि यह गलत है कि ¬φ संतोषजनक है। एवं यदि ¬φ अमान्य है।
+नकारात्मकता के साथ [[शास्त्रीय तर्क|क्लासिकल तर्क]] शास्त्र के लिए, सामान्यतः सूत्र की वैधता के प्रश्न को व्यक्त करना संभव है, क्योंकि विपक्ष के उपरोक्त वर्ग में व्यक्त अवधारणाओं के मध्य संबंधों के कारण संतुष्टि सम्मिलित है। विशेष रूप से φ मान्य है एवं यदि ¬φ असंतुष्ट है, जिसका अर्थ त्रुटिपूर्ण ¬φ संतोषप्रदता है। एवं यदि ¬φ अमान्य है।
-निषेध के बिना तर्कशास्त्र के लिए, जैसे कि तर्क प्रणालियों की सूची सकारात्मक प्रस्तावपरक कलन, वैधता एवं संतुष्टि के प्रश्न असंबंधित हो सकते हैं। तर्क प्रणालियों की सूची के विषय में सकारात्मक प्रस्ताविक कलन, संतुष्टि की समस्या तुच्छ है, क्योंकि प्रत्येक सूत्र संतोषजनक है, जबकि वैधता की समस्या [[सह-एनपी-पूर्ण]] है।
+निषेध के बिना तर्कशास्त्र के लिए, जैसे कि तर्क प्रणालियों की सूची सकारात्मक प्रस्तावपरक कलन, वैधता एवं संतुष्टि के प्रश्न असंबंधित हो सकते हैं। तर्क प्रणालियों की सूची के विषय में सकारात्मक प्रस्ताविक कलन, संतुष्टि की समस्या तुच्छ है, क्योंकि प्रत्येक सूत्र संतोषप्रदता है, जबकि वैधता की समस्या [[सह-एनपी-पूर्ण]] है।
 == क्लासिकल लॉजिक के लिए प्रस्तावित संतुष्टि ==
 {{main|प्रस्तावित संतुष्टि}}
-शास्त्रीय प्रस्तावपरक तर्क के विषय में, प्रस्तावपरक सूत्रों के लिए संतुष्टि निर्णायक है। विशेष रूप से, संतुष्टि एनपी-पूर्ण समस्या है, एवं [[कम्प्यूटेशनल जटिलता सिद्धांत]] में सबसे गहन अध्ययन वाली समस्याओं में से है।
+क्लासिकल प्रस्तावपरक तर्क के विषय में सूत्रों के लिए संतुष्टि निर्णायक है। विशेष रूप से, संतुष्टि एनपी-पूर्ण समस्या है, एवं [[कम्प्यूटेशनल जटिलता सिद्धांत]] में सबसे गहन अध्ययन वाली समस्याओं में से है।
 == प्रथम क्रम के तर्क में संतुष्टि ==
-प्रथम-क्रम तर्क (FOL) के लिए, संतुष्टि [[अनिर्णीत समस्या]] है। विशेष रूप से, यह RE पूर्ण समस्या है एवं इसलिए अर्ध-निर्णायक नहीं है।<ref>{{Cite web |url= https://www.inf.tu-dresden.de/content/institutes/thi/algi/lehre/SS12/AL12/skript/script120413.pdf |title= Chapter 1.3 Undecidability of FOL |accessdate= 21 July 2012 <!-- at 13:25  --> |author= Baier, Christel |author-link= Christel Baier |year= 2012 |work= Lecture Notes&nbsp;— Advanced Logics |publisher= Technische Universität Dresden&nbsp;— Institute for Technical Computer Science |pages= 28–32 |archive-date= 14 October 2020 |archive-url= https://web.archive.org/web/20201014044350/http://www.inf.tu-dresden.de/index.php?node_id=404 |url-status= dead }}</ref> यह तथ्य FOL के लिए वैधता समस्या की अनिश्चितता से संबंधित है। वैधता की समस्या की स्थिति का प्रश्न सर्व प्रथम [[डेविड हिल्बर्ट]] द्वारा तथाकथित एन्त्शेइडुंग्स समस्या के रूप में प्रस्तुत किया गया था। गोडेल की पूर्णता प्रमेय द्वारा सूत्र की सार्वभौमिक वैधता अर्ध-निर्णायक समस्या है। यदि संतुष्टि भी अर्ध-निर्णायक समस्या थी, तो काउंटर-प्रतिमान के अस्तित्व की समस्या भी होगी (सूत्र में काउंटर-प्रतिमान होते हैं यदि इसकी अस्वीकृति संतोषजनक होती है)। इसलिए तार्किक वैधता की समस्या निर्णायक होगी, जो चर्च-ट्यूरिंग प्रमेय का खंडन करती है, जिसका परिणाम एन्त्शेइडुंग्स समस्या के लिए नकारात्मक उत्तर बताता है।
+प्रथम-क्रम तर्क (FOL) के लिए, संतुष्टि [[अनिर्णीत समस्या]] है। विशेष रूप से, यह आर.इ पूर्ण समस्या है एवं इसलिए अर्ध-निर्णायक नहीं है।<ref>{{Cite web |url= https://www.inf.tu-dresden.de/content/institutes/thi/algi/lehre/SS12/AL12/skript/script120413.pdf |title= Chapter 1.3 Undecidability of FOL |accessdate= 21 July 2012 <!-- at 13:25  --> |author= Baier, Christel |author-link= Christel Baier |year= 2012 |work= Lecture Notes&nbsp;— Advanced Logics |publisher= Technische Universität Dresden&nbsp;— Institute for Technical Computer Science |pages= 28–32 |archive-date= 14 October 2020 |archive-url= https://web.archive.org/web/20201014044350/http://www.inf.tu-dresden.de/index.php?node_id=404 |url-status= dead }}</ref> यह तथ्य फ़ोल के लिए वैधता समस्या की अनिश्चितता से संबंधित है। वैधता की समस्या की स्थिति का प्रश्न सर्व प्रथम [[डेविड हिल्बर्ट]] द्वारा तथाकथित एन्त्शेइडुंग्स समस्या के रूप में प्रस्तुत किया गया था। गोडेल की पूर्णता प्रमेय द्वारा सूत्र की सार्वभौमिक वैधता अर्ध-निर्णायक समस्या है। यदि संतुष्टि भी अर्ध-निर्णायक समस्या थी, तो काउंटर-प्रतिमान में अस्तित्व भी समस्या होगी (सूत्र में काउंटर-प्रतिमान होते हैं यदि इसकी अस्वीकृति संतोषप्रदता होती है)। इसलिए तार्किक वैधता की समस्या निर्णायक होगी, जो चर्च-ट्यूरिंग प्रमेय का खंडन करती है, जिसका परिणाम एन्त्शेइडुंग्स समस्या के लिए नकारात्मक उत्तर देता है।
 == प्रतिमान सिद्धांत में संतुष्टि ==
-प्रतिमान सिद्धांत में, [[परमाणु सूत्र]] संतोषजनक होता है यदि [[संरचना (तर्क)]] के तत्वों का संग्रह होता है जो सूत्र को सत्य बनाता है।<ref>{{cite book|author1=Wilifrid Hodges|title=एक छोटा मॉडल सिद्धांत|year=1997|publisher=Cambridge University Press|isbn=0-521-58713-1|pages=12}}</ref> यदि A संरचना है, φ सूत्र है, एवं a तत्वों का संग्रह है, जो संरचना से लिया गया है, जो φ को संतुष्ट करता है, तो सामान्यतः यह लिखा जाता है कि
+प्रतिमान सिद्धांत में, [[परमाणु सूत्र]] संतोषप्रदता होता है यदि [[संरचना (तर्क)]] के तत्वों का संग्रह होता है जो सूत्र को सत्य बनाता है।<ref>{{cite book|author1=Wilifrid Hodges|title=एक छोटा मॉडल सिद्धांत|year=1997|publisher=Cambridge University Press|isbn=0-521-58713-1|pages=12}}</ref> यदि A संरचना है, φ सूत्र है, एवं a तत्वों का संग्रह है, जो संरचना से लिया गया है, जो φ को संतुष्ट करता है, तो सामान्यतः यह लिखा जाता है कि
 : ''A'' ⊧ φ [a]
-यदि φ का कोई मुक्त चर नहीं है, अर्थात, यदि φ [[परमाणु वाक्य]] है, एवं यह A से संतुष्ट है, तो कोई लिखता है
+यदि φ का कोई मुक्त चर नहीं है, अर्थात, यदि φ [[परमाणु वाक्य]] है, एवं यह A से संतुष्ट है, तो इस प्रकार लिखा जाता है,
 : ''A'' ⊧ φ
-इस विषय में, कोई यह भी कह सकता है कि A, φ के लिए प्रतिमान होता है, या कि φ A में सत्य है। यदि T, A द्वारा संतुष्ट परमाणु वाक्यों का संग्रह है, तो कोई लिखता है,
+इस विषय में, यह भी कहा जाता है कि A, φ के लिए प्रतिमान में φ A में सत्य है। यदि T, A द्वारा संतुष्ट परमाणु वाक्यों का संग्रह है, तो इस प्रकार लिखा जाता है,
 : ''A'' ⊧ ''T''
@@ Line 38: / Line 38: @@
 == परिमित संतुष्टि ==
-संतुष्टि से संबंधित समस्या परिमित संतुष्टि की है, जो यह निर्धारित करने का प्रश्न है कि क्या कोई सूत्र परिमित प्रतिमान को स्वीकार करता है जो इसे सत्य बनाता है। तर्क के लिए जिसमें [[परिमित मॉडल संपत्ति|परिमित प्रतिमान संपत्ति]] है, संतुष्टि एवं परिमित संतुष्टि की समस्याएं मिलती हैं, क्योंकि उस तर्क के सूत्र के पास प्रतिमान है यदि एवं केवल यदि उसके पास परिमित प्रतिमान है। [[परिमित मॉडल सिद्धांत|परिमित प्रतिमान सिद्धांत]] के गणितीय क्षेत्र में यह प्रश्न महत्वपूर्ण है।
+संतुष्टि से संबंधित समस्या परिमित संतुष्टि है, जो यह निर्धारित करने का प्रश्न है कि क्या कोई सूत्र परिमित प्रतिमान को स्वीकार करता है जो इसे सत्य बनाता है। तर्क के लिए जिसमें [[परिमित मॉडल संपत्ति|परिमित प्रतिमान संपत्ति]] है, संतुष्टि एवं परिमित संतुष्टि की समस्याएं होती हैं, क्योंकि उस तर्क के सूत्र के पास प्रतिमान है यदि केवल उसके पास परिमित प्रतिमान है, तो [[परिमित मॉडल सिद्धांत|परिमित प्रतिमान सिद्धांत]] के गणितीय क्षेत्र में यह प्रश्न महत्वपूर्ण है।
-परिमित संतुष्टि एवं संतुष्टि को सामान्य रूप से मेल नहीं खाना चाहिए। उदाहरण के लिए, निम्नलिखित वाक्यों के [[तार्किक संयोजन]] के रूप में प्राप्त प्रथम-क्रम तर्क सूत्र पर विचार करें, जहाँ <math>a_0</math> एवं <math>a_1</math> [[तार्किक स्थिरांक]] हैं।
+परिमित संतुष्टि को सामान्य रूप से युग्मित नहीं होना चाहिए। उदाहरण के लिए, निम्नलिखित वाक्यों के [[तार्किक संयोजन]] के रूप में प्राप्त प्रथम-क्रम तर्क सूत्र पर विचार करें, जहाँ <math>a_0</math> एवं <math>a_1</math> [[तार्किक स्थिरांक]] हैं।
 * <math>R(a_0, a_1)</math>
@@ Line 46: / Line 46: @@
 * <math>\forall x y z (R(y, x) \wedge R(z, x) \rightarrow y = z))</math>
 * <math>\forall x \neg R(x, a_0)</math>
-परिणामी सूत्र में अनंत प्रतिमान <math>R(a_0, a_1), R(a_1, a_2), \ldots</math> है , किन्तु यह दिखाया जा सकता है कि इसका कोई परिमित प्रतिमान नहीं है (तथ्य से प्रारम्भ <math>R(a_0, a_1)</math> एवं <math>R</math> की श्रंखला का पालन कर रहा है, परमाणु सूत्र जो दूसरे स्वयंसिद्ध द्वारा उपस्थित होना चाहिए, प्रतिमान की परिमितता के लिए लूप के अस्तित्व की आवश्यकता होगी, जो तीसरे एवं चौथे स्वयं सिद्धों का उल्लंघन करेगा, चाहे वह वापस लूप हो <math>a_0</math> या भिन्न तत्व पर हो।
+परिणामी सूत्र में अनंत प्रतिमान <math>R(a_0, a_1), R(a_1, a_2), \ldots</math> है , किन्तु यह दिखाया जा सकता है कि इसका कोई परिमित प्रतिमान नहीं है (तथ्य से प्रारम्भ <math>R(a_0, a_1)</math> एवं <math>R</math> की श्रंखला का पालन कर रहा है, परमाणु सूत्र जो दूसरे स्वयंसिद्ध द्वारा उपस्थित होना चाहिए, प्रतिमान की परिमितता के लिए लूप के अस्तित्व की आवश्यकता होगी, जो तीसरे एवं चौथे स्वयं सिद्धों का उल्लंघन करेगा, चाहे वह वापस लूप हो <math>a_0</math> या भिन्न तत्व को हो।
 किसी दिए गए तर्क में इनपुट सूत्र के लिए संतुष्टि का निर्णय लेने का कम्प्यूटेशनल जटिलता सिद्धांत परिमित संतुष्टि का निर्णय लेने से भिन्न हो सकता है; वास्तव में, कुछ तर्क के लिए, उनमें से केवल निर्धारणीय (तर्क) है।
-शास्त्रीय प्रथम-क्रम तर्क के लिए, परिमित संतुष्टि गणनात्मक रूप से [[गणना योग्य]] है (कक्षा [[आरई (जटिलता)]] में) एवं ट्रैखटेनब्रॉट के प्रमेय द्वारा अनिर्णीत समस्या सूत्र की अस्वीकृति पर प्रारम्भ होती है।
+क्लासिकल प्रथम-क्रम तर्क के लिए, परिमित संतुष्टि गणनात्मक रूप से [[गणना योग्य]] है (कक्षा [[आरई (जटिलता)]] में) एवं ट्रैखटेनब्रॉट के प्रमेय द्वारा अनिर्णीत समस्या सूत्र की अस्वीकृति पर प्रारम्भ होती है।
 == संख्यात्मक बाधाएँ ==
@@ Line 57: / Line 57: @@
 बाधा संतुष्टि समस्या}}
-प्रायः [[गणितीय अनुकूलन]] के क्षेत्र में दिखाई देते हैं, जहां कोई सामान्यतः कुछ बाधाओं के अधीन उद्देश्य फंक्शन को अधिकतम करना चाहता है। चूंकि, वस्तुनिष्ठ फ़ंक्शन को त्यागकर, केवल यह निर्धारित करने का मूल विषय कि क्या बाधाएं संतोषजनक हैं, कुछ समायोजन में अनिर्णीत हो सकती हैं। निम्न तालिका मुख्य विषयो को सारांशित करती है।
+प्रायः [[गणितीय अनुकूलन]] के क्षेत्र में दिखाई देते हैं, जहां कोई सामान्यतः कुछ बाधाओं के अधीन उद्देश्य फंक्शन को अधिकतम करना चाहता है। चूंकि, वस्तुनिष्ठ फ़ंक्शन को त्यागकर, केवल यह निर्धारित करने का मूल विषय कि क्या बाधाएं संतोषप्रदता हैं, कुछ समायोजन में अनिर्णीत हो सकती हैं। निम्न तालिका मुख्य विषयो को सारांशित करती है।
 {| class="wikitable"
@@ Line 63: / Line 63: @@
 ! प्रतिबंध !! वास्तविक से अधिक !! पूर्णांकों पर
 |-
-| रेखीय || [[PTIME]]  [[linear programming|(रैखिक प्रोग्रामिंग देखें)]]) || [[NP-complete|NP-पूर्ण (पूर्णांक प्रोग्रामिंग देखें)]]
+| रेखीय || [[PTIME|पी.टाइम]]  [[linear programming|(रैखिक प्रोग्रामिंग देखें)]]) || [[NP-complete|एनपी-पूर्ण (पूर्णांक प्रोग्रामिंग देखें)]]
 |-
 |बहुपद
@@ Line 79: / Line 79: @@
 !प्राकृतिक संख्या
 |-
-| [[System of linear equations|रेखीय समीकरण]] || PTIME || PTIME || NP-सम्पूर्ण
+| [[System of linear equations|रेखीय समीकरण]] ||पी.टाइम
+|पीटाइम
+| एन पी-सम्पूर्ण
 |-
-| [[Linear inequality#Systems of linear inequalities|रैखिक असमानताएँ]] || PTIME || NP-सम्पूर्ण || NP-सम्पूर्ण
+| [[Linear inequality#Systems of linear inequalities|रैखिक असमानताएँ]] ||पी.टाइम
+| एन पी-सम्पूर्ण || एन पी-सम्पूर्ण
 |}
 तालिका स्रोत: बॉकमायर एवं वीस्पफेनिंग।<ref name="BockmayrWeispfenning2001" />{{rp|755}}
@@ Line 106: / Line 109: @@
 {{Mathematical logic}}
-{{Metalogic}}
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category: तर्क में अवधारणाएँ]] [[Category: तार्किक सत्य]] [[Category: मॉडल सिद्धांत]] [[Category: तर्कशास्त्र का दर्शन]]
+[[Category:Collapse templates]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 15/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Mathematics navigational boxes]]
+[[Category:Navbox orphans]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with empty portal template]]
+[[Category:Pages with script errors]]
+[[Category:Philosophy and thinking navigational boxes]]
+[[Category:Portal-inline template with redlinked portals]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:तर्क में अवधारणाएँ]]
+[[Category:तर्कशास्त्र का दर्शन]]
+[[Category:तार्किक सत्य]]
+[[Category:मॉडल सिद्धांत]]

Anonymous

Search

संतोषप्रदता: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:15, 30 October 2023

Contents

वैधता की संतुष्टि में कमी

क्लासिकल लॉजिक के लिए प्रस्तावित संतुष्टि

प्रथम क्रम के तर्क में संतुष्टि

प्रतिमान सिद्धांत में संतुष्टि

परिमित संतुष्टि

संख्यात्मक बाधाएँ

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संतोषप्रदता: Difference between revisions

Latest revision as of 16:15, 30 October 2023

वैधता की संतुष्टि में कमी

क्लासिकल लॉजिक के लिए प्रस्तावित संतुष्टि

प्रथम क्रम के तर्क में संतुष्टि

प्रतिमान सिद्धांत में संतुष्टि

परिमित संतुष्टि

संख्यात्मक बाधाएँ

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories