ज़ेकालकिन बहुपद

झेगाल्किन (झेगाल्किन, गेगल्किन या शेगल्किन भी बहुपद (Russian: полиномы Жегалкина), बीजगणितीय सामान्य रूप के रूप में भी जाना जाता है, बूलियन बीजगणित में कार्यों का प्रतिनिधित्व है। 1927 में रूसी गणितज्ञ इवान इवानोविच झेगाल्किन द्वारा पेश किया गया, बहुपद वलय हैं #मापांक अंकगणित पर परिभाषा # पूर्णांक है।मापांक अंकगणितीय परिणाम के परिणामी अध: पतन के कारण झेगाल्किन बहुपद साधारण बहुपदों की तुलना में सरल होते हैं, जिनमें न तो गुणांक और न ही घातांक की आवश्यकता होती है। गुणांक बेमानी हैं क्योंकि 1 एकमात्र अशून्य गुणांक है। घातांकी बेमानी हैं क्योंकि अंकगणित मोड 2, x² = x इसलिए एक बहुपद जैसे 3x²y⁵z सर्वांगसम है, और इसलिए इसे xyz के रूप में फिर से लिखा जा सकता है।

बूलियन समकक्ष

1927 से पहले, बूलियन बीजगणित को तार्किक संयुग्मन, तार्किक संयोजन, तार्किक निषेध, और इसी तरह के तार्किक संचालन के साथ तार्किक मूल्यों का एक कलन माना जाता था। झेगाल्किन ने दिखाया कि सभी बूलियन परिचालनों को सामान्य संख्यात्मक बहुपदों के रूप में लिखा जा सकता है, जो 0 और 1 के रूप में असत्य और सत्य मानों का प्रतिनिधित्व करते हैं, पूर्णांक मोड 2। तार्किक संयोजन xy के रूप में लिखा जाता है, और तार्किक अनन्य या अंकगणितीय जोड़ मॉड 2 के रूप में लिखा जाता है। , (यहां x⊕y के रूप में लिखा गया है जिससे कि + के सामान्य उपयोग के साथ भ्रम से बचने के लिए समावेशी-या ∨ के समानार्थी के रूप में)। तार्किक पूरक ¬x तब x⊕1 है। चूंकि ∧ और ¬ बूलियन बीजगणित के लिए एक आधार बनाते हैं, अन्य सभी तार्किक संचालन इन मूल संचालनों की रचनाएं हैं, और इसलिए साधारण बीजगणित के बहुपद सभी बूलियन संचालनों का प्रतिनिधित्व कर सकते हैं, जिससे प्राथमिक बीजगणित का उपयोग करके बूलियन तर्क को निष्पादित किया जा सकता है।

उदाहरण के लिए, बूलियन 2-आउट-ऑफ-3 थ्रेशोल्ड या माध्यिका संक्रिया को झेगाल्किन बहुपद xy⊕yz⊕zx के रूप में लिखा जाता है।

औपचारिक गुण

औपचारिक रूप से एक झेगाल्किन एकपदी विशिष्ट चरों के एक परिमित सेट का उत्पाद है (इसलिए वर्ग-मुक्त बहुपद), जिसमें खाली सेट सम्मलित है जिसका उत्पाद 1 दर्शाया गया है। 2ⁿ संभव झेगाल्किन एकपदी n चरों में, क्योंकि प्रत्येक एकपदी पूरी तरह से प्रत्येक चर की उपस्थिति या अनुपस्थिति द्वारा निर्दिष्ट है। एक झेगाल्किन बहुपद झेगाल्किन एकपदी के एक सेट का योग (अनन्य-या) है, जिसमें खाली सेट को 0 से दर्शाया गया है। बहुपद में दिए गए एकपदी की उपस्थिति या अनुपस्थिति क्रमशः उस एकपदी के गुणांक 1 या 0 से मेल खाती है। झेगाल्किन एकपदी, रैखिक रूप से स्वतंत्र होने के कारण, 2ⁿ फैला हुआ हैगाल्वा का मैदान 'GF'(2) पर डायमेंशनल सदिश स्थल (NB: नहीं 'GF'(2)ⁿ), जिसका गुणन काफी अलग है)। 2²ⁿ इस स्थान के सदिश, अर्थात इकाई सदिशों के रूप में उन एकपदी के रैखिक संयोजन, झेगाल्किन बहुपद का निर्माण करते हैं। n वेरिएबल्स पर बूलियन कार्य करता है। संख्या के साथ सटीक समझौता, जो {0,1} पर n-आरी संक्रिया को समाप्त करता है, बूलियन आधार के रूप में झेगाल्किन बहुपदों की पूर्णता के लिए एक प्रत्यक्ष गणना तर्क प्रस्तुत करता है।

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

