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

बूल का विस्तार प्रमेय, जिसे अधिकांशतः शैनन विस्तार या अपघटन के रूप में संदर्भित किया जाता है, पहचान (गणित) है: $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)$ (मूल्यांकन (तर्क) और आंशिक अनुप्रयोग देखें)।

इसे बूलियन बीजगणित का मौलिक प्रमेय कहा गया है।इसके सैद्धांतिक महत्व के अतिरिक्त, इसने द्विआधारी निर्णय आरेख (BDDs), बूलियन संतुष्टि समस्या, और कंप्यूटर इंजीनियरिंग से संबंधित कई अन्य विधि और डिजिटल सर्किट के औपचारिक सत्यापन का मार्ग प्रशस्त किया। ऐसे इंजीनियरिंग संदर्भों में (विशेष रूप से BDDs में), विस्तार की व्याख्या सशर्त_(कंप्यूटर_प्रोग्रामिंग) के रूप में की जाती है। यदि-तो-और, चर के साथ $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})$

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

एक्सओआर-फॉर्म

जब अलगाव + को एकमात्र ऑपरेटर द्वारा प्रतिस्थापित किया जाता है तो यह कथन भी धारण करता है:

$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) में किसी भी संख्या में तार्किक प्रतीकों को सम्मिलित करने वाले फ़ंक्शन का विस्तार या विकास करने के लिए,और बूले और उन्नीसवीं सदी के अन्य तार्किकों द्वारा इसे व्यापक रूप से प्रयुक्त किया गया था।

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

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

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

यह भी देखें

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

बाहरी संबंध

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