उदाहरण।सीएनएफ सूत्र खोजें

~ ~

एसडीएनएफ का पूर्ण विघटनकारी सामान्य रूप निम्नलिखित एल्गोरिदम का उपयोग करके बनाया जा सकता है:

1. = 1. डीएनएफ एल्गोरिदम

2. = 2. डीएनएफ एल्गोरिदम

3. = 3. डीएनएफ एल्गोरिदम

4. = 4. डीएनएफ एल्गोरिदम

5. समान रूप से गलत शब्दों, यानी फॉर्म की शर्तों को हटा दें

6. लुप्त चरों के साथ शेष पदों को पूरा करें

7. बिंदु 4 दोहराएँ.

उदाहरण।एसडीएनएफ सूत्र खोजें।

~

SCNF के निर्माण के लिए, आप निम्नलिखित योजना का उपयोग कर सकते हैं:

उदाहरण।एसडीएनएफ सूत्र खोजें।

~

यह ज्ञात है (प्रमेय 2.11, 2.12) कि एसडीएनएफ और एससीएनएफ को सूत्र द्वारा विशिष्ट रूप से परिभाषित किया गया है और इसलिए, उन्हें सूत्र की सत्य तालिका का उपयोग करके बनाया जा सकता है।

सत्य तालिका के अनुसार एसडीएनएफ और एससीएनएफ के निर्माण की योजना सूत्र के लिए नीचे दी गई है ~ :

			~
			1 0 1 0 1 1 0 1	एसडीएनएफ; एसकेएनएफ.

2.2. व्यायाम।

2.2.1 नीचे तार्किक अभिव्यक्तियाँ हैं। बूले के तर्क के नियमों का उपयोग करके अपने संस्करण की अभिव्यक्तियों को यथासंभव सरल बनाएं। फिर अपनी सरलीकृत अभिव्यक्ति की मूल अभिव्यक्ति से तुलना करने के लिए सत्य तालिकाओं का उपयोग करें।

2.2.2. एफ 1 और एफ 2 की तुल्यता के प्रश्न को एसडीएनएफ (तालिका 1) में घटाकर स्पष्ट करें।

2.2.3. सामान्यीकृत और बूलियन सिद्धांत (तालिका 1) का उपयोग करके एफ 3 के लिए दोहरी फ़ंक्शन ढूंढें। परिणामों की तुलना करें.

№	च 1	च 2	च 3

2.3. प्रश्नों पर नियंत्रण रखें.

2.3.1. एक कथन को परिभाषित करें.

2.3.2. किसी कथन पर मुख्य परिचालनों की सूची बनाएं।

2.3.3. सत्य तालिका क्या है?

2.3.4. निम्नलिखित सूत्रों के लिए सत्य तालिकाएँ बनाएँ:

~ ~ ~ ;

2.3.5. संचालन के क्रम पर परंपराओं को ध्यान में रखते हुए, सूत्रों में "अतिरिक्त" कोष्ठक और "" चिह्न हटा दें:

;

2.3.6. समतुल्य परिवर्तनों का उपयोग करते हुए, सूत्रों का समान सत्य सिद्ध करें:

2.3.7. दोहरे सूत्र खोजें:

)

2.3.8. निम्नलिखित सूत्रों को सही DNF (SDNF) फॉर्म में घटाएं:

~

2.3.9. निम्नलिखित सूत्रों को पूर्ण सीएनएफ (एससीएनएफ) फॉर्म में घटाएं:

~

प्रयोगशाला कार्य क्रमांक 3

विषय:“बूलियन फ़ंक्शंस का न्यूनतमकरण। तर्क"

लक्ष्य:बूलियन कार्यों को न्यूनतम करने के तरीकों के साथ काम करने में व्यावहारिक कौशल प्राप्त करना।

3.1. सैद्धांतिक जानकारी.

न्यूनतम रूप

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

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

वियोजक सामान्य रूप में प्रस्तुत सूत्र को ग्लूइंग ऑपरेशन और अवशोषण ऑपरेशन के बार-बार उपयोग से सरल बनाया जाता है और (संयोजक सामान्य रूप के लिए दोहरी पहचान का रूप होता है: और)। यहां, और को किसी भी बूलियन बीजगणित सूत्र के रूप में समझा जा सकता है। परिणामस्वरूप, हम एक विश्लेषणात्मक अभिव्यक्ति पर पहुंचते हैं जहां आगे परिवर्तन संभव नहीं है, यानी। हमें एक डेड-एंड फॉर्म मिलता है।

मृत-अंत रूपों में एक न्यूनतम विघटनकारी रूप भी है, और यह अद्वितीय नहीं हो सकता है। यह सुनिश्चित करने के लिए कि दिया गया डेड-एंड फॉर्म न्यूनतम है, आपको सभी डेड-एंड फॉर्म ढूंढने होंगे और उनमें मौजूद अक्षरों की संख्या के आधार पर उनकी तुलना करनी होगी।

उदाहरण के लिए, फ़ंक्शन को पूर्ण सामान्य वियोजक रूप में दिया जाना चाहिए:

शर्तों को समूहीकृत करना और ग्लूइंग ऑपरेशन को लागू करना, हमारे पास है।

एक अन्य समूहीकरण विधि से हमें प्राप्त होता है:

दोनों डेड-एंड फॉर्म न्यूनतम नहीं हैं। न्यूनतम फॉर्म प्राप्त करने के लिए, आपको मूल सूत्र में एक पद को दोहराने का अनुमान लगाना होगा (यह हमेशा किया जा सकता है, क्योंकि)। पहले मामले में, ऐसा सदस्य हो सकता है। तब । पद जोड़ने पर, हमें प्राप्त होता है:। सभी संभावित विकल्पों पर गौर करने के बाद, आप यह सुनिश्चित कर सकते हैं कि अंतिम दो फॉर्म न्यूनतम हैं।

इस स्तर पर सूत्रों के साथ काम करना अंधेरे में भटकने जैसा है। यदि आप इस उद्देश्य के लिए विशेष रूप से विकसित कुछ ग्राफिक और विश्लेषणात्मक अभ्यावेदन और प्रतीकों का उपयोग करते हैं तो न्यूनतम रूपों की खोज की प्रक्रिया अधिक दृश्य और उद्देश्यपूर्ण हो जाती है।

बहुआयामी घन

एक-आयामी घन के प्रत्येक शीर्ष को एक इकाई के एक घटक के साथ जोड़ा जा सकता है। नतीजतन, चिह्नित शीर्षों का उपसमुच्चय पूर्ण विघटनकारी सामान्य रूप में चर के बूलियन फ़ंक्शन के -आयामी घन पर एक मानचित्रण है। चित्र में. 3.1 खंड 3.7 से फ़ंक्शन के लिए ऐसी मैपिंग दिखाता है।

चित्र 3.1 एसडीएनएफ में प्रस्तुत फ़ंक्शन का त्रि-आयामी क्यूब पर प्रदर्शन

किसी भी वियोजक सामान्य रूप में प्रस्तुत चर के एक फ़ंक्शन को प्रदर्शित करने के लिए, इसके मिनीटर्म और -आयामी घन के तत्वों के बीच एक पत्राचार स्थापित करना आवश्यक है।

(-1) रैंक के एक मिनीटर्म को रैंक के दो मिनीटर्म (एकता का घटक) को एक साथ जोड़ने का परिणाम माना जा सकता है, यानी। , एक -आयामी घन पर, यह दो शीर्षों को प्रतिस्थापित करने से मेल खाता है जो केवल इन शीर्षों को एक किनारे से जोड़ने वाले निर्देशांक के मूल्यों में भिन्न होते हैं (कहा जाता है कि किनारा उस पर घटना वाले शीर्षों को कवर करता है)। इस प्रकार, (-1)वें क्रम के लघुपद -आयामी घन के किनारों के अनुरूप होते हैं। इसी प्रकार, (-2)वें क्रम के लघुपदों का पत्राचार एक-आयामी घन के फलकों के साथ स्थापित किया जाता है, जिनमें से प्रत्येक चार शीर्षों (और चार किनारों) को कवर करता है।

