बूल का विस्तार प्रमेय: Difference between revisions

From Vigyanwiki
(Created page with "{{Use dmy dates|date=May 2019|cs1-dates=y}} बूल का विस्तार प्रमेय, जिसे अक्सर शैनन विस्तार या...")
 
No edit summary
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Use dmy dates|date=May 2019|cs1-dates=y}}
'''बूल का विस्तार प्रमेय''', जिसे अधिकांशतः शैनन विस्तार या अपघटन के रूप में संदर्भित किया जाता है, जहाँ <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 \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>F</math> तर्क के साथ <math>x</math> के बराबर सेट करें <math>1</math> और करने के लिए <math>0</math> क्रमश।


शर्तें <math>F_x</math> और <math>F_{x'}</math> कभी-कभी क्रमशः सकारात्मक और नकारात्मक शैनन कॉफ़ैक्टर्स कहलाते हैं <math>F</math> इसके संबंध में <math>x</math>. ये फ़ंक्शन हैं, जिनकी गणना प्रतिबंधित ऑपरेटर द्वारा की जाती है, <math>\operatorname{restrict}(F, x, 0)</math> और <math>\operatorname{restrict}(F, x, 1)</math> ([[मूल्यांकन (तर्क)]] और आंशिक अनुप्रयोग देखें)।


इसे बूलियन बीजगणित का मौलिक प्रमेय कहा गया है।<ref name="Rosenbloom_1950"/>इसके सैद्धांतिक महत्व के अलावा, इसने [[द्विआधारी निर्णय आरेख]] (BDDs), [[बूलियन संतुष्टि समस्या]], और [[कंप्यूटर इंजीनियरिंग]] से संबंधित कई अन्य तकनीकों और डिजिटल सर्किट के [[औपचारिक सत्यापन]] का मार्ग प्रशस्त किया।
<math>F_x</math> और <math>F_{x'}</math> नियमो को कभी-कभी <math>x</math> के संबंध में <math>F</math> के क्रमशः सकारात्मक और नकारात्मक शैनन कॉफ़ैक्टर्स कहा जाता है
ऐसे इंजीनियरिंग संदर्भों में (विशेष रूप से BDDs में), विस्तार की व्याख्या एक सशर्त_(कंप्यूटर_प्रोग्रामिंग) के रूप में की जाती है। यदि-तो-और, चर के साथ <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>\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 ऑपरेटर द्वारा प्रतिस्थापित किया जाता है।
; एक्सओआर-फॉर्म: जब [[ अलगाव ]] + को [[एकमात्र]] ऑपरेटर द्वारा प्रतिस्थापित किया जाता है तो यह कथन भी धारण करता है:
: <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 रूप नहीं है):
; ड्यूल फॉर्म: शैनन विस्तार का ड्यूल फॉर्म है (जिसका कोई संबंधित 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>
प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फ़ंक्शन के [[उत्पादों का योग]] (SoP) विहित रूप हो जाता है <math>f</math>. उदाहरण के लिए <math>n=2</math> वह हो सकता है
प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फलन <math>f</math> के [[उत्पादों का योग]] (एसओपी) विहित रूप हो जाता है. उदाहरण के लिए <math>n=2</math> हो सकता है


:<math>\begin{align}
:<math>\begin{align}
Line 25: 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>
इसी तरह, द्वैत रूप का प्रयोग उत्पाद के योग (PoS) के विहित रूप (वितरणात्मक गुण#सत्य के कार्यात्मक संयोजकों का उपयोग करके) की ओर ले जाता है। <math>+</math> ऊपर <math>\cdot</math>):
इसी तरह, ड्यूल फॉर्म के प्रयोग से योग उत्पाद का (पिओएस ) के विहित रूप का गुणनफल प्राप्त होता है (<math>+</math> over के वितरण नियम का उपयोग करके) :


:<math>\begin{align}
:<math>\begin{align}
Line 33: Line 36:




== सहकारकों के गुण ==
== '''सहकारकों के गुण''' ==
 
; कॉफ़ैक्टर्स के रैखिक गुण:
: एक बूलियन फ़ंक्शन ''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'' सकारात्मक unate है तो <math>F = x \cdot F_x + F_{x'}</math>
: यदि F ऋणात्मक है तो <math>F = F_x + x' \cdot F_{x'}</math>


; कॉफ़ैक्टर्स के रैखिक गुण
: बूलियन फलन ''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'' सकारात्मक फलन है तो <math>F = x \cdot F_x + F_{x'}</math>
: यदि F ऋणात्मक फलन है तो <math>F = F_x + x' \cdot F_{x'}</math>


== कॉफ़ैक्टर्स के साथ संचालन ==
== '''सहकारकों के साथ संचालन''' ==


; बूलियन अंतर:
; बूलियन अंतर
: शाब्दिक x के संबंध में फ़ंक्शन F का बूलियन अंतर या बूलियन अंतर कैलकुलेशन इस प्रकार परिभाषित किया गया है:
: शाब्दिक 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>
; सार्वभौमिक परिमाणीकरण:
; सार्वभौमिक परिमाणीकरण
: एफ की सार्वभौमिक परिमाणीकरण को इस प्रकार परिभाषित किया गया है:
: F की सार्वभौमिक मात्रा को इस प्रकार परिभाषित किया गया है:
: <math> \forall x F = F_x \cdot F_{x'}</math>
: <math> \forall x F = F_x \cdot F_{x'}</math>
; अस्तित्वगत परिमाणीकरण:
; अस्तित्वगत परिमाणीकरण
: F के अस्तित्वगत परिमाणीकरण को इस प्रकार परिभाषित किया गया है:
: F के अस्तित्वगत परिमाणीकरण को इस प्रकार परिभाषित किया गया है:
: <math> \exists x F = F_x + F_{x'}</math>
: <math> \exists x F = F_x + F_{x'}</math><br />
 
 
== इतिहास ==
== इतिहास ==
[[जॉर्ज बूले]] ने इस विस्तार को अपने प्रस्ताव II के रूप में प्रस्तुत किया, अपने द लॉज़ ऑफ थॉट (1854) में किसी भी संख्या में तार्किक प्रतीकों को शामिल करने वाले फ़ंक्शन का विस्तार या विकास करने के लिए,<ref name="Boole_1854"/>और बूले और उन्नीसवीं सदी के अन्य तार्किकों द्वारा इसे व्यापक रूप से लागू किया गया था।<ref name="Brown_2012"/>
[[जॉर्ज बूले]] ने इस विस्तार को अपने प्रस्ताव II के रूप में प्रस्तुत किया, अपने द लॉज़ ऑफ थॉट (1854) में किसी भी संख्या में तार्किक प्रतीकों को सम्मिलित करने वाले फलन का विस्तार या विकास करने के लिए,<ref name="Boole_1854"/> और बूले और उन्नीसवीं सदी के अन्य तार्किकों द्वारा इसे व्यापक रूप से प्रयुक्त किया गया था।<ref name="Brown_2012"/>
 
[[क्लाउड शैनन]] ने 1949 के एक पेपर में अन्य बूलियन पहचानों के बीच इस विस्तार का उल्लेख किया,<ref name="Shannon_1949"/>और पहचान की स्विचिंग नेटवर्क व्याख्याओं को दिखाया। कंप्यूटर डिजाइन और स्विचिंग थ्योरी के साहित्य में, पहचान को अक्सर गलत तरीके से शैनन के लिए जिम्मेदार ठहराया जाता है।<ref name="Perkowski-Grygiel_1995"/><ref name="Brown_2012"/>
 


== सर्किट स्विचिंग के लिए आवेदन ==
[[क्लाउड शैनन]] ने 1949 के पेपर में अन्य बूलियन पहचानों के बीच इस विस्तार का उल्लेख किया,<ref name="Shannon_1949"/> और पहचान की स्विचिंग नेटवर्क व्याख्याओं को दिखाया। कंप्यूटर डिजाइन और स्विचिंग थ्योरी के साहित्य में, पहचान को अधिकांशतः गलत विधि से शैनन के लिए उत्तरदाई ठहराया जाता है।<ref name="Perkowski-Grygiel_1995"/><ref name="Brown_2012"/>
== परिपथ स्विचिंग के लिए अनुप्रयोग ==
# [[द्विआधारी निर्णय आरेख]] इस प्रमेय के व्यवस्थित उपयोग से अनुसरण करते हैं
# [[द्विआधारी निर्णय आरेख]] इस प्रमेय के व्यवस्थित उपयोग से अनुसरण करते हैं
# किसी भी बूलियन फ़ंक्शन को इस प्रमेय के बार-बार आवेदन द्वारा बुनियादी [[बहुसंकेतक]] के पदानुक्रम का उपयोग करके [[स्विचिंग सर्किट सिद्धांत]] में सीधे लागू किया जा सकता है।
# किसी भी बूलियन फलन को इस प्रमेय के बार-बार आवेदन द्वारा विधि [[बहुसंकेतक]] के पदानुक्रम का उपयोग करके [[स्विचिंग सर्किट सिद्धांत|स्विचिंग स परिपथ सिद्धांत]] में सीधे प्रयुक्त किया जा सकता है।


==संदर्भ==
==संदर्भ==
Line 86: Line 84:
* [https://web.archive.org/web/20070927201537/http://homepages.ius.edu/JFDOYLE/c421/html/Chapter6.htm Shannon’s Decomposition] Example with multiplexers.
* [https://web.archive.org/web/20070927201537/http://homepages.ius.edu/JFDOYLE/c421/html/Chapter6.htm Shannon’s Decomposition] Example with multiplexers.
* [http://www1.cs.columbia.edu/~sedwards/papers/soviani2007optimizing.pdf Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF)] Paper on application.
* [http://www1.cs.columbia.edu/~sedwards/papers/soviani2007optimizing.pdf Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF)] Paper on application.
[[Category: बूलियन बीजगणित]] [[Category: जाली सिद्धांत में प्रमेय]]


[[Category: Machine Translated Page]]
[[Category:Created On 10/06/2023]]
[[Category:Created On 10/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with maths render errors]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:जाली सिद्धांत में प्रमेय]]
[[Category:बूलियन बीजगणित]]

Latest revision as of 17:45, 26 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]

परिपथ स्विचिंग के लिए अनुप्रयोग

  1. द्विआधारी निर्णय आरेख इस प्रमेय के व्यवस्थित उपयोग से अनुसरण करते हैं
  2. किसी भी बूलियन फलन को इस प्रमेय के बार-बार आवेदन द्वारा विधि बहुसंकेतक के पदानुक्रम का उपयोग करके स्विचिंग स परिपथ सिद्धांत में सीधे प्रयुक्त किया जा सकता है।

संदर्भ

  1. ↑ Rosenbloom, Paul Charles (1950). The Elements of Mathematical Logic. p. 5.
  2. ↑ G. D. Hachtel and F. Somezi (1996), Logic Synthesis and Verification Algorithms, p. 234
  3. ↑ Boole, George (1854). An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities. p. 72.
  4. ↑ 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]
  5. ↑ 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.
  6. ↑ 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)


यह भी देखें

  • रीड-मुलर विस्तार

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बूल_का_विस्तार_प्रमेय&oldid=196457’