बूलीय फलन

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

Not to be confused with Binary function.

गणित में, एक बूलियन फ़ंक्शन एक फ़ंक्शन (गणित) होता है जिसका फ़ंक्शन और परिणाम का तर्क दो-तत्व सेट (आमतौर पर {true, false}, {0,1} या {-1,1}) से मान लेता है। वैकल्पिक नाम स्विचिंग फ़ंक्शन हैं, विशेष रूप से पुराने कंप्यूटर विज्ञान साहित्य में उपयोग किए जाते हैं, और सत्य कार्य (या तार्किक कार्य), तर्क में प्रयुक्त। बूलियन फ़ंक्शन बूलियन बीजगणित और स्विचिंग सिद्धांत का विषय हैं।

एक बूलियन फ़ंक्शन रूप लेता है $f:\{0,1\}^{k}\to \{0,1\}$, कहाँ $\{0,1\}$ बूलियन डोमेन के रूप में जाना जाता है और $k$ एक गैर-ऋणात्मक पूर्णांक है जिसे फलन की arity कहा जाता है। मामले में जहां $k=0$, फलन का एक स्थिर तत्व है $\{0,1\}$. एकाधिक आउटपुट के साथ एक बूलियन फ़ंक्शन, $f:\{0,1\}^{k}\to \{0,1\}^{m}$ साथ $m>1$ एक सदिश या सदिश-मूल्यवान बूलियन फ़ंक्शन (सममित क्रिप्टोग्राफी में एक एस-बॉक्स) है।

वहाँ हैं $2^{2^{k}}$ विभिन्न बूलियन कार्यों के साथ $k$ तर्क; विभिन्न सत्य तालिका की संख्या के बराबर $2^{k}$ प्रविष्टियाँ।

प्रत्येक $k$-एरी बूलियन फ़ंक्शन को प्रस्ताविक सूत्र के रूप में व्यक्त किया जा सकता है $k$ चर $x_{1},...,x_{k}$, और दो तर्कवाक्य सूत्र तार्किक तुल्यता हैं यदि और केवल यदि वे एक ही बूलियन फ़ंक्शन को व्यक्त करते हैं।

उदाहरण

सोलह बाइनरी बूलियन फ़ंक्शन

See also: Truth table

प्रारंभिक सममित बूलियन फ़ंक्शन (तार्किक संयोजक या तर्क द्वार) हैं:

• इन्वर्टर (लॉजिक गेट), निषेध या तार्किक पूरक - जो एक इनपुट प्राप्त करता है और जब वह इनपुट गलत होता है तो सही होता है ( नहीं )

• या द्वार या तार्किक संयोजन - सत्य जब सभी इनपुट सत्य हैं (दोनों)

• या गेट या तार्किक विच्छेदन - सच है जब कोई इनपुट सच है (या तो)

• XOR गेट या एकमात्र - सच जब इसका एक इनपुट सत्य है और दूसरा गलत है (बराबर नहीं)

• नंद द्वार या शेफर लाइन - सत्य जब यह मामला नहीं है कि सभी इनपुट सत्य हैं (दोनों नहीं)
• NOR गेट या लॉजिकल NOR - सत्य जब कोई भी इनपुट सत्य नहीं है (न तो)
• XNOR गेट या तार्किक समानता - सच है जब दोनों इनपुट समान (बराबर) हैं

अधिक जटिल फ़ंक्शन का एक उदाहरण बहुसंख्यक फ़ंक्शन (विषम संख्या में इनपुट) है।

प्रतिनिधित्व

File:Three input Boolean circuit.jpg

एक बूलियन फ़ंक्शन एक बूलियन सर्किट के रूप में दर्शाया गया है

एक बूलियन फ़ंक्शन को विभिन्न तरीकों से निर्दिष्ट किया जा सकता है:

