बूलीय फलन

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

Not to be confused with द्विआधारी प्रकार्य.

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

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

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

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

उदाहरण

सोलह बाइनरी बूलियन फलन

See also: सत्यमान सारणी

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

• NOT, प्रतिवाद अथवा तार्किक पूरक - जो एक निविष्टि प्राप्त करता है और उस निविष्टि के गलत होने पर सही हो जाता है (नहीं)

• AND अथवा तार्किक संयोजन - सत्य जब सभी निविष्टि सत्य हैं (दोनों)

• OR अथवा तार्किक विच्छेदन - सच है जब कोई निविष्टि सच है (अन्यतर)

• XOR अथवा अनन्य - सच जब इसका एक निविष्टि सत्य है और दूसरा गलत है (बराबर नहीं)

• NAND अथवा शेफर स्ट्रोक - सत्य जब यह स्तिथि नहीं है कि सभी निविष्टि सत्य हैं (दोनों नहीं)
• NOR अथवा तार्किक NOR - सत्य जब कोई भी निविष्टि सत्य नहीं है (अन्यतर)
• XNOR अथवा तार्किक समानता - सच है जब दोनों निविष्टि समान (बराबर) हैं

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

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

File:Three input Boolean circuit.jpg

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

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

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

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

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

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

• प्रस्तावित निर्देशित विश्वकोश आरेख
  • तर्क द्वार का अंकीय परिपथ (कंप्यूटर साइंस) रेखाचित्र, एक बूलियन परिपथ
  • और-अंर्तवर्तक आरेख, केवल AND और NOT का उपयोग करके

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

विश्लेषण

See also: बूलियन फलनों का विश्लेषण

गुण

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

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

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

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

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

एक बूलियन फलन का झेगाल्किन बहुपद#Möbius रूपान्तरण|Mobius रूपान्तरण (या बूले-मोबियस रूपान्तरण) इसके झेगाल्किन बहुपद (बीजीय सामान्य रूप) के गुणांकों का समुच्चय है, जो एकपदीय घातांक सदिशों के फलन के रूप में होता है। यह एक इनवोल्यूशन (गणित) है | स्व-उलटा परिवर्तन। यह तेजी से फूरियर रूपांतरण के अनुरूप एक तितली आरेख (फास्ट फूरियर ट्रांसफॉर्म) का उपयोग करके कुशलतापूर्वक गणना की जा सकती है। संपाती बूलियन फलन उनके मोबियस रूपांतरण के बराबर होते हैं, अर्थात उनकी सत्यमान फलन (मिन्टरम) मान उनके बीजगणितीय (मोनोमियल) गुणांक के बराबर होते हैं। 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$). जब सभी ऑपरेंड स्वतंत्र होते हैं (कोई चर साझा नहीं करते हैं) एक बूलियन सूत्र में ऑपरेटरों के बहुपदों को बार-बार लागू करके एक फलन का बहुपद रूप पाया जा सकता है। जब गुणांक की गणना की जाती है तो मॉड्यूलर अंकगणित एक बीजगणितीय सामान्य रूप प्राप्त करता है (झेगाल्किन बहुपद)।

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

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