गणना की विधि

झेगाल्किन बहुपद की गणना के लिए सामान्यत: उपयोग की जाने वाली विभिन्न ज्ञात विधियाँ हैं:

• # अनिश्चित गुणांक की विधि
• # विहित वियोगात्मक सामान्य रूप का उपयोग करना
• # टेबल का उपयोग करना
  1. पास्कल विधि
  2. योग विधि
• # कर्णघ मानचित्र का उपयोग करना

अनिश्चित गुणांक की विधि

अनिश्चित गुणांक की विधि का उपयोग करते हुए, एक रैखिक प्रणाली जिसमें फलन के सभी टुपल्स और उनके मान उत्पन्न होते हैं। रैखिक प्रणाली को हल करने से झेगाल्किन बहुपद के गुणांक मिलते हैं।

उदाहरण

बूलियन फलन को देखते हुए $f(A,B,C)={\bar {A}}{\bar {B}}{\bar {C}}+{\bar {A}}B{\bar {C}}+A{\bar {B}}{\bar {C}}+ABC$, इसे झेगाल्किन बहुपद के रूप में व्यक्त करें। यह फलन स्तंभ सदिश के रूप में व्यक्त किया जा सकता है

${\vec {f}}={\begin{pmatrix}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}$.

यह सदिश अनिर्धारित गुणांकों के एक सदिश को बाएँ गुणा करने का निर्गम होना चाहिए

${\vec {c}}={\begin{pmatrix}c_{0}\\c_{1}\\c_{2}\\c_{3}\\c_{4}\\c_{5}\\c_{6}\\c_{7}\end{pmatrix}}$

एक 8x8 तार्किक मैट्रिक्स द्वारा जो संभावित मानों का प्रतिनिधित्व करता है जो A, B, C के सभी संभावित संयोजन ले सकते हैं। ये संभावित मान निम्नलिखित सत्य तालिका में दिए गए हैं:

${\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}A&B&C&\;\;\;\;\;\;\;\;&1&C&B&BC&A&AC&AB&ABC\\\hline 0&0&0&&1&0&0&0&0&0&0&0\\0&0&1&&1&1&0&0&0&0&0&0\\0&1&0&&1&0&1&0&0&0&0&0\\0&1&1&&1&1&1&1&0&0&0&0\\1&0&0&&1&0&0&0&1&0&0&0\\1&0&1&&1&1&0&0&1&1&0&0\\1&1&0&&1&0&1&0&1&0&1&0\\1&1&1&&1&1&1&1&1&1&1&1\end{array}}$.

उपरोक्त सत्य तालिका की जानकारी को निम्न तार्किक मैट्रिक्स में कूटबद्‍ध किया जा सकता है:

$S_{3}={\begin{pmatrix}1&0&0&0&0&0&0&0\\1&1&0&0&0&0&0&0\\1&0&1&0&0&0&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&1&0&0&1&1&0&0\\1&0&1&0&1&0&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}$

जहां 'S' यहाँ सिएरपिन्स्की के लिए खड़ा है, जैसा कि सिएरपिन्स्की त्रिकोण में है, और अधोलेख 3 इसके आकार के प्रतिपादक देता है: $2^{3}\times 2^{3}$.

यह गणितीय प्रेरण और खंड-मैट्रिक्स गुणन के माध्यम से सिद्ध किया जा सकता है कि ऐसा कोई सिएरपिन्स्की मैट्रिक्स $S_{n}$ उसका ही उलटा है।

फिर रैखिक प्रणाली है

$S_{3}{\vec {c}}={\vec {f}}$

जिसके लिए हल किया जा सकता है ${\vec {c}}$:

${\vec {c}}=S_{3}^{-1}{\vec {f}}=S_{3}{\vec {f}}={\begin{pmatrix}1&0&0&0&0&0&0&0\\1&1&0&0&0&0&0&0\\1&0&1&0&0&0&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&1&0&0&1&1&0&0\\1&0&1&0&1&0&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}={\begin{pmatrix}1\\1\\1\oplus 1\\1\oplus 1\\1\oplus 1\\1\oplus 1\\1\oplus 1\oplus 1\\1\oplus 1\oplus 1\oplus 1\end{pmatrix}}={\begin{pmatrix}1\\1\\0\\0\\0\\0\\1\\0\end{pmatrix}}$,

और झेगाल्किन बहुपद के अनुरूप ${\vec {c}}$ है $1\oplus C\oplus AB$.

विहित वियोजक सामान्य रूप का उपयोग करना

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

सारणी का प्रयोग

सारणी विधि द्वारा एक उदाहरण फलन P के लिए झेगाल्किन बहुपद की गणना

होने देना $c_{0},...,c_{2^{n}-1}$n चर के फलन p के लिए एक यथार्थता टेबल का निर्गम हो, जैसे कि इंडेक्स $c_{i}$गुणद के द्विआधारी सूचकांकन से मेल खाता है।एक फलन ζ पुनरावर्ती रूप से परिभाषित करें:

$\zeta (c_{i}):=c_{i}$

$\zeta (c_{0},...,c_{k}):=\zeta (c_{0},...,c_{k-1})\oplus \zeta (c_{1},...,c_{k})$.

ध्यान दें कि

$\zeta (c_{0},...,c_{m})=\bigoplus _{k=0}^{m}{m \choose k}_{2}c_{k}$

कहाँ ${m \choose k}_{2}$ द्विपद गुणांक घटा हुआ मापांक अंकगणितीय 2 है।

तब

$g_{i}=\zeta (c_{0},...,c_{i})$

मैं है^th एक झेगाल्किन बहुपद का गुणांक जिसका शाब्दिक i^th एकपदी वही हैं जो i^th के शाब्दिक हैं। गुणद, सिवाय इसके कि प्रतिकूल शाब्दिक हटा दिए जाते हैं (या 1 से बदल दिए जाते हैं)।

ζ-रूपांतरण का अपना व्युत्क्रम होता है, इसलिए गुणांकों की गणना करने के लिए उसी प्रकार की तालिका का उपयोग किया जा सकता है $c_{0},...,c_{2^{n}-1}$ गुणांक दिया $g_{0},...,g_{2^{n}-1}$. बस जाने

$c_{i}=\zeta (g_{0},...,g_{i})$.

आकृति में तालिका के संदर्भ में, सत्य तालिका के निर्गम (P लेबल वाले पंक्ति में) को त्रिकोणीय तालिका के सबसे बाएं पंक्ति में अनुकरण करें। फिर प्रत्येक जोड़ी के शीर्ष सेल के दाईं ओर सेल को तुरंत भरने के लिए लंबवत आसन्न कोशिकाओं की प्रत्येक जोड़ी के लिए XOR को लागू करके क्रमशः बाएं से दाएं पंक्ति की गणना करें। जब संपूर्ण त्रिकोणीय तालिका भरी जाती है, तो शीर्ष पंक्ति एक रैखिक संयोजन के गुणांकों को पढ़ती है, जिसे सरलीकृत (शून्य को हटाते हुए) करने पर, झेगाल्किन बहुपद प्राप्त होता है।

झेगाल्किन बहुपद से सत्य-तालिका में जाने के लिए, त्रिकोणीय तालिका की शीर्ष पंक्ति को झेगाल्किन बहुपद के गुणांकों से भरना संभव है (धनात्मक शाब्दिकों के किसी भी संयोजन के लिए शून्य में डालकर बहुपद में नहीं)। फिर क्षैतिज रूप से आसन्न कोशिकाओं के प्रत्येक जोड़े में XOR को लागू करके ऊपर से नीचे तक पंक्तियों की गणना करें जिससे कि प्रत्येक जोड़ी के सबसे बाईं ओर के सेल के नीचे सेल को तुरंत भर सकें। जब पूरी त्रिकोणीय तालिका भर जाती है तो उसके सबसे बाएँ स्तंभ को सत्य तालिका के स्तंभ P में अनुकरण किया जा सकता है।