• सत्य तालिका: तर्कों के सभी संभावित मूल्यों के लिए इसके मूल्य को स्पष्ट रूप से सूचीबद्ध करना
  • मार्क्वांड आरेख: दो-आयामी ग्रिड में व्यवस्थित सत्य तालिका मान (कर्नाघ मानचित्र में उपयोग किया जाता है)
  • द्विआधारी निर्णय आरेख, एक द्विआधारी वृक्ष के तल पर सत्य तालिका मानों को सूचीबद्ध करता है
  • वेन आरेख, समतल के क्षेत्रों के रंग के रूप में सत्य तालिका मानों का चित्रण

बीजगणितीय रूप से, प्रारंभिक बूलियन कार्यों का उपयोग करके एक प्रस्तावक सूत्र के रूप में:

• नकारात्मक सामान्य रूप, तर्कों और उनके पूरक के AND और OR का मनमाना मिश्रण
• वियोगात्मक सामान्य रूप, तर्कों और उनके पूरक के ANDs के OR के रूप में
• संयोजक सामान्य रूप, तर्कों और उनके पूरक के ORs के AND के रूप में
• कैननिकल सामान्य रूप, एक मानकीकृत सूत्र जो विशिष्ट रूप से फ़ंक्शन की पहचान करता है:
  • बीजगणितीय सामान्य रूप या Zhegalkin बहुपद, तर्कों के ANDs के XOR के रूप में (कोई पूरक की अनुमति नहीं है)
  • पूर्ण (प्रामाणिक) वियोगात्मक सामान्य रूप, प्रत्येक तर्क या पूरक (minterms) युक्त AND का OR
  • पूर्ण (प्रामाणिक) संयोजक सामान्य रूप, प्रत्येक तर्क या पूरक (maxterms) वाले ओआरएस का AND
  • ब्लेक विहित रूप, फंक्शन के सभी प्रधान शामिल है का OR

बूलियन फ़ार्मुलों को ग्राफ़ के रूप में भी प्रदर्शित किया जा सकता है:

• प्रस्तावित निर्देशित विश्वकोश ग्राफ
  • लॉजिक गेट का सर्किट (कंप्यूटर साइंस) डायग्राम, एक बूलियन सर्किट
  • और-पलटनेवाला ग्राफ, केवल AND और NOT का उपयोग करके

इलेक्ट्रॉनिक सर्किट को अनुकूलित करने के लिए, बूलियन सूत्र क्विन-मैक्लुस्की एल्गोरिथम या कर्णघ मानचित्र का उपयोग करके बूलियन कार्यों का न्यूनतमकरण हो सकता है।

विश्लेषण

See also: Analysis of Boolean functions

गुण

एक बूलियन फ़ंक्शन में विभिन्न गुण हो सकते हैं:

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

सर्किट जटिलता बूलियन कार्यों को उन सर्किटों के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं।

व्युत्पन्न कार्य

सकारात्मक और नकारात्मक शैनन कॉफ़ेक्टर्स (शैनन विस्तार) में बूल के विस्तार प्रमेय का उपयोग करके एक बूलियन फ़ंक्शन को विघटित किया जा सकता है, जो कि (k-1) -री फ़ंक्शन हैं जो किसी एक तर्क (शून्य या एक) को ठीक करने के परिणामस्वरूप होते हैं। इनपुट के एक सेट (एक रैखिक उप-स्थान) पर एक रैखिक बाधा लगाकर प्राप्त सामान्य (के-एरी) कार्यों को उप-कार्यों के रूप में जाना जाता है। किसी एक तर्क के लिए फ़ंक्शन का बूलियन व्युत्पन्न एक (k-1)-एरी फ़ंक्शन है जो तब सत्य होता है जब फ़ंक्शन का आउटपुट चुने गए इनपुट चर के प्रति संवेदनशील होता है; यह दो संगत सहकारकों का XOR है। रीड-मुलर विस्तार में एक व्युत्पन्न और एक सहकारक का उपयोग किया जाता है। अवधारणा को x और x + dx पर फ़ंक्शन के अंतर (XOR) के रूप में प्राप्त दिशा dx में k-ary व्युत्पन्न के रूप में सामान्यीकृत किया जा सकता है।