आयामों द्वारा विशेषता वाले एक -आयामी घन के तत्वों को -क्यूब्स कहा जाता है। इस प्रकार, शीर्ष 0-घन हैं, किनारे 1-घन हैं, फलक 2-घन हैं, आदि। उपरोक्त तर्क को सामान्यीकृत करते हुए, हम यह मान सकते हैं कि चर के एक फ़ंक्शन के लिए विघटनकारी सामान्य रूप में ()वें रैंक का एक मिनीटर्म एक -क्यूब द्वारा दर्शाया जाता है, और प्रत्येक -क्यूब निचले आयाम के उन सभी -क्यूब को कवर करता है जो इसके शीर्षों से जुड़े होते हैं . एक उदाहरण के रूप में, चित्र में। 3.2 तीन चरों का एक फ़ंक्शन दिखाता है। यहां मिनीटर्म और 1-क्यूब () के अनुरूप हैं, और मिनीटर्म को 2-क्यूब () द्वारा दर्शाया गया है।

चित्र.3.2 फ़ंक्शन कवरेज

तो, किसी भी विघटनकारी सामान्य रूप को -क्यूब्स के एक सेट द्वारा एक -आयामी क्यूब पर मैप किया जाता है जो एकता के घटकों (0-क्यूब्स) के अनुरूप सभी शीर्षों को कवर करता है। विपरीत कथन भी सत्य है: यदि -क्यूब्स का एक निश्चित सेट किसी फ़ंक्शन के इकाई मानों के अनुरूप सभी शीर्षों के सेट को कवर करता है, तो इन -क्यूब्स के अनुरूप मिनीटर्म्स का विच्छेदन, विच्छेदन सामान्य में इस फ़ंक्शन की अभिव्यक्ति है रूप। कहा जाता है कि -क्यूब्स (या उनके संगत मिनीटर्म) का ऐसा संग्रह किसी फ़ंक्शन का आवरण बनाता है।

न्यूनतम रूप की चाहत को सहज रूप से ऐसे आवरण की खोज के रूप में समझा जाता है, जिसके घनों की संख्या छोटी हो और उनका आयाम बड़ा हो। न्यूनतम प्रपत्र के अनुरूप कवरेज को न्यूनतम कवरेज कहा जाता है। उदाहरण के लिए, चित्र में कवरिंग फ़ंक्शन के लिए। 3.3 न्यूनतम प्रपत्रों को पूरा करता है और .

चावल। 3.3 फ़ंक्शन कवरेज।

बाएं – ; दायी ओर –

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

चावल। 3.4 फ़ंक्शन डिस्प्ले एक चार आयामी घन पर

कार्नोट मानचित्र

बूलियन फ़ंक्शंस को ग्राफ़िक रूप से प्रदर्शित करने के लिए एक अन्य विधि का उपयोग किया जाता है कार्नोट मानचित्र, जो विशेष रूप से व्यवस्थित पत्राचार तालिकाएँ हैं। तालिका के कॉलम और पंक्तियाँ दो से अधिक चर के मानों के सभी संभावित सेटों के अनुरूप हैं, और इन सेटों को इस तरह से व्यवस्थित किया गया है कि प्रत्येक बाद वाला केवल एक चर के मान में पिछले वाले से भिन्न हो . इसके कारण, तालिका की पड़ोसी कोशिकाएँ क्षैतिज और लंबवत रूप से केवल एक चर के मान में भिन्न होती हैं। तालिका के किनारों पर स्थित कोशिकाओं को भी आसन्न माना जाता है और उनमें यह गुण होता है। चित्र में. चित्र 3.5 दो, तीन, चार चरों के लिए कर्णघ मानचित्र दिखाता है।

चावल। 3.5 कार्नॉघ दो, तीन और चार चरों के लिए मानचित्र बनाता है

सामान्य सत्य तालिकाओं की तरह, सेट की कोशिकाएँ जिनमें फ़ंक्शन मान 1 लेता है, भरी हुई होती हैं (शून्य आमतौर पर फिट नहीं होते हैं, वे खाली कोशिकाओं के अनुरूप होते हैं)। उदाहरण के लिए, चित्र में. 3.6, एकिसी फ़ंक्शन के लिए कर्नाघ मानचित्र दिखाता है, जिसका चार-आयामी घन पर प्रदर्शन चित्र में दिया गया है। 3.4. चीजों को सरल बनाने के लिए, एक वेरिएबल के लिए 1 के मान के अनुरूप पंक्तियों और स्तंभों को उस वेरिएबल को इंगित करने वाले घुंघराले ब्रेस के साथ हाइलाइट किया जाता है।

चावल। 3.6 कार्नॉघ मानचित्र पर चार चरों का एक फ़ंक्शन प्रदर्शित करना

(ए) और इसका न्यूनतम कवरेज (बी)

फ़ंक्शन मैपिंग के बीच एन-आयामी घन और कार्नोट मानचित्र में एक-से-एक पत्राचार होता है। कार्नोट मानचित्र पर एस-एक घन एक पंक्ति, स्तंभ, वर्ग या आयत में रखे गए 2 पड़ोसी कोशिकाओं के एक सेट से मेल खाता है (मानचित्र के विपरीत किनारों की निकटता को ध्यान में रखते हुए)। इसलिए, ऊपर निर्धारित सभी प्रावधान (पैराग्राफ देखें)। बहुआयामी घन), कर्नाघ मानचित्रों के लिए मान्य हैं। तो, चित्र में. 3.6, बीन्यूनतम वियोजक प्रपत्र के अनुरूप मानचित्र इकाइयों का कवरेज दिखाता है विचाराधीन कार्य.

कर्नाघ मानचित्र से मिनीटर्म पढ़ना एक सरल नियम का पालन करता है। कोशिकाएं बन रही हैं एस-घन, मिनिटर दे दो (एन-एस)-वीं रैंक, जिसमें वे भी शामिल हैं (एन-एस)वेरिएबल जो इस पर समान मान रखते हैं एस-क्यूब, जहां मान 1 स्वयं चर से मेल खाता है, और मान 0 उनके निषेध से मेल खाता है। वेरिएबल जो अपने मूल्यों को बरकरार नहीं रखते हैं एस-क्यूब, मिनिटर्म में अनुपस्थित हैं। पढ़ने के अलग-अलग तरीकों से फ़ंक्शन के अलग-अलग निरूपण विच्छेदनात्मक सामान्य रूप में होते हैं (सबसे दाईं ओर वाला न्यूनतम है) (चित्र 3.7)।

कर्नाघ मानचित्रों के उपयोग के लिए मानचित्रण की तुलना में सरल निर्माण की आवश्यकता होती है एन-आयामी घन, विशेष रूप से चार चर के मामले में। पांच चरों के कार्यों को प्रदर्शित करने के लिए, चार चरों के लिए दो कर्णघ मानचित्रों का उपयोग किया जाता है, और छह चरों के कार्यों को प्रदर्शित करने के लिए, ऐसे चार मानचित्रों का उपयोग किया जाता है। चरों की संख्या में और वृद्धि के साथ, कर्णघ मानचित्र व्यावहारिक रूप से अनुपयोगी हो जाते हैं।

साहित्य में प्रसिद्ध वेइच कार्डवे केवल परिवर्तनीय मानों के सेट के अलग-अलग क्रम में भिन्न होते हैं और उनमें कर्णघ मानचित्रों के समान गुण होते हैं।

घनों का सम्मिश्रण

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

). एकता के घटकों के अनुरूप 0-घन को चर मानों के सेट द्वारा दर्शाया जाता है, जिस पर फ़ंक्शन एकता के बराबर होता है। जाहिर है रिकॉर्डिंग में

चावल। 3.8 तीन चरों वाले एक फलन के घनों का सम्मिश्रण ( ए) और इसका प्रतीकात्मक प्रतिनिधित्व ( बी)

घनों का संकुल बनता है अधिकतम फ़ंक्शन कवरेज. इसमें से उन सभी को छोड़कर एस-जो घन उच्च आयाम के घनों से ढके होते हैं, हम मृत-अंत रूपों के अनुरूप आवरण प्राप्त करते हैं। तो, विचाराधीन उदाहरण के लिए (चित्र 3.8) हमारे पास एक डेड-एंड कवरिंग है

,

जो फ़ंक्शन से मेल खाता है . इस मामले में, यह कवरेज न्यूनतम है.