एक तरफ, ध्यान दें कि गणना की यह विधि प्राथमिक सेलुलर स्वचालि के संचालन की विधि से मेल खाती है जिसे नियम 102 कहा जाता है। उदाहरण के लिए, इस तरह के एक सेलुलर स्वचालित को बूलियन अभिव्यक्ति के सत्य तालिका (या विहित वियोजक सामान्य रूप के गुणांक) के निर्गम के साथ स्थापित आठ कोशिकाओं के साथ प्रारंभ करें: 10101001। फिर एक रखते हुए सात और पीढ़ियों के लिए सेलुलर स्वचालित चलाएं। सबसे बाईं सेल की स्थिति का रिकॉर्ड। तब इस सेल का विवरण निकला: 11000010, जो संबंधित झेगाल्किन बहुपद के गुणांकों को दर्शाता है।

पास्कल विधि

बूलियन फलन के लिए झेगाल्किन बहुपद की गणना करने के लिए पास्कल विधि का उपयोग करना ${\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}$. नीचे रूसी में रेखा कहती है:
$\oplus$ - बिटवाइज़ संक्रिया अपवर्जी ‘अथवा’ अवयव

संगणना की मात्रा के संदर्भ में सबसे मितव्ययी और हस्त प्रचालित रूप से झेगाल्किन बहुपद के निर्माण के लिए पास्कल विधि है।

हम एक तालिका बनाते हैं जिसमें सम्मलित हैं $2^{N}$ पंक्ति और $N+1$ पंक्तियाँ, जहाँ N फलन में चरों की संख्या है। तालिका की शीर्ष पंक्ति में हम फलन मानों के सदिश को रखते हैं, जो कि सत्य तालिका का अंतिम स्तंभ है।

परिणामी तालिका की प्रत्येक पंक्ति को खंड (चित्र में काली रेखाएँ) में विभाजित किया गया है। पहली पंक्ति में, खंड एक सेल पर कब्जा करता है, दूसरी पंक्ति में - दो, तीसरी में - चार, चौथी में - आठ, और इसी तरह। एक निश्चित पंक्ति में प्रत्येक खंड, जिसे हम निचला खंड कहते हैं, हमेशा पिछली पंक्ति में ठीक दो खंडों के अनुरूप होता है। हम उन्हें बाएं ऊपरी खंड और दाई ऊपरी खंड कहेंगे।

निर्माण दूसरी पंक्ति से प्रारंभ होता है। बाएं ऊपरी खंड की सामग्री को निचले खंड (आकृति में हरे तीर) की संबंधित कोशिकाओं में बदलाव के बिना स्थानांतरित किया जाता है। फिर, संक्रिया संकलन मापांक दो को दाएं ऊपरी और बाएं ऊपरी खंडों पर बिटवाइज़ किया जाता है और परिणाम को निचले खंड के दाईं ओर की संबंधित कोशिकाओं में स्थानांतरित किया जाता है (चित्र में लाल तीर)। यह संक्रिया ऊपर से नीचे तक सभी लाइनों के साथ और प्रत्येक पंक्ति में सभी खंडों के साथ किया जाता है। निर्माण पूरा होने के बाद, नीचे की रेखा में संख्याओं की एक श्रृंखला होती है, जो कि झेगाल्किन बहुपद के गुणांक हैं, उसी क्रम में लिखी गई है जैसा कि ऊपर वर्णित त्रिभुज विधि में लिखा गया है।

योग विधि

चरों की भिन्न संख्या वाले फलनों के लिए झेगाल्किन बहुपद के गुणांकों का आलेखीय निरूपण।

सत्य तालिका के अनुसार, झेगाल्किन बहुपद के अलग-अलग गुणांकों की गणना करना आसान है। ऐसा करने के लिए, सापेक्ष 2 को सत्य तालिका की उन पंक्तियों में फलन के मानों को जोड़ दें जहां चर जो संयोजन में नहीं हैं (जो गुणांक की गणना के अनुरूप हैं) शून्य मान लेते हैं।

