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

Revision as of 10:07, 17 June 2023

बूल का विस्तार प्रमेय, जिसे अक्सर शैनन विस्तार या अपघटन के रूप में संदर्भित किया जाता है, पहचान (गणित) है: $F=x\cdot F_{x}+x'\cdot F_{x'}$ , कहाँ $F$ क्या कोई बूलियन समारोह है, $x$ चर है, $x'$ का पूरक है $x$ , और $F_{x}$ और $F_{x'}$ हैं $F$ तर्क के साथ $x$ के बराबर सेट करें $1$ और करने के लिए $0$ क्रमश।

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

इसे बूलियन बीजगणित का मौलिक प्रमेय कहा गया है।^[1]इसके सैद्धांतिक महत्व के अलावा, इसने द्विआधारी निर्णय आरेख (BDDs), बूलियन संतुष्टि समस्या, और कंप्यूटर इंजीनियरिंग से संबंधित कई अन्य तकनीकों और डिजिटल सर्किट के औपचारिक सत्यापन का मार्ग प्रशस्त किया। ऐसे इंजीनियरिंग संदर्भों में (विशेष रूप से BDDs में), विस्तार की व्याख्या सशर्त_(कंप्यूटर_प्रोग्रामिंग) के रूप में की जाती है। यदि-तो-और, चर के साथ $x$ स्थिति होने के नाते और कोफ़ेक्टर्स शाखाएँ होने के नाते ( $F_{x}$ कब $x$ सत्य है और क्रमशः $F_{x'}$ कब $x$ गलत है)।^[2]

प्रमेय का कथन

प्रमेय को बताने का अधिक स्पष्ट तरीका है:

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})

रूपांतर और निहितार्थ

एक्सओआर-फॉर्म: जब अलगाव + को एकमात्र ऑपरेटर द्वारा प्रतिस्थापित किया जाता है तो यह कथन भी धारण करता है:; $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})$
दोहरा रूप: शैनन विस्तार का दोहरा रूप है (जिसका कोई संबंधित XOR रूप नहीं है):; $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}))$

प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फ़ंक्शन के उत्पादों का योग (SoP) विहित रूप हो जाता है $f$ . उदाहरण के लिए $n=2$ वह हो सकता है

{\begin{aligned}f(X_{1},X_{2})&=X_{1}\cdot f(1,X_{2})+X_{1}'\cdot f(0,X_{2})\\&=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{aligned}}

इसी तरह, द्वैत रूप का प्रयोग उत्पाद के योग (PoS) के विहित रूप (वितरणात्मक गुण#सत्य के कार्यात्मक संयोजकों का उपयोग करके) की ओर ले जाता है। $+$ ऊपर $\cdot$ ):

{\begin{aligned}f(X_{1},X_{2})&=(X_{1}+f(0,X_{2}))\cdot (X_{1}'+f(1,X_{2}))\\&=(X_{1}+X_{2}+f(0,0))\cdot (X_{1}+X_{2}'+f(0,1))\cdot (X_{1}'+X_{2}+f(1,0))\cdot (X_{1}'+X_{2}'+f(1,1))\end{aligned}}

सहकारकों के गुण

कॉफ़ैक्टर्स के रैखिक गुण: बूलियन फ़ंक्शन F के लिए जो दो बूलियन फ़ंक्शंस G और H से बना है, निम्नलिखित सत्य हैं:; अगर $F=H'$ तब $F_{x}=H'_{x}$; अगर $F=G\cdot H$ तब $F_{x}=G_{x}\cdot H_{x}$; अगर $F=G+H$ तब $F_{x}=G_{x}+H_{x}$; अगर $F=G\oplus H$ तब $F_{x}=G_{x}\oplus H_{x}$
संयुक्त कार्यों के लक्षण: यदि एफ एक असमान फलन है और...; यदि F सकारात्मक unate है तो $F=x\cdot F_{x}+F_{x'}$; यदि F ऋणात्मक है तो $F=F_{x}+x'\cdot F_{x'}$

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

बूलियन अंतर: शाब्दिक x के संबंध में फ़ंक्शन F का बूलियन अंतर या बूलियन अंतर कैलकुलेशन इस प्रकार परिभाषित किया गया है:; ${\frac {\partial F}{\partial x}}=F_{x}\oplus F_{x'}$
सार्वभौमिक परिमाणीकरण: एफ की सार्वभौमिक परिमाणीकरण को इस प्रकार परिभाषित किया गया है:; $\forall xF=F_{x}\cdot F_{x'}$
अस्तित्वगत परिमाणीकरण: F के अस्तित्वगत परिमाणीकरण को इस प्रकार परिभाषित किया गया है:; $\exists xF=F_{x}+F_{x'}$

इतिहास

जॉर्ज बूले ने इस विस्तार को अपने प्रस्ताव 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.

[Rosenbloom_1950-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

[Boole_1854-3] Boole, George (1854). An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities. p. 72.

[Brown_2012-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]

[Shannon_1949-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.

[Perkowski-Grygiel_1995-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)

[1]

[2]

[3]

[4]

[5]

[6]

@@ 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>F</math> तर्क के साथ <math>x</math> के बराबर सेट करें <math>1</math> और करने के लिए <math>0</math> क्रमश।
+बूल का विस्तार प्रमेय, जिसे अक्सर शैनन विस्तार या अपघटन के रूप में संदर्भित किया जाता है, [[पहचान (गणित)]] है: <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), [[बूलियन संतुष्टि समस्या]], और [[कंप्यूटर इंजीनियरिंग]] से संबंधित कई अन्य तकनीकों और डिजिटल सर्किट के [[औपचारिक सत्यापन]] का मार्ग प्रशस्त किया।
+इसे बूलियन बीजगणित का मौलिक प्रमेय कहा गया है।<ref name="Rosenbloom_1950" />इसके सैद्धांतिक महत्व के अलावा, इसने [[द्विआधारी निर्णय आरेख]] (BDDs), [[बूलियन संतुष्टि समस्या]], और [[कंप्यूटर इंजीनियरिंग]] से संबंधित कई अन्य तकनीकों और डिजिटल सर्किट के [[औपचारिक सत्यापन]] का मार्ग प्रशस्त किया।
-ऐसे इंजीनियरिंग संदर्भों में (विशेष रूप से 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>
+ऐसे इंजीनियरिंग संदर्भों में (विशेष रूप से 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>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>
@@ Line 36: / Line 38: @@
 ; कॉफ़ैक्टर्स के रैखिक गुण:
-: एक बूलियन फ़ंक्शन ''F'' के लिए जो दो बूलियन फ़ंक्शंस ''G'' और ''H'' से बना है, निम्नलिखित सत्य हैं:
+: बूलियन फ़ंक्शन ''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>
@@ Line 63: / Line 65: @@
 [[जॉर्ज बूले]] ने इस विस्तार को अपने प्रस्ताव 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"/>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:07, 17 June 2023

Contents

प्रमेय का कथन

रूपांतर और निहितार्थ

सहकारकों के गुण

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

इतिहास

सर्किट स्विचिंग के लिए आवेदन

संदर्भ

यह भी देखें

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:07, 17 June 2023

प्रमेय का कथन

रूपांतर और निहितार्थ

सहकारकों के गुण

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

इतिहास

सर्किट स्विचिंग के लिए आवेदन

संदर्भ

यह भी देखें

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories