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

From Vigyanwiki

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


यह भी देखें

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

बाहरी संबंध