मान लीजिए, उदाहरण के लिए, हमें तीन चरों के फलन के लिए xz संयोजन का गुणांक ज्ञात करने की आवश्यकता है $f(x,y,z)$. इस संयुग्मन में कोई चर y नहीं है। निविष्ट सेट खोजें जिसमें चर y शून्य मान लेता है। ये समुच्चय 0, 1, 4, 5 (000, 001, 100, 101) हैं। तब संयोजन xz पर गुणांक है

$a_{5}=f_{0}\oplus f_{1}\oplus f_{4}\oplus f_{5}=f(0,0,0)\oplus f(0,0,1)\oplus f(1,0,0)\oplus f(1,0,1)$

चूंकि निरंतर अवधि के साथ कोई चर नहीं हैं,

$a_{0}=f_{0}$.

एक शब्द के लिए जिसमें सभी चर सम्मलित हैं, योग में फलन के सभी मान सम्मलित हैं:

$a_{N-1}=f_{0}\oplus f_{1}\oplus f_{2}\oplus ...\oplus f_{N-2}\oplus f_{N-1}$

आइए हम झेगाल्किन बहुपद के गुणांकों को रेखांकन के रूप में कुछ बिंदुओं पर कार्यों के मूल्यों के योग सापेक्ष 2 के रूप में दर्शाते हैं। ऐसा करने के लिए, हम एक वर्गाकार तालिका का निर्माण करते हैं, जहाँ प्रत्येक स्तंभ किसी एक बिंदु पर फलन के मान का प्रतिनिधित्व करता है, और पंक्ति झेगाल्किन बहुपद का गुणांक है। किसी स्तंभ और पंक्ति के प्रतिच्छेदन बिंदु का अर्थ है कि इस बिंदु पर फलन का मान बहुपद के दिए गए गुणांक के योग में सम्मलित है (चित्र देखें)। हम इस तालिका को कहते हैं $T_{N}$, जहाँ N फलन के चरों की संख्या है।

एक पैटर्न है जो आपको N चर के फलन के लिए एक टेबल प्राप्त करने की अनुमति देता है, जिसमें एक फलन के लिए एक तालिका होती है $N-1$ चर। नई मेज $T_{N}+1$ के 2 × 2 मैट्रिक्स के रूप में व्यवस्थित किया गया है $T_{N}$ टेबल, और मैट्रिक्स का दाहिना ऊपरी खंड साफ़ हो गया है।

लैटिस-सैद्धांतिक व्याख्या

तालिका के स्तंभों पर विचार करें $T_{N}$ आकार के बूलियन जाली के तत्वों के अनुरूप $2^{N}$. प्रत्येक स्तंभ के लिए $f_{M}$ नंबर M को द्विआधारी नंबर के रूप में व्यक्त करें $M_{2}$, तब $f_{M}\leq f_{K}$ यदि और केवल यदि $M_{2}\vee K_{2}=K_{2}$, कहाँ $\vee$ बिटवाइज़ OR दर्शाता है।

यदि तालिका की पंक्तियाँ $T_{N}$ क्रमांकित हैं, ऊपर से नीचे तक, 0 से संख्याओं के साथ $2^{N}-1$, तब पंक्ति संख्या R की सारणीबद्ध सामग्री तत्व द्वारा उत्पन्न आदर्श (आदेश सिद्धांत) है $f_{R}$ जाली का है।

ध्यान दें कि तालिका का समग्र पैटर्न $T_{N}$ एक तार्किक मैट्रिक्स सिएरपिन्स्की त्रिभुज का है। इसके अतिरिक्त, पैटर्न एक प्राथमिक सेलुलर स्वचालित से मेल खाता है जिसे नियम 60 कहा जाता है, जो सबसे बाईं सेल से 1 पर सेट होता है और अन्य सभी सेल साफ़ हो जाते हैं।

कर्णघ मानचित्र का उपयोग

कर्णघ मानचित्र को झेगाल्किन बहुपद में बदलना।

यह आंकड़ा तीन चरों का एक कार्य दिखाता है, P (A, B, C) एक कर्णघ मानचित्र के रूप में दर्शाया गया है, जिसे पाठक उदाहरण के रूप में मान सकते हैं कि इस तरह के मानचित्रों को झेगाल्किन बहुपदों में कैसे परिवर्तित किया जाए; सामान्य प्रक्रिया निम्नलिखित चरणों में दी गई है:

• हम कर्णघ मानचित्र की सभी कोशिकाओं को उनके कोड में इकाइयों की संख्या के आरोही क्रम में मानते हैं। तीन चर के कार्य के लिए, कोशिकाओं का क्रम 000–100–010–001–110–101–011–111 होगा। कर्णघ मानचित्र की प्रत्येक कोशिका झेगलकिन बहुपद के एक सदस्य के साथ जुड़ी हुई है, जो उस कोड की स्थिति पर निर्भर करता है जिसमें वे हैं। उदाहरण के लिए, सेल 111 सदस्य ABC से मेल खाता है, सेल 101 सदस्य AC से मेल खाता है, सेल 010 सदस्य B से मेल खाता है, और सेल 000 सदस्य 1 से मेल खाता है।
• यदि संबंधित सेल 0 है, तो अगले सेल पर जाएं।
• यदि विचाराधीन सेल 1 है, तो संबंधित शब्द को झेगाल्किन बहुपद में जोड़ें, फिर कर्णघ मानचित्र में सभी कोशिकाओं को उलट दें जहां यह शब्द 1 है (या इस शब्द द्वारा उत्पन्न आदर्श (आदेश सिद्धांत) से संबंधित है, एक बूलियन जाली में) एकपदी की) और अगले सेल पर जाएं। उदाहरण के लिए, यदि सेल 110 की जांच करते समय, इसमें 1 दिखाई देता है, तो AB शब्द को झेगाल्किन बहुपद में जोड़ा जाता है और कर्णघ मानचित्र के सभी सेल उलटे होते हैं, जिसके लिए A = 1 और B = 1. यदि इकाई में है सेल 000, फिर एक शब्द 1 को झेगाल्किन बहुपद में जोड़ा जाता है और पूरे कर्णघ मानचित्र को उल्टा कर दिया जाता है।
• परिवर्तन प्रक्रिया को पूर्ण माना जा सकता है, जब उलटने के बाद, कर्णघ मानचित्र की सभी कोशिकाएँ शून्य हो जाती हैं, या परवाह न करने की स्थिति।

मोबियस परिवर्तन

मोबियस व्युत्क्रम सूत्र एक बूलियन लघुगणक अभिव्यक्ति और एक झेगाल्किन बहुपद के गुणांकों से संबंधित है। यह मोबियस सूत्र का आंशिक क्रम संस्करण है, न कि संख्या सिद्धांत। आंशिक क्रम के लिए मोबियस उलटा सूत्र है:

$g(x)=\sum _{y:y\leq x}f(y)\leftrightarrow f(x)=\sum _{y:y\leq x}g(y)\mu (y,x)$,कहाँ $\mu (y,x)=(-1)^{|x|-|y|}$, |x का x 0. से $-1\equiv 1$ झेगाल्किन बीजगणित में, मोबियस फलन स्थिर 1 होने के लिए निपात हो जाता है।

किसी दी गई संख्या x के विभाजकों का समुच्चय भी उस संख्या द्वारा उत्पन्न आदर्श (आदेश सिद्धांत) है: $\langle x\rangle$. चूँकि योग सापेक्ष 2 है, सूत्र को इस रूप में पुन: स्थापित किया जा सकता है

$g(x)=\bigoplus _{y:y\in \langle x\rangle }f(y)\leftrightarrow f(x)=\bigoplus _{y:y\in \langle x\rangle }g(y)$

उदाहरण

एक उदाहरण के रूप में, तीन-चर स्थितियोंे पर विचार करें। निम्न तालिका विभाज्यता संबंध दर्शाती है:

x	x के विभाजक
000	000
001	000, 001
010	000, 010
011	000, 001, 010, 011
100	000, 100
101	000, 001, 100, 101
110	000, 010, 100, 110
111	000, 001, 010, 011, 100, 101, 110, 111

तब

$g(000)=f(000)$

$g(001)=f(000)\oplus f(001)$

$g(010)=f(000)\oplus f(010)$

$g(011)=f(000)\oplus f(001)\oplus f(010)\oplus f(011)$

$g(100)=f(000)\oplus f(100)$

$g(101)=f(000)\oplus f(001)\oplus f(100)\oplus (101)$

$g(110)=f(000)\oplus f(010)\oplus f(100)\oplus f(110)$

$g(111)=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\oplus f(100)\oplus f(101)\oplus f(110)\oplus f(111)$

समीकरणों की उपरोक्त प्रणाली को f के लिए हल किया जा सकता है, और उपरोक्त प्रणाली में g और f का आदान-प्रदान करके परिणाम को प्राप्त करने योग्य होने के रूप में संक्षेपित किया जा सकता है।

नीचे दी गई तालिका द्विआधारी संख्याओं को उनके संबंधित झेगाल्किन एकपदी और बूलियन गुणद के साथ दिखाती है:

बूलियन मिंटर्म	ABC	झेगाल्किन एकपद
${\bar {A}}{\bar {B}}{\bar {C}}$	000	1
${\bar {A}}{\bar {B}}C$	001	C
${\bar {A}}B{\bar {C}}$	010	B
${\bar {A}}BC$	011	BC
$A{\bar {B}}{\bar {C}}$	100	A
$A{\bar {B}}C$	101	AC
$AB{\bar {C}}$	110	AB
$ABC$	111	ABC

झेगाल्किन एकपदी स्वाभाविक रूप से विभाज्यता द्वारा आदेशित होते हैं, जबकि बूलियन गुणद स्वाभाविक रूप से स्वयं को आदेश नहीं देते हैं, प्रत्येक तीन-चर वेन आरेख के एक विशेष आठवें का प्रतिनिधित्व करता है। एकपद का क्रम निम्नानुसार बिट श्रृंखला्स में स्थानांतरित होता है। दिया गया $a_{1}a_{2}a_{3}$ और $b_{1}b_{2}b_{3}$, बिट त्रिक की एक जोड़ी, फिर $a_{1}a_{2}a_{3}\leq b_{1}b_{2}b_{3}\leftrightarrow a_{1}\leq b_{1}\wedge a_{2}\leq b_{2}\wedge a_{3}\leq b_{3}$.

एक तीन-चर बूलियन राशि-के-गुणदऔर एक झेगाल्किन बहुपद के बीच पत्राचार तब होता है:

$f(000){\bar {A}}{\bar {B}}{\bar {C}}\vee f(001){\bar {A}}{\bar {B}}C\vee f(010){\bar {A}}B{\bar {C}}\vee f(011){\bar {A}}BC\vee f(100)A{\bar {B}}{\bar {C}}\vee f(101)A{\bar {B}}C\vee f(110)AB{\bar {C}}\vee f(111)ABC$

$\qquad \qquad \equiv g(000)\oplus g(001)C\oplus g(010)B\oplus g(011)BC\oplus g(100)A\oplus g(101)AC\oplus g(110)AB\oplus g(111)ABC$.

उपरोक्त समीकरणों की प्रणाली को तार्किक मैट्रिक्स समीकरण के रूप में संक्षेपित किया जा सकता है:

${\begin{pmatrix}g(000)\\g(001)\\g(010)\\g(011)\\g(100)\\g(101)\\g(110)\\g(111)\end{pmatrix}}={\begin{pmatrix}1&&0&&0&&0&&0&&0&&0&&0\\1&&1&&0&&0&&0&&0&&0&&0\\1&&0&&1&&0&&0&&0&&0&&0\\1&&1&&1&&1&&0&&0&&0&&0\\1&&0&&0&&0&&1&&0&&0&&0\\1&&1&&0&&0&&1&&1&&0&&0\\1&&0&&1&&0&&1&&0&&1&&0\\1&&1&&1&&1&&1&&1&&1&&1\end{pmatrix}}{\begin{pmatrix}f(000)\\f(001)\\f(010)\\f(011)\\f(100)\\f(101)\\f(110)\\f(111)\end{pmatrix}}$

जो वाजिब त्रिकोणमिति। एन. जे. वाइल्डबर्गर बूले-मोबियस रूपांतरण कहते हैं।

नीचे परिवर्तन का "XOR स्प्रेडशीट" रूप दिखाया गया है, जो g से f की दिशा में जा रहा है:

$f_{000}$	$f_{001}$	$f_{010}$	$f_{011}$	$f_{100}$	$f_{101}$	$f_{110}$	$f_{111}$
$g_{000}$	$g_{000}\oplus g_{001}$	$g_{000}\oplus g_{010}$	$g_{000}\oplus g_{010}\oplus g_{001}\oplus g_{011}$	$g_{000}\oplus g_{100}$	$g_{000}\oplus g_{100}\oplus g_{001}\oplus g_{101}$	$g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}$	$g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}\oplus g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}$
$g_{001}$	$g_{001}\oplus g_{010}$	$g_{001}\oplus g_{011}$	$g_{001}\oplus g_{011}\oplus g_{010}\oplus g_{100}$	$g_{001}\oplus g_{101}$	$g_{001}\oplus g_{101}\oplus g_{010}\oplus g_{110}$	$g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}$
$g_{010}$	$g_{010}\oplus g_{011}$	$g_{010}\oplus g_{100}$	$g_{010}\oplus g_{100}\oplus g_{011}\oplus g_{101}$	$g_{010}\oplus g_{110}$	$g_{010}\oplus g_{110}\oplus g_{011}\oplus g_{111}$
$g_{011}$	$g_{011}\oplus g_{100}$	$g_{011}\oplus g_{101}$	$g_{011}\oplus g_{101}\oplus g_{100}\oplus g_{110}$	$g_{011}\oplus g_{111}$
$g_{100}$	$g_{100}\oplus g_{101}$	$g_{100}\oplus g_{110}$	$g_{100}\oplus g_{110}\oplus g_{101}\oplus g_{111}$
$g_{101}$	$g_{101}\oplus g_{110}$	$g_{101}\oplus g_{111}$
$g_{110}$	$g_{110}\oplus g_{111}$
$g_{111}$

संबंधित कार्य

1927 में, उसी वर्ष झेगाल्किन के पेपर के रूप में,अमेरिकी गणितज्ञ एरिक टेम्पल बेल ने रिचर्ड डेडेकिंड के आदर्श सिद्धांत और सामान्यमापांक अंकगणित (अंकगणित मॉड 2 के विपरीत) के आधार पर बूलियन बीजगणित का एक परिष्कृत अंकगणित प्रकाशित किया।1936 में अमेरिकी गणितज्ञ मार्शल स्टोन द्वारा झेगाल्किन बहुपदों के बहुत सरल अंकगणितीय चरित्र को पहली बार पश्चिम में देखा गया था (स्वतंत्र रूप से, उस युग में सोवियत और पश्चिमी गणितज्ञों के बीच संचार बहुत सीमित था)।जब उन्होंने अपने प्रसिद्ध स्टोन द्वैत प्रमेय को लिखते समय देखा कि बूलियन बीजगणित और वलय(गणित) के बीच कथित रूप से ढीली समानता वास्तव में परिमित और अनंत बीजगणित दोनों के लिए एक सटीक तुल्यता धारण के रूप में तैयार की जा सकती है, जिससे उन्हें अपने कागज को काफी हद तक अगले कुछ साल तक पुनर्गठित करना पड़ा। ।

यह भी देखें

• बीजगणितीय सामान्य रूप (एएनएफ)
• रीड-मुलर विस्तार
• बूलियन डोमेन
• बूलियन-मूल्यवान फलन

अग्रिम पठन

• Gindikin [Гиндикин], Semen Grigorʹevich [Семен Г.] (1972). Algebraic logic алгебра логики в задачах [Algebraic Logic] (in русский) (1 ed.). Moscow, Russia: Наука [Nauka]. ISBN 0-387-96179-8. (288 pages) (NB. Translation: Springer-Verlag, 1985.[1])
• Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. Historical Overview of the Research on Decomposition". A Survey of Literature on Function Decomposition. Version IV. Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA. pp. 21–22. CiteSeerX 10.1.1.64.1129. (188 pages)