निषेध सामान्य रूप: Difference between revisions
(Created page with "गणितीय तर्क में, एक सूत्र नकारात्मक सामान्य रूप (एनएनएफ) में है य...") |
(Work done) |
||
| Line 1: | Line 1: | ||
[[गणितीय तर्क]] में, | [[गणितीय तर्क]] में, किसी सूत्र '''निषेध साधारण रूप''' (नेगेशन नार्मल फॉर्म, '''एनएनएफ''') में होता है यदि [[नकार|निषेध]] संक्रियक (<math>\lnot</math>, {{smallcaps|not}}) केवल चरों पर लागू होता है और केवल द्वितीय अनुमत [[बूलियन बीजगणित|बूलियन संक्रियक]] अवश्यक होते हैं जो [[तार्किक संयोजन|संयोजन]] (<math>\land</math>, {{smallcaps|and}}) और वियोजन (<math>\lor</math>, {{smallcaps|or}}) हैं। | ||
निषेध सामान्य रूप विहित रूप नहीं है: उदाहरण के लिए, <math>a \land (b\lor \lnot c)</math> और <math>(a \land b) \lor (a \land \lnot c)</math> समतुल्य हैं, और दोनों निषेध सामान्य रूप में हैं। | |||
[[विधेय तर्क]] और कई [[मॉडल तर्क]] में, प्रत्येक सूत्र को | [[विधेय तर्क|प्राचीन तर्क]] और कई [[मॉडल तर्क]] में, प्रत्येक सूत्र को उनकी परिभाषाओं द्वारा निहितार्थों और समकक्षों को प्रतिस्थापित करके, निषेध को अंदर की ओर पुश करने के लिए डी मॉर्गन के नियमों का उपयोग करके और दोहरे निषेधों को समाप्त करके इस रूप में लाया जा सकता है। इस प्रक्रिया को निम्नलिखित [[पुनर्लेखन नियम|पुनर्लेखन नियमों]] का उपयोग करके दर्शाया जा सकता है (''स्वचालित तर्क की पुस्तिका'' 1, पृष्ठ 204): | ||
:<math>\begin{align} | :<math>\begin{align} | ||
| Line 14: | Line 14: | ||
\lnot \forall x A &~\to~ \exists x \lnot A | \lnot \forall x A &~\to~ \exists x \lnot A | ||
\end{align}</math> | \end{align}</math> | ||
(इन नियमों में, <math>\Rightarrow</math> प्रतीक | (इन नियमों में, <math>\Rightarrow</math> प्रतीक पुनर्लेखित किए जाने वाले सूत्र में तार्किक निहितार्थ को दर्शाता है, और <math>\to</math> पुनरलेखन ऑपरेशन है।) | ||
निषेध साधारण रूप में परिवर्तन से सूत्र का आकार केवल रैखिक रूप से बढ़ सकता है: परमाणु सूत्रों के घटित होने की संख्या समान रहती है, <math>\land</math> और <math>\lor</math> की कुल परिवर्तन संख्या अभिनिर्मित होती है, और साधारण रूप में <math>\lnot</math> की परिवर्तन संख्या मूल सूत्र की लंबाई से सीमित होती है। | |||
निषेधात्मक साधारण रूप में एक सूत्र को प्रवाल संयोजनिक साधारण रूप या वियोजनिक साधारण रूप में डिस्ट्रीब्यूटिविटी का उपयोग करके डाला जा सकता है। डिस्ट्रीब्यूटिविटी के अनुप्रयोग का बार-बार उपयोग सूत्र का आकार गणनीय रूप से बढ़ा सकता है। चिरसम्मत प्रस्तावीय तर्क में, निषेधात्मक साधारण रूप में परिवर्तन का गणकीय गुण पर प्रभाव नहीं होता है: [[बूलियन संतुष्टि समस्या|संतुष्टि समस्या]] एनपी-पूर्ण ही रहती है, और वैधता समस्या [[सह-एनपी-पूर्ण]] ही रहती है। संयोजनिक साधारण रूप में सूत्रों के लिए, वैधता समस्या बहुपद समय में हल की जा सकती है, और वियोजनिक साधारण रूप में सूत्रों के लिए, संतुष्टि समस्या बहुपद समय में हल की जा सकती है। | |||
== उदाहरण और प्रति उदाहरण == | == उदाहरण और प्रति उदाहरण == | ||
निम्नलिखित सूत्र सभी | निम्नलिखित सूत्र सभी निषेधात्मक सामान्य रूप में हैं: | ||
:<math>\begin{align} | :<math>\begin{align} | ||
(A &\vee B) \wedge C \\ | (A &\vee B) \wedge C \\ | ||
| Line 28: | Line 28: | ||
A &\wedge \lnot B | A &\wedge \lnot B | ||
\end{align}</math> | \end{align}</math> | ||
पहला उदाहरण | पहला उदाहरण भी संयोजक सामान्य रूप में है और अंतिम दो उदाहरण संयोजनात्मक सामान्य रूप और वियोजक सामान्य रूप दोनों में हैं, लेकिन दूसरा उदाहरण दोनों में से कोई नहीं है। | ||
निम्नलिखित सूत्र | निम्नलिखित सूत्र निषेधात्मक सामान्य रूप में नहीं हैं: | ||
:<math>\begin{align} | :<math>\begin{align} | ||
A &\Rightarrow B \\ | A &\Rightarrow B \\ | ||
| Line 37: | Line 37: | ||
\lnot (A &\vee \lnot C) | \lnot (A &\vee \lnot C) | ||
\end{align}</math> | \end{align}</math> | ||
हालाँकि, वे क्रमशः | हालाँकि, वे क्रमशः निषेधात्मक सामान्य रूप में निम्नलिखित सूत्रों के समतुल्य हैं: | ||
:<math>\begin{align} | :<math>\begin{align} | ||
\lnot A &\vee B \\ | \lnot A &\vee B \\ | ||
| Line 44: | Line 44: | ||
\lnot A &\wedge C | \lnot A &\wedge C | ||
\end{align}</math> | \end{align}</math> | ||
==संदर्भ== | ==संदर्भ== | ||
* [[John Alan Robinson]] and [[Andrei Voronkov]], ''Handbook of Automated Reasoning'' '''1''':203''ff'' (2001) {{isbn|0444829490}}. | * [[John Alan Robinson]] and [[Andrei Voronkov]], ''Handbook of Automated Reasoning'' '''1''':203''ff'' (2001) {{isbn|0444829490}}. | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* [https://archive.today/20121208184549/http://www.izyt.com/BooleanLogic/applet.php Java applet for converting logical formula to Negation Normal Form, showing laws used] | * [https://archive.today/20121208184549/http://www.izyt.com/BooleanLogic/applet.php Java applet for converting logical formula to Negation Normal Form, showing laws used] | ||
Revision as of 19:03, 29 June 2023
गणितीय तर्क में, किसी सूत्र निषेध साधारण रूप (नेगेशन नार्मल फॉर्म, एनएनएफ) में होता है यदि निषेध संक्रियक (, not) केवल चरों पर लागू होता है और केवल द्वितीय अनुमत बूलियन संक्रियक अवश्यक होते हैं जो संयोजन (, and) और वियोजन (, or) हैं।
निषेध सामान्य रूप विहित रूप नहीं है: उदाहरण के लिए, और समतुल्य हैं, और दोनों निषेध सामान्य रूप में हैं।
प्राचीन तर्क और कई मॉडल तर्क में, प्रत्येक सूत्र को उनकी परिभाषाओं द्वारा निहितार्थों और समकक्षों को प्रतिस्थापित करके, निषेध को अंदर की ओर पुश करने के लिए डी मॉर्गन के नियमों का उपयोग करके और दोहरे निषेधों को समाप्त करके इस रूप में लाया जा सकता है। इस प्रक्रिया को निम्नलिखित पुनर्लेखन नियमों का उपयोग करके दर्शाया जा सकता है (स्वचालित तर्क की पुस्तिका 1, पृष्ठ 204):
(इन नियमों में, प्रतीक पुनर्लेखित किए जाने वाले सूत्र में तार्किक निहितार्थ को दर्शाता है, और पुनरलेखन ऑपरेशन है।)
निषेध साधारण रूप में परिवर्तन से सूत्र का आकार केवल रैखिक रूप से बढ़ सकता है: परमाणु सूत्रों के घटित होने की संख्या समान रहती है, और की कुल परिवर्तन संख्या अभिनिर्मित होती है, और साधारण रूप में की परिवर्तन संख्या मूल सूत्र की लंबाई से सीमित होती है।
निषेधात्मक साधारण रूप में एक सूत्र को प्रवाल संयोजनिक साधारण रूप या वियोजनिक साधारण रूप में डिस्ट्रीब्यूटिविटी का उपयोग करके डाला जा सकता है। डिस्ट्रीब्यूटिविटी के अनुप्रयोग का बार-बार उपयोग सूत्र का आकार गणनीय रूप से बढ़ा सकता है। चिरसम्मत प्रस्तावीय तर्क में, निषेधात्मक साधारण रूप में परिवर्तन का गणकीय गुण पर प्रभाव नहीं होता है: संतुष्टि समस्या एनपी-पूर्ण ही रहती है, और वैधता समस्या सह-एनपी-पूर्ण ही रहती है। संयोजनिक साधारण रूप में सूत्रों के लिए, वैधता समस्या बहुपद समय में हल की जा सकती है, और वियोजनिक साधारण रूप में सूत्रों के लिए, संतुष्टि समस्या बहुपद समय में हल की जा सकती है।
उदाहरण और प्रति उदाहरण
निम्नलिखित सूत्र सभी निषेधात्मक सामान्य रूप में हैं:
पहला उदाहरण भी संयोजक सामान्य रूप में है और अंतिम दो उदाहरण संयोजनात्मक सामान्य रूप और वियोजक सामान्य रूप दोनों में हैं, लेकिन दूसरा उदाहरण दोनों में से कोई नहीं है।
निम्नलिखित सूत्र निषेधात्मक सामान्य रूप में नहीं हैं:
हालाँकि, वे क्रमशः निषेधात्मक सामान्य रूप में निम्नलिखित सूत्रों के समतुल्य हैं:
संदर्भ
- John Alan Robinson and Andrei Voronkov, Handbook of Automated Reasoning 1:203ff (2001) ISBN 0444829490.
