कार्यात्मक पूर्णता: Difference between revisions

Revision as of 18:32, 21 February 2023

गणितीय तर्क में, तार्किक संयोजकों या बूलियन संकारक का एक कार्यात्मक रूप से पूर्ण समुच्चय वह है जिसका उपयोग समुच्चय के इकाई को एक बूलियन अभिव्यक्ति में जोड़कर सभी संभव सत्य तालिकाओं को व्यक्त करने के लिए किया जा सकता है।^[1]^[2] संयोजकों का एक प्रसिद्ध पूर्ण समुच्चय {तार्किक संयोजन, निषेध} है। प्रत्येक सिंगलटन (गणित) समुच्चय {एनएएनडी} और {नॉर} कार्यात्मक रूप से पूर्ण हैं। हालांकि, समुच्चय {एएनडी, नॉर} अपूर्ण है, इसकी कारण से एनओटी को व्यक्त करने में असमर्थता है।

एक गेट(द्वार) या गेट्स का समूह जो कार्यात्मक रूप से पूर्ण है, उसे एक सार्वभौमिक गेट /गेट्स भी कहा जा सकता है।

गेट्स का एक कार्यात्मक रूप से पूरा समुच्चय अपनी गणना के भाग के रूप में 'मूल्यहीन बिट्स' का उपयोग या उत्पन्न कर सकता है जो या तो निविष्टि का हिस्सा नहीं हैं या प्रणाली के निर्गम का भाग नहीं हैं।

प्रस्तावात्मक तर्क के संदर्भ में, संयोजकों के कार्यात्मक रूप से पूर्ण समुच्चय को भी (अभिव्यंजक रूप से) समुचित कहा जाता है।^[3]

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

परिचय

तर्क पर आधुनिक विषय सामान्य रूप से संयोजकों के कुछ उपसमुच्चय को प्रारम्भिक रूप में लेते हैं: तार्किक संयोजन ( $\land$ ); विच्छेदन ( $\lor$ ); निषेध ( $\neg$ ); सशर्त सामग्री ( $\to$ ); और संभवत: तार्किक द्विसशर्त ( $\leftrightarrow$ ) आगे के संयोजकों को परिभाषित किया जा सकता है, यदि वांछित हो, तो उन्हें इन मौलिक के संदर्भ में परिभाषित किया जा सकता है। उदाहरण के लिए, नॉर (कभी-कभी निरूपित किया जाता है $\downarrow$ , निषेध की अस्वीकृति) को दो निषेधों के संयोजन के रूप में व्यक्त किया जा सकता है:

A\downarrow B:=\neg A\land \neg B

इसी तरह, संयुग्मन का निषेध, एनएएनडी (कभी-कभी के रूप में निरूपित किया जाता है $\uparrow$ ), संयोजन और निषेध के संदर्भ में परिभाषित किया जा सकता है। यह पता चला है कि प्रत्येक बाइनरी संयोजक को परिभाषित किया जा सकता है $\{\neg ,\land ,\lor ,\to ,\leftrightarrow \}$ , इसलिए यह समुच्चय कार्यात्मक रूप से पूर्ण है।

हालाँकि, इसमें अभी भी कुछ अतिरेक है: यह समुच्चय न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय नहीं है, क्योंकि सशर्त और द्विप्रतिबंध को अन्य संयोजकों के रूप में परिभाषित किया जा सकता है

{\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}

यह इस प्रकार है कि लघु समुच्चय $\{\neg ,\land ,\lor \}$ कार्यात्मक रूप से भी पूर्ण है। लेकिन यह अभी भी न्यूनतम नहीं है, जैसा कि $\lor$ के रूप में परिभाषित किया जा सकता है

A\lor B:=\neg (\neg A\land \neg B).

वैकल्पिक रूप से, $\land$ के रूप में परिभाषित किया जा सकता है $\lor$ इसी तरह, या $\lor$ के रूप में परिभाषित किया जा सकता है $\rightarrow$ :

\ A\vee B:=\neg A\rightarrow B.

आगे कोई सरलीकरण संभव नहीं है। इसलिए, प्रत्येक दो-तत्व वाले संयोजकों का समुच्चय $\neg$ और एक $\{\land ,\lor ,\rightarrow \}$ का न्यूनतम कार्यात्मक रूप से पूर्ण उपसमुच्चय है $\{\neg ,\land ,\lor ,\to ,\leftrightarrow \}$ .

औपचारिक परिभाषा

बूलियन प्रक्षेत्र B = {0,1} दिया गया है, बूलियन फलन ƒ का एक समुच्चय F_i: B^n_i → 'B' 'कार्यात्मक रूप से पूर्ण' है यदि 'B' पर प्रतिरूप (बीजगणित) आधारिक कार्यों द्वारा उत्पन्न किया गया है ƒ_i सभी फलन सम्मिलित हैं ƒ: 'B'ⁿ → 'B', सभी निश्चित धनात्मक पूर्णांकों के लिए n ≥ 1 दूसरे शब्दों में, समुच्चय क्रियात्मक रूप से पूर्ण होता है यदि प्रत्येक बूलियन फलन जिसमें कम से कम एक चर होता है, ƒ_i को फलन के संदर्भ में व्यक्त किया जा सकता है चूँकि कम से कम एक चर के प्रत्येक बूलियन फलन को बाइनरी बूलियन फलन के संदर्भ में व्यक्त किया जा सकता है, F कार्यात्मक रूप से पूर्ण है यदि और केवल यदि प्रत्येक बाइनरी बूलियन फलन को F में फलन के संदर्भ में व्यक्त किया जा सकता है।

एक अधिक स्वाभाविक स्थिति यह होगी कि F द्वारा उत्पन्न प्रतिरूप संगणक में सभी फलन : 'B'ⁿ → 'B', सभी पूर्णांकों के लिए n ≥ 0 लिए होते हैं। हालाँकि, ऊपर दिए गए उदाहरण इस प्रबल अर्थ में कार्यात्मक रूप से पूर्ण नहीं हैं क्योंकि F के संदर्भ में एक अशक्त फलन, अर्थात एक स्थिर अभिव्यक्ति लिखना संभव नहीं है, यदि F में स्वयं कम से कम एक शून्य फलन सम्मिलित नहीं है। इस प्रबल परिभाषा के साथ, कार्यात्मक रूप से सबसे छोटे समुच्चय में 2 तत्व होंगे।

एक अन्य प्राकृतिक स्थिति यह होगी कि एफ द्वारा उत्पन्न प्रतिरूप दो अशक्त स्थिर कार्यों के साथ कार्यात्मक रूप से पूर्ण या, समकक्ष रूप से, पिछले पैराग्राफ के प्रबल अर्थों में कार्यात्मक रूप से पूर्ण हो। बूलियन फलन का उदाहरण S(x, y, z) =z यदि x = y और S(x, y, z) = x अन्यथा दिखाता है कि यह स्थिति कार्यात्मक पूर्णता दुर्बल है।^[4]^[5]^[6]

कार्यात्मक पूर्णता की विशेषता

एमिल लियोन पोस्ट ने प्रमाणित किया कि तार्किक संयोजकों का एक समुच्चय कार्यात्मक रूप से पूर्ण है यदि और केवल यदि यह संयोजकों के निम्नलिखित समुच्चयों में से किसी का उपसमुच्चय नहीं है:

