बूल का विस्तार प्रमेय

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

$F_{x}$ और $F_{x'}$ नियमो को कभी-कभी $x$ के संबंध में $F$ के क्रमशः सकारात्मक और नकारात्मक शैनन कॉफ़ैक्टर्स कहा जाता है

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

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

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

प्रमेय का कथन

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

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

भिन्नताएं और प्रभाव

XOR-फॉर्म

यह कथन जब धारण करता है जब संयोजन "+" को XOR ऑपरेटर द्वारा प्रतिस्थापित किया जाता है।

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

प्रत्येक तर्क के लिए बार-बार आवेदन करने से बूलियन फलन $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}}$

इसी तरह, ड्यूल फॉर्म के प्रयोग से योग उत्पाद का (पिओएस ) के विहित रूप का गुणनफल प्राप्त होता है ($+$ over के वितरण नियम का उपयोग करके)  :

${\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 एक असमान फलन है और...

यदि F सकारात्मक फलन है तो $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'}$

सार्वभौमिक परिमाणीकरण

F की सार्वभौमिक मात्रा को इस प्रकार परिभाषित किया गया है:

$\forall xF=F_{x}\cdot F_{x'}$

अस्तित्वगत परिमाणीकरण

F के अस्तित्वगत परिमाणीकरण को इस प्रकार परिभाषित किया गया है:

$\exists xF=F_{x}+F_{x'}$

इतिहास

जॉर्ज बूले ने इस विस्तार को अपने प्रस्ताव II के रूप में प्रस्तुत किया, अपने द लॉज़ ऑफ थॉट (1854) में किसी भी संख्या में तार्किक प्रतीकों को सम्मिलित करने वाले फलन का विस्तार या विकास करने के लिए, और बूले और उन्नीसवीं सदी के अन्य तार्किकों द्वारा इसे व्यापक रूप से प्रयुक्त किया गया था।

क्लाउड शैनन ने 1949 के पेपर में अन्य बूलियन पहचानों के बीच इस विस्तार का उल्लेख किया, और पहचान की स्विचिंग नेटवर्क व्याख्याओं को दिखाया। कंप्यूटर डिजाइन और स्विचिंग थ्योरी के साहित्य में, पहचान को अधिकांशतः गलत विधि से शैनन के लिए उत्तरदाई ठहराया जाता है।

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

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

यह भी देखें

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

बाहरी संबंध

• Shannon’s Decomposition Example with multiplexers.
• Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.