Boolean algebra और शुरुआती सरलीकरण

मान्यताएँ और उद्देश्य

Boolean variables के मान 0 और 1 हैं। यहाँ + का अर्थ OR, साथ लिखने या · का अर्थ AND और prime का अर्थ complement है: A′ यानी NOT A। ये Boolean operators हैं, सामान्य पूर्णांक जोड़ और गुणा नहीं। खास तौर पर Boolean algebra में 1+1=1; इसे दो का arithmetic sum न समझें। XOR के लिए ⊕ और अस्पष्टता हटाने के लिए parentheses प्रयोग करेंगे। कोष्ठक अलग क्रम न दें तो पहले complement, फिर AND और फिर OR लगाएँ।

पूर्वज्ञान: truth tables और binary digits पढ़ना। पाठ के बाद आप छोटी truth table बना सकेंगे, सही शर्तों के साथ identities लगा सकेंगे, XOR और OR का अंतर समझ सकेंगे और output बदले बिना combinational expression सरल कर सकेंगे। मॉडल आदर्श, दो मानों वाला और steady-state है। Timing, electrical behavior, hazards और unknown values इसमें नहीं हैं। Algebraic simplification अपने आप न्यूनतम area या सबसे तेज वास्तविक hardware साबित नहीं करती। Karnaugh maps और व्यवस्थित minimization आगे के विषय हैं।

1. Operators और truth tables

NOT का एक input है; नीचे AND, OR और XOR के दो-दो inputs हैं। AND तभी 1 है जब दोनों inputs 1 हों। OR तब 1 है जब कम-से-कम एक input 1 हो। XOR तब 1 है जब ठीक एक input 1 हो। Truth table सभी assignments लिखती है, इसलिए function पूरी तरह तय करती है।

A	B	AB	A+B	A⊕B	A′
0	0	0	0	0	1
0	1	0	1	1	1
1	0	0	1	1	0
1	1	1	1	0	0

दो expressions तभी equivalent हैं जब अलग variables के हर assignment पर outputs समान हों। दो variables की चार rows और तीन की आठ rows हैं। Expression में A दोहराने से नया स्वतंत्र input नहीं बनता। एक अलग output equivalence गलत सिद्ध करता है; कुछ समान rows उसे सिद्ध नहीं करतीं।

2. मामले जाँचकर समझने वाले नियम

Identity: A+0=A और A·1=A। Domination: A+1=1 और A·0=0। Idempotence: A+A=A और AA=A। Complement: A+A′=1 और AA′=0। Double complement: (A′)′=A। A=0 और A=1 रखकर इन नियमों को सीधे जाँच सकते हैं।

AND और OR commutative तथा associative हैं। इसलिए A+B=B+A और (AB)C=A(BC)। दो distributive laws हैं: A(B+C)=AB+AC और A+BC=(A+B)(A+C)। दूसरा Boolean algebra का विशेष नियम है; सामान्य अंकगणित का अंदाज़ा बिना जाँचे न लगाएँ। A=1 पर दूसरे नियम के दोनों पक्ष 1 हैं; A=0 पर दोनों BC रह जाते हैं।

Absorption: A+AB=A। A common लेने पर A(1+B)=A·1=A। इसका dual A(A+B)=A है। Dual बनाने में पूरे identity में AND और OR तथा 0 और 1 की अदला-बदली करते हैं; इसका अर्थ हर variable का complement करना नहीं है। Absorption अनावश्यक term हटाता है, किसी परिचित अक्षर वाली मनमानी term नहीं।

3. De Morgan और complement का दायरा

De Morgan के नियम हैं (AB)′=A′+B′ और (A+B)′=A′B′। पूरे समूह का complement लेते समय operator बदलता है और हर operand complement होता है। उदाहरण: (A+BC)′=A′(BC)′=A′(B′+C′)। केवल + को AND करना गलत है; केवल अक्षरों को complement करना भी गलत है।

हल किया उदाहरण: (A′B′)′ सरल करें। De Morgan से (A′)′+(B′)′=A+B। A=B=1 पर मूल expression NOT(0 AND 0)=1 है, जो OR से मिलता है। इसके बदले A′+B′ लिखें तो उसी row पर 0 आएगा। इससे साबित होता है कि बाहर का complement यूँ ही हटाना गलत है।

दो से अधिक operands पर यही नियम बार-बार लगाएँ: (ABC)′=A′+B′+C′। Prime ठीक पहले के variable या कोष्ठक वाले समूह पर लागू होता है। इसलिए A′B और (AB)′ की truth tables अलग हैं।

4. Algebra से सरलीकरण का उदाहरण

F=AB+AB′+A′B लें। पहले दो terms मिलाएँ: AB+AB′=A(B+B′)=A। अब F=A+A′B। दूसरा distributive law लगाने पर A+A′B=(A+A′)(A+B)=1·(A+B)=A+B।

यह ठीक वही function है। हर row जाँचें: 00 पर सभी product terms शून्य हैं; 01 पर A′B एक है; 10 पर AB′ एक है; 11 पर AB एक है। Output क्रम 0,1,1,1 यानी OR मिलता है। अलग inputs केवल दो हैं, इसलिए चार rows चाहिए; expression में कई बार लिखे inputs को अलग न गिनें।

एक आकर्षक लेकिन गलत कदम है A+A′B=A+B′। A=0,B=1 रखने पर बायाँ पक्ष 1 और दायाँ 0 है। कभी-कभी गलत कदम के कथित “नियम” को खोजने से आसान एक counterexample देना होता है।

5. XOR और parity

XOR का sum-of-products रूप A⊕B=A′B+AB′ है। दोनों terms अलग मामले बताती हैं: केवल B एक हो या केवल A एक हो। OR में 11 का मामला भी शामिल है; इसलिए A+B और A⊕B एक-दूसरे की जगह नहीं रख सकते।

XOR के नियम हैं A⊕0=A, A⊕1=A′ और A⊕A=0। यह associative है, इसलिए A⊕B⊕C तब 1 है जब तीन inputs में 1 की संख्या विषम हो। यह odd parity है, “ठीक एक” की शर्त नहीं: input 111 पर भी 1 मिलता है। Full adder के sum bit में यह अंतर काम आएगा।

XNOR, XOR का complement है। दो inputs पर समान bits होने पर 1 देता है, इसलिए एक-bit equality test बना सकता है। कई-bit words की equality में हर corresponding bit की तुलना सही होनी चाहिए; दोनों words के सभी bits को एक साथ XOR करना पर्याप्त नहीं।

6. Truth table से expression

Minterm ऐसा AND term है जिसमें हर input variable ठीक एक बार आता है, complemented या uncomplemented रूप में। A=0,B=1,C=0 वाली row का minterm A′BC′ है। यह केवल उसी row पर 1 है: हर literal एक आवश्यक bit जाँचता है। जिन rows में output 1 है, उनके minterms का OR करने पर canonical sum of products (SOP) मिलता है।

हल किया उदाहरण: F(A,B,C) केवल 001, 011, 101 और 111 पर 1 हो; index में A सबसे महत्वपूर्ण bit है। Canonical SOP है A′B′C+A′BC+AB′C+ABC। C common लें: C(A′B′+A′B+AB′+AB)=C। मूल rows ठीक वे थीं जहाँ C=1, इसलिए यह सरलीकरण सीधे भी समझ आता है। सभी rows शून्य हों तो empty OR का मान 0 लेते हैं; हर row एक हो तो function 1 है।

केवल “SOP” कहने से हर product term में हर variable होना आवश्यक नहीं। AB+C एक SOP है, लेकिन A,B,C के संदर्भ में canonical नहीं है। Canonical minterm में सभी variables होने की शर्त है। Maxterms से product-of-sums बनाना इससे जुड़ा अगला विषय है, इस शुरुआती निर्माण के लिए आवश्यक नहीं।

भरोसेमंद तरीका और सामान्य गलतियाँ

Operators का अर्थ, input variables और grouping लिखें। हर कदम किसी सही identity से निकालें; फिर पूरी truth tables से स्वतंत्र जाँच करें। स्पष्ट रखें कि expression केवल equivalent मिला है या किसी बताए cost model में optimal भी सिद्ध हुआ है। Boolean terms को fractions की तरह cancel न करें, A+A=2A न लिखें, OR को XOR से न बदलें और पूरा De Morgan लगाए बिना complement न खिसकाएँ।

मौलिक अभ्यास: छह single-correct MCQ

ये बुनियाद मजबूत करने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।

C01. सभी Boolean A और B के लिए A+AB के equivalent कौन-सा expression है?

A. A+B B. AB C. B D. A

उत्तर: D