एकदिष्‍ट संयोजक; किसी भी जुड़े हुए चर के सत्य मान को F से T में बिना किसी T से F में परिवर्तित करने से ये संयोजक कभी भी T से F में अपना पुनरावृत्ति मूल्य नहीं परिवर्तित करते हैं, उदाहरण $\vee ,\wedge ,\top ,\bot$
एफ़िन रूपांतरण संयोजक, जैसे कि प्रत्येक जुड़ा चर या तो सदैव या कभी भी इन संयोजकों के प्रतिफल के सत्य मान को प्रभावित नहीं करता है, उदाहरण $\neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow$
स्व-द्वैत संयोजक, जो अपने स्वयं के डे मॉर्गन द्वैत के समान हैं; यदि सभी चरों के सत्य मान प्रतिलोम कर दिए जाते हैं, तो क्या सत्य मान इन संयोजकों का प्रतिफल होता है, उदाहरण $\neg$ , बहुसंख्यक फलन (p,q,r)।
'सत्य-संरक्षण' संयोजक; वे किसी भी व्याख्या के अंतर्गत सत्य मान 'T' प्रतिफल देते हैं जो सभी चरों को 'T' प्रदान करता है, उदाहरण $\vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow$
मिथ्या-संरक्षण संयोजक; वे किसी भी व्याख्या के अंतर्गत सत्य मान F प्रतिफल देते हैं जो F को सभी चरों को निर्दिष्ट करता है, उदाहरण $\vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow$

वास्तव में, पोस्ट ने दो-तत्व समुच्चय {T, F}, जिसे वर्तमान मे पोस्ट का नियम कहा जाता है, पर सभी प्रतिरूप (बीजगणित) के नियम (क्रम) का पूरा विवरण दिया (संरचना के अंतर्गत संचालन के समुच्चय और सभी अनुमानों को सम्मिलित किया गया) जो उपरोक्त परिणाम को एक सरल उपप्रमेय के रूप में दर्शाता है: संयोजक के पांच उल्लिखित समुच्चय वास्तव में अधिकतम प्रतिरूप हैं।

न्यूनतम कार्यात्मक रूप से पूर्ण संक्रियक समुच्चय

जब एकल तार्किक संयोजक या बूलियन संक्रियक अपने आप में कार्यात्मक रूप से पूर्ण हो जाता है, तो इसे शेफ़र फलन ^[7] या कभी-कभी एकमात्र समुचित संक्रियक कहा जाता है। इस गुण के साथ कोई एकात्मक संक्रियक नहीं है। तार्किक एनएएनडी और तार्किक नॉर, जो बूलियन बीजगणित द्वैत सिद्धांत हैं, केवल दो बाइनरी शेफ़र फलन हैं। इन्हें 1880 के आसपास चार्ल्स सैंडर्स पियर्स द्वारा खोजा गया था, लेकिन प्रकाशित नहीं किया गया था, और स्वतंत्र रूप से पुनः खोजा गया और 1913 में हेनरी एम शेफ़र द्वारा प्रकाशित किया गया।^[8] डिजिटल इलेक्ट्रॉनिक्स शब्दावली में, बाइनरी एनएएनडी गेट (↑) और बाइनरी नॉर गेट (↓) केवल बाइनरी सार्वभौमिक तर्क गेट (द्वार) हैं।

एरिटी ≤ 2 के साथ तार्किक संयोजकों के न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय निम्नलिखित हैं:^[9]

एक तत्व: {↑}, {↓}

दो तत्व:

$\{\vee ,\neg \}$ , $\{\wedge ,\neg \}$ , $\{\to ,\neg \}$ , $\{\gets ,\neg \}$ , $\{\to ,\bot \}$ , $\{\gets ,\bot \}$ , $\{\to ,\nleftrightarrow \}$ , $\{\gets ,\nleftrightarrow \}$ , $\{\to ,\nrightarrow \}$ , $\{\to ,\nleftarrow \}$ , $\{\gets ,\nrightarrow \}$ , $\{\gets ,\nleftarrow \}$ , $\{\nrightarrow ,\neg \}$ , $\{\nleftarrow ,\neg \}$ , $\{\nrightarrow ,\top \}$ , $\{\nleftarrow ,\top \}$ , $\{\nrightarrow ,\leftrightarrow \}$ , $\{\nleftarrow ,\leftrightarrow \}.$

तीन तत्व:

$\{\lor ,\leftrightarrow ,\bot \}$ , $\{\lor ,\leftrightarrow ,\nleftrightarrow \}$ , $\{\lor ,\nleftrightarrow ,\top \}$ , $\{\land ,\leftrightarrow ,\bot \}$ , $\{\land ,\leftrightarrow ,\nleftrightarrow \}$ , $\{\land ,\nleftrightarrow ,\top \}.$

अधिकांश बाइनरी तार्किक संयोजक में तीन से अधिक का न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय नहीं है।^[9] उपरोक्त सूचियों को पठनीय रखने के लिए, एक या अधिक निविष्टि को ध्यान न देने वाले संकारक को छोड़ दिया गया है। उदाहरण के लिए, एक संक्रियक जो पहले निविष्टि को उपेक्षा करता है और दूसरे के निषेध को निर्गत करता है, उसे एकल निषेध द्वारा प्रतिस्थापित किया जा सकता है।

उदाहरण

