बूल का विस्तार प्रमेय: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
बूल का विस्तार प्रमेय, जिसे | बूल का विस्तार प्रमेय, जिसे अधिकांशतः शैनन विस्तार या अपघटन के रूप में संदर्भित किया जाता है, जहाँ <math>F = x \cdot F_x + x' \cdot F_{x'}</math> [[पहचान (गणित)]] है: जहां<math>F</math> कोई [[बूलियन समारोह|बूलियन फलन]] है, <math>x</math> चर है, <math>x'</math>, <math>x</math> का पूरक है, और <math>F_x</math>और <math>F_{x'}</math> तर्क <math>x</math> सेट के साथ <math>F</math> हैं क्रमशः 1 और 0 के समानता है। | ||
<math>F_x</math> और <math>F_{x'}</math> नियमो | <math>F_x</math> और <math>F_{x'}</math> नियमो को कभी-कभी <math>x</math> के संबंध में <math>F</math> के क्रमशः सकारात्मक और नकारात्मक शैनन कॉफ़ैक्टर्स कहा जाता है | ||
इस प्रकार के | इस प्रकार के फलन जिनकी गणना प्रतिबंधित ऑपरेटर <math>\operatorname{restrict}(F, x, 0)</math> और <math>\operatorname{restrict}(F, x, 1)</math> ([[मूल्यांकन (तर्क)]] और आंशिक अनुप्रयोग द्वारा की जाती है, देखें)। | ||
इस प्रक्रिया के अनुसार | इस प्रक्रिया के अनुसार बूलियन बीजगणित को मौलिक प्रमेय कहा गया है।<ref name="Rosenbloom_1950" /> इसके सैद्धांतिक महत्व के यदि , इसके [[द्विआधारी निर्णय आरेख]] (बीडीडीएस), [[बूलियन संतुष्टि समस्या]], और [[कंप्यूटर इंजीनियरिंग]] से संबंधित कई अन्य विधि और डिजिटल सर्किट के [[औपचारिक सत्यापन]] का मार्ग प्रशस्त किया। | ||
इस प्रकार | इस प्रकार के इंजीनियरिंग संदर्भों में (विशेष रूप से बीडीडीएस में), इसके सैद्धांतिक महत्व के अलावा, इसके बाइनरी डिसीजन डायग्राम (बीडीडीएस), सैटिस्फिबिलिटी सॉल्वर, और कंप्यूटर इंजीनियरिंग से संबंधित कई अन्य तकनीकों और डिजिटल सर्किट के औपचारिक सत्यापन के लिए मार्ग प्रशस्त किया। इस प्रकार के इंजीनियरिंग संदर्भों में (विशेष रूप से बीडीडी में), विस्तार की व्याख्या जब -तो-और के रूप में की जाती है, जिसमें चर x स्थिति होती है और कोफ़ैक्टर्स शाखाएँ होती हैं। इस प्रक्रिया के अनुसार विस्तार की व्याख्या सशर्त_(कंप्यूटर_प्रोग्रामिंग) के रूप में की जाती है। यदि-तो-और, चर के साथ <math>x</math> स्थिति होने के यदि और कोफ़ेक्टर्स शाखाएँ होती है। जब (<math>F_x</math> जब <math>x</math> सत्य होता है और क्रमशः <math>F_{x'}</math> जब <math>x</math> गलत है)।<ref>G. D. Hachtel and F. Somezi (1996), ''Logic Synthesis and Verification Algorithms'', p. 234</ref> | ||
== प्रमेय का कथन == | == प्रमेय का कथन == | ||
प्रमेय को बताने की स्पष्ट विधि | प्रमेय को बताने की स्पष्ट विधि है: | ||
: <math>f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) + X_1' \cdot f(0, X_2, \dots , X_n)</math> | : <math>f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) + X_1' \cdot f(0, X_2, \dots , X_n)</math> | ||
== '''भिन्नताएं और प्रभाव''' == | == '''भिन्नताएं और प्रभाव''' == | ||
; XOR-फॉर्म :यह कथन जब | ; XOR-फॉर्म :यह कथन जब धारण करता है जब [[ अलगाव |संयोजन]] "+" को XOR ऑपरेटर द्वारा प्रतिस्थापित किया जाता है। | ||
: <math>f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) \oplus X_1' \cdot f(0, X_2, \dots , X_n)</math> | : <math>f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) \oplus X_1' \cdot f(0, X_2, \dots , X_n)</math> | ||
; ड्यूल | ; ड्यूल फॉर्म: शैनन विस्तार का ड्यूल फॉर्म है (जिसका कोई संबंधित XOR फॉर्म नहीं है): | ||
: <math>f(X_1, X_2, \dots , X_n) = (X_1 + f(0, X_2, \dots , X_n)) \cdot (X_1' + f(1, X_2, \dots , X_n))</math> | : <math>f(X_1, X_2, \dots , X_n) = (X_1 + f(0, X_2, \dots , X_n)) \cdot (X_1' + f(1, X_2, \dots , X_n))</math> | ||
प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फलन <math>f</math> के [[उत्पादों का योग]] (एसओपी) विहित रूप हो जाता है. उदाहरण के लिए <math>n=2</math> हो सकता है | प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फलन <math>f</math> के [[उत्पादों का योग]] (एसओपी) विहित रूप हो जाता है. उदाहरण के लिए <math>n=2</math> हो सकता है | ||
| Line 28: | Line 28: | ||
& = X_1 X_2 \cdot f(1, 1) + X_1 X_2' \cdot f(1, 0) + X_1' X_2 \cdot f(0, 1) + X_1' X_2' \cdot f(0, 0) | & = X_1 X_2 \cdot f(1, 1) + X_1 X_2' \cdot f(1, 0) + X_1' X_2 \cdot f(0, 1) + X_1' X_2' \cdot f(0, 0) | ||
\end{align}</math> | \end{align}</math> | ||
इसी तरह, ड्यूल | इसी तरह, ड्यूल फॉर्म के प्रयोग से योग उत्पाद का (पिओएस ) के विहित रूप का गुणनफल प्राप्त होता है (<math>+</math> over के वितरण नियम का उपयोग करके) : | ||
:<math>\begin{align} | :<math>\begin{align} | ||
| Line 39: | Line 39: | ||
; कॉफ़ैक्टर्स के रैखिक गुण | ; कॉफ़ैक्टर्स के रैखिक गुण | ||
: बूलियन फलन | : बूलियन फलन ''F'' के लिए जो दो बूलियन फलन ''G'' और ''H'' से बना है, निम्नलिखित सत्य हैं: | ||
: यदि | : यदि <math>F = H'</math> जब <math>F_x = H'_x</math> | ||
: यदि | : यदि <math>F = G \cdot H</math> जब <math>F_x = G_x \cdot H_x</math> | ||
: यदि | : यदि <math>F = G + H</math> जब <math>F_x = G_x + H_x</math> | ||
: यदि | : यदि <math>F = G \oplus H</math> जब <math>F_x = G_x \oplus H_x</math> | ||
; संयुक्त कार्यों के लक्षण | ; संयुक्त कार्यों के लक्षण | ||
: यदि ''F'' एक असमान फलन है और... | : यदि ''F'' एक असमान फलन है और... | ||
: यदि ''F'' सकारात्मक फलन है तो <math>F = x \cdot F_x + F_{x'}</math> | : यदि ''F'' सकारात्मक फलन है तो <math>F = x \cdot F_x + F_{x'}</math> | ||
: यदि Fऋणात्मक | : यदि Fऋणात्मक फलन है तो <math>F = F_x + x' \cdot F_{x'}</math> | ||
== '''सहकारकों के साथ संचालन''' == | == '''सहकारकों के साथ संचालन''' == | ||
; बूलियन अंतर | ; बूलियन अंतर | ||
: शाब्दिक x के संबंध में फलन | : शाब्दिक x के संबंध में फलन F का बूलियन अंतर या बूलियन व्युत्पन्न इस प्रकार परिभाषित किया गया है: | ||
: <math> \frac{\partial F}{\partial x} = F_x \oplus F_{x'}</math> | : <math> \frac{\partial F}{\partial x} = F_x \oplus F_{x'}</math> | ||
; सार्वभौमिक परिमाणीकरण | ; सार्वभौमिक परिमाणीकरण | ||
| Line 61: | Line 61: | ||
: <math> \exists x F = F_x + F_{x'}</math><br /> | : <math> \exists x F = F_x + F_{x'}</math><br /> | ||
== इतिहास == | == इतिहास == | ||
[[जॉर्ज बूले]] ने इस विस्तार को अपने प्रस्ताव II के रूप में प्रस्तुत किया, अपने द लॉज़ ऑफ थॉट (1854) में किसी भी संख्या में तार्किक प्रतीकों को सम्मिलित | [[जॉर्ज बूले]] ने इस विस्तार को अपने प्रस्ताव II के रूप में प्रस्तुत किया, अपने द लॉज़ ऑफ थॉट (1854) में किसी भी संख्या में तार्किक प्रतीकों को सम्मिलित करने वाले फलन का विस्तार या विकास करने के लिए,<ref name="Boole_1854"/> और बूले और उन्नीसवीं सदी के अन्य तार्किकों द्वारा इसे व्यापक रूप से प्रयुक्त किया गया था।<ref name="Brown_2012"/> | ||
[[क्लाउड शैनन]] ने 1949 के | [[क्लाउड शैनन]] ने 1949 के पेपर में अन्य बूलियन पहचानों के बीच इस विस्तार का उल्लेख किया,<ref name="Shannon_1949"/> और पहचान की स्विचिंग नेटवर्क व्याख्याओं को दिखाया। कंप्यूटर डिजाइन और स्विचिंग थ्योरी के साहित्य में, पहचान को अधिकांशतः गलत विधि से शैनन के लिए उत्तरदाई ठहराया जाता है।<ref name="Perkowski-Grygiel_1995"/><ref name="Brown_2012"/> | ||
== परिपथ स्विचिंग के लिए अनुप्रयोग == | == परिपथ स्विचिंग के लिए अनुप्रयोग == | ||
# [[द्विआधारी निर्णय आरेख]] इस प्रमेय के व्यवस्थित उपयोग से अनुसरण करते हैं | # [[द्विआधारी निर्णय आरेख]] इस प्रमेय के व्यवस्थित उपयोग से अनुसरण करते हैं | ||
# किसी भी बूलियन फलन | # किसी भी बूलियन फलन को इस प्रमेय के बार-बार आवेदन द्वारा विधि [[बहुसंकेतक]] के पदानुक्रम का उपयोग करके [[स्विचिंग सर्किट सिद्धांत|स्विचिंग स परिपथ सिद्धांत]] में सीधे प्रयुक्त किया जा सकता है। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 14:02, 17 June 2023
बूल का विस्तार प्रमेय, जिसे अधिकांशतः शैनन विस्तार या अपघटन के रूप में संदर्भित किया जाता है, जहाँ पहचान (गणित) है: जहां कोई बूलियन फलन है, चर है, , का पूरक है, और और तर्क सेट के साथ हैं क्रमशः 1 और 0 के समानता है।
और नियमो को कभी-कभी के संबंध में के क्रमशः सकारात्मक और नकारात्मक शैनन कॉफ़ैक्टर्स कहा जाता है
इस प्रकार के फलन जिनकी गणना प्रतिबंधित ऑपरेटर और (मूल्यांकन (तर्क) और आंशिक अनुप्रयोग द्वारा की जाती है, देखें)।
इस प्रक्रिया के अनुसार बूलियन बीजगणित को मौलिक प्रमेय कहा गया है।[1] इसके सैद्धांतिक महत्व के यदि , इसके द्विआधारी निर्णय आरेख (बीडीडीएस), बूलियन संतुष्टि समस्या, और कंप्यूटर इंजीनियरिंग से संबंधित कई अन्य विधि और डिजिटल सर्किट के औपचारिक सत्यापन का मार्ग प्रशस्त किया।
इस प्रकार के इंजीनियरिंग संदर्भों में (विशेष रूप से बीडीडीएस में), इसके सैद्धांतिक महत्व के अलावा, इसके बाइनरी डिसीजन डायग्राम (बीडीडीएस), सैटिस्फिबिलिटी सॉल्वर, और कंप्यूटर इंजीनियरिंग से संबंधित कई अन्य तकनीकों और डिजिटल सर्किट के औपचारिक सत्यापन के लिए मार्ग प्रशस्त किया। इस प्रकार के इंजीनियरिंग संदर्भों में (विशेष रूप से बीडीडी में), विस्तार की व्याख्या जब -तो-और के रूप में की जाती है, जिसमें चर x स्थिति होती है और कोफ़ैक्टर्स शाखाएँ होती हैं। इस प्रक्रिया के अनुसार विस्तार की व्याख्या सशर्त_(कंप्यूटर_प्रोग्रामिंग) के रूप में की जाती है। यदि-तो-और, चर के साथ स्थिति होने के यदि और कोफ़ेक्टर्स शाखाएँ होती है। जब ( जब सत्य होता है और क्रमशः जब गलत है)।[2]
प्रमेय का कथन
प्रमेय को बताने की स्पष्ट विधि है:
भिन्नताएं और प्रभाव
- XOR-फॉर्म
- यह कथन जब धारण करता है जब संयोजन "+" को XOR ऑपरेटर द्वारा प्रतिस्थापित किया जाता है।
- ड्यूल फॉर्म
- शैनन विस्तार का ड्यूल फॉर्म है (जिसका कोई संबंधित XOR फॉर्म नहीं है):
प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फलन के उत्पादों का योग (एसओपी) विहित रूप हो जाता है. उदाहरण के लिए हो सकता है
इसी तरह, ड्यूल फॉर्म के प्रयोग से योग उत्पाद का (पिओएस ) के विहित रूप का गुणनफल प्राप्त होता है ( over के वितरण नियम का उपयोग करके) :
सहकारकों के गुण
- कॉफ़ैक्टर्स के रैखिक गुण
- बूलियन फलन F के लिए जो दो बूलियन फलन G और H से बना है, निम्नलिखित सत्य हैं:
- यदि जब
- यदि जब
- यदि जब
- यदि जब
- संयुक्त कार्यों के लक्षण
- यदि F एक असमान फलन है और...
- यदि F सकारात्मक फलन है तो
- यदि Fऋणात्मक फलन है तो
सहकारकों के साथ संचालन
- बूलियन अंतर
- शाब्दिक x के संबंध में फलन F का बूलियन अंतर या बूलियन व्युत्पन्न इस प्रकार परिभाषित किया गया है:
- सार्वभौमिक परिमाणीकरण
- F की सार्वभौमिक मात्रा को इस प्रकार परिभाषित किया गया है:
- अस्तित्वगत परिमाणीकरण
- F के अस्तित्वगत परिमाणीकरण को इस प्रकार परिभाषित किया गया है:
इतिहास
जॉर्ज बूले ने इस विस्तार को अपने प्रस्ताव II के रूप में प्रस्तुत किया, अपने द लॉज़ ऑफ थॉट (1854) में किसी भी संख्या में तार्किक प्रतीकों को सम्मिलित करने वाले फलन का विस्तार या विकास करने के लिए,[3] और बूले और उन्नीसवीं सदी के अन्य तार्किकों द्वारा इसे व्यापक रूप से प्रयुक्त किया गया था।[4]
क्लाउड शैनन ने 1949 के पेपर में अन्य बूलियन पहचानों के बीच इस विस्तार का उल्लेख किया,[5] और पहचान की स्विचिंग नेटवर्क व्याख्याओं को दिखाया। कंप्यूटर डिजाइन और स्विचिंग थ्योरी के साहित्य में, पहचान को अधिकांशतः गलत विधि से शैनन के लिए उत्तरदाई ठहराया जाता है।[6][4]
परिपथ स्विचिंग के लिए अनुप्रयोग
- द्विआधारी निर्णय आरेख इस प्रमेय के व्यवस्थित उपयोग से अनुसरण करते हैं
- किसी भी बूलियन फलन को इस प्रमेय के बार-बार आवेदन द्वारा विधि बहुसंकेतक के पदानुक्रम का उपयोग करके स्विचिंग स परिपथ सिद्धांत में सीधे प्रयुक्त किया जा सकता है।
संदर्भ
- ↑ Rosenbloom, Paul Charles (1950). The Elements of Mathematical Logic. p. 5.
- ↑ G. D. Hachtel and F. Somezi (1996), Logic Synthesis and Verification Algorithms, p. 234
- ↑ Boole, George (1854). An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities. p. 72.
- ↑ 4.0 4.1 Brown, Frank Markham (2012) [2003, 1990]. Boolean Reasoning - The Logic of Boolean Equations (reissue of 2nd ed.). Mineola, New York: Dover Publications, Inc. p. 42. ISBN 978-0-486-42785-0. [1]
- ↑ Shannon, Claude (January 1949). "The Synthesis of Two-Terminal Switching Circuits" (PDF). Bell System Technical Journal. 28: 59–98 [62]. doi:10.1002/j.1538-7305.1949.tb03624.x. ISSN 0005-8580.
- ↑ 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, p. 21, CiteSeerX 10.1.1.64.1129 (188 pages)
यह भी देखें
- रीड-मुलर विस्तार
बाहरी संबंध
- Shannon’s Decomposition Example with multiplexers.
- Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.
