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

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