एक बूलियन फलन का Zhegalkin बहुपद#Möbius रूपान्तरण|Mobius रूपान्तरण (या बूले-मोबियस रूपान्तरण) इसके Zhegalkin बहुपद (बीजीय सामान्य रूप) के गुणांकों का समुच्चय है, जो एकपदीय घातांक सदिशों के फलन के रूप में होता है। यह एक इनवोल्यूशन (गणित) है | स्व-उलटा परिवर्तन। यह तेजी से फूरियर रूपांतरण के अनुरूप एक तितली आरेख (फास्ट फूरियर ट्रांसफॉर्म) का उपयोग करके कुशलतापूर्वक गणना की जा सकती है। संपाती बूलियन फलन उनके मोबियस रूपांतरण के बराबर होते हैं, अर्थात उनकी सत्य तालिका (मिन्टरम) मान उनके बीजगणितीय (मोनोमियल) गुणांक के बराबर होते हैं। k तर्कों के 2^2^(k−1) संपाती फलन हैं।

क्रिप्टोग्राफिक विश्लेषण

बूलियन फ़ंक्शन का वॉल्श रूपांतरण एक k-ary पूर्णांक-मूल्यवान फ़ंक्शन है, जो पैरिटी फ़ंक्शन (वाल्श समारोह) में अपघटन के गुणांक देता है, फूरियर रूपांतरण द्वारा लयबद्ध में वास्तविक-मूल्यवान फ़ंक्शन के अपघटन के अनुरूप होता है। इसका वर्ग पावर स्पेक्ट्रम या वॉल्श स्पेक्ट्रम है। एकल बिट सदिश का वॉल्श गुणांक बूलियन फ़ंक्शन के आउटपुट के साथ उस बिट के सहसंबंध के लिए एक उपाय है। अधिकतम (पूर्ण मान में) वॉल्श गुणांक को फलन की रैखिकता के रूप में जाना जाता है।बिट्स (ऑर्डर) की उच्चतम संख्या जिसके लिए सभी वॉल्श गुणांक 0 हैं (अर्थात सबफंक्शन संतुलित हैं) को लचीलापन के रूप में जाना जाता है, और फ़ंक्शन को उस क्रम से सहसंबंध प्रतिरक्षा कहा जाता है।वॉल्श गुणांक रैखिक क्रिप्ट विश्लेषण में एक महत्वपूर्ण भूमिका निभाते हैं।

बूलियन फ़ंक्शन का स्वत: सहसंबंध एक k-ary पूर्णांक-मूल्यवान फ़ंक्शन है जो इनपुट और फ़ंक्शन ouput में परिवर्तन के एक निश्चित सेट के बीच संबंध देता है। किसी दिए गए बिट वेक्टर के लिए यह उस दिशा में डेरिवेटिव के हैमिंग वजन से संबंधित है। अधिकतम स्वसहसंबंध गुणांक (निरपेक्ष मूल्य में) को निरपेक्ष संकेतक के रूप में जाना जाता है।यदि बिट्स की एक निश्चित संख्या के लिए सभी स्वतःसंबंध गुणांक 0 हैं (अर्थात डेरिवेटिव संतुलित हैं) तो फ़ंक्शन को उस क्रम के प्रचार मानदंड को पूरा करने के लिए कहा जाता है; यदि वे सभी शून्य हैं तो फलन तुला फलन है। स्वतः सहसंबंध गुणांक विभेदक क्रिप्ट विश्लेषण में महत्वपूर्ण भूमिका निभाते हैं।