A गलत है: A=0,B=1 पर यह 1 देता है, जबकि A+AB का मान 0 है।

B गलत है: A=1,B=0 पर यह 0 देता है, जबकि A+AB का मान 1 है।

C गलत है: A=1,B=0 पर यह 0 देता है, जबकि मूल का मान 1 है।

D absorption से सही है: A+AB=A(1+B)=A।

C02. (A+BC)′ पर De Morgan लगाएँ। कौन-सा परिणाम equivalent है?

A. A′+B′C′ B. A′(B′+C′) C. A′B′C′ D. A+B′+C′

उत्तर: B

A गलत है: बाहर का OR, AND बनना चाहिए; A=0,B=C=1 पर यह 1 देता है लेकिन मूल 0 है।

B सही है: (A+BC)′=A′(BC)′=A′(B′+C′)।

C गलत है: BC का complement B′+C′ है, B′C′ नहीं; A=0,B=0,C=1 पर यह 0 और मूल 1 देता है।

D गलत है: A का भी complement चाहिए; A=1,B=C=1 पर यह 1 और मूल 0 देता है।

C03. किस दिए assignment पर A+B और A⊕B अलग हैं?

A. A=0, B=0 B. A=0, B=1 C. A=1, B=1 D. A=1, B=0

उत्तर: C

A गलत है: 00 पर OR और XOR दोनों 0 हैं।

B गलत है: 01 पर OR और XOR दोनों 1 हैं।

C सही है: 11 पर OR 1 और XOR 0 है।

D गलत है: 10 पर OR और XOR दोनों 1 हैं।

C04. Variable क्रम A,B,C में कौन-सा minterm केवल row 101 पर 1 है?

A. AB′C B. A′BC C. ABC′ D. A+B′+C

उत्तर: A

A सही है: A=1 के लिए A, B=0 के लिए B′ और C=1 के लिए C; इनका AND ठीक 101 चुनता है।

B गलत है: A′BC row 011 चुनता है, 101 नहीं।

C गलत है: ABC′ row 110 चुनता है, 101 नहीं।

D गलत है: यह OR term है; 100 जैसी कई दूसरी rows पर भी 1 है।

C05. केवल तीन अलग variables A, B और C वाले दो expressions की equivalence पूरी truth table से सिद्ध करने के लिए कितनी input rows जाँचनी हैं?

A. 3 B. 6 C. 9 D. 8

उत्तर: D

A गलत है: 3 variables की संख्या है, binary assignments की नहीं।

B गलत है: स्वतंत्र विकल्पों की संख्या 2×3 नहीं; विकल्पों का गुणा होता है।

C गलत है: 3² अलग विकल्पों की गणना है, 2³ नहीं।

D सही है: तीन स्वतंत्र inputs के दो-दो मान हैं, इसलिए 2³=8 rows; दोहराव नए inputs नहीं जोड़ता।

C06. किस शर्त पर A⊕B⊕C का मान 1 होता है?

A. ठीक एक input 1 हो। B. 1 वाले inputs की संख्या विषम हो। C. कम-से-कम एक input 1 हो। D. 1 वाले inputs की संख्या सम हो।

उत्तर: B

A गलत है: इसमें 111 छूट जाता है, जिस पर XOR 1 है।

B सही है: एक या तीन 1 होने पर odd parity और XOR 1 है।

C गलत है: दो 1 भी यह शर्त पूरी करते हैं लेकिन XOR 0 है।

D गलत है: शून्य या दो 1 होने पर XOR 0 है, 1 नहीं।

पाठ्यक्रम से संबंध और सीमा

यह Digital Logic का शुरुआती पाठ है; इससे GATE CS का पूरा Digital Logic पूरा नहीं होता। आधिकारिक GATE 2027 CS पाठ्यक्रम में Boolean algebra और minimization, combinational तथा sequential design, और number representation तथा arithmetic शामिल हैं। Karnaugh map, tabular minimization, sequential design, signed-number arithmetic और floating-point arithmetic के लिए आगे अलग पाठ चाहिए। पाठ्यक्रम से विषय की प्रासंगिकता जाँची गई है; यहाँ के उदाहरण और प्रश्न मौलिक हैं।

Official GATE 2027 CS syllabus, Section 2 (checked 2026-10-14).

तकनीकी convention का संदर्भ; हल किए उदाहरण और अभ्यास मौलिक हैं: MIT Computation Structures combinational logic.