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

गणितीय तर्क में, तार्किक संयोजकों या बूलियन समारोह का कार्यात्मक रूप से पूर्ण सेट वह है जिसका उपयोग सेट (गणित) के सदस्यों को बूलियन अभिव्यक्ति में जोड़कर सभी संभव सत्य तालिकाओं को व्यक्त करने के लिए किया जा सकता है। संयोजकों का एक प्रसिद्ध पूर्ण समुच्चय { तार्किक संयोजन, निषेध} है। प्रत्येक सिंगलटन (गणित) सेट { शेफर लाइन} और { तार्किक NOR} कार्यात्मक रूप से पूर्ण हैं। हालांकि, सेट { AND, तार्किक विच्छेदन } अधूरा है, इसकी वजह से 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: बी^n_i → 'बी' 'कार्यात्मक रूप से पूर्ण' है यदि 'बी' पर क्लोन (बीजगणित) बुनियादी कार्यों द्वारा उत्पन्न किया गया है ƒ_i सभी कार्य शामिल हैं ƒ: 'B'ⁿ → 'B', सभी निश्चित धनात्मक पूर्णांकों के लिए n ≥ 1. दूसरे शब्दों में, समुच्चय क्रियात्मक रूप से पूर्ण होता है यदि प्रत्येक बूलियन फलन जिसमें कम से कम एक चर होता है, को फलन के संदर्भ में व्यक्त किया जा सकता है ƒ_i. चूँकि कम से कम एक चर के प्रत्येक बूलियन फ़ंक्शन को बाइनरी बूलियन फ़ंक्शंस के संदर्भ में व्यक्त किया जा सकता है, F कार्यात्मक रूप से पूर्ण है यदि और केवल यदि प्रत्येक बाइनरी बूलियन फ़ंक्शन को F में फ़ंक्शंस के संदर्भ में व्यक्त किया जा सकता है।

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

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

कार्यात्मक पूर्णता का लक्षण वर्णन

Further information: Post's lattice

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

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

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

न्यूनतम कार्यात्मक रूप से पूर्ण ऑपरेटर सेट

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

एरिटी ≤ 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(↑) पूर्णता। जैसा कि दिखाया गया है,
  • ¬ए ≡ ए ↑ ए
  • ए ∧ बी ≡ ¬ (ए ↑ बी) ≡ (ए ↑ बी) ↑ (ए ↑ बी)
  • ए ∨ बी ≡ (ए ↑ ए) ↑ (बी ↑ बी)
• का उपयोग करने के उदाहरण NOR(↓) पूर्णता। जैसा कि दिखाया गया है,
  • ¬ए ≡ ए ↓ ए
  • ए ∨ बी ≡ ¬ (ए ↓ बी) ≡ (ए ↓ बी) ↓ (ए ↓ बी)
  • ए ∧ बी ≡ (ए ↓ ए) ↓ (बी ↓ बी)

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

एक्स ≡ (ए ↑ बी); ए ∧ बी ≡ एक्स ↑ एक्स

अन्य डोमेन में

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

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

क्वांटम कम्प्यूटिंग में, हैडमार्ड गेट और क्वांटम लॉजिक गेट # फेज शिफ्ट गेट्स सार्वभौमिक हैं, यद्यपि क्वांटम लॉजिक गेट के साथ # यूनिवर्सल क्वांटम गेट्स कार्यात्मक पूर्णता की तुलना में।

सेट सिद्धांत

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

यह भी देखें

• Algebra of sets
• Boolean algebra
• Completeness (logic)
• List of Boolean algebra topics
• NAND logic
• NOR logic
• One instruction set computer