एक बूलियन फ़ंक्शन के वॉल्श गुणांक और इसके स्वत: सहसंबंध गुणांक वीनर-खिनचिन प्रमेय के समकक्ष से संबंधित हैं, जो बताता है कि स्वत: सहसंबंध और पावर स्पेक्ट्रम वॉल्श रूपांतरण जोड़ी हैं।

इन अवधारणाओं को स्वाभाविक रूप से सदिश बूलियन कार्यों के लिए उनके आउटपुट बिट्स (निर्देशांक) पर व्यक्तिगत रूप से, या अधिक अच्छी तरह से, आउटपुट बिट्स के सभी रैखिक कार्यों के सेट को देखकर, इसके घटकों के रूप में जाना जाता है। घटकों के वॉल्श रूपांतरणों के सेट को रैखिक सन्निकटन तालिका (LAT) के रूप में जाना जाता है या सहसंबंध मैट्रिक्स; यह इनपुट और आउटपुट बिट्स के विभिन्न रैखिक संयोजनों के बीच संबंध का वर्णन करता है। घटकों के स्वत: सहसंबंध गुणांक का सेट स्वत: सहसंबंध तालिका है,घटकों के वाल्श परिवर्तन से संबंधित अधिक व्यापक रूप से प्रयुक्त अंतर वितरण तालिका (DDT) के लिएजो इनपुट और आउटपुट बिट्स में अंतर के बीच सहसंबंधों को सूचीबद्ध करता है (यह भी देखें: एस-बॉक्स)।

वास्तविक बहुपद रूप

=== यूनिट हाइपरक्यूब === पर कोई भी बूलियन फ़ंक्शन $f(x):\{0,1\}^{n}\rightarrow \{0,1\}$ में एक बहुरेखीय बहुपद द्वारा विशिष्ट रूप से वास्तविक संख्या में विस्तारित (प्रक्षेपित) किया जा सकता है $\mathbb {R} ^{n}$, लैग्रेंज बहुपद द्वारा गुणा किए गए सत्य तालिका मानों के योग द्वारा निर्मित:

$$f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})$$

उदाहरण के लिए, बाइनरी एक्सओआर फ़ंक्शन का विस्तार $x\oplus y$ है

$$0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy$$

जो बराबर है

$$x+y-2xy$$

कुछ अन्य उदाहरण निषेध हैं ($1-x$), और ($xy$) और या ($x+y-xy$). जब सभी ऑपरेंड स्वतंत्र होते हैं (कोई चर साझा नहीं करते हैं) एक बूलियन सूत्र में ऑपरेटरों के बहुपदों को बार-बार लागू करके एक फ़ंक्शन का बहुपद रूप पाया जा सकता है। जब गुणांक की गणना की जाती है तो मॉड्यूलर अंकगणित एक बीजगणितीय सामान्य रूप प्राप्त करता है (Zhegalkin बहुपद)।

बहुपद के गुणांकों के लिए प्रत्यक्ष व्यंजक उपयुक्त अवकलज लेकर प्राप्त किए जा सकते हैं:

$${\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}$$

यह मोबियस ट्रांसफॉर्म के रूप में सामान्यीकृत होता है। बिट वैक्टर के आंशिक रूप से ऑर्डर किए गए सेट के मोबियस उलटा:

$$f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)$$

कहाँ $|a|$ बिट वेक्टर के वजन को दर्शाता है $a$. मोडुलो 2 लिया, यह झेगलकिन बहुपद है | बूलियन मोबियस रूपांतरण, बीजगणितीय सामान्य रूप गुणांक देता है:

$${\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)$$

दोनों ही मामलों में, योग को सभी बिट-वैक्टर a पर m द्वारा कवर किया जाता है, यानी m के एक बिट का एक सबसेट का एक बिट।

जब डोमेन एन-डायमेंशनल अतिविम तक सीमित है $[0,1]^{n}$, बहुपद $f^{*}(x):[0,1]^{n}\rightarrow [0,1]$ एक सकारात्मक परिणाम की संभावना देता है जब बूलियन फ़ंक्शन f को अलग-अलग संभावनाओं x के साथ n स्वतंत्र यादृच्छिक (बर्नौली वितरण) चर पर लागू किया जाता है। इस तथ्य का एक विशेष मामला पैरिटी फ़ंक्शन के लिए पाइलिंग-अप लेम्मा है। बूलियन फ़ंक्शन के बहुपद रूप का उपयोग फजी लॉजिक के प्राकृतिक विस्तार के रूप में भी किया जा सकता है।

=== सममित हाइपरक्यूब === पर अक्सर, बूलियन डोमेन को इस रूप में लिया जाता है $\{-1,1\}$, झूठी (0) मैपिंग के साथ 1 और सही (1) से -1 (बूलियन कार्यों का विश्लेषण देखें)। के अनुरूप बहुपद $g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}$ तब दिया जाता है:

$$g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}$$

सममित बूलियन डोमेन का उपयोग बूलियन कार्यों के विश्लेषण के कुछ पहलुओं को सरल करता है, क्योंकि निषेध -1 से गुणा करने के अनुरूप है और समता समारोह एकपदीय हैं (एक्सओआर गुणन है)। इस प्रकार यह बहुपद रूप फलन के वॉल्श रूपांतरण (इस संदर्भ में फूरियर रूपांतरण के रूप में भी जाना जाता है) से मेल खाता है (ऊपर देखें)। बहुपद की भी वही सांख्यिकीय व्याख्या होती है जो मानक बूलियन डोमेन में होती है, सिवाय इसके कि यह अब अपेक्षित मानों से संबंधित है $E(X)=P(X=1)-P(X=-1)\in [-1,1]$ (उदाहरण के लिए पाइलिंग-अप लेम्मा देखें)।

अनुप्रयोग

कम्प्यूटेशनल जटिलता सिद्धांत के सवालों के साथ-साथ डिजिटल कम्प्यूटर के लिए प्रोसेसर के डिजाइन में बूलियन फ़ंक्शंस एक बुनियादी भूमिका निभाते हैं, जहाँ वे लॉजिक गेट का उपयोग करके इलेक्ट्रॉनिक सर्किट में कार्यान्वित किए जाते हैं।

क्रिप्टोग्राफ़ी में बूलियन फ़ंक्शंस के गुण महत्वपूर्ण हैं, विशेष रूप से सममित कुंजी एल्गोरिदम के डिज़ाइन में (प्रतिस्थापन बॉक्स देखें)।

सहकारी खेल सिद्धांत सिद्धांत में, मोनोटोन बूलियन कार्यों को सरल खेल (मतदान खेल) कहा जाता है; सामाजिक चयन सिद्धांत में समस्याओं को हल करने के लिए इस धारणा को लागू किया जाता है।

यह भी देखें

• छद्म-बूलियन समारोह
• बूलियन-मूल्यवान फ़ंक्शन
• बूलियन बीजगणित विषयों की सूची
• समुच्चयों का बीजगणित
• निर्णय वृक्ष मॉडल
• संकेतक समारोह
• हस्ताक्षरित सेट

अग्रिम पठन

• Crama, Yves; Hammer, Peter L. (2011), Boolean Functions: Theory, Algorithms, and Applications, Cambridge University Press, doi:10.1017/CBO9780511852008, ISBN 9780511852008
• "Boolean function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (November 2003). "Arithmetic expressions optimisation using dual polarity property". Serbian Journal of Electrical Engineering. 1 (71–80, number 1): 71–80. doi:10.2298/SJEE0301071J.
• Arnold, Bradford Henry (1 January 2011). Logic and Boolean Algebra. Courier Corporation. ISBN 978-0-486-48385-6.
• Mano, M. M.; Ciletti, M. D. (2013), Digital Design, Pearson