Tabular minimization और prime implicant covers
दो अलग समस्याएँ
हर उपयोगी group खोजना और function बनाने के लिए जरूरी groups चुनना अलग काम हैं। Quine–McCluskey tabular method पहले prime implicants बनाता है, फिर required one-rows का cover चुनता है। यहाँ two-level SOP में पहले product terms और फिर total literals कम करते हैं। यह cost model हर technology में minimum delay या transistor count की गारंटी नहीं।
पूर्वज्ञान: minterms, Boolean SOP, Gray-map groups और don’t-cares। Variable क्रम A,B,C,D है; index में A सबसे महत्वपूर्ण bit है। 0-01 जैसे cube का dash बताता है कि उस input का कोई भी मान हो सकता है; वह minus sign नहीं। यह cube A′C′D है और rows 1,5 cover करता है।
Implicant केवल required ones या allowed don’t-cares cover करता है, required zero नहीं। Prime implicant से एक और literal हटाकर उसे बड़ा नहीं कर सकते, यदि यह शर्त बनाए रखनी हो। Essential prime कम-से-कम एक ऐसी required one cover करता है जिसे कोई दूसरा prime cover नहीं करता। Prime का अर्थ essential नहीं; कई primes optional हैं।
Combination का नियम
On-set minterms और घोषित don’t-cares को 1 bits की संख्या से groups में रखें। दो cubes तभी combine करें जब dash positions समान हों और बाकी fixed bits में ठीक एक अंतर हो। उस position पर dash लगाएँ। जैसे 0010 और 0110 से 0-10; फिर 0-10 और 1-10 से --10। लेकिन 0-10 और -010 combine नहीं होंगे: dash positions अलग हैं।
Combine हुए हर cube को mark करें। Duplicate नए cubes हटाएँ लेकिन covered rows रखें। जब तक combination संभव हो, जारी रखें। किसी भी level पर uncombined cube prime है। केवल अंतिम level रखना गलत है; पहले न combine हुए छोटे primes छूट जाएँगे।
चार-variable उदाहरण
F=Σm(0,1,2,5,6,7,8,9,10,14) लें, कोई don’t-care नहीं। One-count से binary minterms:
| Ones | Minterms |
|---|---|
| 0 | 0000 |
| 1 | 0001, 0010, 1000 |
| 2 | 0101, 0110, 1001, 1010 |
| 3 | 0111, 1110 |
पहले round के अलग pairs हैं 000-,00-0,-000,0-01,-001,0-10,-010,100-,10-0,01-1,011-,-110,1-10। हर एक दो specified ones cover करता है; source pair से हटे fixed bit को जाँचें।
दूसरे round में -00-,-0-0,--10 मिलते हैं। जैसे 000- और 100- से -00-, तथा 0-10 और 1-10 से --10। अलग रास्तों से एक ही cube मिले तो duplicates मिलाएँ। इन final cubes के dash positions और fixed-bit differences अगले combination की शर्त पूरी नहीं करते, इसलिए तीसरा round नहीं।
पहले round के uncombined 0-01,01-1,011- भी primes हैं। सभी छह primes:
| नाम | Cube | Product | Required rows |
|---|---|---|---|
| P | -00- | B′C′ | 0,1,8,9 |
| Q | -0-0 | B′D′ | 0,2,8,10 |
| R | --10 | CD′ | 2,6,10,14 |
| S | 0-01 | A′C′D | 1,5 |
| T | 01-1 | A′BD | 5,7 |
| U | 011- | A′BC | 6,7 |
Coverage chart में एक axis पर required rows, दूसरी पर primes और membership के marks होते हैं। ऊपर की table वही जानकारी compact sets में देती है।
Essentials चुनकर cover पूरा करें
Row 9 केवल P cover करता है, इसलिए P essential है। Row 14 केवल R, इसलिए R essential है। P और R का union {0,1,2,6,8,9,10,14} है। Rows 5,7 बचती हैं। T दोनों cover करता है; S तथा U लेने पर दो अतिरिक्त terms चाहिए। अतः minimum cover P+R+T=B′C′+CD′+A′BD।
यह cost model में optimal क्यों है? Unique rows से P और R जरूरी हैं। दोनों row 5 नहीं cover करते, इसलिए कम-से-कम एक और term चाहिए। T वह term देता है और row 7 भी cover करता है। इसलिए तीन terms आवश्यक और पर्याप्त; literals 2+2+3=7 हैं। Union ठीक on-set है या नहीं, जाँचें। Q जैसा prime valid होकर भी minimum cover में अनावश्यक हो सकता है।
जब कोई essential न मिले
H(A,B,C)=Σm(0,1,2,5,6,7) में सभी primes pairs हैं: P1=00-,P2=0-0,P3=11-,P4=1-1,P5=-01,P6=-10। हर required row दो primes में है, इसलिए कोई essential नहीं। इसका अर्थ minimization असंभव नहीं।
Selection variables P1…P6 लें, जिनका अर्थ संबंधित prime चुनना है। हर row के available primes का OR और सभी row requirements का AND लें:
(P1+P2)(P1+P5)(P2+P6)(P4+P5)(P3+P6)(P3+P4).
यह selection decisions का Boolean expression है, मूल input variables का नहीं। X·X=X और X+XY=X से expand/simplify करें या छोटे candidate subsets enumerate करें। सबसे छोटे solutions {P1,P4,P6} और {P2,P3,P5} हैं। हर solution में तीन दो-literal terms हैं। दो pairs अधिकतम चार अलग rows cover करते हैं; छह rows के लिए कम-से-कम तीन terms चाहिए। कई equally minimal covers मान्य हो सकते हैं। ऐसा systematic cover expression अक्सर Petrick's method कहलाता है।
Don't-cares और जाँच की सीमाएँ
Don't-cares बड़े primes बनाने में मदद कर सकते हैं, लेकिन chart में mandatory columns केवल required ones की हैं। केवल don’t-cares cover करने वाला prime चुनना जरूरी नहीं। जैसे तीन variables में on-set {1,3} और don’t-cares {5,7} से --1 यानी C मिलता है। सभी required ones cover हैं और कोई required zero नहीं। Row 7 required zero होती तो यह cube गलत होता।
पूरी तरह all-zero function में F=0 लें; one-row cover नहीं चाहिए। All-one function में all-dash cube से F=1। Variable क्रम स्थिर रखें और dash cube को एक खास assignment न मानें। Minimization के बाद सभी specified rows जाँचें। Tabular method इस two-level समस्या के लिए exact है, लेकिन cubes/cover candidates बहुत हो सकते हैं; छोटा उदाहरण arbitrary inputs पर efficient scaling सिद्ध नहीं करता।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. कौन-सी cube जोड़ी एक tabular step में combine हो सकती है?
A. 0-10 और -010 B. 0010 और 0110 C. 0000 और 0011 D. 00-0 और 0-00
उत्तर: B
A गलत है: dash positions अलग हैं।
B सही है: केवल B बदलता है, इसलिए 0-10।
C गलत है: दो fixed bits बदलते हैं।
D गलत है: dash positions अलग हैं।
C02. Prime implicant essential कब है?
A. सभी primes में उसके literals सबसे कम हों। B. वह अंतिम combination round में आए। C. वह ऐसी required one-row cover करे जिसे कोई दूसरा prime न करे। D. वह कोई भी don’t-care cover करे।
उत्तर: C
A गलत है: आकार से unique coverage सिद्ध नहीं।
B गलत है: पहले rounds के primes भी essential हो सकते हैं।
C सही है: unique required row के कारण उसे हर prime cover में चुनना होगा।
D गलत है: don’t-care rows cover करना जरूरी नहीं।
C03. चार-variable chart में row 9 केवल P और 14 केवल R से cover है। P,R के बाद बची rows 5,7 दोनों T cover करता है। न्यूनतम terms कितनी हैं?
A. 3 B. 2 C. 6 D. 1
उत्तर: A
A सही है: P,R जरूरी हैं और T तीसरी आवश्यक/पर्याप्त term है।
B गलत है: P,R के बाद required rows बचती हैं।
C गलत है: सभी छह primes चुनना जरूरी नहीं।
D गलत है: दो अलग forced primes पहले से हैं।
C04. पहले rounds के uncombined cubes क्यों रखने चाहिए?
A. वे हमेशा forbidden zeros हैं। B. वे सभी redundant duplicates हैं। C. उन्हें final cover में सभी चुनना है। D. दूसरे cubes आगे combine हों तब भी वे prime implicants हैं।
उत्तर: D
A गलत है: valid cubes required zeros नहीं लेते।
B गलत है: uncombined cube अलग जरूरी prime हो सकता है।
C गलत है: primes बनाना और cover चुनना अलग काम हैं।
D सही है: बड़ा न कर सकना prime की शर्त है।
C05. Incompletely specified function के prime chart में किन rows को cover करना अनिवार्य है?
A. केवल हर don’t-care B. हर required one-row C. हर required zero-row D. हर binary row
उत्तर: B
A गलत है: don’t-cares grouping में मदद कर सकते हैं, cover जरूरी नहीं।
B सही है: SOP में सभी required ones और कोई required zero नहीं।
C गलत है: SOP में required zero cover करने से function गलत होगा।
D गलत है: required zeros को zero ही रखना है।
C06. छह required rows के primes केवल दो-cell pairs हैं; बड़ा implicant नहीं। तीन primes का valid cover मिलता है। न्यूनतम terms कितनी हैं?
A. 2 B. 6 C. 3 D. दिया cover होने पर भी तय नहीं कर सकते
उत्तर: C
A गलत है: दो pairs अधिकतम चार अलग rows cover करते हैं।
B गलत है: तीन terms का valid cover पहले से है।
C सही है: कम-से-कम ceiling(6/2)=3 चाहिए और तीन-term cover उपलब्ध है।
D गलत है: lower bound और matching construction न्यूनतम सिद्ध करते हैं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन