बूलीय फलन

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

गणित में, बूलियन फलन एक फलन (गणित) होता है जिसका फलन और परिणाम का तर्क दो-तत्व सम्मुच्चय (सामान्यतः {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-एरी) कार्यों को उप-कार्यों के रूप में जाना जाता है।

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

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

गूढ़लेखिकी विश्लेषण

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

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

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

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

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

एकांक अतिविम पर कोई भी बूलियन फलन $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})$$

उदाहरण के लिए, युग्मक XOR फलन का विस्तार $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 द्वारा आच्छादित किया जाता है।

जब कार्यक्षेत्र n-विमीय अतिविम $[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 से गुणा करने के अनुरूप है और समता फलन एकपदीय हैं (XOR गुणन है)। इस प्रकार यह बहुपद रूप फलन के वॉल्श रूपांतरण (इस संदर्भ में फूरियर रूपांतरण के रूप में भी जाना जाता है) से मेल खाता है (ऊपर देखें)। बहुपद की भी वही सांख्यिकीय व्याख्या होती है जो मानक बूलियन कार्यक्षेत्र में होती है, सिवाय इसके कि यह अब अपेक्षित मानों से संबंधित है $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