हाइपरक्यूब विधि द्वारा बूलियन कार्यों का न्यूनतमकरण

इस लेख में मैं एक ऐसे विषय पर बात करूंगा जो कंप्यूटर विज्ञान और ऑटोमेटा के सिद्धांत में महत्वपूर्ण है - बूलियन कार्यों को कम करना। यह सवाल शायद हर किसी से पूछा गया था जो इस विषय पर अध्ययन या आया था।



हालांकि, कई विधियां हैं, सबसे दिलचस्प वे हैं जिन्हें औपचारिक रूप दिया जा सकता है, और तदनुसार बहुत कठिनाई के बिना क्रमादेशित किया जा सकता है। और मनमाने बूलियन भावों के साथ काम करना। एक आदर्श विधि का आविष्कार नहीं किया गया है, हर किसी के पास एक या एक और कमजोर और मजबूत गुणवत्ता है। मैं तथाकथित हाइपरक्यूब विधि - क्वीन विधि पर ध्यान केंद्रित करूंगा।



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



विधि प्रसिद्ध संबंध और अवशोषण नियमों को लागू करने में शामिल है।









एल्गोरिथ्म का वर्णन करने से पहले, मैं बताऊंगा कि विधि को हाइपरक्यूब विधि क्यों कहा जाता है।

एक मनमाना फ़ंक्शन ले लो, M1 (f) यूनिट सेट है। सीधे शब्दों में, चर के कई सेट हैं, जिस पर फ़ंक्शन सही विवरण में बदल जाता है।

हाइपरक्यूब एक सेट M1 (f) है।

यदि एक M1 (K) M1 (f) में सम्‍मिलित है, तो एक संयुग्मित मोनोमियल एक इम्प्लिकेंट है।

यदि अन्य कोई K2 नहीं है, तो एक इम्प्लिकेंट को सरल कहा जाता है, कि M1 (K) M1 (K2) में समाहित है, सरल शब्दों में - यह सबसे बड़े हाइपरक्यूब से मेल खाता है।

इस विधि के मुख्य चरण

• एक सत्य तालिका बनाएँ।
• एम 1 (एफ) और प्रत्यारोपण से सभी हाइपरक्यूब्स लिखें।
• सरल प्रत्यारोपण लें।
• एक कवरेज तालिका बनाएँ।
• शेष सरल प्रत्यारोपण से एक मृत अंत DNF बनाते हैं।

एक उदाहरण के रूप में निम्नलिखित बूलियन फ़ंक्शन को लें।

हम इसके लिए एक सत्य तालिका का निर्माण करते हैं:



हम M1 (f) और संबंधित प्रत्यारोपण में पड़ी सभी हाइपरक्यूब लिखते हैं:



हम सरल प्रत्यारोपण का चयन करते हैं और उनके कवर की एक तालिका बनाते हैं:





चूंकि इम्प्लांट yz दूसरों के साथ ओवरलैप होता है, इसलिए इसे एक्सप्रेशन से हटाया जा सकता है। यह पता चला है कि मृत-अंत DNF फ़ंक्शन का रूप है:

मैं सभी को सलाह देता हूं कि आप केजी की अद्भुत पुस्तक को पढ़ें। समोफालोवा "डिजिटल ऑटोमेटा का अनुप्रयुक्त सिद्धांत"।