बूलीय बीजगणित, न्यूनीकरण व संयोजी परिपथ

बूलीय बीजगणित छोटा बीजगणित है — दो अवयव, तीन संक्रियाएँ — और उसका सम्पूर्ण रूप कुछ ही अभिगृहीतों से व्युत्पन्न हो सकता है, अतः कंठस्थ करने योग्य अत्यल्प है और प्रवाह पाने योग्य बहुत। परीक्षा में दो सर्वसमिकाएँ अधिकांश काम करती हैं। डी मॉर्गन के नियम पूरकित गुणनफल को पूरकों के योग में बदलते हैं और विपरीत भी, और इसी से कोई व्यंजक केवल-NAND या केवल-NOR रूप में ढकेला जाता है; तथा सहमति व अवशोषण सर्वसमिकाएँ वे हैं जो आपको मानचित्र बनाए बिना कोई पद काटने देती हैं। बीजगणित से आगे खंड न्यूनीकरण पूछता है, और डिजिटल लॉजिक में यही एक स्थान है जिसका अपना प्रश्न-आकार है: इस फलन के कितने अभाज्य अन्तर्निहित हैं, और उनमें कितने अनिवार्य हैं? वे दो भिन्न संख्याएँ हैं, और उनके बीच का अंतर ही सम्पूर्ण अभिप्राय है। अभाज्य अन्तर्निहित वह गुणनफल-पद है जिसे फलन को अन्तर्निहित करते हुए और बड़ा नहीं किया जा सकता — कर्णॉ मानचित्र पर प्रत्येक वह समूह जिसे दुगुना नहीं किया जा सकता। अनिवार्य अभाज्य अन्तर्निहित वह है जो ऐसा लघुपद ढकता है जिसे कोई अन्य अभाज्य अन्तर्निहित नहीं ढकता, अतः उसे प्रत्येक न्यूनतम व्यंजक में आना ही होगा। कोई फलन अभाज्य अन्तर्निहितों में समृद्ध हो सकता है और उसमें अनिवार्य लगभग न हों, ठीक वही स्थिति नीचे हल की गई है। तत्पश्चात् संयोजी आधा यह सब लागू करता है: योजक, बहुसंकेतक व विकोडक मानक खंड हैं, और साथ रखने योग्य उपयोगी तथ्य यह है कि 2^n-से-1 बहुसंकेतक n + 1 चरों के किसी भी फलन को साकार कर सकता है, जो बहुत से कार्यान्वयन प्रश्नों को गणना-अभ्यास बना देता है।

वे सर्वसमिकाएँ जो अपना मूल्य चुकाती हैं

कंठस्थ रखने योग्य सर्वसमिकाएँ, तथा प्रत्येक किस हेतु
सर्वसमिकाकथनकिस हेतु प्रयुक्त
डी मॉर्गन(A·B)' = A' + B' तथा (A + B)' = A'·B'केवल-NAND या केवल-NOR रूप में रूपांतरण
अवशोषणA + A·B = A तथा A·(A + B) = Aउस पद को हटाना जिसे मानचित्र अनावश्यक दिखाता
सहमतिA·B + A'·C + B·C = A·B + A'·Cअनावश्यक मध्य पद बीजगणितीय रूप से हटाना
योग पर वितरणA + B·C = (A + B)·(A + C)SOP व POS रूपों के बीच जाना
गुणनफलों के योग का पूरकf' उन लघुपदों का योग है जो f में नहींबीजगणित बिना SOP से POS पाना
🧠 NAND व NOR प्रत्येक स्वयं में पर्याप्त हैं
दोनों द्वार क्रियात्मक रूप से पूर्ण हैं: NOT वह NAND है जिसके निवेश जुड़े हों, AND वह NAND है जिसके पश्चात् वही NOT हो, OR डी मॉर्गन से निकलता है, और शेष सब उन्हीं से बनता है। इसीलिए वास्तविक हार्डवेयर अधिकांशतः NAND है — एक कोशिका-प्रकार, एक मास्क। तथ्य का परीक्षणीय रूप गणना-प्रश्न है, और याद रखने योग्य संख्या यह है कि XOR को चार 2-निवेशी NAND द्वार चाहिए, तीन नहीं और पाँच नहीं। तत्पश्चात् अर्ध योजक योग हेतु XOR व वहन हेतु AND है; पूर्ण योजक दो अर्ध योजक व एक OR है, और यहीं से मानक "कितने द्वार" प्रश्न आरंभ होते हैं।

