बूलीय फलन

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

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