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

गणितीय तर्क में, तार्किक संयोजकों या बूलियन संकारक का एक कार्यात्मक रूप से पूर्ण समुच्चय वह है जिसका उपयोग समुच्चय के इकाई को एक बूलियन अभिव्यक्ति में जोड़कर सभी संभव सत्य तालिकाओं को व्यक्त करने के लिए किया जा सकता है। संयोजकों का एक प्रसिद्ध पूर्ण समुच्चय { AND, NOT } है। प्रत्येक सिंगलटन (गणित) समुच्चय { NAND } और {NOR } कार्यात्मक रूप से पूर्ण हैं। हालांकि, समुच्चय {AND, OR } अपूर्ण है, इसकी कारण से NOT को व्यक्त करने में असमर्थता है।

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

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

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

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

परिचय

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

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

इसी तरह, संयुग्मन का निगेशन, NAND (कभी-कभी के रूप में निरूपित किया जाता है $\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 अन्यथा दिखाता है कि यह स्थिति कार्यात्मक पूर्णता दुर्बल है।

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

Further information: लियोन पोस्ट का नियम

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

• एकदिष्‍ट संयोजक; किसी भी जुड़े हुए चर के सत्य मान को 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}, जिसे वर्तमान मे पोस्ट का नियम कहा जाता है, पर सभी प्रतिरूप (बीजगणित) के नियम (क्रम) का पूरा विवरण दिया (संरचना के अंतर्गत संचालन के समुच्चय और सभी अनुमानों को सम्मिलित किया गया) जो उपरोक्त परिणाम को एक सरल उपप्रमेय के रूप में दर्शाता है: संयोजक के पांच उल्लिखित समुच्चय वास्तव में अधिकतम प्रतिरूप हैं।

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

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

arity ≤ 2 के साथ तार्किक संयोजकों के न्यूनतम कार्यात्मक रूप से पूर्ण समुच्चय निम्नलिखित हैं:

एक तत्व

{↑}, {↓}

दो तत्व:

$\{\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 \}.$

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

उदाहरण

• NAND (↑) पूर्णता का उपयोग करने के उदाहरण। जैसा कि दिखाया गया है,
• ¬A ≡ A ↑ A
• A ∧ B ≡ ¬(A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
• A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
• NOR(↓) पूर्णता का उपयोग करने के उदाहरण। जैसा कि दिखाया गया है,
• ¬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 गेट सार्वभौमिक हैं, हालांकि कार्यात्मक पूर्णता की तुलना में अधिक प्रतिबंधात्मक परिभाषा है।

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

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

यह भी देखें

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