अभाज्य अन्तर्निहित, तथा उनमें कौन अनिवार्य

f(A,B,C,D) = Σm(0,1,2,3,5,7,8,10,14,15) लें। उसका कर्णॉ मानचित्र कई प्रकार से समूह बनाता है, और प्रश्न जो गणनाएँ पूछता है वे ये हैं: उसके छह अभाज्य अन्तर्निहित हैं और केवल दो अनिवार्य। छह हैं A′B′, A′D, B′D′, ABC, ACD′ तथा BCD। दो अनिवार्य हैं A′D, लघुपद 5 का एकमात्र आवरण, तथा B′D′, लघुपद 8 का एकमात्र आवरण।

छह अभाज्य अन्तर्निहित, तथा केवल दो अनिवार्य क्यों
अभाज्य अन्तर्निहितजो लघुपद ढकता हैअनिवार्य?
A′D1, 3, 5, 7हाँ — 5 का एकमात्र आवरण
B′D′0, 2, 8, 10हाँ — 8 का एकमात्र आवरण
A′B′0, 1, 2, 3नहीं — प्रत्येक लघुपद अन्यत्र भी ढका
ABC14, 15नहीं — 14, ACD′ में; 15, BCD में
ACD′10, 14नहीं
BCD7, 15नहीं
🎯 दोनों गणनाएँ क्यों अलग हो जाती हैं
अभाज्य अन्तर्निहित एक समूह के विषय में स्थानीय तथ्य है — उसे दुगुना नहीं किया जा सकता। अनिवार्यता सम्पूर्ण फलन के विषय में वैश्विक तथ्य है — किसी लघुपद का अन्य कोई घर नहीं। अतः जिस फलन के लघुपदों तक कई मार्गों से पहुँचा जा सकता है उसके अभाज्य अन्तर्निहित अनेक व अनिवार्य अल्प होते हैं, और यहाँ वही होता है: केवल लघुपद 5 व 8 ठीक एक-एक समूह में हैं, अतः केवल दो अभाज्य अन्तर्निहित बाध्य हैं। शेष सब चुनाव है। यहाँ न्यूनतम व्यंजक संयोगवश अद्वितीय है — A′D + ABC + B′D′, तीन पद व सात शब्दांश — परंतु अद्वितीयता गणनाओं से सुनिश्चित नहीं होती, और "कितने न्यूनतम व्यंजक हैं" पूछता प्रश्न पुनः भिन्न प्रश्न है। कुछ भी गिनने से पूर्व पढ़ें कि तीनों में कौन पूछा जा रहा है।
⚠️ अनपेक्षित का प्रयोग किया जा सकता है, करना आवश्यक नहीं
अनपेक्षित प्रविष्टि अनुमति है, बाध्यता नहीं: जब वह समूह को बड़ा करे तब सम्मिलित करें, जब न करे तब छोड़ दें। वही असमता है जहाँ अंक जाते हैं। अनपेक्षितों सहित अभाज्य अन्तर्निहित गिनना उनके बिना गिनने से भिन्न संख्या देता है, क्योंकि अनपेक्षित किसी समूह को बड़ा कर सकता है और इस प्रकार किसी छोटे समूह की अभाज्यता नष्ट कर सकता है। तथा अनपेक्षित स्वयं कभी अनिवार्य अभाज्य अन्तर्निहित नहीं बनाता — अनिवार्यता किसी 1 को ढकने के विषय में है, अतः जो समूह केवल अनपेक्षित ढकता है वह, कितना ही बड़ा हो, आवश्यक ही नहीं।

योजक, बहुसंकेतक व विकोडक

