Karnaugh maps और canonical Boolean रूप
Truth table को नए क्रम में क्यों रखें
Truth table हर input पर function का मान बताती है। Karnaugh map उन्हीं rows को ऐसे क्रम में रखता है कि एक-bit का अंतर साफ दिखे और product terms मिल सकें। यहाँ आदर्श, steady-state Boolean logic है: + का अर्थ OR, साथ लिखने का अर्थ AND और prime का अर्थ NOT है। Variables का क्रम A,B,C या A,B,C,D है; हर numerical row index में A सबसे महत्वपूर्ण bit है।
पूर्वज्ञान: Boolean identities, minterms और binary indexing। लक्ष्य: on-set और off-set notation समझना, सही map groups बनाना, हटने वाले literals का कारण बताना और छोटे सरलीकरण को जाँचना। इस पाठ में तीन-variable maps और चार-variable wraparound उदाहरण हैं; tabular minimization, hazards हटाना और सामान्य minimum-cost circuit synthesis नहीं।
Minterms ones और maxterms zeros बताते हैं
Minterm m_i केवल row i पर 1 होता है। Row 101 के लिए m_5=AB′C। जिस variable का row bit 0 हो उसका complement लें और सभी variables का AND करें। F=Σm(0,2,3,6,7) का अर्थ ठीक उन्हीं rows पर F=1 और बाकी पर 0 है, जब तक don’t-cares अलग से न दिए हों। यहाँ Σ minterms का OR बताता है, row numbers का arithmetic योग नहीं।
Maxterm M_i केवल row i पर 0 होता है। Row 101 के लिए M_5=A′+B+C′ है: उस row पर हर literal 0 है, इसलिए उनका OR भी 0 है। Maxterm बनाते समय जिस variable का row bit 1 हो उसे complement करें। यह minterm की bit-to-literal convention के उलट है।
पूरी तरह तय तीन-variable function में ऊपर के on-set का off-set {1,4,5} है। इसलिए F=ΠM(1,4,5)=(A+B+C′)(A′+B+C)(A′+B+C′)। Π maxterms का AND है। हर off-set row एक factor को zero करती है; on-set row पर सभी factors एक हैं। Canonical SOP और canonical POS एक ही function दर्शाते हैं, लेकिन उनमें लिखी terms की संख्या समान होना आवश्यक नहीं।
तीन-variable map बनाएँ
Rows A=0,1 और columns BC को Gray क्रम 00,01,11,10 में रखें। पास के labels में ठीक एक bit बदलता है। सामान्य binary क्रम 00,01,10,11 के बीच वाले columns में यह गुण नहीं है और उससे गलत grouping हो सकती है। पहला और अंतिम column भी adjacent हैं, क्योंकि 00 तथा 10 में केवल B बदलता है।
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | m_0 | m_1 | m_3 | m_2 |
| 1 | m_4 | m_5 | m_7 | m_6 |
हर output को उसके index वाले cell में रखें; truth-table output list को सीधे बाएँ से दाएँ copy न करें। F=Σm(0,2,3,6,7) के लिए:
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
सही groups और variables हटने का कारण
SOP के लिए 1 वाले cells के groups बनाएँ; घोषित don’t-cares चाहें तो इस्तेमाल कर सकते हैं। Group ऐसा आयत है जिसकी हर side की लंबाई दो की घात हो; उसमें 1,2,4,8,… cells होते हैं। Group किनारे के पार wrap हो सकता है, लेकिन किसी तय 0 को शामिल नहीं कर सकता। केवल diagonal छूना adjacency नहीं है। Groups overlap कर सकते हैं और हर जरूरी 1 cover होना चाहिए। कोई बड़ा उपयोगी group न मिले तो single-cell group भी मान्य है।
Group में constant variable रखें: मान 1 हो तो सामान्य और 0 हो तो complemented रूप में। दोनों मान लेने वाला variable हटा दें। उदाहरण: m_0+m_2=A′B′C′+A′BC′=A′C′(B′+B)=A′C′। दोनों cells में केवल B बदलता है, इसलिए B हटता है। n-variable map में 2^k cells का सही group k literals हटाता है।
Map इस reduction को व्यवस्थित बनाता है, मनमाने literals मिटाने की अनुमति नहीं देता। तीन cells का group एक product term नहीं है। बड़ा group अधिक literals हटाता है, लेकिन पूरी coverage जाँचे बिना केवल बड़े groups चुनना global optimum का प्रमाण नहीं।
हल किया उदाहरण 1 में किनारे के पार जोड़ी
F के map में {2,3,6,7} group लें। ये दोनों rows के सबसे दाएँ दो columns हैं। A और C बदलते हैं, B=1 स्थिर है, इसलिए term B है।
Cell 0 अभी cover नहीं हुआ। Top row में बाएँ-दाएँ किनारे के पार {0,2} pair लें। A=0 और C=0 स्थिर हैं, B बदलता है, इसलिए A′C′ मिलता है। अतः F=B+A′C′। Cell 2 पर overlap मान्य है; OR में कोई term दो बार आने से मान नहीं बदलता।
दोनों दिशाओं से जाँचें: B ठीक 2,3,6,7 rows cover करता है; A′C′ ठीक 0,2 cover करता है। उनका union दिया on-set है; कोई अतिरिक्त zero row नहीं जुड़ी। जिस two-level SOP cost model में पहले product terms और फिर literals कम करते हैं, उसमें यह cover न्यूनतम है: cell 0, ones में केवल cell 2 से जुड़ सकता है, इसलिए prime term A′C′ चाहिए। बाकी ones के लिए दूसरी term चाहिए और B एक literal से सभी cover करता है। कुल दो terms और तीन literals हैं। यह प्रमाण इसी function और cost model के लिए है।
हल किया उदाहरण 2 में zeros से POS
इसी F के zeros {1,5} मिलाएँ: B=0 और C=1 स्थिर हैं। पूरे group पर zero होने वाला sum term B+C′ है। Zeros {4,5} में A=1 और B=0 स्थिर हैं, इसलिए A′+B मिलता है। Simplified POS (B+C′)(A′+B) है। Boolean identity (X+Y)(X+Z)=X+YZ से यह B+A′C′ के बराबर है।
Zero grouping में constant 0 वाला variable सामान्य और constant 1 वाला complemented रूप में sum term में आता है। यह उलट नियम जरूरी है, क्योंकि चुने group पर sum term zero होना चाहिए। Zero groups को one-group वाले literal नियम से न पढ़ें।
Don't-cares अनुमति हैं, अनिवार्यता नहीं
X वाला don’t-care cell कहता है कि specification उस input पर कोई भी output स्वीकार करती है। यह electrical unknown नहीं है जिसे propagate करना ही हो; न ही यह मनचाही row अनदेखी करने की अनुमति है। SOP में उपयोगी group बढ़ाने के लिए X को 1 की तरह लें या इस्तेमाल न करें। हर X को cover करना जरूरी नहीं।
हल किया उदाहरण 3: required ones {1,3}, don’t-cares {5,7} और required zeros {0,2,4,6} हैं। चार cells {1,3,5,7} से F=C मिलता है। Required ones पर C=1 और required zeros पर C=0 है। Implementation दोनों X rows पर भी 1 देती है, जो मान्य है। यदि 5 या 7 में से कोई required zero होता, तो यह grouping गलत होती। Required assignments जाँचें और don’t-cares पर किए choices भी लिखें।
चार-variable corners और जाँच की विधि
चार variables के लिए दोनों axes पर Gray क्रम 00,01,11,10 लें: rows AB और columns CD। चार corner cells 0,2,8,10 हैं। वे एक सही wrapped rectangle बनाते हैं: A और C बदलते हैं, जबकि B=0,D=0 स्थिर हैं; इसलिए term B′D′ है। वे चार अलग-थलग cells नहीं। जैसे बायाँ-दायाँ किनारा adjacent है, वैसे ही ऊपर-नीचे का किनारा भी है।
मुख्य बातें: variable क्रम लिखें; index से cells भरें; on-set, off-set और don’t-cares अलग रखें; हर group के cells बताएँ; constant literals निकालें और सभी required rows पर expression जाँचें। Diagonal grouping न करें, SOP group में required zero न लें, groups को disjoint होना जरूरी न मानें और equivalence को hardware optimum के प्रमाण से न मिलाएँ।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. Variable क्रम A,B,C में कौन-सा maxterm केवल row 101 पर zero है?
A. AB′C B. A+B′+C C. A′+B+C′ D. A′BC′
उत्तर: C
A गलत है: यह minterm m_5 है, जो केवल 101 पर एक है, zero नहीं।
B गलत है: यह sum 010 पर zero है, 101 पर नहीं।
C सही है: 101 पर A′,B,C′ सभी zero हैं; हर दूसरी row कम-से-कम एक literal को एक करती है।
D गलत है: यह product term है, maxterm नहीं।
C02. किस BC column क्रम में हर पड़ोसी जोड़ी, पहले-अंतिम सहित, एक bit में अलग है?
A. 00,01,10,11 B. 00,01,11,10 C. 00,11,01,10 D. 01,10,00,11
उत्तर: B
A गलत है: 01 से 10 में दोनों bits बदलते हैं।
B सही है: पड़ोसी labels और wraparound जोड़ी में ठीक एक bit बदलता है।
C गलत है: 00 से 11 में दोनों bits बदलते हैं।
D गलत है: 01 से 10 में दोनों bits बदलते हैं।
C03. तीन-variable map में cells {0,2} की जोड़ी का product term क्या है?
A. A′C′ B. A′B′ C. B′C′ D. AC′
उत्तर: A
A सही है: rows 000 और 010 में A=0,C=0 स्थिर हैं और B बदलता है।
B गलत है: B स्थिर नहीं; A′B′ rows 0 और 1 cover करता है।
C गलत है: B स्थिर नहीं और A स्थिर है; B′C′ rows 0 और 4 cover करता है।
D गलत है: दोनों cells में A=0 है, इसलिए A′ चाहिए।
C04. बाकी सभी rows zero होने पर F(A,B,C)=Σm(0,2,3,6,7) के बराबर कौन-सा expression है?
A. B+C′ B. A′+B C. B+AC′ D. B+A′C′
उत्तर: D
A गलत है: यह row 4=100 भी लेता है, जहाँ C′=1 लेकिन F=0 है।
B गलत है: यह row 1=001 भी लेता है, जहाँ A′=1 लेकिन F=0 है।
C गलत है: row 0 छूटती है और row 4 गलत जुड़ती है।
D सही है: B से 2,3,6,7 और A′C′ से 0,2 मिलते हैं; union ठीक दिया set है।
C05. Required ones {1,3}, don’t-cares {5,7} और required zeros {0,2,4,6} हैं। सही कथन कौन-सा है?
A. हर don’t-care को zero बनाना जरूरी है। B. कुछ rows don’t-cares हैं इसलिए F=1 मान्य है। C. F=C मान्य है क्योंकि हर required row सही है। D. Row 3 cover होने से F=B मान्य है।
उत्तर: C
A गलत है: don’t-cares पर कोई भी output मान्य है; zero जरूरी नहीं।
B गलत है: constant 1 सभी required zero rows का उल्लंघन करता है।
C सही है: C required rows 1,3 पर 1 और 0,2,4,6 पर 0 है; 5,7 के choices मान्य हैं।
D गलत है: B required row 1 छोड़ता है और required-zero rows 2,6 जोड़ता है।
C06. Gray-ordered AB rows और CD columns वाले चार-variable map में चार corners {0,2,8,10} को ठीक कौन-सी term cover करती है?
A. A′C′ B. B′D′ C. BD D. A′B′C′D′
उत्तर: B
A गलत है: corners में A और C बदलते हैं, fixed zero नहीं हैं।
B सही है: B=0,D=0 स्थिर हैं और A तथा C दोनों मान लेते हैं।
C गलत है: B और D दोनों zero हैं, इसलिए complements चाहिए।
D गलत है: यह minterm केवल cell 0 cover करता है, चारों corners नहीं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन