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

ज़ेगल्किन (ज़ेगल्किन, गेगल्किन या शेगल्किन भी^[1] बहुपद (Russian: полиномы Жегалкина), बीजगणितीय सामान्य रूप के रूप में भी जाना जाता है, बूलियन बीजगणित में कार्यों का प्रतिनिधित्व है। 1927 में रूसी गणितज्ञ इवान इवानोविच ज़ेगाल्किन द्वारा पेश किया गया,^[2] बहुपद वलय हैं #मापांक अंकगणित पर परिभाषा # पूर्णांक है।मापांक अंकगणितीय परिणाम के परिणामी अध: पतन के कारण ज़ेगल्किन बहुपद साधारण बहुपदों की तुलना में सरल होते हैं, जिनमें न तो गुणांक और न ही घातांक की आवश्यकता होती है। गुणांक बेमानी हैं क्योंकि 1 एकमात्र अशून्य गुणांक है। घातांकी बेमानी हैं क्योंकि अंकगणित मोड 2, x में^{2</सुप> = एक्स। इसलिए एक बहुपद जैसे 3x²और⁵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^{2<अवधि>ⁿ} इस स्थान के सदिश, यानी इकाई सदिशों के रूप में उन एकपदी के रैखिक संयोजन, ज़ेगल्किन बहुपद का निर्माण करते हैं। एन वेरिएबल्स पर बूलियन कार्य करता है की संख्या के साथ सटीक समझौता, जो {0,1} पर एन-आरी ऑपरेशंस को समाप्त करता है, बूलियन आधार के रूप में ज़ेगाल्किन बहुपदों की पूर्णता के लिए एक प्रत्यक्ष गणना तर्क प्रस्तुत करता है।

यह सदिश स्थान 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 तार्किक मैट्रिक्स द्वारा जो संभावित मानों का प्रतिनिधित्व करता है जो ए, बी, सी के सभी संभावित संयोजन ले सकते हैं। ये संभावित मान निम्नलिखित सत्य तालिका में दिए गए हैं:

{\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' यहाँ Sierpinski के लिए खड़ा है, जैसा कि Sierpinski त्रिकोण में है, और सबस्क्रिप्ट 3 इसके आकार के प्रतिपादक देता है: $2^{3}\times 2^{3}$ .

यह गणितीय प्रेरण और ब्लॉक-मैट्रिक्स गुणन के माध्यम से सिद्ध किया जा सकता है कि ऐसा कोई सिएरपिन्स्की मैट्रिक्स $S_{n}$ उसका ही उलटा है।^{[nb 1]}

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

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}$ एन वेरिएबल्स के फंक्शन पी के लिए एक ट्रुथ टेबल का आउटपुट हो, जैसे कि इंडेक्स $c_{i}$ minterms के बाइनरी इंडेक्सिंग से मेल खाता है।^{[nb 2]}एक फ़ंक्शन ζ पुनरावर्ती रूप से परिभाषित करें:

\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 के शाब्दिक हैं^वें मिनट टर्म, सिवाय इसके कि नेगेटिव लिटरल हटा दिए जाते हैं (या 1 से बदल दिए जाते हैं)।

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

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

.

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

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

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

पास्कल विधि

बूलियन फ़ंक्शन के लिए ज़ेगल्किन बहुपद की गणना करने के लिए पास्कल विधि का उपयोग करना

{\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}

. नीचे रूसी में रेखा कहती है:

\oplus

- बिटवाइज़ ऑपरेशन एक्सक्लूसिव OR

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

हम एक तालिका बनाते हैं जिसमें शामिल हैं $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-1$ चर। नई मेज $T_{N}+1$ के 2 × 2 मैट्रिक्स के रूप में व्यवस्थित किया गया है $T_{N}$ टेबल, और मैट्रिक्स का दाहिना ऊपरी ब्लॉक साफ़ हो गया है।

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

तालिका के स्तंभों पर विचार करें $T_{N}$ आकार के बूलियन जाली के तत्वों के अनुरूप $2^{N}$ . प्रत्येक स्तंभ के लिए $f_{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 पर सेट होता है और अन्य सभी सेल साफ़ हो जाते हैं।

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

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

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

हम कर्णघ मानचित्र की सभी कोशिकाओं को उनके कोड में इकाइयों की संख्या के आरोही क्रम में मानते हैं। तीन चर के कार्य के लिए, कोशिकाओं का क्रम 000–100–010–001–110–101–011–111 होगा। कर्णघ मानचित्र की प्रत्येक कोशिका झेगलकिन बहुपद के एक सदस्य के साथ जुड़ी हुई है, जो उस कोड की स्थिति पर निर्भर करता है जिसमें वे हैं। उदाहरण के लिए, सेल 111 सदस्य एबीसी से मेल खाता है, सेल 101 सदस्य एसी से मेल खाता है, सेल 010 सदस्य बी से मेल खाता है, और सेल 000 सदस्य 1 से मेल खाता है।
यदि संबंधित सेल 0 है, तो अगले सेल पर जाएं।
यदि विचाराधीन सेल 1 है, तो संबंधित शब्द को ज़ेगल्किन बहुपद में जोड़ें, फिर कर्णघ मानचित्र में सभी कोशिकाओं को उलट दें जहां यह शब्द 1 है (या इस शब्द द्वारा उत्पन्न आदर्श (आदेश सिद्धांत) से संबंधित है, एक बूलियन जाली में) एकपदी्स की) और अगले सेल पर जाएं। उदाहरण के लिए, यदि सेल 110 की जांच करते समय, इसमें एक दिखाई देता है, तो 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)

,^[5]कहाँ

\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	divisors of 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 का आदान-प्रदान करके परिणाम को प्राप्त करने योग्य होने के रूप में संक्षेपित किया जा सकता है।

नीचे दी गई तालिका बाइनरी संख्याओं को उनके संबंधित ज़ेगल्किन एकपदी और बूलियन minterms के साथ दिखाती है:

Boolean minterm	ABC	ज़ेगल्किन monomial
${\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

ज़ेगल्किन एकपदी स्वाभाविक रूप से विभाज्यता द्वारा आदेशित होते हैं, जबकि बूलियन minterms स्वाभाविक रूप से स्वयं को आदेश नहीं देते हैं; प्रत्येक तीन-चर वेन आरेख के एक विशेष आठवें का प्रतिनिधित्व करता है। एकपदी्स का क्रम निम्नानुसार बिट स्ट्रिंग्स में स्थानांतरित होता है: दिया गया $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}}

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

नीचे परिवर्तन का "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}$

यह भी देखें

↑ As base case,
$S_{0}:={\begin{pmatrix}1\end{pmatrix}}$

$(S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}$
where $I_{n}$ is here taken to denote the identity matrix of size $2^{n}\times 2^{n}$ . The inductive assumption is
$(S_{n})^{2}=I_{n}$ .
Then the inductive step is:
$S_{n+1}:={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}\equiv {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\otimes S_{n}$ ,
where $\otimes$ denotes the Kronecker product,
$(S_{n+1})^{2}={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}{\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}={\begin{pmatrix}S_{n}S_{n}\oplus OS_{n}&S_{n}O\oplus OS_{n}\\S_{n}S_{n}\oplus S_{n}S_{n}&S_{n}O\oplus S_{n}S_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\I_{n}\oplus I_{n}&I_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\O&I_{n}\end{pmatrix}}=I_{n+1}$ ,
or, in terms of the Kronecker product:
$S_{n+1}^{2}=(S_{1}\otimes S_{n})(S_{1}\otimes S_{n})=S_{1}^{2}\otimes S_{n}^{2}=I_{1}\otimes I_{n}=I_{n+1}$ . ∎
↑ A minterm is the Boolean counterpart of a Zhegalkin monomial. For an n-variable context, there are $2^{n}$ Zhegalkin monomials and $2^{n}$ Boolean minterms as well. A minterm for an n-variable context consists of an AND-product of n literals, each literal either being a variable in the context or the NOT-negation of such a variable. Moreover, for each variable in the context there must appear exactly once in each minterm a corresponding literal (either the assertion or negation of that variable). A truth table for a Boolean function of n variables has exactly $2^{n}$ rows, the inputs of each row corresponding naturally to a minterm whose context is the set of independent variables of that Boolean function. (Each 0-input corresponds to a negated variable; each 1-input corresponds to an asserted variable.)
Any Boolean expression may be converted to sum-of-minterms form by repeatedly distributing AND with respect to OR, NOT with respect to AND or OR (through the De Morgan identities), cancelling out double negations (cf. negation normal form); and then, when a sum-of-products has been obtained, multiply products with missing literals with instances of the law of excluded middle that contain the missing literals; then — lastly — distribute AND with respect to OR again.
Note that there is a formal correspondence, for a given context, between Zhegalkin monomials and Boolean minterms. However, the correspondence is not logical equivalence. For example, for the context {A, B, C}, there is a formal correspondence between the Zhegalkin monomial AB and the Boolean minterm $AB{\bar {C}}$ , but they are not logically equivalent. (For more of this example, see the second table in the section "Möbius transformation". The same set of bitstrings is used to index both the set of Boolean minterms and the set of Zhegalkin monomials.)

संदर्भ

↑ Steinbach, Bernd [in Deutsch]; Posthoff, Christian (2009). "Preface". Written at Freiberg, Germany. Logic Functions and Equations - Examples and Exercises (1st ed.). Dordrecht, Netherlands: Springer Science + Business Media B. V. p. xv. ISBN 978-1-4020-9594-8. LCCN 2008941076.
↑ ^2.0 ^2.1 Жега́лкин [Zhegalkin], Ива́н Ива́нович [Ivan Ivanovich] (1927). "O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye" О технике вычислений предложений в символической логике [On the technique of calculating propositions in symbolic logic (Sur le calcul des propositions dans la logique symbolique)]. Matematicheskii Sbornik (in русский and français). Moscow, Russia. 34 (1): 9–28. Mi msb7433. Archived from the original on 2017-10-12. Retrieved 2017-10-12.
↑ Suprun [Супрун], Valeriy P. [Валерий Павлович] (1987). "Tablichnyy metod polinomial'nogo razlozheniya bulevykh funktsiy" Табличный метод полиномиального разложения булевых функций [The tabular method of polynomial decomposition of Boolean functions]. Kibernetika [Кибернетика] (Cybernetics) (in русский) (1): 116–117.
↑ Suprun [Супрун], Valeriy P. [Валерий Павлович] (2017). "Osnovy teorii bulevykh funktsiy" Основы теории булевых функций [Fundamentals of the theory of Boolean functions]. М.: Lenand [Ленанд] / URSS (in русский): 208.
↑ "Möbius inversion". Encyclopedia of Mathematics. 2021-02-17 [2011-02-07]. Archived from the original on 2020-07-16. Retrieved 2021-03-27.
↑ Bell, Eric Temple (1927). "Arithmetic of Logic". Transactions of the American Mathematical Society. 29 (3): 597–611. doi:10.2307/1989098. JSTOR 1989098.
↑ Stone, Marshall (1936). "The Theory of Representations for Boolean Algebras". Transactions of the American Mathematical Society. 40 (1): 37–111. doi:10.2307/1989664. ISSN 0002-9947. JSTOR 1989664.

अग्रिम पठन

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)

[NB1-3] As base case,
$S_{0}:={\begin{pmatrix}1\end{pmatrix}}$

$(S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}$
where $I_{n}$ is here taken to denote the identity matrix of size $2^{n}\times 2^{n}$ . The inductive assumption is
$(S_{n})^{2}=I_{n}$ .
Then the inductive step is:
$S_{n+1}:={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}\equiv {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\otimes S_{n}$ ,
where $\otimes$ denotes the Kronecker product,
$(S_{n+1})^{2}={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}{\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}={\begin{pmatrix}S_{n}S_{n}\oplus OS_{n}&S_{n}O\oplus OS_{n}\\S_{n}S_{n}\oplus S_{n}S_{n}&S_{n}O\oplus S_{n}S_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\I_{n}\oplus I_{n}&I_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\O&I_{n}\end{pmatrix}}=I_{n+1}$ ,
or, in terms of the Kronecker product:
$S_{n+1}^{2}=(S_{1}\otimes S_{n})(S_{1}\otimes S_{n})=S_{1}^{2}\otimes S_{n}^{2}=I_{1}\otimes I_{n}=I_{n+1}$ . ∎

[NB2-4] A minterm is the Boolean counterpart of a Zhegalkin monomial. For an n-variable context, there are $2^{n}$ Zhegalkin monomials and $2^{n}$ Boolean minterms as well. A minterm for an n-variable context consists of an AND-product of n literals, each literal either being a variable in the context or the NOT-negation of such a variable. Moreover, for each variable in the context there must appear exactly once in each minterm a corresponding literal (either the assertion or negation of that variable). A truth table for a Boolean function of n variables has exactly $2^{n}$ rows, the inputs of each row corresponding naturally to a minterm whose context is the set of independent variables of that Boolean function. (Each 0-input corresponds to a negated variable; each 1-input corresponds to an asserted variable.)
Any Boolean expression may be converted to sum-of-minterms form by repeatedly distributing AND with respect to OR, NOT with respect to AND or OR (through the De Morgan identities), cancelling out double negations (cf. negation normal form); and then, when a sum-of-products has been obtained, multiply products with missing literals with instances of the law of excluded middle that contain the missing literals; then — lastly — distribute AND with respect to OR again.
Note that there is a formal correspondence, for a given context, between Zhegalkin monomials and Boolean minterms. However, the correspondence is not logical equivalence. For example, for the context {A, B, C}, there is a formal correspondence between the Zhegalkin monomial AB and the Boolean minterm $AB{\bar {C}}$ , but they are not logically equivalent. (For more of this example, see the second table in the section "Möbius transformation". The same set of bitstrings is used to index both the set of Boolean minterms and the set of Zhegalkin monomials.)

[Steinbach_2009-1] Steinbach, Bernd [in Deutsch]; Posthoff, Christian (2009). "Preface". Written at Freiberg, Germany. Logic Functions and Equations - Examples and Exercises (1st ed.). Dordrecht, Netherlands: Springer Science + Business Media B. V. p. xv. ISBN 978-1-4020-9594-8. LCCN 2008941076.

[Zhegalkin_1927-2] 2.0 ^2.1 Жега́лкин [Zhegalkin], Ива́н Ива́нович [Ivan Ivanovich] (1927). "O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye" О технике вычислений предложений в символической логике [On the technique of calculating propositions in symbolic logic (Sur le calcul des propositions dans la logique symbolique)]. Matematicheskii Sbornik (in русский and français). Moscow, Russia. 34 (1): 9–28. Mi msb7433. Archived from the original on 2017-10-12. Retrieved 2017-10-12.

[Suprun_1987-5] Suprun [Супрун], Valeriy P. [Валерий Павлович] (1987). "Tablichnyy metod polinomial'nogo razlozheniya bulevykh funktsiy" Табличный метод полиномиального разложения булевых функций [The tabular method of polynomial decomposition of Boolean functions]. Kibernetika [Кибернетика] (Cybernetics) (in русский) (1): 116–117.

[Suprun_2017-6] Suprun [Супрун], Valeriy P. [Валерий Павлович] (2017). "Osnovy teorii bulevykh funktsiy" Основы теории булевых функций [Fundamentals of the theory of Boolean functions]. М.: Lenand [Ленанд] / URSS (in русский): 208.

[Möbius_2021-7] "Möbius inversion". Encyclopedia of Mathematics. 2021-02-17 [2011-02-07]. Archived from the original on 2020-07-16. Retrieved 2021-03-27.

[Bell_1927-8] Bell, Eric Temple (1927). "Arithmetic of Logic". Transactions of the American Mathematical Society. 29 (3): 597–611. doi:10.2307/1989098. JSTOR 1989098.

[Stone_1936-9] Stone, Marshall (1936). "The Theory of Representations for Boolean Algebras". Transactions of the American Mathematical Society. 40 (1): 37–111. doi:10.2307/1989664. ISSN 0002-9947. JSTOR 1989664.

[1]

[2]

[nb 1]

[nb 2]

[3]

[4]

[5]

[6]

[7]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

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

औपचारिक गुण

गणना की विधि

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

उदाहरण

टेबल का उपयोग

पास्कल विधि

योग विधि

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

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

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

उदाहरण

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

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

औपचारिक गुण

गणना की विधि

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

उदाहरण

टेबल का उपयोग

पास्कल विधि

योग विधि

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

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

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

उदाहरण

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories