बूलियन फ़ंक्शन
गणित में, एक बूलियन फ़ंक्शन एक फ़ंक्शन (गणित) है जिसका फ़ंक्शन और परिणाम का तर्क दो-तत्व सेट (आमतौर पर {सही, गलत}, {0,1} या {-1,1}) से मान ग्रहण करता है।[1][2] वैकल्पिक नाम स्विचिंग फ़ंक्शन हैं, जिनका उपयोग विशेष रूप से पुराने कंप्यूटर विज्ञान साहित्य में किया जाता है,[3][4] और सत्य फ़ंक्शन (या तार्किक फ़ंक्शन), तर्क में उपयोग किया जाता है। बूलियन फ़ंक्शन बूलियन बीजगणित और स्विचिंग सिद्धांत का विषय हैं।[5]
एक बूलियन फ़ंक्शन फॉर्म लेता है , कहाँ बूलियन डोमेन के रूप में जाना जाता है और एक गैर-ऋणात्मक पूर्णांक है जिसे फ़ंक्शन की योग्यता कहा जाता है। मामले में जहां , फ़ंक्शन एक स्थिर तत्व है . एकाधिक आउटपुट वाला एक बूलियन फ़ंक्शन, साथ एक वेक्टरियल या वेक्टर-मूल्यवान बूलियन फ़ंक्शन (सममित क्रिप्टोग्राफी में एक एस-बॉक्स) है।[6]
वहाँ हैं विभिन्न बूलियन कार्यों के साथ तर्क; विभिन्न सत्य तालिकाओं की संख्या के बराबर प्रविष्टियाँ।
प्रत्येक -एरी बूलियन फ़ंक्शन को एक प्रस्ताव सूत्र के रूप में व्यक्त किया जा सकता है चर , और दो प्रस्ताव सूत्र तार्किक तुल्यता हैं यदि और केवल यदि वे समान बूलियन फ़ंक्शन को व्यक्त करते हैं।
उदाहरण
अल्पविकसित सममित बूलियन फ़ंक्शन (तार्किक संयोजक या तर्क द्वार ) हैं:
- इन्वर्टर (लॉजिक गेट), नकार या तार्किक पूरक - जो एक इनपुट प्राप्त करता है और इनपुट गलत होने पर सही रिटर्न देता है (नहीं)
- न ही गेट या तार्किक संयोजन - सत्य है जब सभी इनपुट सत्य हैं (दोनों)
- या गेट या तार्किक विच्छेद - सत्य है जब कोई इनपुट सत्य है (या तो)
- XOR गेट या एकमात्र - सत्य है जब इसका एक इनपुट सत्य है और दूसरा गलत है (बराबर नहीं)
- NAND गेट या शेफ़र लाइन - सत्य है जब ऐसा नहीं है कि सभी इनपुट सत्य हैं (दोनों नहीं)
- NOR गेट या लॉजिकल NOR - सत्य है जब कोई भी इनपुट सत्य नहीं है (न ही)
- XNOR गेट या तार्किक समानता - सत्य है जब दोनों इनपुट समान हों (बराबर)
अधिक जटिल फ़ंक्शन का एक उदाहरण बहुसंख्यक फ़ंक्शन (विषम संख्या में इनपुट का) है।
प्रतिनिधित्व
एक बूलियन फ़ंक्शन को विभिन्न तरीकों से निर्दिष्ट किया जा सकता है:
- सत्य तालिका: तर्कों के सभी संभावित मूल्यों के लिए इसके मूल्य को स्पष्ट रूप से सूचीबद्ध करना
- मार्क्वांड आरेख: सत्य तालिका मान दो-आयामी ग्रिड में व्यवस्थित होते हैं (कर्नाघ मानचित्र में प्रयुक्त)
- बाइनरी निर्णय आरेख, बाइनरी ट्री के नीचे सत्य तालिका मानों को सूचीबद्ध करना
- वेन आरेख, विमान के क्षेत्रों के रंग के रूप में सत्य तालिका मूल्यों को दर्शाता है
बीजगणितीय रूप से, अल्पविकसित बूलियन फ़ंक्शंस का उपयोग करते हुए एक प्रस्तावक सूत्र के रूप में:
विहित सामान्य रूप का निषेध, तर्कों और उनके पूरकों के AND और ORs का एक मनमाना मिश्रण
- तर्कों और उनके पूरकों के AND के OR के रूप में विच्छेदनात्मक सामान्य रूप
- संयोजक सामान्य रूप, तर्कों और उनके पूरकों के ORs के AND के रूप में
- कैनोनिकल सामान्य रूप, एक मानकीकृत सूत्र जो विशिष्ट रूप से फ़ंक्शन की पहचान करता है:
- बीजगणितीय सामान्य रूप या ज़ेगलकिन बहुपद, तर्कों के ANDs के XOR के रूप में (कोई पूरक की अनुमति नहीं है)
- पूर्ण (विहित) विच्छेदात्मक सामान्य रूप, प्रत्येक तर्क या पूरक वाले ANDs का एक OR (minterms)
- पूर्ण (विहित) संयोजी सामान्य रूप, प्रत्येक तर्क या पूरक (अधिकतम शब्द) वाले ओआरएस का एक और
- ब्लेक विहित रूप , फ़ंक्शन के सभी प्रमुख निहितार्थों का OR
बूलियन सूत्रों को ग्राफ़ के रूप में भी प्रदर्शित किया जा सकता है:
- प्रस्तावात्मक निर्देशित चक्रीय ग्राफ
- लॉजिक गेट का सर्किट (कंप्यूटर विज्ञान) आरेख, एक बूलियन सर्किट
- और-इन्वर्टर ग्राफ़, केवल AND और NOT का उपयोग करते हुए
इलेक्ट्रॉनिक सर्किट को अनुकूलित करने के लिए, बूलियन फ़ार्मुलों को क्विन-मैकक्लुस्की एल्गोरिदम या कर्णघ मानचित्र का उपयोग करके बूलियन कार्यों को न्यूनतम किया जा सकता है।
विश्लेषण
गुण
एक बूलियन फ़ंक्शन में विभिन्न प्रकार के गुण हो सकते हैं:[7]
- स्थिर कार्य: अपने तर्कों की परवाह किए बिना हमेशा सत्य या सदैव असत्य होता है।
- मोनोटोनिक फ़ंक्शन#बूलियन फ़ंक्शंस में: तर्क मानों के प्रत्येक संयोजन के लिए, किसी तर्क को ग़लत से सत्य में बदलने से आउटपुट केवल असत्य से सत्य पर स्विच हो सकता है, न कि सत्य से असत्य पर। किसी फ़ंक्शन को एक निश्चित वेरिएबल में एकजुट कार्य कहा जाता है यदि वह उस वेरिएबल में परिवर्तन के संबंध में मोनोटोन है।
- रैखिकता#बूलियन फ़ंक्शन: प्रत्येक चर के लिए, चर के मान को फ़्लिप करने से या तो हमेशा सत्य मान में अंतर आता है या कभी भी कोई अंतर नहीं आता (एक समता फ़ंक्शन)।
- सममित बूलियन फ़ंक्शन: मान इसके तर्कों के क्रम पर निर्भर नहीं करता है।
- एक बार पढ़ने का कार्य|रीड-वन्स: प्रत्येक चर के एक उदाहरण के साथ तार्किक संयोजन, तार्किक विघटन और निषेध के साथ व्यक्त किया जा सकता है।
- संतुलित बूलियन फ़ंक्शन: यदि इसकी सत्य तालिका में शून्य और एक की समान संख्या है। फ़ंक्शन का हैमिंग भार सत्य तालिका में मौजूद संख्याओं की संख्या है।
- मुड़ा हुआ कार्य: इसके सभी डेरिवेटिव संतुलित हैं (ऑटोसहसंबंध स्पेक्ट्रम शून्य है)
- एमवें क्रम से सहसंबंध प्रतिरक्षा: यदि आउटपुट अधिकतम एम तर्कों के सभी (रैखिक) संयोजनों से असंबंधित है
- इवेसिव बूलियन फ़ंक्शन: यदि फ़ंक्शन के मूल्यांकन के लिए हमेशा सभी तर्कों के मान की आवश्यकता होती है
- एक बूलियन फ़ंक्शन एक शेफ़र फ़ंक्शन है यदि इसका उपयोग किसी भी मनमाने ढंग से बूलियन फ़ंक्शन को बनाने के लिए किया जा सकता है (कार्यात्मक पूर्णता देखें)
- किसी फ़ंक्शन की बीजगणितीय डिग्री उसके बीजगणितीय सामान्य रूप में उच्चतम क्रम के एकपदी का क्रम है
सर्किट जटिलता सर्किट के आकार या गहराई के संबंध में बूलियन कार्यों को वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकती है।
व्युत्पन्न फलन
सकारात्मक और नकारात्मक शैनन सहकारकों (शैनन विस्तार) में बूले के विस्तार प्रमेय का उपयोग करके एक बूलियन फ़ंक्शन को विघटित किया जा सकता है, जो कि तर्कों में से एक (शून्य या एक) को ठीक करने के परिणामस्वरूप (k-1) -ary फ़ंक्शन हैं। इनपुट के एक सेट (एक रैखिक उपस्थान) पर एक रैखिक बाधा लगाकर प्राप्त किए गए सामान्य (k-ary) फ़ंक्शन को उप-फ़ंक्शन के रूप में जाना जाता है।[8] किसी एक तर्क के लिए फ़ंक्शन का बूलियन व्युत्पन्न एक (k-1)-ary फ़ंक्शन है जो तब सत्य होता है जब फ़ंक्शन का आउटपुट चुने गए इनपुट चर के प्रति संवेदनशील होता है; यह दो संगत सहकारकों का XOR है। रीड-मुलर विस्तार में एक व्युत्पन्न और एक सहकारक का उपयोग किया जाता है। अवधारणा को दिशा dx में k-ary व्युत्पन्न के रूप में सामान्यीकृत किया जा सकता है, जिसे x और x + dx पर फ़ंक्शन के अंतर (XOR) के रूप में प्राप्त किया जा सकता है।[8]
एक बूलियन फ़ंक्शन का ज़ेगल्किन बहुपद#मोबियस ट्रांसफॉर्मेशन|मोबियस ट्रांसफॉर्म (या बूले-मोबियस ट्रांसफॉर्म) एकपदी घातांक वैक्टर के एक फ़ंक्शन के रूप में, इसके ज़ेगल्किन बहुपद (बीजगणितीय सामान्य रूप) के गुणांक का सेट है। यह एक इनवोलुशन (गणित)|स्व-प्रतिलोम परिवर्तन है। इसकी गणना बटरफ्लाई आरेख (फास्ट मोबियस ट्रांसफॉर्म) का उपयोग करके कुशलतापूर्वक की जा सकती है, जो फास्ट फूरियर ट्रांसफॉर्म के अनुरूप है।[9] संयोग बूलियन फ़ंक्शन उनके मोबियस ट्रांसफॉर्म के बराबर हैं, यानी उनकी सत्य तालिका (मिनटर्म) मान उनके बीजगणितीय (मोनोमियल) गुणांक के बराबर हैं।[10] k तर्कों के 2^2^(k−1) संपाती फलन हैं।[11]
क्रिप्टोग्राफ़िक विश्लेषण
बूलियन फ़ंक्शन का वॉल्श रूपांतरण एक k-ary पूर्णांक-मूल्यवान फ़ंक्शन है जो पैरिटी फ़ंक्शन (वाल्श समारोह) में अपघटन के गुणांक देता है, जो फूरियर रूपांतरण द्वारा लयबद्ध में वास्तविक-मूल्यवान कार्यों के अपघटन के अनुरूप होता है। इसका वर्ग पावर स्पेक्ट्रम या वॉल्श स्पेक्ट्रम है। एकल बिट वेक्टर का वॉल्श गुणांक बूलियन फ़ंक्शन के आउटपुट के साथ उस बिट के सहसंबंध के लिए एक उपाय है। अधिकतम (निरपेक्ष मान में) वॉल्श गुणांक को फ़ंक्शन की रैखिकता के रूप में जाना जाता है।[8]बिट्स (ऑर्डर) की उच्चतम संख्या जिसके लिए सभी वॉल्श गुणांक 0 हैं (यानी सबफ़ंक्शन संतुलित हैं) को लचीलेपन के रूप में जाना जाता है, और फ़ंक्शन को उस ऑर्डर के लिए सहसंबंध प्रतिरक्षा कहा जाता है।[8]वॉल्श गुणांक रैखिक क्रिप्टोएनालिसिस में महत्वपूर्ण भूमिका निभाते हैं।
बूलियन फ़ंक्शन का स्वत:सहसंबंध एक k-ary पूर्णांक-मूल्यवान फ़ंक्शन है जो इनपुट और फ़ंक्शन आउटपुट में परिवर्तनों के एक निश्चित सेट के बीच सहसंबंध देता है। किसी दिए गए बिट वेक्टर के लिए यह उस दिशा में व्युत्पन्न के हैमिंग वजन से संबंधित है। अधिकतम स्वसहसंबंध गुणांक (निरपेक्ष मान में) को पूर्ण संकेतक के रूप में जाना जाता है।[7][8]यदि एक निश्चित संख्या में बिट्स के लिए सभी ऑटोसहसंबंध गुणांक 0 हैं (यानी डेरिवेटिव संतुलित हैं) तो फ़ंक्शन को उस क्रम में प्रसार मानदंड को पूरा करने के लिए कहा जाता है; यदि वे सभी शून्य हैं तो फलन एक मुड़ा हुआ फलन है।[12] ऑटोसहसंबंध गुणांक विभेदक क्रिप्टोएनालिसिस में महत्वपूर्ण भूमिका निभाते हैं।
बूलियन फ़ंक्शन के वॉल्श गुणांक और इसके ऑटोसहसंबंध गुणांक वीनर-खिनचिन प्रमेय के समकक्ष से संबंधित हैं, जो बताता है कि ऑटोसहसंबंध और पावर स्पेक्ट्रम एक वॉल्श ट्रांसफॉर्म जोड़ी हैं।[8]
रैखिक सन्निकटन तालिका
इन अवधारणाओं को उनके आउटपुट बिट्स (निर्देशांक) पर व्यक्तिगत रूप से विचार करके, या अधिक अच्छी तरह से, आउटपुट बिट्स के सभी रैखिक कार्यों के सेट को देखकर, जिसे इसके घटकों के रूप में जाना जाता है, स्वाभाविक रूप से वेक्टरियल बूलियन फ़ंक्शंस तक बढ़ाया जा सकता है।[6] घटकों के वॉल्श परिवर्तनों के सेट को रैखिक सन्निकटन तालिका (LAT) के रूप में जाना जाता है।[13][14] या सहसंबंध मैट्रिक्स;[15][16] यह इनपुट और आउटपुट बिट्स के विभिन्न रैखिक संयोजनों के बीच संबंध का वर्णन करता है। घटकों के स्वतःसहसंबंध गुणांक का सेट स्वतःसहसंबंध तालिका है,[14]घटकों के वॉल्श परिवर्तन से संबंधित[17] अधिक व्यापक रूप से प्रयुक्त अंतर वितरण तालिका (डीडीटी) के लिए[13][14]जो इनपुट और आउटपुट बिट्स में अंतर के बीच सहसंबंधों को सूचीबद्ध करता है (यह भी देखें: एस-बॉक्स)।
वास्तविक बहुपद रूप
यूनिट हाइपरक्यूब पर
कोई बूलियन फ़ंक्शन एक बहुरेखीय बहुपद द्वारा वास्तविक संख्या तक विशिष्ट रूप से विस्तारित (प्रक्षेपित) किया जा सकता है , सत्य तालिका मानों को लैग्रेंज बहुपद से गुणा करके निर्मित किया गया है:
बहुपद के गुणांकों के लिए प्रत्यक्ष अभिव्यक्ति उचित व्युत्पन्न लेकर प्राप्त की जा सकती है:
जब डोमेन एन-डायमेंशनल अतिविम तक सीमित होता है , बहुपद जब बूलियन फ़ंक्शन f को व्यक्तिगत संभावनाओं x के साथ n स्वतंत्र यादृच्छिक (बर्नौली वितरण) चर पर लागू किया जाता है, तो सकारात्मक परिणाम की संभावना मिलती है। इस तथ्य का एक विशेष मामला पैरिटी फ़ंक्शन के लिए जमा हुआ लेम्मा है। बूलियन फ़ंक्शन के बहुपद रूप का उपयोग फजी लॉजिक के प्राकृतिक विस्तार के रूप में भी किया जा सकता है।
सममित हाइपरक्यूब पर
अक्सर, बूलियन डोमेन को इस रूप में लिया जाता है , गलत ( 0 ) से 1 और सत्य ( 1 ) से -1 तक मैपिंग के साथ (बूलियन फ़ंक्शंस का विश्लेषण देखें)। के अनुरूप बहुपद फिर इसके द्वारा दिया जाता है:
अनुप्रयोग
बूलियन फ़ंक्शंस कम्प्यूटेशनल जटिलता सिद्धांत के प्रश्नों के साथ-साथ डिजिटल कम्प्यूटर ों के लिए प्रोसेसर के डिज़ाइन में एक बुनियादी भूमिका निभाते हैं, जहां उन्हें लॉजिक गेट का उपयोग करके इलेक्ट्रॉनिक सर्किट में कार्यान्वित किया जाता है।
बूलियन फ़ंक्शंस के गुण क्रिप्टोग्राफी में महत्वपूर्ण हैं, विशेष रूप से सममित कुंजी एल्गोरिदम के डिज़ाइन में (प्रतिस्थापन बॉक्स देखें)।
सहकारी खेल सिद्धांत सिद्धांत में, मोनोटोन बूलियन फ़ंक्शंस को सरल गेम (वोटिंग गेम) कहा जाता है; यह धारणा सामाजिक चयन सिद्धांत में समस्याओं को हल करने के लिए लागू की जाती है।
यह भी देखें
- छद्म-बूलियन फ़ंक्शन
- बूलियन-मूल्यवान फ़ंक्शन
- बूलियन बीजगणित विषयों की सूची
- सेट का बीजगणित
- निर्णय वृक्ष मॉडल
- संकेतक कार्य
- हस्ताक्षरित सेट
संदर्भ
- ↑ "बूलियन फ़ंक्शन - गणित का विश्वकोश". encyclopediaofmath.org. Retrieved 2021-05-03.
- ↑ Weisstein, Eric W. "बूलियन फ़ंक्शन". mathworld.wolfram.com. Retrieved 2021-05-03.
- ↑ "स्विचिंग फ़ंक्शन". TheFreeDictionary.com. Retrieved 2021-05-03.
- ↑ Davies, D. W. (December 1957). "तीन वेरिएबल्स के स्विचिंग फ़ंक्शन". IRE Transactions on Electronic Computers. EC-6 (4): 265–275. doi:10.1109/TEC.1957.5222038. ISSN 0367-9950.
- ↑ McCluskey, Edward J. (2003-01-01), "Switching theory", Encyclopedia of Computer Science, GBR: John Wiley and Sons Ltd., pp. 1727–1731, ISBN 978-0-470-86412-8, retrieved 2021-05-03
- ↑ 6.0 6.1 Carlet, Claude. "क्रिप्टोग्राफी के लिए वेक्टरियल बूलियन फ़ंक्शंस" (PDF). University of Paris. Archived (PDF) from the original on 2016-01-17.
- ↑ 7.0 7.1 "Boolean functions — Sage 9.2 Reference Manual: Cryptography". doc.sagemath.org. Retrieved 2021-05-01.
- ↑ 8.0 8.1 8.2 8.3 8.4 8.5 Tarannikov, Yuriy; Korolev, Peter; Botev, Anton (2001). Boyd, Colin (ed.). "बूलियन फ़ंक्शंस के ऑटोसहसंबंध गुणांक और सहसंबंध प्रतिरक्षा". Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 2248: 460–479. doi:10.1007/3-540-45682-1_27. ISBN 978-3-540-45682-7.
- ↑ Carlet, Claude (2010), "Boolean Functions for Cryptography and Error-Correcting Codes" (PDF), Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Encyclopedia of Mathematics and its Applications, Cambridge: Cambridge University Press, pp. 257–397, ISBN 978-0-521-84752-0, retrieved 2021-05-17
- ↑ Pieprzyk, Josef; Wang, Huaxiong; Zhang, Xian-Mo (2011-05-01). "मोबियस रूपांतरण, संपाती बूलियन फ़ंक्शन और बूलियन फ़ंक्शंस की गैर-संयोग संपत्ति". International Journal of Computer Mathematics. 88 (7): 1398–1416. doi:10.1080/00207160.2010.509428. ISSN 0020-7160. S2CID 9580510.
- ↑ Nitaj, Abderrahmane; Susilo, Willy; Tonien, Joseph (2017-10-01). "बूलियन कार्यों के लिए डिरिचलेट उत्पाद". Journal of Applied Mathematics and Computing. 55 (1): 293–312. doi:10.1007/s12190-016-1037-4. ISSN 1865-2085. S2CID 16760125.
- ↑ Canteaut, Anne; Carlet, Claude; Charpin, Pascale; Fontaine, Caroline (2000-05-14). "अत्यधिक अरेखीय बूलियन कार्यों की प्रसार विशेषताएँ और सहसंबंध-प्रतिरक्षा". Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques. EUROCRYPT'00. Bruges, Belgium: Springer-Verlag: 507–522. ISBN 978-3-540-67517-4.
- ↑ 13.0 13.1 Heys, Howard M. "रैखिक और विभेदक क्रिप्टोनालिसिस पर एक ट्यूटोरियल" (PDF). Archived (PDF) from the original on 2017-05-17.
- ↑ 14.0 14.1 14.2 "S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography". doc.sagemath.org. Retrieved 2021-05-04.
- ↑ Daemen, Joan; Govaerts, René; Vandewalle, Joos (1995). Preneel, Bart (ed.). "सहसंबंध मैट्रिक्स". Fast Software Encryption. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 1008: 275–285. doi:10.1007/3-540-60590-8_21. ISBN 978-3-540-47809-6.
- ↑ Daemen, Joan (10 June 1998). "Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael" (PDF). NIST. Archived (PDF) from the original on 2018-07-23.
- ↑ Nyberg, Kaisa (December 1, 2019). "विस्तारित ऑटोसहसंबंध और बूमरैंग टेबल्स और वेक्टरियल बूलियन फ़ंक्शंस के नॉनलाइनरिटी गुणों के बीच लिंक" (PDF). Archived (PDF) from the original on 2020-11-02.
अग्रिम पठन
- 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
- Templates that generate short descriptions
- Collapse templates
- Navigational boxes
- Navigational boxes without horizontal lists
- Sidebars with styles needing conversion
- Templates generating microformats
- Templates that are not mobile friendly
- Wikipedia metatemplates
- Mathematics navigational boxes
- Navbox orphans
- Philosophy and thinking navigational boxes
- Templates Translated in Hindi
- बूलियन बीजगणित
- बाइनरी अंकगणित
- तर्क द्वार
- प्रोग्रामिंग निर्माण
- Machine Translated Page
- Created On 23/06/2023