दो बूलियन फ़ंक्शंस के लिए, वियोजन संक्रिया उनके घन संकुलों के मिलन से मेल खाती है, और संयोजन संक्रिया उनके घन संकुलों के प्रतिच्छेदन से मेल खाती है। किसी फ़ंक्शन का निषेधन घनों के एक कॉम्प्लेक्स के पूरक से मेल खाता है, यानी, और उन सभी शीर्षों द्वारा निर्धारित किया जाता है जिन पर फ़ंक्शन मान 0 लेता है। इस प्रकार, बीजगणित के बीच एक-से-एक पत्राचार (आइसोमोर्फिज्म) होता है बूलियन फ़ंक्शंस और बूलियन सेट क्यूब्स के कॉम्प्लेक्स का प्रतिनिधित्व करते हैं।

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

बूलियन फ़ंक्शंस को न्यूनतम करना

समस्या का निरूपण.बूलियन आधार पर एक सर्किट को छोटा करने से न्यूनतम कवरेज के अनुरूप न्यूनतम विच्छेदात्मक रूप खोजा जा सकता है। सामान्य रूप में शामिल पत्रों की कुल संख्या कवरेज की लागत से व्यक्त की जाती है , n चरों के दिए गए फ़ंक्शन का आवरण बनाने वाले घनों की संख्या कहां है। न्यूनतम कवरेज की विशेषता इसकी कीमत का न्यूनतम मूल्य है।

आमतौर पर, न्यूनतमकरण समस्या को दो चरणों में हल किया जाता है। सबसे पहले, हम एक कम किए गए कवर की तलाश करते हैं जिसमें अधिकतम आयाम के सभी क्यूब शामिल हों, लेकिन इस कवर के किसी भी क्यूब द्वारा कवर किया गया एक भी क्यूब शामिल नहीं है। संगत वियोजक सामान्य रूप को लघुकृत कहा जाता है, और इसके लघुपदों को सरल निहितार्थ कहा जाता है। किसी दिए गए फ़ंक्शन के लिए, कम किया गया कवरेज अद्वितीय है, लेकिन यह इस तथ्य के कारण अनावश्यक हो सकता है कि कुछ क्यूब्स अन्य क्यूब्स के संग्रह द्वारा कवर किए गए हैं।

दूसरे चरण में, कम से मृत-अंत विघटनकारी सामान्य रूपों में संक्रमण किया जाता है, जिसमें से न्यूनतम रूपों का चयन किया जाता है। सभी निरर्थक घनों को कम कवर से बाहर करके डेड-एंड फॉर्म बनाए जाते हैं, जिसके बिना घनों का शेष सेट अभी भी किसी दिए गए फ़ंक्शन का आवरण बनाता है, लेकिन किसी भी घन के आगे बहिष्करण के साथ, यह अब सेट को कवर नहीं करता है फ़ंक्शन के एकल मानों के अनुरूप सभी शीर्ष, यानी यह एक कवर होना बंद कर देता है।

एक कम कवरेज क्यूब जो किसी दिए गए फ़ंक्शन के शीर्षों को कवर करता है जो किसी भी अन्य क्यूब्स द्वारा कवर नहीं किया जाता है, अनावश्यक नहीं हो सकता है और हमेशा न्यूनतम कवरेज में शामिल किया जाएगा। इस तरह के घन को, इसके संगत निहितार्थ की तरह, एक चरम (आवश्यक निहितार्थ) कहा जाता है, और जिन शीर्षों को यह कवर करता है उन्हें रद्द शीर्ष कहा जाता है। एक्सट्रीमल्स का सेट आवरण का मूल बनाता है, यह स्पष्ट है कि कम आवरण से न्यूनतम आवरण की ओर बढ़ते समय, सबसे पहले, सभी एक्सट्रीमल्स को अलग किया जाना चाहिए। यदि एक्सट्रीमल्स का सेट एक आवरण नहीं बनाता है, तो इसे कम आवरण से क्यूब्स के साथ कवर करने के लिए पूरक किया जाता है।

दी गई परिभाषाएँ चित्र में दर्शाई गई हैं। 3.9, जहां कम कवरेज (चित्र 3.9ए देखें, ) और न्यूनतम कवरेज (चित्र 3.9 बी) और (चित्र 3.9, बी देखें) निम्नानुसार व्यक्त किए गए हैं।

परिभाषा 1.संयोजक एकपदी (प्रारंभिक संयोजन)चरों का इन चरों या उनके निषेधों का संयोजन है।

उदाहरण के लिए, एक प्रारंभिक संयोजन है।

परिभाषा 2.विच्छेदनात्मक एकपदी (प्रारंभिक वियोजन)चरों से इन चरों का विच्छेद या उनका निषेधन होता है।

उदाहरण के लिए, एक प्राथमिक विच्छेद है।

परिभाषा 3.एक सूत्र जो किसी दिए गए प्रस्तावित बीजगणित सूत्र के समतुल्य है और प्राथमिक संयोजक एकपदी का विच्छेदन है, कहलाता है विच्छेदात्मक सामान्य रूप(डीएनएफ) इस सूत्र का।

उदाहरण के लिए,- डीएनएफ.

परिभाषा 4.एक सूत्र जो किसी दिए गए प्रस्तावित बीजगणित सूत्र के समतुल्य है और प्रारंभिक विच्छेदनात्मक एकपदी का संयोजन है, कहलाता है संयोजक सामान्य रूप(CNF) इस सूत्र का.

उदाहरण के लिए, - केएनएफ।

प्रत्येक प्रस्तावक बीजगणित सूत्र के लिए कोई भी वियोजक और संयोजक सामान्य रूपों का एक सेट पा सकता है।

सामान्य प्रपत्रों के निर्माण के लिए एल्गोरिदम

तार्किक बीजगणित की तुल्यताओं का उपयोग करते हुए, सूत्र में सभी बुनियादी संक्रियाओं को बदलें: संयोजन, वियोजन, निषेध:

दोहरी नकारात्मकताओं से छुटकारा पाएं.

यदि आवश्यक हो, तो संयोजन और विच्छेदन के संचालन के लिए वितरण और अवशोषण सूत्रों के गुणों को लागू करें।

2.6. उत्तम विभक्ति और उत्तम समुच्चय सामान्य रूप

किसी भी बूलियन फ़ंक्शन में DNF और CNF के रूप में कई प्रतिनिधित्व हो सकते हैं। इन अभ्यावेदनों के बीच एक विशेष स्थान पर परफेक्ट डीएनएफ (एसडीएनएफ) और परफेक्ट सीएनएफ (एससीएनएफ) का कब्जा है।

परिभाषा 1. उत्तम विभक्ति सामान्य रूप(एसडीएनएफ) एक डीएनएफ है जिसमें प्रत्येक संयुग्मक एकपदी में सेट से प्रत्येक चर बिल्कुल एक बार होता है, या तो स्वयं या उसके निषेधन में।

संरचनात्मक रूप से, डीएनएफ में घटाए गए प्रत्येक प्रस्तावित बीजगणित सूत्र के लिए एसडीएनएफ को निम्नानुसार परिभाषित किया जा सकता है:

परिभाषा 2. उत्तम विभक्ति सामान्य रूपएक प्रस्तावित बीजगणित सूत्र के (एसडीएनएफ) को इसका डीएनएफ कहा जाता है, जिसमें निम्नलिखित गुण होते हैं:

परिभाषा 3. उत्तम संयोजक सामान्य रूप(एससीएनएफ) एक सीएनएफ है जिसमें प्रत्येक डिसजंक्टिव मोनोमियल में सेट से प्रत्येक चर बिल्कुल एक बार होता है, और या तो स्वयं या उसका निषेधन प्रकट होता है।

संरचनात्मक रूप से, सीएनएफ में घटाए गए प्रत्येक प्रस्तावित बीजगणित सूत्र के लिए एससीएनएफ को निम्नानुसार परिभाषित किया जा सकता है।

परिभाषा 4. उत्तम संयोजक सामान्य रूपकिसी दिए गए प्रस्तावित बीजगणित सूत्र के (एससीएनएफ) को सीएनएफ कहा जाता है जो निम्नलिखित गुणों को संतुष्ट करता है।

प्रमेय 1.वेरिएबल्स का प्रत्येक बूलियन फ़ंक्शन जो समान रूप से गलत नहीं है, उसे एसडीएनएफ में और एक अनूठे तरीके से दर्शाया जा सकता है।

एसडीएनएफ खोजने के तरीके

पहली विधि

दूसरी विधि

उन पंक्तियों का चयन करें जहां सूत्र मान 1 लेता है;

हम इस शर्त के तहत संयोजनों का विच्छेदन बनाते हैं कि यदि एक चर को 1 के मान के साथ संयोजन में शामिल किया जाता है, तो हम इस चर को लिखते हैं यदि 0 के मान के साथ, तो इसका निषेधन; हमें एसडीएनएफ मिलता है।

प्रमेय 2.वेरिएबल्स का प्रत्येक बूलियन फ़ंक्शन जो समान रूप से सत्य नहीं है, उसे एससीएनएफ में और एक अनूठे तरीके से दर्शाया जा सकता है।

एससीएनएफ खोजने के तरीके

पहली विधि- समतुल्य परिवर्तनों का उपयोग करना:

दूसरी विधि- सत्य तालिकाओं का उपयोग करना:

उन पंक्तियों का चयन करें जहां सूत्र मान 0 लेता है;

हम इस शर्त के तहत वियोजनों का एक संयोजन बनाते हैं कि यदि एक चर को 0 के मान के साथ वियोजन में शामिल किया जाता है, तो हम इस चर को लिखते हैं यदि 1 के मान के साथ, तो इसका निषेधन; हमें एसकेएनएफ मिलता है।

उदाहरण 1।सीएनएफ फ़ंक्शन का निर्माण करें।

समाधान

आइए परिवर्तनीय परिवर्तन के नियमों का उपयोग करके संयोजक "" को हटा दें:

= /डी मॉर्गन के नियम और दोहरा निषेध/ =

/वितरणात्मक कानून/=

उदाहरण 2. DNF का सूत्र बताइये।

समाधान

आइए और का उपयोग करके तार्किक संक्रियाओं को व्यक्त करें:

= /आइए निषेध को चर के रूप में वर्गीकृत करें और दोहरे नकारात्मक को कम करें/ =

= /वितरण का नियम/ .

उदाहरण 3.डीएनएफ और एसडीएनएफ में सूत्र लिखें।

समाधान

तर्क के नियमों का उपयोग करते हुए, हम इस सूत्र को एक ऐसे रूप में बदल देते हैं जिसमें केवल प्रारंभिक संयोजनों का विच्छेदन होता है। परिणामी सूत्र वांछित DNF होगा:

एसडीएनएफ के निर्माण के लिए, आइए इस सूत्र के लिए एक सत्य तालिका बनाएं:

हम तालिका की उन पंक्तियों को चिह्नित करते हैं जिनमें सूत्र (अंतिम स्तंभ) मान 1 लेता है। ऐसी प्रत्येक पंक्ति के लिए, हम एक सूत्र लिखते हैं जो इस पंक्ति के चर के सेट पर सत्य है:

लाइन 1: ;

पंक्ति 3: ;

पंक्ति 5: .

इन तीन सूत्रों का विच्छेदन केवल पंक्ति 1, 3, 5 में चर के सेट पर मान 1 लेगा, और इसलिए वांछित पूर्ण विच्छेदन सामान्य रूप (पीडीएनएफ) होगा:

उदाहरण 4.सूत्र को SKNF में दो तरीकों से लाएँ:

ए) समतुल्य परिवर्तनों का उपयोग करना;

बी) सत्य तालिका का उपयोग करना।

समाधान:

आइए हम दूसरे प्राथमिक विच्छेदन को रूपांतरित करें:

सूत्र इस प्रकार दिखता है:

बी) इस सूत्र के लिए एक सत्य तालिका बनाएं:

हम तालिका की उन पंक्तियों को चिह्नित करते हैं जिनमें सूत्र (अंतिम स्तंभ) मान 0 लेता है। ऐसी प्रत्येक पंक्ति के लिए, हम एक सूत्र लिखते हैं जो इस पंक्ति के चर के सेट पर सत्य है:

लाइन 2: ;

पंक्ति 6: .

इन दो सूत्रों का संयोजन केवल पंक्ति 2 और 6 में चर के सेट पर मान 0 लेगा, और इसलिए वांछित पूर्ण संयोजक सामान्य रूप (पीसीएनएफ) होगा:

स्वतंत्र समाधान के लिए प्रश्न और कार्य

1. समतुल्य परिवर्तनों का उपयोग करते हुए, सूत्रों को DNF तक कम करें:

2. समतुल्य परिवर्तनों का उपयोग करते हुए, सूत्रों को CNF में लाएँ:

3. दूसरे वितरण नियम का उपयोग करके, DNF को CNF में बदलें:

ए) ;

4. दिए गए DNF को SDNF में बदलें:

5. दिए गए CNF को SCNF में बदलें:

6. दिए गए तार्किक सूत्रों के लिए, एसडीएनएफ और एससीएनएफ का निर्माण दो तरीकों से करें: समकक्ष परिवर्तनों का उपयोग करना और सत्य तालिका का उपयोग करना।

बी) ;

प्रमेयों को स्वचालित रूप से सिद्ध करने के लिए संयोजक सामान्य रूप सुविधाजनक है। किसी भी बूलियन सूत्र को CNF में घटाया जा सकता है। इसके लिए आप उपयोग कर सकते हैं: दोहरे निषेध का नियम, डी मॉर्गन का नियम, वितरण।

विश्वकोश यूट्यूब

• 1 / 5

  सूत्रों केएनएफ में:

  ¬ ए ∧ (बी ∨ सी) , (\displaystyle \नकारात्मक ए\वेज (बी\वी सी),) (ए ∨ बी) ∧ (¬ बी ∨ सी ∨ ¬ डी) ∧ (डी ∨ ¬ ई) , (\displaystyle (ए\वी बी)\वेज (\नेगेटिव बी\वी सी\वीई \नेग डी)\वेज ( डी\वी\नेग ई),) ए∧बी. (\डिस्प्लेस्टाइल ए\वेज बी.)

  सूत्रों केएनएफ में नहीं:

  ¬ (बी ∨ सी) , (\displaystyle \नकारात्मक (बी\वी सी),) (ए ∧ बी) ∨ सी , (\displaystyle (ए\वेज बी)\वी सी,) ए ∧ (बी ∨ (डी ∧ ई)) . (\displaystyle ए\वेज (बी\वी (डी\वेज ई)).)

  लेकिन ये 3 सूत्र सीएनएफ में नहीं हैं, सीएनएफ में निम्नलिखित सूत्रों के बराबर हैं:

  ¬ बी ∧ ¬ सी , (\displaystyle \नकारात्मक बी\वेज \नकारात्मक सी,) (ए ∨ सी) ∧ (बी ∨ सी) , (\displaystyle (ए\वी सी)\वेज (बी\वी सी),) ए ∧ (बी ∨ डी) ∧ (बी ∨ ई) . (\displaystyle ए\वेज (बी\वी डी)\वेज (बी\वी ई.)

  सीएनएफ का निर्माण

  सीएनएफ के निर्माण के लिए एल्गोरिदम

  1) सूत्र में निहित सभी तार्किक संक्रियाओं से छुटकारा पाएं, उन्हें मूल संक्रियाओं से प्रतिस्थापित करें: संयोजन, वियोजन, निषेध। यह समतुल्य सूत्रों का उपयोग करके किया जा सकता है:

  ए → बी = ¬ ए ∨ बी , (\displaystyle ए\दायां तीर बी=\नकारात्मक ए\वी बी,) ए ↔ बी = (¬ ए ∨ बी) ∧ (ए ∨ ¬ बी) . (\displaystyle ए\लेफ्टराइटएरो बी=(\नकारात्मक ए\वी बी)\वेज (ए\वी \नकारात्मक बी).)

  2) संपूर्ण अभिव्यक्ति से संबंधित निषेध चिह्न को सूत्रों के आधार पर व्यक्तिगत चर कथनों से संबंधित निषेध चिह्न से बदलें:

  ¬ (ए ∨ बी) = ¬ ए ∧ ¬ बी , (\displaystyle \नकारात्मक (ए\वी बी)=\नकारात्मक ए\वेज \नकारात्मक बी,) ¬ (ए ∧ बी) = ¬ ए ∨ ¬ बी . (\displaystyle \नकारात्मक (ए\वेज बी)=\नकारात्मक ए\वी \नकारात्मक बी.)

  3) दोहरी नकारात्मकताओं से छुटकारा पाएं।

  4) यदि आवश्यक हो, तो संयोजन और विच्छेदन के संचालन के लिए वितरण और अवशोषण सूत्रों के गुणों को लागू करें।

  CNF के निर्माण का एक उदाहरण

  आइए हम सूत्र को CNF में लाएं

  एफ = (एक्स → वाई) ∧ ((¬ वाई → जेड) → ¬ एक्स) . (\displaystyle F=(X\राइटएरो Y)\वेज ((\नेगेटिव Y\राइटएरो Z)\राइटएरो \नेगेटिव X.)

  आइए सूत्र को रूपांतरित करें एफ (\डिस्प्लेस्टाइल एफ)ऐसे फ़ॉर्मूले में जिसमें शामिल नहीं है → (\displaystyle \दायां तीर ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ (\displaystyle F=(\neg नकारात्मक Y\vee Z)\vee \neg X).)

  परिणामी सूत्र में, हम निषेध को चर में स्थानांतरित करते हैं और दोहरे नकारात्मक को कम करते हैं:

  एफ = (¬ एक्स ∨ वाई) ∧ ((¬ वाई ∧ ¬ जेड) ∨ ¬ एक्स) . (\displaystyle F=(\neg X\vee Y)\वेज ((\neg Y\wee \neg Z)\vee \neg

  उदाहरण के लिए, निम्नलिखित सूत्र 2-CNF में लिखा गया है:

  (ए ∨ बी) ∧ (¬ बी ∨ सी) ∧ (बी ∨ ¬ सी) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C.).)

  सरल संयोजक बुलाया संयोजक एक या अनेक चर, पर यह प्रत्येक चर की बैठक नहीं अधिक एक टाइम्स (या खुद, या उसकी नकार).

  उदाहरण के लिए, एक सरल संयोजन है,

  संधि तोड़नेवाला सामान्य आकार(डीएनएफ) बुलाया अलगाव सरल संयोजक.

  उदाहरण के लिए, अभिव्यक्ति DNF है.

  उत्तम संधि तोड़नेवाला सामान्य आकार(एसडीएनएफ) बुलाया इस कदर संधि तोड़नेवाला सामान्य रूप, पर कौन वी प्रत्येक संयोजक शामिल सभी चर दिया गया सूची (या खुद, या उनका इनकार), और वी एक और आयतन वहीठीक है.

  उदाहरण के लिए, अभिव्यक्ति डीएनएफ है, लेकिन एसडीएनएफ नहीं। अभिव्यक्ति एसडीएनएफ है.

  सीएनएफ और एसकेएनएफ के लिए समान परिभाषाएँ (संयोजन के स्थान पर विच्छेदन और इसके विपरीत) सत्य हैं। आइए हम सटीक शब्दांकन दें।

  सरल अलगाव बुलाया अलगाव एक या अनेक चर, पर यह प्रत्येक चर शामिल नहीं अधिक एक टाइम्स (या खुद, या उसकी नकार).उदाहरण के लिए, अभिव्यक्ति एक सरल वियोजन है,

  मेल करनेवाला सामान्य आकार(केएनएफ) बुलाया संयोजक सरल विच्छेदन(उदाहरण के लिए, अभिव्यक्ति सीएनएफ है)।

  एक पूर्ण संयोजक सामान्य रूप (पीसीएनएफ) एक सीएनएफ है जिसमें प्रत्येक सरल वियोजन में किसी दी गई सूची के सभी चर (या तो स्वयं या उनके निषेध) शामिल होते हैं, और उसी क्रम में।

  उदाहरण के लिए, अभिव्यक्ति एसकेएनएफ है.

  आइए हम एक रूप से दूसरे रूप में संक्रमण के लिए एल्गोरिदम प्रस्तुत करें। स्वाभाविक रूप से, विशिष्ट मामलों में (एक निश्चित रचनात्मक दृष्टिकोण के साथ) एल्गोरिदम का उपयोग किसी दिए गए फॉर्म के विशिष्ट प्रकार का उपयोग करके सरल परिवर्तनों की तुलना में अधिक श्रम-गहन हो सकता है:

  ए) डीएनएफ से सीएनएफ में संक्रमण

  इस संक्रमण के लिए एल्गोरिथ्म इस प्रकार है: हम डीएनएफ के ऊपर दो निषेध लगाते हैं और, डी मॉर्गन के नियमों का उपयोग करते हुए (ऊपरी निषेध को छुए बिना), हम डीएनएफ के निषेध को वापस डीएनएफ पर कम करते हैं। इस स्थिति में, आपको अवशोषण नियम (या ब्लेक का नियम) का उपयोग करके कोष्ठक खोलना होगा। परिणामी DNF का निषेध (ऊपरी) (फिर से डी मॉर्गन के नियम के अनुसार) हमें तुरंत CNF देता है:

  ध्यान दें कि यदि हम बाहर निकालते हैं तो सीएनएफ को मूल अभिव्यक्ति से भी प्राप्त किया जा सकता है परकोष्ठक से परे;

  बी) सीएनएफ से डीएनएफ में संक्रमण

  यह संक्रमण केवल कोष्ठक खोलकर किया जाता है (अवशोषण नियम फिर से उपयोग किया जाता है)

  इस प्रकार, हमें DNF प्राप्त हुआ।

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

  सी) संक्षिप्त नाम डीएनएफ (या एसडीएनएफ) द्वारा नियम ब्लेक

  इस नियम के अनुप्रयोग में दो भाग होते हैं:

  यदि DNF में असंयुक्त पदों में से कुछ पद हैं , फिर संपूर्ण विच्छेदन में हम पद जोड़ते हैं को 1 को 2. हम सभी संभावित युग्मों के लिए इस ऑपरेशन को कई बार (संभवतः क्रमिक रूप से, या एक साथ) करते हैं, और फिर सामान्य अवशोषण लागू करते हैं;

  यदि जोड़ा गया शब्द पहले से ही डीएनएफ में शामिल था, तो इसे पूरी तरह से खारिज किया जा सकता है, उदाहरण के लिए,

  या

  बेशक, संक्षिप्त डीएनएफ को विशिष्ट रूप से परिभाषित नहीं किया गया है, लेकिन उन सभी में अक्षरों की संख्या समान है (उदाहरण के लिए, डीएनएफ है , ब्लेक के नियम को लागू करने के बाद, कोई इसके बराबर DNF पर पहुंच सकता है):

  ग) डीएनएफ से एसडीएनएफ में संक्रमण

  उदाहरण के लिए, यदि किसी सरल संयोजन में कोई चर नहीं है, जेड, इसमें अभिव्यक्ति डालें, और फिर कोष्ठक खोलें (हम दोहराए जाने वाले असंयुक्त शब्दों को नहीं लिखते हैं)। उदाहरण के लिए:

  घ) केएनएफ से एसकेएनएफ में संक्रमण

  यह परिवर्तन पिछले वाले के समान तरीके से किया जाता है: यदि एक साधारण वियोजन में कुछ चर गायब है (उदाहरण के लिए, जेड, फिर हम इसमें एक अभिव्यक्ति जोड़ते हैं (इससे वियोजन स्वयं नहीं बदलता है), जिसके बाद हम वितरण कानून का उपयोग करके कोष्ठक खोलते हैं):

  इस प्रकार, एसकेएनएफ सीएनएफ से प्राप्त किया गया था।

  ध्यान दें कि न्यूनतम या कम सीएनएफ आमतौर पर संबंधित डीएनएफ से प्राप्त किया जाता है।

  तार्किक कार्यों के सामान्य रूप इकाई Ki 2.7 के घटकों के संयोजी शब्दों के विच्छेदन के रूप में एक बूलियन फ़ंक्शन के प्रतिनिधित्व को इस फ़ंक्शन के DNF का विच्छेदन सामान्य रूप कहा जाता है। इसमें नकार के साथ या उसके बिना लिए गए सभी तार्किक चरों में से एक होता है, तो किसी फ़ंक्शन के प्रतिनिधित्व के इस रूप को इस फ़ंक्शन का पूर्ण विघटनकारी सामान्य रूप एसडीएनएफ कहा जाता है। जैसा कि आप देख सकते हैं, एसडीएनएफ फ़ंक्शन बनाते समय, आपको सभी मिनटर्म्स का एक विच्छेदन बनाने की आवश्यकता होती है जिसके लिए फ़ंक्शन मान 1 लेता है।

  
  अपना काम सोशल नेटवर्क पर साझा करें

  यदि यह कार्य आपको पसंद नहीं आता है, तो पृष्ठ के नीचे समान कार्यों की एक सूची है। आप खोज बटन का भी उपयोग कर सकते हैं

  
  

  व्याख्यान 1.xx

  तार्किक कार्यों के सामान्य रूप

  संयोजक पदों (इकाई घटक) के विच्छेदन के रूप में एक बूलियन फ़ंक्शन का प्रतिनिधित्वके मैं

  , (2.7)

  बुलाया विच्छेदात्मक सामान्य रूप(डीएनएफ) इस फ़ंक्शन का।

  यदि DNF में सभी संयोजक पद हैं minterms , अर्थात सभी तार्किक चरों में से एक, निषेध के साथ या उसके बिना लिया गया हो, तो फ़ंक्शन प्रतिनिधित्व के इस रूप को कहा जाता हैउत्तम विभक्ति सामान्य रूप(एसडीएनएफ ) यह फ़ंक्शन. इसे एसडीएनएफ कहा जाता हैउत्तम , क्योंकि वियोजन में प्रत्येक पद में सभी चर शामिल होते हैं;संधि तोड़नेवाला , क्योंकि सूत्र में मुख्य संक्रिया विच्छेदन है। अवधारणा "सामान्य आकार" का अर्थ है किसी सूत्र को लिखने का एक स्पष्ट तरीका जो किसी दिए गए फ़ंक्शन को कार्यान्वित करता है।

  उपरोक्त को ध्यान में रखते हुए, निम्नलिखित प्रमेय प्रमेय 2.1 से अनुसरण करता है।

  प्रमेय 2. कोई भी बूलियन फ़ंक्शन(समान रूप से नहीं 0) एसडीएनएफ में प्रस्तुत किया जा सकता है, .

  उदाहरण 3. आइए हमारे पास एक तालिका दी गई फ़ंक्शन हैएफ (एक्स 1 , एक्स 2 , एक्स 3 ) (तालिका 10)।

  तालिका 10

  			एफ (एक्स 1 , एक्स 2 , एक्स 3 )

  सूत्र (2.6) के आधार पर हम प्राप्त करते हैं:

  जैसा कि आप देख सकते हैं, एसडीएनएफ फ़ंक्शन बनाते समय, आपको सभी न्यूनतम शब्दों का एक विच्छेदन बनाने की आवश्यकता होती है जिसके लिए फ़ंक्शन मान 1 लेता है।

  वियोजक पदों (शून्य घटक) के संयोजन के रूप में एक बूलियन फ़ंक्शन का प्रतिनिधित्वडी मैं

  , (2.8)

  बुलाया संयोजक सामान्य रूप(CNF) इस फ़ंक्शन का।

  यदि सभी विघटनकारी सीएनएफ शब्द हैंअधिकतम शर्तें , अर्थात, फ़ंक्शन के सभी तार्किक चरों में से एक, निषेध के साथ या उसके बिना लिया गया हो, तो ऐसे CNF को कहा जाता हैपूर्ण संयोजक सामान्य रूप(एसकेएनएफ) इस फ़ंक्शन का।

  प्रमेय 3. कोई भी बूलियन फ़ंक्शन(1 के समान नहीं है) एसकेएनएफ को प्रस्तुत किया जा सकता है, और ऐसा प्रतिनिधित्व ही एकमात्र है.

  प्रमेय का प्रमाण संयोजनात्मक अपघटन पर निम्नलिखित शैनन लेम्मा के आधार पर प्रमेय 2.1 के प्रमाण के समान ही किया जा सकता है।

  शैनन की लेम्मा . कोई भी बूलियन फ़ंक्शन f (x 1, x 2, …, x m) m से चरों को इस प्रकार दर्शाया जा सकता है:

  . (2.9)

  यह ध्यान दिया जाना चाहिए कि तार्किक फ़ंक्शन (DNF और CNF) के प्रतिनिधित्व के दोनों रूप सैद्धांतिक रूप से उनकी क्षमताओं में समान हैं: किसी भी तार्किक सूत्र को DNF (समान शून्य को छोड़कर) और CNF (समान शून्य को छोड़कर) दोनों में दर्शाया जा सकता है ). स्थिति के आधार पर, किसी फ़ंक्शन का किसी न किसी रूप में प्रतिनिधित्व छोटा हो सकता है।

  व्यवहार में, डीएनएफ का सबसे अधिक उपयोग किया जाता है, क्योंकि यह फॉर्म किसी व्यक्ति के लिए अधिक परिचित है: बचपन से, वह रकम को गुणा करने की तुलना में उत्पादों को जोड़ने का अधिक आदी है (बाद वाले मामले में, वह सहज रूप से कोष्ठक खोलने की इच्छा रखता है और इस तरह डीएनएफ पर आगे बढ़ता है)।

  उदाहरण 4. फ़ंक्शन f (x 1 , x 2 , x 3. के लिए ), तालिका द्वारा दिया गया है। 10, इसे SKNF को लिखें।

  एसडीएनएफ के विपरीत, किसी तार्किक फ़ंक्शन की सत्यता तालिका में एससीएनएफ को संकलित करते समय, आपको वेरिएबल्स के संयोजन को देखने की आवश्यकता होती है, जिस पर फ़ंक्शन मान 0 लेता है, और संबंधित अधिकतम शब्दों का संयोजन बनाता है,लेकिन चर को विपरीत व्युत्क्रम के साथ लिया जाना चाहिए:

  यह ध्यान दिया जाना चाहिए कि किसी फ़ंक्शन के एसडीएनएफ से सीधे उसके एससीएनएफ या इसके विपरीत में जाना असंभव है। ऐसे परिवर्तनों का प्रयास करते समय, परिणाम ऐसे कार्य होते हैं जो वांछित कार्यों के विपरीत होते हैं। एसडीएनएफ और एससीएनएफ कार्यों के लिए अभिव्यक्ति सीधे इसकी सत्य तालिका से ही प्राप्त की जा सकती है।

  उदाहरण 5. फ़ंक्शन f (x 1 , x 2 , x 3. के लिए ), तालिका द्वारा दिया गया है। 10, एसडीएनएफ से एसकेएनएफ पर स्विच करने का प्रयास करें।

  उदाहरण 2.3 के परिणाम का उपयोग करने पर हमें मिलता है:

  जैसा कि आप देख सकते हैं, सामान्य व्युत्क्रम के तहत हमने एक तार्किक फ़ंक्शन का SCNF प्राप्त किया, जो उदाहरण 2.4 में प्राप्त फ़ंक्शन का व्युत्क्रम है:

  क्योंकि इसमें वे सभी अधिकतम शब्द शामिल हैं जो विचाराधीन फ़ंक्शन के एससीएनएफ के लिए अभिव्यक्ति में नहीं हैं।

  1. संचालन के गुणों का उपयोग करते हुए (तालिका 9 देखें) पहचान (), योग मॉड्यूल 2 (), निहितार्थ (), हम संचालन और, या, नहीं (बूलियन आधार पर) पर आगे बढ़ते हैं।

  2. निषेध के गुणों और डी मॉर्गन के नियमों (तालिका 9 देखें) का उपयोग करते हुए, हम यह सुनिश्चित करते हैं कि निषेध संक्रियाएँ केवल व्यक्तिगत चर पर लागू होती हैं, न कि संपूर्ण अभिव्यक्तियों पर।

  3. तार्किक संचालन AND और OR (तालिका 9 देखें) के गुणों का उपयोग करके, हम सामान्य रूप (DNF या CNF) प्राप्त करते हैं।

  4. यदि आवश्यक हो, तो हम पूर्ण रूपों (एसडीएनएफ या एसकेएनएफ) की ओर बढ़ते हैं। उदाहरण के लिए, एससीएनएफ प्राप्त करने के लिए आपको अक्सर संपत्ति का उपयोग करने की आवश्यकता होती है:।

  उदाहरण 6. एक तार्किक फ़ंक्शन को SKNF में कनवर्ट करें

  उपरोक्त एल्गोरिथम के चरणों को क्रम से आगे बढ़ाने पर, हमें मिलता है:

  अवशोषण गुण का उपयोग करके, हम प्राप्त करते हैं:

  इस प्रकार, हमने CNF फ़ंक्शन प्राप्त किया हैएफ (एक्स 1 , एक्स 2 , एक्स 3 ). इसका एससीएनएफ प्राप्त करने के लिए, आपको प्रत्येक वियोजन को दोहराना होगा जिसमें कोई भी चर गायब है, इस चर के साथ दो बार और इसके निषेध के साथ:

  2.2.6. तर्क कार्यों को न्यूनतम करना

  चूँकि समान तार्किक फ़ंक्शन को इस प्रकार दर्शाया जा सकता हैएच व्यक्तिगत सूत्र, फिर सबसे सरल रूप खोजनाआर बूलियन फ़ंक्शन को परिभाषित करने वाला म्यूल, बूलियन फ़ंक्शन को लागू करने वाले लॉजिक सर्किट को सरल बनाता हैकरने के लिए. न्यूनतम प्रपत्र एलहे तार्किक कार्यकिसी आधार पर हम उस पर विचार कर सकते हैं जिसमें मनोरंजन के सुपरपोजिशन की न्यूनतम संख्या शामिल होको कोष्ठकों की अनुमति देते हुए, आधार का उल्लेख करें। हालाँकि, एक प्रभावी निर्माण करना कठिन हैएल न्यूनतम कोष्ठक प्राप्त करने के लिए ऐसे न्यूनतमकरण के लिए एल्गोरिदमआर हम.

  आइए संयोजन सर्किट के संश्लेषण में एक सरल न्यूनतमकरण समस्या पर विचार करें, जिसमें हम किसी फ़ंक्शन के न्यूनतम कोष्ठक रूप की तलाश नहीं कर रहे हैं, बल्कि इसके न्यूनतम डीएनएफ की तलाश कर रहे हैं। इस कार्य के लिए सरल, कुशल एल्गोरिदम हैं।

  क्विन की विधि

  न्यूनतम किए जाने वाले फ़ंक्शन को एसडीएनएफ में दर्शाया गया है, और सभी संभावित अपूर्ण ग्लूइंग ऑपरेशन इस पर लागू किए जाते हैं

  , (2.10)

  और फिर अवशोषण

  , (2.11)

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

  ध्यान दें कि समीकरण (2.10) के बाईं ओर को तुरंत सरल और अधिक स्पष्ट तरीके से छोटा किया जा सकता है:

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

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

  कर्णघ मानचित्र विधि

  कार्नोट मैप्स (तालिकाओं) की विधि तार्किक कार्यों को कम करने के लिए एक अधिक दृश्य, कम श्रम-गहन और विश्वसनीय तरीका है, लेकिन इसका उपयोग व्यावहारिक रूप से 3-4 चर, अधिकतम 5-6 चर के कार्यों तक सीमित है।

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

  दो लेन के AND और OR कार्यों के लिए सत्य सारणी और कार्नॉघ मानचित्रइ चर चित्र में प्रस्तुत किए गए हैं। 8. कार्ड के प्रत्येक सेल में एक मान लिखा होता हैए इस सेल के अनुरूप तर्क मानों के सेट पर किसी फ़ंक्शन का मानएन कॉमरेड

  ए) और बी) या

  चावल। 8. दो चर वाले कार्यों के लिए कर्णघ मानचित्र का उदाहरण

  कर्नाघ मानचित्र में And फ़ंक्शन के लिए केवल एक 1 है, इसलिए इसे किसी भी चीज़ से चिपकाया नहीं जा सकता है। न्यूनतम फ़ंक्शन की अभिव्यक्ति में केवल इस 1 के अनुरूप पद शामिल होगा:

  एफ = एक्स वाई .

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

  एफ = एक्स + वाई.

  चित्र में. 9 तीन चर वाले दो कार्यों की सत्य सारणी दिखाता है (ए ) और उनके कार्नोट मानचित्र (बी और सी). फ़ंक्शन एफ 2 पहले से इस मायने में भिन्न है कि इसे चर के तीन सेटों पर परिभाषित नहीं किया गया है (तालिका में इसे डैश द्वारा दर्शाया गया है)।

  न्यूनतम डीएनएफ फ़ंक्शन का निर्धारण करते समय, निम्नलिखित नियमों का उपयोग किया जाता है। 1 युक्त सभी कोशिकाओं को बंद आयताकार क्षेत्रों में संयोजित किया जाता है जिन्हें कहा जाता है k-घन, जहाँ k = लघुगणक 2 K, K एक आयताकार क्षेत्र में मात्रा 1. इस मामले में, प्रत्येक क्षेत्र 2 कोशिकाओं की संख्या के साथ एक आयत होना चाहिए k, जहाँ k = 0, 1, 2, 3,…। के = के लिए 1 आयत कहलाता हैएक एक घन है और इसमें 2 1 = 2 इकाइयाँ हैं; के = के लिए 2 आयत में 2 शामिल हैं 2 = 4 इकाई और कहा जाता हैदो-घन; k = 2 3 के 3 क्षेत्र के लिए = 8 इकाई कहलाती हैतीन घन ; आदि ऐसी इकाइयाँ जिन्हें आयतों में नहीं जोड़ा जा सकता, कहा जा सकता हैशून्य-घन , जिसमें केवल एक इकाई है (2 0 = 1). जैसा कि देखा जा सकता है, सम के लिएक क्षेत्रों का आकार चौकोर हो सकता है (लेकिन जरूरी नहीं), और यदि विषम भी होक केवल आयतें.

  						ख ग

  चावल। 9. तीन चर वाले कार्यों के लिए कर्णघ मानचित्र का उदाहरण

  ये क्षेत्र ओवरलैप हो सकते हैं, यानी एक ही कोशिकाएं विभिन्न क्षेत्रों में प्रवेश कर सकती हैं। फिर न्यूनतम डीएनएफ फ़ंक्शन को संबंधित सभी संयोजक शब्दों के विच्छेदन के रूप में लिखा जाता हैके - क्यूब्स।

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

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

  चित्र में कर्णघ मानचित्र के अनुसार फ़ंक्शन के लिए। 9,बी हम पाते हैं

  चूंकि ऊपरी बंद क्षेत्र के लिए चरएक्स 1 और एक्स 2 निम्न के लिए व्युत्क्रम के बिना मान हैंएक्स 1 व्युत्क्रम के साथ मायने रखता है, और x 3 बिना व्युत्क्रमण के।

  चित्र में मानचित्र में अपरिभाषित मान। 9,वी इसे शून्य या एक से प्रतिस्थापित करके और अधिक परिभाषित किया जा सकता है। इस फ़ंक्शन के लिए, यह स्पष्ट है कि दोनों अपरिभाषित मानों को 1 से प्रतिस्थापित करना अधिक लाभदायक है। इस स्थिति में, दो क्षेत्र बनते हैं, जो विभिन्न प्रकार के 2-क्यूब हैं। फिर न्यूनतम DNF फ़ंक्शन के लिए अभिव्यक्ति इस प्रकार होगी:

  बंद क्षेत्रों का निर्माण करते समय, कार्नोट मानचित्र को क्षैतिज और लंबवत दोनों तरह से एक सिलेंडर में मोड़ने की अनुमति है।आर विपरीत चेहरों के मिलन से टिकल अक्षआर आप, यानी कार्नोट समरूपता मानचित्र के किनारों पर स्थित इकाइयाँएच लेकिन जोड़ा भी जा सकता है.

  कार्नॉघ मानचित्र विभिन्न तरीकों से बनाए जा सकते हैं (चित्र 10)।

  									एक्स 2 एक्स 3

  ए बी

  चावल। 10. कार्नॉघ मानचित्रों को चित्रित करने के विभिन्न तरीके
  3 चर वाले फ़ंक्शन के लिए

  लेकिन 2-4 चर के कार्यों के लिए कर्णघ मानचित्रों के लिए सबसे सुविधाजनक विकल्प चित्र में दिखाए गए हैं। 11 तालिकाएँ, क्योंकि वे प्रत्येक कोशिका के लिए दिखाती हैंए हमारे पास सभी चर प्रत्यक्ष या व्युत्क्रम रूप में हैं।

  ए बी

  चावल। ग्यारह। कार्नॉघ मानचित्रों की सबसे सुविधाजनक छवि
  फ़ंक्शन 3 के लिए (ए) और 4 (बी) चर

  5 और 6 चर वाले कार्यों के लिए, चित्र में दिखाई गई विधि। 10,वी.

  चावल। 12. 5 चरों के एक फ़ंक्शन के लिए कर्णघ मानचित्र की छवि

  चावल। 13. 6 चर वाले फ़ंक्शन के लिए कर्णघ मानचित्र की छवि

  इसी तरह के अन्य कार्य जिनमें आपकी रुचि हो सकती है.vshm>
  9020.		द्वैत का सिद्धांत. बूलियन फ़ंक्शंस का वेरिएबल्स में विस्तार। उत्तम विभक्ति और संयोजक सामान्य रूप	96.34 केबी
  	यह प्रमेय प्रकृति में रचनात्मक है, क्योंकि यह प्रत्येक फ़ंक्शन के लिए एक सूत्र बनाने की अनुमति देता है जो इसे एक पूर्ण डी.एन. के रूप में लागू करता है। एफ। ऐसा करने के लिए, प्रत्येक फ़ंक्शन के लिए सत्य तालिका में, हम सभी पंक्तियों को चिह्नित करते हैं
  6490.		तार्किक कार्यों का विवरण और न्यूनतमकरण	187.21 केबी
  	किसी फ़ंक्शन के तर्कों और उसके मूल्यों के बीच संबंध मौखिक रूप में व्यक्त किया जाता है। उदाहरण: एक तीन-तर्क फ़ंक्शन एक मान लेता है जब कोई दो या अधिक फ़ंक्शन तर्क बराबर होते हैं। इसमें तर्क मानों के सभी सेटों के लिए फ़ंक्शन मानों वाली एक सत्य तालिका का निर्माण शामिल है। इस उदाहरण में, सत्य तालिका का उपयोग करके, हम DNF के रूप में निम्नलिखित प्रविष्टि प्राप्त करते हैं...
  6707.		संबंधपरक डेटाबेस का डिज़ाइन. शास्त्रीय दृष्टिकोण में डिजाइन समस्याएं। सामान्यीकरण के सिद्धांत, सामान्य रूप	70.48 केबी
  	रिलेशनल डेटाबेस प्रोजेक्ट क्या है? यह परस्पर जुड़े रिश्तों का एक सेट है जिसमें सभी विशेषताओं को परिभाषित किया गया है, रिश्तों की प्राथमिक कुंजी निर्दिष्ट की गई हैं, और रिश्तों के कुछ अतिरिक्त गुण निर्दिष्ट किए गए हैं जो अखंडता बनाए रखने के सिद्धांतों से संबंधित हैं। इसलिए, डेटाबेस डिज़ाइन बहुत सटीक और सत्यापित होना चाहिए। वास्तव में, एक डेटाबेस प्रोजेक्ट भविष्य के सॉफ़्टवेयर पैकेज की नींव है जिसका उपयोग काफी लंबे समय तक और कई उपयोगकर्ताओं द्वारा किया जाएगा।
  4849.		राज्य कार्यों को लागू करने के रूप और तरीके	197.3 केबी
  	"फ़ंक्शन" शब्द का घरेलू और विदेशी वैज्ञानिक साहित्य में एक ही अर्थ नहीं है। दार्शनिक और सामान्य समाजशास्त्रीय शब्दों में, इसे "संबंधों की किसी प्रणाली में किसी वस्तु के गुणों की बाहरी अभिव्यक्ति" के रूप में माना जाता है; व्यक्तियों या निकायों के सामान्य या विशिष्ट कार्यों के एक समूह के रूप में
  17873.		तीसरी कक्षा के छात्रों के लिए तार्किक यूयूडी का गठन	846.71 केबी
  	प्राथमिक स्कूली बच्चों में तार्किक सार्वभौमिक क्रियाओं के गठन की समस्या के मनोवैज्ञानिक और शैक्षणिक पहलू तार्किक यूयूडी के गठन का आकलन करने के तरीके। सामान्य शिक्षा प्रणाली में सार्वभौमिक शैक्षिक गतिविधियों के विकास की अवधारणा का विकास नई सामाजिक आवश्यकताओं को पूरा करता है। आधुनिक शिक्षा प्रणाली का सबसे महत्वपूर्ण कार्य यूयूडी की सार्वभौमिक शैक्षिक गतिविधियों का गठन है। सार्वभौमिक शैक्षिक गतिविधियों का गठन स्कूल की कठिनाइयों को रोकने की कुंजी है।
  2638.		स्वचालित अवरोधन प्रणालियों में तार्किक कनेक्शन का तकनीकी कार्यान्वयन	1.04 एमबी
  	स्वचालित ब्लॉकिंग सिस्टम में तार्किक कनेक्शन का तकनीकी कार्यान्वयन तीन-अंकीय और चार-अंकीय बैटरी के लिए नियंत्रण एल्गोरिदम का तकनीकी कार्यान्वयन रिले संपर्क और संपर्क रहित असतत और अभिन्न तर्क तत्वों का उपयोग करके प्राप्त किया जा सकता है...
  10203.		आपातकालीन स्थिति और विकास के संरचनात्मक और तार्किक मॉडल के निर्माण के लिए जोखिम उन्मुख दृष्टिकोण की अवधारणा का अनुप्रयोग	70.8 केबी
  	सामान्य जोखिम विश्लेषण उत्पादन वातावरण शक्तिशाली तकनीकी प्रणालियों और प्रौद्योगिकियों से संतृप्त होता जा रहा है जो मानव श्रम को उत्पादक और शारीरिक रूप से कम कठिन, लेकिन अधिक खतरनाक बनाता है। जोखिम की विशेषता खतरनाक स्थिति की शुरुआत की अप्रत्याशितता और अचानकता है। हर दिन हमें कई जोखिमों का सामना करना पड़ता है, लेकिन उनमें से अधिकांश संभावित बने रहते हैं। जोखिम सिद्धांत किसी व्यक्ति पर नकारात्मक प्रभाव के साथ-साथ उसके स्वास्थ्य और जीवन को होने वाले नुकसान का मात्रात्मक मूल्यांकन प्रदान करता है।
  11576.		लेन-देन की अवधारणा, प्रकार और रूप। लेन-देन के आवश्यक स्वरूप का अनुपालन करने में विफलता के परिणाम	49.82 केबी
  	किसी लेन-देन को अमान्य के रूप में मान्यता देना; पाठ्यक्रम कार्य का व्यावहारिक मूल्य लेन-देन की अवधारणा को सरल बनाने में निहित है, अर्थात इसकी सार्वजनिक प्रस्तुति को अधिक सुलभ रूप में प्रस्तुत करना।
  6213.		फ़ंक्शन सन्निकटन	3.08 एमबी
  	पहले में विश्लेषणात्मक या सारणीबद्ध रूप से निर्दिष्ट एक निश्चित फ़ंक्शन को मूल फ़ंक्शन के करीब लेकिन गणना के लिए सरल और अधिक सुविधाजनक किसी अन्य फ़ंक्शन के साथ बदलना शामिल है। उदाहरण के लिए, किसी फ़ंक्शन को बहुपद से बदलने से आप संख्यात्मक एकीकरण और विभेदन के लिए सरल सूत्र प्राप्त कर सकते हैं; तालिका को अनुमानित फ़ंक्शन के साथ बदलने से आप इसके मध्यवर्ती बिंदुओं पर मान प्राप्त कर सकते हैं। दूसरी समस्या भी उत्पन्न होती है: बिंदुओं के एक अलग सेट में इस खंड पर दिए गए फ़ंक्शन के मानों से एक निश्चित खंड पर एक फ़ंक्शन को पुनर्स्थापित करना। इस प्रश्न का उत्तर...
  14058.		राज्य के कार्यों का विकास	29.99 केबी
  	एक कानूनी घटना के रूप में रूसी राज्य को सबसे पहले राज्य के उद्देश्य के कार्यान्वयन के साथ-साथ सरकार के एक गणतंत्रात्मक स्वरूप के साथ एक लोकतांत्रिक संघीय कानूनी सामाजिक धर्मनिरपेक्ष राज्य के रूप में इसकी मुख्य संवैधानिक विशेषताओं को सुनिश्चित करना चाहिए। राज्य का मुख्य उद्देश्य कला द्वारा निर्धारित होता है।