अर्ध योजक योग = A ⊕ B व वहन = A·B देता है। पूर्ण योजक एक वहन-निवेश जोड़ता है और दो अर्ध योजकों तथा एक OR के बराबर है। n पूर्ण योजकों को श्रृंखलित करने पर वहन-तरंग योजक मिलता है, जिसका विलंब समस्या है: वहन को प्रत्येक चरण से प्रसरित होना है, अतः निकृष्टतम विलंब n के अनुपाती है — और वहन-अग्रदृष्टि इसी को सुधारने हेतु है, द्वारों की कीमत पर।

🧠 2^n-से-1 बहुसंकेतक n + 1 चरों का कोई भी फलन साकार करता है
n चयन-रेखाओं को n चरों से चालित करें। तब 2^n आँकड़ा-निवेशों में प्रत्येक उन चरों के एक संयोजन से संगत होता है, और शेष एक चर का अवशिष्ट फलन सदा 0, 1, वह चर, या उसका पूरक होता है — और चारों निःशुल्क उपलब्ध हैं। अतः 8-से-1 MUX (तीन चयन) चार चरों का कोई भी फलन कार्यान्वित करता है, और 4-से-1 तीन चरों का। सर्वाधिक सामान्य त्रुटि सुरक्षित दिशा में एक की चूक है: यह मानना कि 8-से-1 केवल तीन चर सँभालता है, और अनावश्यक 16-से-1 की ओर बढ़ना। विकोडक वही विचार उलटा है — n-से-2^n विकोडक प्रत्येक लघुपद उत्पन्न करता है, अतः विकोडक व एक OR द्वार कोई एक फलन कार्यान्वित करते हैं, और विकोडक व कई OR द्वार समान निवेशों के कई फलन एक साथ।

मुख्य बिंदु

  • डी मॉर्गन केवल-NAND व केवल-NOR रूपों का सेतु है; दोनों द्वार स्वयं में क्रियात्मक रूप से पूर्ण हैं।
  • XOR चार 2-निवेशी NAND द्वार लेता है; पूर्ण योजक दो अर्ध योजक व एक OR है।
  • अभाज्य अन्तर्निहित वह समूह है जिसे दुगुना नहीं किया जा सकता — एक समूह के विषय में स्थानीय तथ्य।
  • अनिवार्य अभाज्य अन्तर्निहित किसी लघुपद का एकमात्र आवरण है — फलन के विषय में वैश्विक तथ्य।
  • दोनों गणनाएँ स्वतंत्र रूप से भिन्न हैं: Σm(0,1,2,3,5,7,8,10,14,15) के छह अभाज्य अन्तर्निहित व दो अनिवार्य हैं।
  • अनपेक्षित अनुमति है, बाध्यता नहीं, और वह कभी किसी अभाज्य अन्तर्निहित को अनिवार्य नहीं बनाता।
  • 2^n-से-1 बहुसंकेतक n + 1 चरों का कोई भी फलन साकार करता है — 8-से-1 चार ढकता है।
  • वहन-तरंग योजक का विलंब शब्द-लंबाई के साथ बढ़ता है, और वहन-अग्रदृष्टि का कारण यही है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. f(A,B,C,D) = Σm(0,1,2,3,5,7,8,10,14,15) के कितने अभाज्य अन्तर्निहित हैं?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 6

    वे हैं A′B′, A′D, B′D′, ABC, ACD′ तथा BCD — छह। सावधानी योग्य बात यह है कि यह न्यूनतम व्यंजक के पदों की संख्या नहीं है, जो तीन है, न अनिवार्य अभाज्य अन्तर्निहितों की, जो दो है। छहों में प्रत्येक मानचित्र पर वह समूह है जिसे दुगुना नहीं किया जा सकता; वह आवश्यक है या नहीं यह पृथक् प्रश्न है जिसका उत्तर अनिवार्यता देती है। जो अभ्यर्थी 3 उत्तर देते हैं उन्होंने न्यूनतम आवरण ढूँढ़कर अपूछे प्रश्न का उत्तर दिया है, और यह अंक खोने का सर्वाधिक सामान्य तरीका यही है।

  2. उसी फलन f(A,B,C,D) = Σm(0,1,2,3,5,7,8,10,14,15) हेतु कितने अभाज्य अन्तर्निहित अनिवार्य हैं?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 2

    दो। A′D लघुपद 5 को ढकता एकमात्र अभाज्य अन्तर्निहित है, और B′D′ लघुपद 8 को ढकता एकमात्र, अतः दोनों को प्रत्येक न्यूनतम व्यंजक में आना ही होगा। प्रत्येक अन्य लघुपद हेतु कम-से-कम दो अभाज्य अन्तर्निहित उपलब्ध हैं, अतः शेष कुछ बाध्य नहीं — A′B′ अनावश्यक है क्योंकि 0, 1, 2 व 3 सभी A′D या B′D′ से ढक ही जाते हैं, और 14 व 15 को ABC ले सकता है या ACD′ व BCD की जोड़ी। विधि यांत्रिक है और इसी क्रम में करने योग्य: अभाज्य अन्तर्निहित सूचीबद्ध करें, फिर प्रत्येक लघुपद हेतु गिनें कि उसे कितने ढकते हैं, और जो ठीक एक बार ढके गए वे अनिवार्य अन्तर्निहितों के नाम बताते हैं।

  3. 2-निवेशी XOR कार्यान्वित करने हेतु आवश्यक 2-निवेशी NAND द्वारों की न्यूनतम संख्या है:

    1. 3
    2. 4
    3. 5
    4. 6
    उत्तर देखें

    उत्तर: B — 4

    चार। मानक रचना N1 = (A·B)′ लेती है, तत्पश्चात् N2 = (A·N1)′ व N3 = (B·N1)′, और अंततः N4 = (N2·N3)′, जो A ⊕ B के बराबर होता है। तीन लुभावना उत्तर है क्योंकि बीजगणितीय रूप से लिखने पर XOR तीन संक्रियाओं जैसा "लगता" है, और पाँच वह है जो A′B + AB′ के भोले अनुवाद से पहले NAND को साझा किए बिना मिलता है — साझा करना ही सम्पूर्ण बचत है। इस मार्ग से XNOR को पाँच चाहिए, क्योंकि वह XOR तथा एक प्रतिलोमकारी NAND है, और वह अंतर स्वयं परीक्षणीय है।

  4. बिना अतिरिक्त द्वार 8-से-1 बहुसंकेतक अधिकतम कितने चरों का कोई भी बूलीय फलन कार्यान्वित कर सकता है:

    1. 3 चर
    2. 4 चर
    3. 8 चर
    4. 2 चर
    उत्तर देखें

    उत्तर: B — 4 चर

    तीन चयन-रेखाएँ तीन चर लेती हैं। तत्पश्चात् प्रत्येक आँकड़ा-निवेश उन तीन के एक संयोजन को सँभालता है, और जो शेष रहता है वह अकेले चौथे चर का फलन है — जो केवल 0, 1, वह चर, या उसका पूरक हो सकता है, और चारों बिना द्वार उपलब्ध हैं। अतः 8-से-1 MUX चार चर ढकता है, और सामान्यतः 2^n-से-1 MUX, n + 1। विकल्प A उस MUX का उत्तर है जो शुद्ध चयनक के रूप में प्रयुक्त हो, अवशिष्ट-फलन चाल की अवहेलना करते हुए, और अनावश्यक 16-से-1 की ओर अभ्यर्थियों के बढ़ने का कारण यही है।

  5. न्यूनीकरण में अनपेक्षित शर्तों के विषय में निम्नलिखित में कौन कथन सही हैं? (एक से अधिक सही हो सकते हैं।)

    1. अनपेक्षित को समूह में सम्मिलित किया जा सकता है जब उससे वह बड़ा हो
    2. प्रत्येक अनपेक्षित किसी समूह से ढका जाना चाहिए
    3. अनपेक्षित सम्मिलित करने से फलन के अभाज्य अन्तर्निहितों की संख्या बदल सकती है
    4. केवल अनपेक्षित ढकता समूह भी अनिवार्य अभाज्य अन्तर्निहित हो सकता है
    उत्तर देखें

    उत्तर: A — अनपेक्षित को समूह में सम्मिलित किया जा सकता है जब उससे वह बड़ा हो; C — अनपेक्षित सम्मिलित करने से फलन के अभाज्य अन्तर्निहितों की संख्या बदल सकती है

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

  6. सहमति प्रमेय से A·B + A′·C + B·C सरल होकर बनता है:

    1. A·B + A′·C
    2. A′·C + B·C
    3. A·B + B·C
    4. इसे और सरल नहीं किया जा सकता
    उत्तर देखें

    उत्तर: A — A·B + A′·C

    अनावश्यक पद वह है जिसके शब्दांश अन्य दो की सहमति हैं — B·C, जो A·B के B तथा A′·C के C से बना है, विरोधी चर A हटाकर। वह कुछ नहीं जोड़ता: जहाँ भी B·C, 1 है, वहाँ या A, 1 है और A·B उसे ढकता है, या A, 0 है और A′·C ढकता है। अतः उत्तर A·B + A′·C है। विकल्प B व C ऐसा पद हटाते हैं जो वास्तविक काम कर रहा है, और मानचित्र यह तुरंत दिखा देता है — ठीक वही अतिरेक जिसे कर्णॉ मानचित्र दो अन्य के संघ में पूर्णतः समाहित समूह के रूप में उजागर करता है, इसीलिए बीजगणितीय व आलेखीय विधियाँ सहमत होती हैं।

  7. 4-बिट वहन-तरंग योजक ऐसे पूर्ण योजकों से बना है जिनमें प्रत्येक का प्रसरण विलंब 10 ns है। उसका निकृष्टतम विलंब लगभग है:

    1. 10 ns
    2. 20 ns
    3. 40 ns
    4. 2.5 ns
    उत्तर देखें

    उत्तर: C — 40 ns

    चरण 0 का वहन-निर्गम चरण 1 का निवेश है, और इसी प्रकार आगे, अतः निकृष्टतम स्थिति में सर्वाधिक न्यून बिट पर उत्पन्न वहन को चारों चरणों से तरंगित होना है: 4 × 10 = 40 ns। शब्द-लंबाई में यही रैखिक वृद्धि वहन-अग्रदृष्टि की सम्पूर्ण प्रेरणा है, जो वहनों को सीधे प्रचालकों से निकालती है और विलंब को O(n) से लगभग O(log n) कर देती है, अत्यधिक अधिक द्वारों की कीमत पर। विकल्प A एकल चरण का उत्तर है और वह अभ्यर्थी देता है जो "प्रसरण विलंब" को एक चरण के बजाय योजक का गुण पढ़ता है।

  8. 3-से-8 विकोडक अपने तीन निवेशों के सभी लघुपद उत्पन्न करता है। उन तीन चरों का कोई भी बूलीय फलन कार्यान्वित करने हेतु क्या जोड़ना होगा?

    1. फलन के लघुपदों पर एक ही OR द्वार
    2. फलन के लघुपदों पर एक AND द्वार
    3. दूसरा विकोडक
    4. कुछ नहीं — अकेला विकोडक ऐसा कोई भी फलन कार्यान्वित करता है
    उत्तर देखें

    उत्तर: A — फलन के लघुपदों पर एक ही OR द्वार

    गुणनफल-योग रूप में कोई भी फलन उन लघुपदों का OR है जहाँ वह 1 है, और विकोडक प्रत्येक लघुपद पहले ही पृथक् रेखा पर उत्पन्न कर चुका है — अतः सही रेखाओं पर एक OR द्वार उसे पूर्ण करता है। AND लघुपदों का गुणनफल निकालता, जो किसी भी दो भिन्न लघुपदों हेतु 0 है और अतः निरर्थक। ध्यान देने योग्य बचत यह है कि वही विकोडक समान तीन निवेशों के कई फलनों की एक साथ सेवा करता है, प्रत्येक हेतु एक OR द्वार, और इसीलिए विकोडक-सहित-OR छोटा बहु-निर्गम खंड बनाने का मानक तरीका है। विकल्प D भावना में लगभग सही और तथ्य में गलत है: विकोडक आपको पद देता है, योग नहीं।