एनएएनडी(↑) पूर्णता का उपयोग करने के उदाहरण। जैसा कि दिखाया गया है,^[10]
¬A ≡ A ↑ A
A ∧ B ≡ ¬(A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
NOR(↓) पूर्णता का उपयोग करने के उदाहरण। जैसा कि दिखाया गया है,^[11]
¬A ≡ A ↓ A
A ∨ B ≡ ¬(A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
A ∧ B ≡ (A ↓ A) ↓ (B ↓ B)

ध्यान दें कि गेट्स की संख्या को कम करने के लिए एक इलेक्ट्रॉनिक परिपथ या सॉफ़्टवेयर फलन को पुन: उपयोग करके अनुकूलित किया जा सकता है। उदाहरण के लिए, A ∧ B संक्रिया, जब ↑ गेट्स द्वारा व्यक्त किया जाता है, A ↑ B के पुन: उपयोग के साथ कार्यान्वित किया जाता है,

X ≡ (A ↑ B); A ∧ B ≡ X ↑ X

अन्य प्रक्षेत्र में

तार्किक संयोजकों (बूलियन संक्रियक) के अतिरिक्त, कार्यात्मक पूर्णता को अन्य प्रक्षेत्र में प्रस्तुत किया जा सकता है। उदाहरण के लिए, प्रतिवर्ती संगणना द्वारों के एक समुच्चय को कार्यात्मक रूप से पूर्ण कहा जाता है, यदि यह प्रत्येक प्रतिवर्ती संक्रियक को व्यक्त कर सकता है।

3-निविष्टि फ्रेडकिन गेट अपने आप में एकमात्र समुचित संक्रियक द्वारा कार्यात्मक रूप से पूर्ण प्रतिवर्ती गेट है। टोफोली गेट जैसे कई अन्य तीन-निविष्टि सार्वभौमिक तर्क द्वार हैं।

क्वांटम कंप्यूटिंग में, हैडमार्ड गेट और T गेट सार्वभौमिक हैं, हालांकि कार्यात्मक पूर्णता की तुलना में अधिक प्रतिबंधात्मक परिभाषा है।

समुच्चय सिद्धांत

समुच्चय के बीजगणित और बूलियन बीजगणित के बीच एक समरूपता है, अर्थात, उनके पास एक ही बूलियन बीजगणित (संरचना) है। फिर, यदि हम बूलियन संकारक को समुच्चय संकारक में मानचित्र करते हैं, तो उपरोक्त अनुवाद समुच्चय के लिए भी मान्य हैं: समुच्चय-सिद्धांत संकारक के कई न्यूनतम पूर्ण समुच्चय हैं जो किसी अन्य समुच्चय संबंध को उत्पन्न कर सकते हैं। अधिक लोकप्रिय न्यूनतम पूर्ण संक्रियक समुच्चय {¬, ∩} और {¬, ∪} हैं। यदि सार्वभौमिक समुच्चय निषिद्ध है तो संक्रियक असत्यता- (Ø) संरक्षित होने तक सीमित हैं, और कार्यात्मक रूप से पूर्ण बूलियन बीजगणित के समान नहीं हो सकते हैं।

यह भी देखें

समुच्चयों का बीजगणित - समुच्चयों से संबंधित सर्वसमिकाएँ और संबंध
बूलियन बीजगणित - "सत्य" और "असत्य" का बीजगणितीय कुशलतापूर्वक प्रयोग
पूर्णता (तर्क) - कुछ तार्किक प्रणालियों की विशेषता
बूलियन बीजगणित के विषयों की सूची
एनएएनडी लॉजिक – केवल एनएएनडी गेट्स से निर्मित लॉजिक
नॉर तर्क - सिर्फ नॉर गेट्स का उपयोग करके अन्य गेट्स बनाना
निर्देश समुच्चय कंप्यूटर - अमूर्त मशीन जो केवल एक निर्देश का उपयोग करती है

संदर्भ

↑ Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3. ("Complete set of logical connectives").
↑ Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic (2nd ed.), New York: McGraw–Hill, ISBN 978-0-07-046649-4. ("[F]unctional completeness of [a] set of logical operators").
↑ Smith, Peter (2003), An introduction to formal logic, Cambridge University Press, ISBN 978-0-521-00804-4. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
↑ Wesselkamper, T.C. (1975), "A sole sufficient operator", Notre Dame Journal of Formal Logic, 16: 86–88, doi:10.1305/ndjfl/1093891614
↑ Massey, G.J. (1975), "Concerning an alleged Sheffer function", Notre Dame Journal of Formal Logic, 16 (4): 549–550, doi:10.1305/ndjfl/1093891898
↑ Wesselkamper, T.C. (1975), "A Correction To My Paper" A. Sole Sufficient Operator", Notre Dame Journal of Formal Logic, 16 (4): 551, doi:10.1305/ndjfl/1093891899
↑ The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. Martin, N.M. (1989), Systems of logic, Cambridge University Press, p. 54, ISBN 978-0-521-36770-7.
↑ Scharle, T.W. (1965), "Axiomatization of propositional calculus with Sheffer functors", Notre Dame J. Formal Logic, 6 (3): 209–217, doi:10.1305/ndjfl/1093958259.
↑ ^9.0 ^9.1 Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between $\nleftarrow$ and $\nrightarrow$ .
↑ "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
↑ "NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html

[Enderton2001-1] Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3. ("Complete set of logical connectives").

[Nolt1998-2] Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic (2nd ed.), New York: McGraw–Hill, ISBN 978-0-07-046649-4. ("[F]unctional completeness of [a] set of logical operators").

[Smith2003-3] Smith, Peter (2003), An introduction to formal logic, Cambridge University Press, ISBN 978-0-521-00804-4. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)

[Wesselkamper1975a-4] Wesselkamper, T.C. (1975), "A sole sufficient operator", Notre Dame Journal of Formal Logic, 16: 86–88, doi:10.1305/ndjfl/1093891614

[Massey1975-5] Massey, G.J. (1975), "Concerning an alleged Sheffer function", Notre Dame Journal of Formal Logic, 16 (4): 549–550, doi:10.1305/ndjfl/1093891898

[Wesselkamper1975b-6] Wesselkamper, T.C. (1975), "A Correction To My Paper" A. Sole Sufficient Operator", Notre Dame Journal of Formal Logic, 16 (4): 551, doi:10.1305/ndjfl/1093891899

[Martin1989-7] The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. Martin, N.M. (1989), Systems of logic, Cambridge University Press, p. 54, ISBN 978-0-521-36770-7.

[Scharle1965-8] Scharle, T.W. (1965), "Axiomatization of propositional calculus with Sheffer functors", Notre Dame J. Formal Logic, 6 (3): 209–217, doi:10.1305/ndjfl/1093958259.

[Wernick-9] 9.0 ^9.1 Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between $\nleftarrow$ and $\nrightarrow$ .

[10] "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html

[11] "NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
-[[गणितीय तर्क]] में, [[तार्किक संयोजक]]ों या [[बूलियन समारोह]] का कार्यात्मक रूप से पूर्ण सेट वह है जिसका उपयोग [[सेट (गणित)]] के सदस्यों को [[बूलियन अभिव्यक्ति]] में जोड़कर सभी संभव सत्य तालिकाओं को व्यक्त करने के लिए किया जा सकता है।<ref name="Enderton2001">{{citation | last1=Enderton | first1=Herbert | title=A mathematical introduction to logic | publisher=[[Academic Press]] | location=Boston, MA | edition=2nd | isbn=978-0-12-238452-3 | year=2001}}. ("Complete set of logical connectives").</ref><ref name="Nolt1998">{{citation | last1=Nolt | first1=John | last2=Rohatyn | first2=Dennis | last3=Varzi | first3=Achille | title=Schaum's outline of theory and problems of logic | publisher=[[McGraw–Hill]] | location=New York | edition=2nd | isbn=978-0-07-046649-4 | year=1998}}. ("[F]unctional completeness of [a] set of logical operators").</ref> संयोजकों का एक प्रसिद्ध पूर्ण समुच्चय { [[तार्किक संयोजन]], निषेध} है। प्रत्येक [[सिंगलटन (गणित)]] सेट { [[शेफर लाइन]]} और { [[तार्किक NOR]]} कार्यात्मक रूप से पूर्ण हैं। हालांकि, सेट { AND, [[तार्किक विच्छेदन]] } अधूरा है, इसकी वजह से NOT को व्यक्त करने में असमर्थता है।
+[[गणितीय तर्क|गणितीय]] तर्क में, तार्किक संयोजकों या बूलियन संकारक का एक '''कार्यात्मक रूप से पूर्ण''' समुच्चय वह है जिसका उपयोग समुच्चय के इकाई को एक बूलियन अभिव्यक्ति में जोड़कर सभी संभव सत्य तालिकाओं को व्यक्त करने के लिए किया जा सकता है।<ref name="Enderton2001">{{citation | last1=Enderton | first1=Herbert | title=A mathematical introduction to logic | publisher=[[Academic Press]] | location=Boston, MA | edition=2nd | isbn=978-0-12-238452-3 | year=2001}}. ("Complete set of logical connectives").</ref><ref name="Nolt1998">{{citation | last1=Nolt | first1=John | last2=Rohatyn | first2=Dennis | last3=Varzi | first3=Achille | title=Schaum's outline of theory and problems of logic | publisher=[[McGraw–Hill]] | location=New York | edition=2nd | isbn=978-0-07-046649-4 | year=1998}}. ("[F]unctional completeness of [a] set of logical operators").</ref> संयोजकों का एक प्रसिद्ध पूर्ण समुच्चय {[[तार्किक संयोजन]], निषेध} है। प्रत्येक [[सिंगलटन (गणित)]] समुच्चय {[[शेफर लाइन|एनएएनडी]]} और {[[तार्किक NOR|नॉर]]} कार्यात्मक रूप से पूर्ण हैं। हालांकि, समुच्चय {एएनडी, नॉर} अपूर्ण है, इसकी कारण से एनओटी को व्यक्त करने में असमर्थता है।
-एक द्वार या फाटकों का समूह जो कार्यात्मक रूप से पूर्ण है, उसे एक सार्वभौमिक द्वार / द्वार भी कहा जा सकता है।
+एक गेट(द्वार) या गेट्स का समूह जो कार्यात्मक रूप से पूर्ण है, उसे एक सार्वभौमिक गेट /गेट्स भी कहा जा सकता है।
-फाटकों का एक कार्यात्मक रूप से पूरा सेट अपनी गणना के भाग के रूप में 'कचरा बिट्स' का उपयोग या उत्पन्न कर सकता है जो या तो इनपुट का हिस्सा नहीं हैं या सिस्टम के आउटपुट का हिस्सा नहीं हैं।
+गेट्स का एक कार्यात्मक रूप से पूरा समुच्चय अपनी गणना के भाग के रूप में 'मूल्यहीन बिट्स' का उपयोग या उत्पन्न कर सकता है जो या तो निविष्टि का हिस्सा नहीं हैं या प्रणाली के निर्गम का भाग नहीं हैं।
-प्रस्तावपरक तर्क के संदर्भ में, संयोजकों के कार्यात्मक रूप से पूर्ण सेट को भी (अभिव्यंजक रूप से) पर्याप्त कहा जाता है।<ref name="Smith2003">{{Citation | last1=Smith | first1=Peter | title=An introduction to formal logic | publisher=[[Cambridge University Press]] | isbn=978-0-521-00804-4 | year=2003}}. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)</ref>
+प्रस्तावात्मक तर्क के संदर्भ में, संयोजकों के कार्यात्मक रूप से पूर्ण समुच्चय को भी (अभिव्यंजक रूप से) समुचित कहा जाता है।<ref name="Smith2003">{{Citation | last1=Smith | first1=Peter | title=An introduction to formal logic | publisher=[[Cambridge University Press]] | isbn=978-0-521-00804-4 | year=2003}}. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)</ref>
-[[डिजिटल इलेक्ट्रॉनिक्स]] के दृष्टिकोण से, कार्यात्मक पूर्णता का अर्थ है कि हर संभव [[तर्क द्वार]] को सेट द्वारा निर्धारित प्रकार के गेट्स के नेटवर्क के रूप में महसूस किया जा सकता है। विशेष रूप से, सभी लॉजिक गेट्स को या तो केवल बाइनरी NAND गेट्स, या केवल बाइनरी NOR गेट्स से इकट्ठा किया जा सकता है।
+[[डिजिटल इलेक्ट्रॉनिक्स]] के दृष्टिकोण से, कार्यात्मक पूर्णता का अर्थ है कि हर संभव [[तर्क द्वार|तर्क]] गेट को समुच्चय द्वारा निर्धारित प्रकार के गेट्स के नेटवर्क के रूप में संपादित किया जा सकता है। विशेष रूप से, सभी तार्किक गेट्स को या तो केवल बाइनरी एनएएनडी गेट्स, या केवल बाइनरी नॉर गेट्स से संग्रहीत किया जा सकता है।
 == परिचय ==
-तर्क पर आधुनिक पाठ आमतौर पर संयोजकों के कुछ उपसमुच्चय को आदिम रूप में लेते हैं: तार्किक संयोजन (<math>\land</math>); तार्किक संयोजन (<math>\lor</math>); निषेध (<math>\neg</math>); [[सामग्री सशर्त]] (<math>\to</math>); और संभवत: [[तार्किक द्विसशर्त]] (<math>\leftrightarrow</math>). आगे के संयोजकों को परिभाषित किया जा सकता है, यदि वांछित हो, तो उन्हें इन आदिमों के संदर्भ में परिभाषित किया जा सकता है। उदाहरण के लिए, NOR (कभी-कभी निरूपित किया जाता है <math>\downarrow</math>, निषेध की अस्वीकृति) को दो निषेधों के संयोजन के रूप में व्यक्त किया जा सकता है:
+तर्क पर आधुनिक विषय सामान्य रूप से संयोजकों के कुछ उपसमुच्चय को प्रारम्भिक रूप में लेते हैं: तार्किक संयोजन (<math>\land</math>); विच्छेदन (<math>\lor</math>); निषेध (<math>\neg</math>); [[सामग्री सशर्त|सशर्त सामग्री]] (<math>\to</math>); और संभवत: [[तार्किक द्विसशर्त]] (<math>\leftrightarrow</math>) आगे के संयोजकों को परिभाषित किया जा सकता है, यदि वांछित हो, तो उन्हें इन मौलिक के संदर्भ में परिभाषित किया जा सकता है। उदाहरण के लिए, नॉर (कभी-कभी निरूपित किया जाता है <math>\downarrow</math>, निषेध की अस्वीकृति) को दो निषेधों के संयोजन के रूप में व्यक्त किया जा सकता है:
 :<math>A \downarrow B := \neg A \land \neg B</math>
-इसी तरह, संयुग्मन का निषेध, NAND (कभी-कभी के रूप में निरूपित किया जाता है <math>\uparrow</math>), संयोजन और निषेध के संदर्भ में परिभाषित किया जा सकता है। यह पता चला है कि प्रत्येक बाइनरी संयोजक को परिभाषित किया जा सकता है <math>\{ \neg, \land, \lor, \to, \leftrightarrow \}</math>, इसलिए यह सेट कार्यात्मक रूप से पूर्ण है।
+इसी तरह, संयुग्मन का निषेध, एनएएनडी (कभी-कभी के रूप में निरूपित किया जाता है <math>\uparrow</math>), संयोजन और निषेध के संदर्भ में परिभाषित किया जा सकता है। यह पता चला है कि प्रत्येक बाइनरी संयोजक को परिभाषित किया जा सकता है <math>\{ \neg, \land, \lor, \to, \leftrightarrow \}</math>, इसलिए यह समुच्चय कार्यात्मक रूप से पूर्ण है।
-हालाँकि, इसमें अभी भी कुछ अतिरेक है: यह सेट न्यूनतम कार्यात्मक रूप से पूर्ण सेट नहीं है, क्योंकि सशर्त और द्विप्रतिबंध को अन्य संयोजकों के रूप में परिभाषित किया जा सकता है
+हालाँकि, इसमें अभी भी कुछ अतिरेक है: यह समुच्चय न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय नहीं है, क्योंकि सशर्त और द्विप्रतिबंध को अन्य संयोजकों के रूप में परिभाषित किया जा सकता है
 :<math>\begin{align}
@@ Line 20: / Line 21: @@
    A \leftrightarrow B &:= (A \to B) \land (B \to A).
 \end{align}</math>
-यह इस प्रकार है कि छोटा सेट <math>\{\neg, \land, \lor\}</math> कार्यात्मक रूप से भी पूर्ण है। लेकिन यह अभी भी न्यूनतम नहीं है, जैसा कि <math>\lor</math> के रूप में परिभाषित किया जा सकता है
+यह इस प्रकार है कि लघु समुच्चय <math>\{\neg, \land, \lor\}</math> कार्यात्मक रूप से भी पूर्ण है। लेकिन यह अभी भी न्यूनतम नहीं है, जैसा कि <math>\lor</math> के रूप में परिभाषित किया जा सकता है
 :<math>A \lor B := \neg(\neg A \land \neg B).</math>
@@ Line 26: / Line 27: @@
 :<math> \ A \vee B := \neg A \rightarrow B. </math>
-आगे कोई सरलीकरण संभव नहीं है। इसलिए, प्रत्येक दो-तत्व वाले संयोजकों का सेट <math>\neg</math> और एक <math>\{\land, \lor, \rightarrow\}</math> का न्यूनतम कार्यात्मक रूप से पूर्ण उपसमुच्चय है <math>\{\neg, \land, \lor, \to, \leftrightarrow\}</math>.
+आगे कोई सरलीकरण संभव नहीं है। इसलिए, प्रत्येक दो-तत्व वाले संयोजकों का समुच्चय <math>\neg</math> और एक <math>\{\land, \lor, \rightarrow\}</math> का न्यूनतम कार्यात्मक रूप से पूर्ण उपसमुच्चय है <math>\{\neg, \land, \lor, \to, \leftrightarrow\}</math>.
 == औपचारिक परिभाषा ==
-[[बूलियन डोमेन]] B = {0,1} दिया गया है, बूलियन फ़ंक्शन ''ƒ'' का एक सेट ''F''<sub>i</sub>: बी<sup>n<sub>i</sub></sup> → 'बी' 'कार्यात्मक रूप से पूर्ण' है यदि 'बी' पर [[क्लोन (बीजगणित)]] बुनियादी कार्यों द्वारा उत्पन्न किया गया है ƒ<sub>i</sub> सभी कार्य शामिल हैं ƒ: 'B'<sup>n</sup> → 'B', सभी निश्चित धनात्मक पूर्णांकों के लिए {{nowrap|''n'' ≥ 1}}. दूसरे शब्दों में, समुच्चय क्रियात्मक रूप से पूर्ण होता है यदि प्रत्येक बूलियन फलन जिसमें कम से कम एक चर होता है, को फलन के संदर्भ में व्यक्त किया जा सकता है ƒ<sub>i</sub>. चूँकि कम से कम एक चर के प्रत्येक बूलियन फ़ंक्शन को बाइनरी बूलियन फ़ंक्शंस के संदर्भ में व्यक्त किया जा सकता है, F कार्यात्मक रूप से पूर्ण है यदि और केवल यदि प्रत्येक बाइनरी बूलियन फ़ंक्शन को F में फ़ंक्शंस के संदर्भ में व्यक्त किया जा सकता है।
+[[बूलियन डोमेन|बूलियन प्रक्षेत्र]] B = {0,1} दिया गया है, बूलियन फलन ''ƒ'' का एक समुच्चय ''F''<sub>i</sub>: B<sup>n<sub>i</sub></sup> → 'B' 'कार्यात्मक रूप से पूर्ण' है यदि 'B' पर [[क्लोन (बीजगणित)|प्रतिरूप (बीजगणित)]] आधारिक कार्यों द्वारा उत्पन्न किया गया है ƒ<sub>i</sub> सभी फलन सम्मिलित हैं ƒ: 'B'<sup>n</sup> → 'B', सभी निश्चित धनात्मक पूर्णांकों के लिए {{nowrap|''n'' ≥ 1}} दूसरे शब्दों में, समुच्चय क्रियात्मक रूप से पूर्ण होता है यदि प्रत्येक बूलियन फलन जिसमें कम से कम एक चर होता है, ƒ<sub>i</sub> को फलन के संदर्भ में व्यक्त किया जा सकता है चूँकि कम से कम एक चर के प्रत्येक बूलियन फलन को बाइनरी बूलियन फलन के संदर्भ में व्यक्त किया जा सकता है, F कार्यात्मक रूप से पूर्ण है यदि और केवल यदि प्रत्येक बाइनरी बूलियन फलन को F में फलन के संदर्भ में व्यक्त किया जा सकता है।
-एक अधिक स्वाभाविक स्थिति यह होगी कि F द्वारा उत्पन्न क्लोन में सभी कार्य होते हैं: 'B'<sup>n</sup> → 'B', सभी पूर्णांकों के लिए {{nowrap|''n'' ≥ 0}}. हालाँकि, ऊपर दिए गए उदाहरण इस मजबूत अर्थ में कार्यात्मक रूप से पूर्ण नहीं हैं क्योंकि F के संदर्भ में एक [[arity]] फ़ंक्शन, यानी एक स्थिर अभिव्यक्ति लिखना संभव नहीं है, यदि F में स्वयं कम से कम एक शून्य फ़ंक्शन शामिल नहीं है। इस मजबूत परिभाषा के साथ, कार्यात्मक रूप से सबसे छोटे सेट में 2 तत्व होंगे।
+एक अधिक स्वाभाविक स्थिति यह होगी कि F द्वारा उत्पन्न प्रतिरूप संगणक में सभी फलन : 'B'<sup>n</sup> → 'B', सभी पूर्णांकों के लिए {{nowrap|''n'' ≥ 0}} लिए होते हैं। हालाँकि, ऊपर दिए गए उदाहरण इस प्रबल अर्थ में कार्यात्मक रूप से पूर्ण नहीं हैं क्योंकि F के संदर्भ में एक अशक्त फलन, अर्थात एक स्थिर अभिव्यक्ति लिखना संभव नहीं है, यदि F में स्वयं कम से कम एक शून्य फलन सम्मिलित नहीं है। इस प्रबल परिभाषा के साथ, कार्यात्मक रूप से सबसे छोटे समुच्चय में 2 तत्व होंगे।
-एक अन्य प्राकृतिक स्थिति यह होगी कि एफ द्वारा उत्पन्न क्लोन दो अशक्त स्थिर कार्यों के साथ कार्यात्मक रूप से पूर्ण या, समकक्ष रूप से, पिछले पैराग्राफ के मजबूत अर्थों में कार्यात्मक रूप से पूर्ण हो। बूलियन फ़ंक्शन का उदाहरण S(x, y, z) =z अगर x = y और S(x, y, z) = x अन्यथा दिखाता है कि यह स्थिति कार्यात्मक पूर्णता से सख्ती से कमजोर है।<ref name=Wesselkamper1975a>{{citation
+एक अन्य प्राकृतिक स्थिति यह होगी कि एफ द्वारा उत्पन्न प्रतिरूप दो अशक्त स्थिर कार्यों के साथ कार्यात्मक रूप से पूर्ण या, समकक्ष रूप से, पिछले पैराग्राफ के प्रबल अर्थों में कार्यात्मक रूप से पूर्ण हो। बूलियन फलन का उदाहरण S(x, y, z) =z यदि x = y और S(x, y, z) = x अन्यथा दिखाता है कि यह स्थिति कार्यात्मक पूर्णता दुर्बल है।<ref name=Wesselkamper1975a>{{citation
   | title = A sole sufficient operator
   | url = http://projecteuclid.org/euclid.ndjfl/1093891614
@@ Line 68: / Line 69: @@
-== कार्यात्मक पूर्णता का लक्षण वर्णन ==
+== कार्यात्मक पूर्णता की विशेषता ==
-{{further|Post's lattice}}
+{{further|लियोन पोस्ट का नियम}}
-[[एमिल लियोन पोस्ट]] ने साबित किया कि तार्किक संयोजकों का एक सेट कार्यात्मक रूप से पूर्ण है यदि और केवल अगर यह संयोजकों के निम्नलिखित सेटों में से किसी का उपसमुच्चय नहीं है:
+[[एमिल लियोन पोस्ट]] ने प्रमाणित किया कि तार्किक संयोजकों का एक समुच्चय कार्यात्मक रूप से पूर्ण है यदि और केवल यदि यह संयोजकों के निम्नलिखित समुच्चयों में से किसी का उपसमुच्चय नहीं है:
-* [[मोनोटोनिक]] संयोजक; किसी भी जुड़े हुए चर के सत्य मान को F से T में बिना किसी T से F में बदले बदलने से ये संयोजक कभी भी T से F में अपना वापसी मूल्य नहीं बदलते हैं, उदा। <math>\vee, \wedge, \top, \bot</math>.
+* [[मोनोटोनिक|एकदिष्‍ट]] संयोजक; किसी भी जुड़े हुए चर के सत्य मान को F से T में बिना किसी T से F में परिवर्तित करने से ये संयोजक कभी भी T से F में अपना पुनरावृत्ति मूल्य नहीं परिवर्तित करते हैं, उदाहरण <math>\vee, \wedge, \top, \bot</math>
-* affine रूपांतरण संयोजक, जैसे कि प्रत्येक जुड़ा चर या तो हमेशा या कभी भी इन संयोजकों के रिटर्न के सत्य मान को प्रभावित नहीं करता है, उदा. <math>\neg, \top, \bot, \leftrightarrow, \nleftrightarrow</math>.
+* एफ़िन रूपांतरण संयोजक, जैसे कि प्रत्येक जुड़ा चर या तो सदैव या कभी भी इन संयोजकों के प्रतिफल के सत्य मान को प्रभावित नहीं करता है, उदाहरण <math>\neg, \top, \bot, \leftrightarrow, \nleftrightarrow</math>
-* स्व-द्वैत संयोजक, जो अपने स्वयं के डे मॉर्गन द्वैत के बराबर हैं; यदि सभी चरों के सत्य मान उलट दिए जाते हैं, तो क्या सत्य मान इन संयोजकों की वापसी होती है, उदा। <math>\neg</math>, बहुसंख्यक कार्य (पी, क्यू, आर)।
+* स्व-द्वैत संयोजक, जो अपने स्वयं के डे मॉर्गन द्वैत के समान हैं; यदि सभी चरों के सत्य मान प्रतिलोम कर दिए जाते हैं, तो क्या सत्य मान इन संयोजकों का प्रतिफल होता है, उदाहरण <math>\neg</math>, बहुसंख्यक फलन (''p'',''q'',''r'')।
-* 'सत्य-संरक्षण' संयोजक; वे किसी भी व्याख्या के तहत सत्य मान 'टी' लौटाते हैं जो सभी चरों को 'टी' प्रदान करता है, उदा। <math>\vee, \wedge, \top, \rightarrow, \leftrightarrow</math>.
+* 'सत्य-संरक्षण' संयोजक; वे किसी भी व्याख्या के अंतर्गत सत्य मान ''''T'''<nowiki/>' प्रतिफल देते हैं जो सभी चरों को ''''T'''<nowiki/>' प्रदान करता है, उदाहरण <math>\vee, \wedge, \top, \rightarrow, \leftrightarrow</math>
-* मिथ्या-संरक्षण संयोजक; वे किसी भी व्याख्या के तहत सत्य मान F लौटाते हैं जो F को सभी चरों को निर्दिष्ट करता है, उदा। <math>\vee, \wedge, \bot, \nrightarrow, \nleftrightarrow</math>.
+* मिथ्या-संरक्षण संयोजक; वे किसी भी व्याख्या के अंतर्गत सत्य मान '''F''' प्रतिफल देते हैं जो '''F''' को सभी चरों को निर्दिष्ट करता है, उदाहरण <math>\vee, \wedge, \bot, \nrightarrow, \nleftrightarrow</math>
-वास्तव में, पोस्ट ने दो-तत्व सेट {टी, एफ}, जिसे आजकल पोस्ट की जाली कहा जाता है, पर सभी क्लोन (बीजगणित) के जाली (क्रम) का पूरा विवरण दिया (संरचना के तहत संचालन के सेट और सभी अनुमानों को शामिल किया गया) जो उपरोक्त परिणाम को एक साधारण परिणाम के रूप में दर्शाता है: कनेक्टिव्स के पांच उल्लिखित सेट वास्तव में अधिकतम क्लोन हैं।
+वास्तव में, पोस्ट ने दो-तत्व समुच्चय {'''T''', '''F'''}, जिसे वर्तमान मे पोस्ट का नियम कहा जाता है, पर सभी प्रतिरूप (बीजगणित) के नियम (क्रम) का पूरा विवरण दिया (संरचना के अंतर्गत संचालन के समुच्चय और सभी अनुमानों को सम्मिलित किया गया) जो उपरोक्त परिणाम को एक सरल उपप्रमेय के रूप में दर्शाता है: संयोजक के पांच उल्लिखित समुच्चय वास्तव में अधिकतम प्रतिरूप हैं।
-== न्यूनतम कार्यात्मक रूप से पूर्ण ऑपरेटर सेट ==
+== न्यूनतम कार्यात्मक रूप से पूर्ण संक्रियक समुच्चय ==
-जब एक एकल तार्किक संयोजक या बूलियन ऑपरेटर अपने आप में कार्यात्मक रूप से पूर्ण हो जाता है, तो इसे शेफ़र फ़ंक्शन कहा जाता है<ref name=Martin1989>The term was originally restricted to ''binary'' operations, but since the end of the 20th century it is used more generally. {{citation
+जब एकल तार्किक संयोजक या बूलियन संक्रियक अपने आप में कार्यात्मक रूप से पूर्ण हो जाता है, तो इसे '''शेफ़र फलन''' <ref name=Martin1989>The term was originally restricted to ''binary'' operations, but since the end of the 20th century it is used more generally. {{citation
   | title =  Systems of logic
   | year = 1989
@@ Line 88: / Line 89: @@
   | isbn = 978-0-521-36770-7
   | page = 54
-}}.</ref> या कभी-कभी एकमात्र पर्याप्त ऑपरेटर। इस संपत्ति के साथ कोई [[एकात्मक ऑपरेशन]] ऑपरेटर नहीं है। [[तार्किक नंद]] और लॉजिकल एनओआर, जो बूलियन बीजगणित # द्वैत सिद्धांत हैं, केवल दो बाइनरी शेफ़र फ़ंक्शन हैं। इन्हें 1880 के आसपास [[चार्ल्स सैंडर्स पियर्स]] द्वारा खोजा गया था, लेकिन प्रकाशित नहीं किया गया था, और स्वतंत्र रूप से फिर से खोजा गया और 1913 में हेनरी एम. शेफ़र द्वारा प्रकाशित किया गया।<ref name=Scharle1965>{{Citation
+}}.</ref> या कभी-कभी एकमात्र समुचित संक्रियक कहा जाता है। इस गुण के साथ कोई [[एकात्मक ऑपरेशन|एकात्मक]] संक्रियक नहीं है। [[तार्किक नंद|तार्किक एनएएनडी]] और तार्किक नॉर, जो बूलियन बीजगणित द्वैत सिद्धांत हैं, केवल दो बाइनरी शेफ़र फलन हैं। इन्हें 1880 के आसपास [[चार्ल्स सैंडर्स पियर्स]] द्वारा खोजा गया था, लेकिन प्रकाशित नहीं किया गया था, और स्वतंत्र रूप से पुनः खोजा गया और 1913 में हेनरी एम शेफ़र द्वारा प्रकाशित किया गया।<ref name=Scharle1965>{{Citation
   | title = Axiomatization of propositional calculus with Sheffer functors
   | url = http://projecteuclid.org/euclid.ndjfl/1093958259
@@ Line 99: / Line 100: @@
   | issue = 3
 | doi-access = free
-  }}.</ref>
+  }}.</ref> डिजिटल इलेक्ट्रॉनिक्स शब्दावली में, बाइनरी एनएएनडी गेट (↑) और बाइनरी नॉर गेट (↓) केवल बाइनरी [[यूनिवर्सल लॉजिक गेट|सार्वभौमिक तर्क गेट (द्वार]]) हैं।
-डिजिटल इलेक्ट्रॉनिक्स शब्दावली में, बाइनरी NAND गेट (↑) और बाइनरी NOR गेट (↓) केवल बाइनरी [[यूनिवर्सल लॉजिक गेट]] हैं।
+एरिटी ≤ 2 के साथ तार्किक संयोजकों के न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय निम्नलिखित हैं:<ref name="Wernick">Wernick, William (1942) "Complete Sets of Logical Functions," ''Transactions of the American Mathematical Society 51'': 117&ndash;32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math>\nleftarrow</math> and <math>\nrightarrow</math>.</ref>
+;एक तत्व: {↑}, {↓}
+====== दो तत्व: ======
+<math>\{\vee, \neg\}</math>, <math>\{\wedge, \neg\}</math>, <math>\{\to, \neg\}</math>, <math>\{\gets, \neg\}</math>, <math>\{\to, \bot\}</math>, <math>\{\gets, \bot\}</math>, <math>\{\to, \nleftrightarrow\}</math>, <math>\{\gets, \nleftrightarrow\}</math>, <math>\{\to, \nrightarrow\}</math>, <math>\{\to, \nleftarrow\}</math>, <math>\{\gets, \nrightarrow\}</math>, <math>\{\gets, \nleftarrow\}</math>, <math>\{\nrightarrow, \neg\}</math>, <math>\{\nleftarrow, \neg\}</math>, <math>\{\nrightarrow, \top\}</math>, <math>\{\nleftarrow, \top\}</math>, <math>\{\nrightarrow, \leftrightarrow\}</math>, <math>\{\nleftarrow, \leftrightarrow\}.</math>
+====== तीन तत्व: ======
+<math>\{\lor, \leftrightarrow, \bot\}</math>, <math>\{\lor, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\lor, \nleftrightarrow, \top\}</math>, <math>\{\land, \leftrightarrow, \bot\}</math>, <math>\{\land, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\land, \nleftrightarrow, \top\}.</math>
-एरिटी ≤ 2 के साथ तार्किक संयोजकों के न्यूनतम कार्यात्मक रूप से पूर्ण सेट निम्नलिखित हैं:<ref name="Wernick">Wernick, William (1942) "Complete Sets of Logical Functions," ''Transactions of the American Mathematical Society 51'': 117&ndash;32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math>\nleftarrow</math> and <math>\nrightarrow</math>.</ref>
+अधिकांश बाइनरी तार्किक संयोजक में तीन से अधिक का न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय नहीं है।<ref name="Wernick" /> उपरोक्त सूचियों को पठनीय रखने के लिए, एक या अधिक निविष्टि को ध्यान न देने वाले संकारक को छोड़ दिया गया है। उदाहरण के लिए, एक संक्रियक जो पहले निविष्टि को उपेक्षा करता है और दूसरे के निषेध को निर्गत करता है, उसे एकल निषेध द्वारा प्रतिस्थापित किया जा सकता है।
-;एक तत्व: {↑}, {↓}।
-दो तत्व: <math>\{\vee, \neg\}</math>, <math>\{\wedge, \neg\}</math>, <math>\{\to, \neg\}</math>, <math>\{\gets, \neg\}</math>, <math>\{\to, \bot\}</math>, <math>\{\gets, \bot\}</math>, <math>\{\to, \nleftrightarrow\}</math>, <math>\{\gets, \nleftrightarrow\}</math>, <math>\{\to, \nrightarrow\}</math>, <math>\{\to, \nleftarrow\}</math>, <math>\{\gets, \nrightarrow\}</math>, <math>\{\gets, \nleftarrow\}</math>, <math>\{\nrightarrow, \neg\}</math>, <math>\{\nleftarrow, \neg\}</math>, <math>\{\nrightarrow, \top\}</math>, <math>\{\nleftarrow, \top\}</math>, <math>\{\nrightarrow, \leftrightarrow\}</math>, <math>\{\nleftarrow, \leftrightarrow\}.</math>
-तीन तत्व: <math>\{\lor, \leftrightarrow, \bot\}</math>, <math>\{\lor, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\lor, \nleftrightarrow, \top\}</math>, <math>\{\land, \leftrightarrow, \bot\}</math>, <math>\{\land, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\land, \nleftrightarrow, \top\}.</math>
-अधिकांश बाइनरी लॉजिकल कनेक्टिव्स में तीन से अधिक का न्यूनतम कार्यात्मक रूप से पूर्ण सेट नहीं है।<ref name="Wernick" />उपरोक्त सूचियों को पठनीय रखने के लिए, एक या अधिक इनपुट को अनदेखा करने वाले ऑपरेटरों को छोड़ दिया गया है। उदाहरण के लिए, एक ऑपरेटर जो पहले इनपुट को अनदेखा करता है और दूसरे के निषेध को आउटपुट करता है, उसे एक एकल निषेध द्वारा प्रतिस्थापित किया जा सकता है।
 == उदाहरण ==
-* का उपयोग करने के उदाहरण <code>NAND</code>(↑) पूर्णता। जैसा कि दिखाया गया है,<ref>"NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html</ref>
+* एनएएनडी(↑) पूर्णता का उपयोग करने के उदाहरण। जैसा कि दिखाया गया है,<ref>"NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html</ref>
-** ¬ए ≡ ए ↑ ए
+*¬A ≡ A ↑ A
-** ए ∧ बी ≡ ¬ (ए ↑ बी) ≡ (ए ↑ बी) ↑ (ए ↑ बी)
+*A ∧ B ≡ ¬(A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
-** ए ∨ बी ≡ (ए ↑ ए) ↑ (बी ↑ बी)
+*A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
-* का उपयोग करने के उदाहरण <code>NOR</code>(↓) पूर्णता। जैसा कि दिखाया गया है,<ref>"NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html</ref>
+* <code>NOR</code>(↓) पूर्णता का उपयोग करने के उदाहरण। जैसा कि दिखाया गया है,<ref>"NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html</ref>
-** ¬ए ≡ ए ↓ ए
+*¬A ≡ A ↓ A
-** ए ∨ बी ≡ ¬ (ए ↓ बी) ≡ (ए ↓ बी) ↓ (ए ↓ बी)
+*A ∨ B ≡ ¬(A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
-** ए ∧ बी ≡ (ए ↓ ए) ↓ (बी ↓ बी)
+*A ∧ B ≡ (A ↓ A) ↓ (B ↓ B)
-ध्यान दें कि फाटकों की संख्या को कम करने के लिए एक इलेक्ट्रॉनिक सर्किट या सॉफ़्टवेयर फ़ंक्शन को पुन: उपयोग करके अनुकूलित किया जा सकता है। उदाहरण के लिए, ए ∧ बी ऑपरेशन, जब ↑ गेट्स द्वारा व्यक्त किया जाता है, ए ↑ बी के पुन: उपयोग के साथ कार्यान्वित किया जाता है,
+ध्यान दें कि गेट्स की संख्या को कम करने के लिए एक इलेक्ट्रॉनिक परिपथ या सॉफ़्टवेयर फलन को पुन: उपयोग करके अनुकूलित किया जा सकता है। उदाहरण के लिए, A ∧ B संक्रिया, जब ↑ गेट्स द्वारा व्यक्त किया जाता है, A ↑ B के पुन: उपयोग के साथ कार्यान्वित किया जाता है,
-: एक्स ≡ (ए ↑ बी); ए ∧ बी ≡ एक्स ↑ एक्स
+: X ≡ (A ↑ B); A ∧ B ≡ X ↑ X
-== अन्य डोमेन में ==
+== अन्य प्रक्षेत्र में ==
-तार्किक संयोजकों (बूलियन ऑपरेटर्स) के अलावा, कार्यात्मक पूर्णता को अन्य डोमेन में पेश किया जा सकता है। उदाहरण के लिए, प्रतिवर्ती संगणना द्वारों के एक सेट को कार्यात्मक रूप से पूर्ण कहा जाता है, यदि यह प्रत्येक प्रतिवर्ती ऑपरेटर को व्यक्त कर सकता है।
+तार्किक संयोजकों (बूलियन संक्रियक) के अतिरिक्त, कार्यात्मक पूर्णता को अन्य प्रक्षेत्र में प्रस्तुत किया जा सकता है। उदाहरण के लिए, प्रतिवर्ती संगणना द्वारों के एक समुच्चय को कार्यात्मक रूप से पूर्ण कहा जाता है, यदि यह प्रत्येक प्रतिवर्ती संक्रियक को व्यक्त कर सकता है।
--इनपुट [[फ्रेडकिन गेट]] अपने आप में कार्यात्मक रूप से पूर्ण प्रतिवर्ती गेट है - एकमात्र पर्याप्त ऑपरेटर। [[टोफोली गेट]] जैसे कई अन्य तीन-इनपुट यूनिवर्सल लॉजिक गेट हैं।
+-निविष्टि [[फ्रेडकिन गेट]] अपने आप में एकमात्र समुचित संक्रियक द्वारा कार्यात्मक रूप से पूर्ण प्रतिवर्ती गेट है। [[टोफोली गेट]] जैसे कई अन्य तीन-निविष्टि सार्वभौमिक तर्क द्वार हैं।
-[[क्वांटम कम्प्यूटिंग]] में, [[हैडमार्ड गेट]] और क्वांटम लॉजिक गेट # फेज शिफ्ट गेट्स सार्वभौमिक हैं, यद्यपि क्वांटम लॉजिक गेट के साथ # यूनिवर्सल क्वांटम गेट्स कार्यात्मक पूर्णता की तुलना में।
+क्वांटम कंप्यूटिंग में, हैडमार्ड गेट और T गेट सार्वभौमिक हैं, हालांकि कार्यात्मक पूर्णता की तुलना में अधिक प्रतिबंधात्मक परिभाषा है।
-== सेट सिद्धांत ==
+== समुच्चय सिद्धांत ==
-सेट के बीजगणित और [[बूलियन बीजगणित]] के बीच एक समरूपता है, अर्थात, उनके पास एक ही [[बूलियन बीजगणित (संरचना)]] है। फिर, यदि हम बूलियन ऑपरेटरों को सेट ऑपरेटरों में मैप करते हैं, तो उपरोक्त अनुवाद सेट के लिए भी मान्य हैं: सेट-थ्योरी ऑपरेटरों के कई न्यूनतम पूर्ण सेट हैं जो किसी अन्य सेट संबंध को उत्पन्न कर सकते हैं। अधिक लोकप्रिय न्यूनतम पूर्ण ऑपरेटर सेट {¬, ∩} और {¬, ∪} हैं। यदि सार्वभौमिक सेट रसेल के विरोधाभास, सेट ऑपरेटरों को झूठा होने के लिए प्रतिबंधित किया गया है- (Ø) संरक्षित, और कार्यात्मक रूप से पूर्ण बूलियन बीजगणित के बराबर नहीं हो सकता है।
+समुच्चय के बीजगणित और [[बूलियन बीजगणित]] के बीच एक समरूपता है, अर्थात, उनके पास एक ही [[बूलियन बीजगणित (संरचना)]] है। फिर, यदि हम बूलियन संकारक को समुच्चय संकारक में मानचित्र करते हैं, तो उपरोक्त अनुवाद समुच्चय के लिए भी मान्य हैं: समुच्चय-सिद्धांत संकारक के कई न्यूनतम पूर्ण समुच्चय हैं जो किसी अन्य समुच्चय संबंध को उत्पन्न कर सकते हैं। अधिक लोकप्रिय न्यूनतम पूर्ण संक्रियक समुच्चय {¬, ∩} और {¬, ∪} हैं। यदि सार्वभौमिक समुच्चय निषिद्ध है तो संक्रियक असत्यता- (Ø) संरक्षित होने तक सीमित हैं, और कार्यात्मक रूप से पूर्ण बूलियन बीजगणित के समान नहीं हो सकते हैं।
 == यह भी देखें ==
-* {{annotated link|Algebra of sets}}
+* समुच्चयों का बीजगणित - समुच्चयों से संबंधित सर्वसमिकाएँ और संबंध
-* {{annotated link|Boolean algebra}}
+* बूलियन बीजगणित - "सत्य" और "असत्य" का बीजगणितीय कुशलतापूर्वक प्रयोग
-* {{annotated link|Completeness (logic)}}
+* पूर्णता (तर्क) - कुछ तार्किक प्रणालियों की विशेषता
-* {{annotated link|List of Boolean algebra topics}}
+* बूलियन बीजगणित के विषयों की सूची
-* {{annotated link|NAND logic}}
+* एनएएनडी लॉजिक – केवल एनएएनडी गेट्स से निर्मित लॉजिक
-* {{annotated link|NOR logic}}
+* नॉर तर्क - सिर्फ नॉर गेट्स का उपयोग करके अन्य गेट्स बनाना
-* {{annotated link|One instruction set computer}}
+* निर्देश समुच्चय कंप्यूटर - अमूर्त मशीन जो केवल एक निर्देश का उपयोग करती है

Anonymous

Search

कार्यात्मक पूर्णता: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:32, 21 February 2023

Contents

परिचय

औपचारिक परिभाषा

कार्यात्मक पूर्णता की विशेषता

न्यूनतम कार्यात्मक रूप से पूर्ण संक्रियक समुच्चय

दो तत्व:

तीन तत्व:

उदाहरण

अन्य प्रक्षेत्र में

समुच्चय सिद्धांत

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

कार्यात्मक पूर्णता: Difference between revisions

Revision as of 18:32, 21 February 2023

परिचय

औपचारिक परिभाषा

कार्यात्मक पूर्णता की विशेषता

न्यूनतम कार्यात्मक रूप से पूर्ण संक्रियक समुच्चय

दो तत्व:

तीन तत्व:

उदाहरण

अन्य प्रक्षेत्र में

समुच्चय सिद्धांत

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories