1. कर्नो मानचित्र क्या है
कर्नो मानचित्रकर्नो मानचित्रसत्य सारणी की ऐसी जालीदार रचना जिसमें सरलीकरण दिख जाता है।पूरी प्रविष्टि पढ़ें सत्य सारणीसत्य सारणीहर मान-निर्धारण के लिए एक पंक्ति और उसमें सूत्र का मान।पूरी प्रविष्टि पढ़ें को ग्रिड के रूप में फिर से खींचा गया रूप है। मॉरिस कर्नो ने इसे 1953 में बेल लैब्स में प्रस्तुत किया था, ताकि स्विचिंग परिपथों को देखकर ही सरल किया जा सके; छोटी बूलियन फलन को हाथ से न्यूनतम करने का यह आज भी सबसे तेज़ तरीका है - न बीजगणित, न याद रखने योग्य नियम, बस आयत।
मानचित्र का हर कोष्ठ सत्य सारणी की एक पंक्ति रखता है। इसे केवल पुनर्व्यवस्था से अधिक बनाता है उन पंक्तियों का क्रम: पड़ोसी कोष्ठ ठीक एक चरप्रतिज्ञप्ति चरp या A जैसा अक्षर जो किसी भी प्रतिज्ञप्ति के लिए खड़ा होता है।पूरी प्रविष्टि पढ़ें में भिन्न होते हैं।
यही एक गुण सारा काम कर देता है। यदि दो पड़ोसी कोष्ठ दोनों सत्य हैं, तो उनके बीच बदलने वाला चर अभिव्यक्ति को सत्य बनाने का कारण नहीं हो सकता; इसलिए वह हट जाता है और एक ही पद दोनों कोष्ठों को ढक लेता है। सरलीकरण इस तरह सबसे बड़े संभव आयत खींचने का काम बन जाता है।
2. स्तंभों का क्रम अजीब क्यों लगता है
कर्नो मानचित्र के स्तंभ 00, 01, 10, 11 नहीं गिनते। वे 00, 01, 11, 10 चलते हैं - परावर्तित ग्रे कोड, यानी ऐसा क्रम जिसमें हर मान अगले से केवल एक बिट में भिन्न होता है। द्विआधारी गिनती में 01 के बगल में 10 आ जाता, जो दो बिट में भिन्न है, और तब पड़ोसी कोष्ठ कुछ नहीं बताते।
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
किनारे भी पड़ोसी हैं। सबसे बाएँ और सबसे दाएँ स्तंभ एक चर में भिन्न हैं, और यही ऊपर तथा नीचे की पंक्तियों के लिए भी सच है; इसलिए कोई समूह एक किनारे से निकलकर दूसरे किनारे पर जारी रह सकता है - चार चरों वाले मानचित्र के चारों कोने इसी कारण एक ही समूह बनाते हैं। कर्नो मानचित्र असल में एक टोरस पर खिंचा होता है; सपाट पन्ना केवल सुविधा है।
3. एक को समूहित करना
मानचित्र से न्यूनतम गुणनफलों का योगवियोजी प्रसामान्य रूपAND का OR: साहित्यक-संयोजनों का वियोजन।पूरी प्रविष्टि पढ़ें पढ़ने के लिए, 1 वाले हर कोष्ठ को आयताकार समूहों से ढकें, चार नियमों के अनुसार:
- समूह 1, 2, 4, 8 … कोष्ठों का आयत होता है - हर भुजा दो की घात।
- समूह मानचित्र के किनारों से लपेट सकता है - क्षैतिज, ऊर्ध्वाधर या दोनों दिशाओं में।
- समूह एक-दूसरे पर आ सकते हैं। किसी कोष्ठ का दो बार ढका जाना मुफ़्त है; किसी का बिना ढका रह जाना फलन बदल देता है।
- हर समूह को जितना बड़ा हो सके उतना बड़ा बनाइए, फिर सभी एक को ढकने के लिए जितने कम समूह चलें उतने ही लीजिए।
हर समूह एक पद बनता है। उसे पढ़ने के लिए देखिए कि पूरे समूह में कौन-से चर अपरिवर्तित रहते हैं: वही पद में आते हैं - जहाँ वे 1 हैं वहाँ ज्यों के त्यों, जहाँ 0 हैं वहाँ निषेधनिषेधसत्यमान उलट देता है: ¬p ठीक तब सत्य है जब p असत्य हो।पूरी प्रविष्टि पढ़ें के साथ - और बदलने वाला हर चर हट जाता है। दो कोष्ठों का समूह एक चर खोता है, चार का दो, आठ का तीन। न्यूनतम अभिव्यक्ति इन पदों का वियोजनवियोजनकम से कम एक भाग सत्य हो तो सत्य: p ∨ q।पूरी प्रविष्टि पढ़ें है।
4. एक हल किया हुआ उदाहरण
लीजिए (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D)। इसके मानचित्र में चार चर हैं: पंक्तियों में A और B, स्तंभों में C और D।
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
दो समूह सभी एक को ढक लेते हैं। पहला वह चार-कोष्ठीय खंड है जहाँ A = 0 वाली दो पंक्तियाँ और C = 1 वाले दो स्तंभ मिलते हैं: इसके भीतर B और D दोनों बदलते हैं, इसलिए वे हट जाते हैं और पद ¬A ∧ C बनता है। दूसरा वह पूरी पंक्ति है जहाँ A और B दोनों 1 हैं, चारों स्तंभों तक फैली हुई: इसके साथ C और D बदलते हैं और A ∧ B शेष रहता है।
इसलिए न्यूनतम रूप है (¬A ∧ C) ∨ (A ∧ B)। मूल अभिव्यक्ति का तीसरा पद, B ∧ C ∧ D, लुप्त हो गया: उसने जो भी कोष्ठ ढके थे, वे पहले से ही उन दो समूहों में से किसी एक के भीतर थे। अवशोषण जब दिखाई देता है, तो ऐसा ही दिखता है।
5. अभाज्य और अनिवार्य अन्तर्भावक
जिस समूह को और बड़ा नहीं किया जा सकता, उसे अभाज्य अन्तर्भावकअभाज्य अन्तर्भावकमानचित्र पर ऐसा समूह जिसे और बड़ा नहीं किया जा सकता।पूरी प्रविष्टि पढ़ें (प्राइम इम्प्लिकेंट) कहते हैं। अभाज्य अन्तर्भावकों को सूचीबद्ध करना समस्या का आसान आधा हिस्सा है; उनमें से किन्हें रखना है यह चुनना वह आधा है जो गड़बड़ाता है।
यदि किसी कोष्ठ को केवल एक ही अभाज्य अन्तर्भावक ढकता है, तो वह अन्तर्भावक अनिवार्य है: कोई भी न्यूनतम रूप उसे छोड़ नहीं सकता, क्योंकि उस कोष्ठ को और कुछ ढकता ही नहीं। पहले अनिवार्य अन्तर्भावकअनिवार्य अभाज्य अन्तर्भावककिसी विशेष 1 को ढकने वाला एकमात्र अभाज्य अन्तर्भावक।पूरी प्रविष्टि पढ़ें लीजिए, फिर बचा हुआ हिस्सा शेष समूहों में से जितने कम से कम हो सकें उतनों से ढकिए।
लालची तरीका - हर बार सबसे बड़ा उपलब्ध समूह उठा लेना - लुभावना है और हमेशा काम नहीं करता। चक्रीय सारणी पर, जहाँ कोई भी अन्तर्भावक अनिवार्य नहीं होता और हर कोष्ठ दो बार ढका जाता है, लालची चुनाव सर्वोत्तम उत्तर से एक पद लंबा निकल सकता है। इस साइट का मानचित्र इसके बजाय बचे हुए सभी विकल्प खंगालता है, जो छह चरों पर कुछ भी महँगा नहीं पड़ता।
6. इसके बजाय शून्य को समूहित करना
ऊपर कही हर बात शून्यों पर भी उतनी ही लागू होती है। उन्हें उन्हीं आयतों से ढकिए, हर समूह को निषेधित पदार्थों के साथ पढ़िए - जो चर पूरे समूह में 1 है वह निषेध के साथ आता है और जो 0 है वह ज्यों का त्यों - और समूहों को ∨ के बजाय ∧ से जोड़िए।
परिणाम है योगों का गुणनफलसंयोजी प्रसामान्य रूपOR का AND: उपवाक्यों का संयोजन।पूरी प्रविष्टि पढ़ें: वियोजनों का एक संयोजनसंयोजनतभी सत्य जब दोनों भाग सत्य हों: p ∧ q।पूरी प्रविष्टि पढ़ें जो ठीक उन्हीं कोष्ठों में असत्य है जिनमें अभिव्यक्ति असत्य है, और इसलिए बाकी सब जगह सत्य। दोनों में से कौन-सा रूप छोटा होगा यह फलन पर निर्भर है - कम एक वाली सूत्र का गुणनफलों का योग छोटा होता है और कम शून्य वाली का योगों का गुणनफल - इसलिए चुनने से पहले मानचित्र से दोनों पढ़ लेना उपयोगी है।
सत्य तालिका से अभिव्यक्तिकिसी भी सत्य तालिका को तार्किक अभिव्यक्ति में बदलें। अपनी कस्टम सत्य तालिका से डिसजंक्टिव नॉर्मल फॉर्म (DNF) या कंजंक्टिव नॉर्मल फॉर्म (CNF) में बूलियन सूत्र उत्पन्न करें।7. बड़े मानचित्र और परवाह-रहित कोष्ठ
पाँच और छह चरों को चार-चर वाले दो या चार मानचित्रों को एक के ऊपर एक रखकर खींचा जा सकता है, जहाँ पड़ोसी परतों में एक ही स्थान के कोष्ठ सटे हुए माने जाते हैं। यह चलता तो है, पर जिस सटावट ने विधि को दृश्य बनाया था वह अब देखने की नहीं, याद रखने की चीज़ बन जाती है। उससे आगे, क्वाइन-मैक्क्लस्की एल्गोरिद्म वही काम सारणी के रूप में करता है: वह ठीक इसी समूहन का यांत्रिक रूप है, और यहाँ के मानचित्रों के पीछे भी वही चलता है।
हार्डवेयर डिज़ाइन एक और विचार जोड़ता है। कुछ निवेश-संयोजन कभी आते ही नहीं - द्विआधारी कोडित दशमलव अंक कभी 1010 नहीं होता - इसलिए डिज़ाइनर को परवाह नहीं कि परिपथ उनके साथ क्या करे। ऐसे कोष्ठों पर X अंकित होता है और उन्हें किसी भी मान से पढ़ा जा सकता है, जो भी समूहों को बड़ा बनाए। इस कैलकुलेटर के मानचित्र एक सूत्र से बनते हैं, जो हर नियतन को कोई न कोई मान देता है, इसलिए यहाँ कोई कोष्ठ परवाह-रहित नहीं होता।
8. स्वयं आज़माइए
कैलकुलेटर में दो से छह चरों वाली कोई अभिव्यक्ति लिखिए और उसका मानचित्र सत्य सारणी के नीचे खिंच जाएगा, जिसमें हर समूह अपने रंग में घिरा होगा और न्यूनतम रूप नीचे लिखा होगा। शून्यों को समूहित देखने के लिए योगों के गुणनफल पर स्विच कीजिए।
कर्नो मानचित्र सॉल्वरदो से छह चरों वाले किसी भी व्यंजक का मानचित्र बनाइए, जिसमें हर समूह घेरा हो और न्यूनतम गुणनफलों का योग या योगों का गुणनफल उसी से पढ़ा गया हो।