Bounded, complemented और distributive lattices
उद्देश्य और पूर्वज्ञान
पहले पाठ के meet, join तथा Hasse diagram को आधार बनाकर boundedness, complementation और distributivity अलग-अलग जाँचेंगे। Counterexamples से गलत implications हटाएँगे और इनके संयुक्त रूप को Boolean algebra से जोड़ेंगे। सभी finite examples nonempty lattices हैं। नीचे 0 तथा 1 bottom और top के नाम हैं; जरूरी नहीं कि वे संख्याएँ शून्य और एक हों।
1. Boundedness पूरे lattice की property है
Bounded lattice में least element 0 और greatest element 1 होते हैं: हर x के लिए 0≤x≤1। इसलिए x∧0=0, x∨0=x, x∧1=x तथा x∨1=1। Lattice की परिभाषा हर pair के meet/join देती है; infinite carrier में endpoints जरूरी नहीं।
हर finite nonempty lattice bounded है। Elements x₁,…,xₙ के iterated meet m और join j लें। Meet/join की associativity उनके greatest-lower/least-upper-bound अर्थ से आती है। m हर element के नीचे और j हर element के ऊपर है; अतः m=0, j=1। इसके विपरीत integers को सामान्य ≤ से order करने पर min/max वाला lattice मिलता है, पर least या greatest integer नहीं। Theorem में finiteness आवश्यक भूमिका निभाती है।
2. Complement के दो अनिवार्य tests
Bounded lattice में y, x का complement है यदि x∧y=0 और x∨y=1 दोनों हों। Complemented lattice में हर element का कम-से-कम एक complement हो। इस परिभाषा से uniqueness नहीं मिलती। Bottom और top एक-दूसरे के complement हैं।
तीन-element chain 0<a<1 में meet=min, join=max। y=0 पर a∨0=a≠1; y=a पर a∧a=a≠0; y=1 पर a∧1=a≠0। इसलिए a का complement नहीं। यह bounded और, अगले प्रमाण से, distributive है, लेकिन complemented नहीं। केवल top-bottom वाला diagram पर्याप्त नहीं।
3. Distributive identities का प्रमाण
Distributive lattice में हर triple के लिए x∧(y∨z)=(x∧y)∨(x∧z) तथा x∨(y∧z)=(x∨y)∧(x∨z) होती हैं। Lattice theory में एक identity से उसकी dual निकलती है; यहाँ direct checks या ज्ञात models प्रयोग करेंगे। एक failing triple distributivity को खारिज करता है; एक successful triple उसे सिद्ध नहीं करता।
हर chain distributive है। मानें y≤z, तब y∨z=z। साथ ही x∧y≤x∧z, इसलिए (x∧y)∨(x∧z)=x∧z=x∧(y∨z)। Min/max का dual तर्क दूसरी identity देता है। हर triple cover होता है, क्योंकि y,z हमेशा comparable हैं।
P(U) में meet intersection, join union है। कोई element X∩(Y∪Z) में तभी है जब वह X में और Y,Z में कम-से-कम एक में हो। यही (X∩Y)∪(X∩Z) की शर्त है। दूसरी identity का भी समान membership proof है। अतः power-set lattice distributive है।
4. Diamond M₃ में complement है, distributivity नहीं
M₃={0,p,q,r,1} लें। बीच के p,q,r pairwise incomparable हैं; हर एक 0 से ऊपर और 1 से नीचे है, अन्य strict comparisons नहीं। अलग middle elements का meet=0, join=1। Comparable pair का lower element meet और upper element join है। इस प्रकार हर pair के meet/join मिलते हैं और यह lattice है।
यह complemented है। 0 और 1 एक-दूसरे के complements हैं; हर middle element के अन्य दोनों middle elements complements हैं। जैसे p∧q=0, p∨q=1; q के स्थान पर r के लिए भी यही। लेकिन
p∧(q∨r)=p∧1=p,
(p∧q)∨(p∧r)=0∨0=0।
p≠0 होने से distributivity fail होती है। अतः complemented ⇒ distributive गलत है और complements nonunique हो सकते हैं। तीन-element chain उलटी implication, distributive ⇒ complemented, को खारिज करती है।
5. Unique complements और Boolean structure
Bounded distributive lattice में b तथा c दोनों a के complements हों तो
b=b∧1=b∧(a∨c)=(b∧a)∨(b∧c)=0∨(b∧c)=b∧c।
इसी तरह c=b∧c, इसलिए b=c। Distributivity complement मौजूद होने पर uniqueness देती है, existence नहीं। तीन-element chain इसे याद रखने का counterexample है।
Boolean algebra को bounded, distributive, complemented lattice के रूप में परिभाषित कर सकते हैं। Unique complement को x′ लिखें। P(U) में bottom ∅, top U, meet ∩, join ∪ तथा complement U\X है। U={a,b,c} में {a,c} का complement {b} है: intersection खाली और union U दोनों जाँचें। Characteristic bit-vectors में यही operations bitwise AND, OR, NOT हैं। यह Boolean logic का गणितीय संबंध है; circuit-design पाठ का स्थानापन्न नहीं।
De Morgan identity (x∨y)′=x′∧y′ को uniqueness से सिद्ध करें। Distributivity से (x∨y)∧(x′∧y′)=0। दूसरी ओर (x∨y)∨(x′∧y′)=((x∨y)∨x′)∧((x∨y)∨y′)=1। इसलिए x′∧y′, x∨y का complement है। Dual proof से (x∧y)′=x′∨y′ मिलता है।
6. Divisor lattices की गणना और criterion
D(n), n के सभी positive divisors का divisibility-ordered lattice है। Bottom संख्यात्मक 1, top n, meet=gcd, join=lcm। n=p₁^e₁⋯pₖ^eₖ लिखें। हर divisor exponent vector (a₁,…,aₖ) देता है, जहाँ 0≤aᵢ≤eᵢ। Meet/join हर coordinate में min/max लेते हैं। प्रत्येक coordinate की chain distributivity से D(n) distributive है।
d के complement c के लिए gcd(d,c)=1 और lcm(d,c)=n चाहिए। हर prime coordinate में min(aᵢ,bᵢ)=0 तथा max(aᵢ,bᵢ)=eᵢ। यदि 0<aᵢ<eᵢ तो कोई bᵢ दोनों शर्तें नहीं पूरा करता। इसलिए d का complement तभी है जब हर exponent 0 या eᵢ हो; तब complement n/d है। हर divisor का complement तभी होगा जब n squarefree हो, सामान्य convention में n=1 भी शामिल है।
D(12)={1,2,3,4,6,12} bounded तथा distributive है। 3 का complement 4 है: gcd=1, lcm=12। 2 का complement नहीं, क्योंकि उसके prime 2 का exponent 0 और 2 के बीच है। अनुमान 12/2=6 गलत: gcd(2,6)=2, न कि 1। D(30) में 30=2·3·5 squarefree है, इसलिए यह Boolean है। हर divisor तीन primes के subset को चुनता है और complement बाकी primes को।
जाँच और सामान्य गलतियाँ
पहले lattice होना जाँचें। Carrier के भीतर bottom/top पहचानें। हर element के लिए दोनों complement equations देखें। Distributivity का general proof या स्पष्ट failing triple दें। Bounded, distributive और complemented तीनों होने पर ही Boolean कहें। D(n) में bottom का label 1 है; gcd=0 माँगना गलत है। केवल complements होने या diagram के परिचित दिखने से Boolean निष्कर्ष न निकालें।
मौलिक अभ्यास: छह एकल-सही-विकल्प MCQs
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में केवल एक सही विकल्प चुनें।
LT01. हर finite nonempty lattice के लिए कौन सा कथन सही है?
A. वह complemented है। B. वह distributive है। C. उसमें least और greatest element हैं। D. वह total order है।
उत्तर: C
A: तीन-element chain के middle element का complement नहीं।
B: M₃ finite nondistributive lattice है।
C: सभी elements का meet bottom और join top है।
D: Power-set lattice में incomparable elements होते हैं।
LT02. Chain 0<a<1 में a के complements कौन से हैं?
A. केवल 0 B. केवल 1 C. 0 तथा 1 दोनों D. कोई नहीं
उत्तर: D
A: a∨0=a है, top नहीं।
B: a∧1=a है, bottom नहीं।
C: दोनों candidates एक-एक आवश्यक equation fail करते हैं।
D: 0 join test fail करता है; a तथा 1 meet test fail करते हैं।
LT03. M₃ के incomparable middle elements p,q,r के लिए p∧(q∨r) और (p∧q)∨(p∧r) क्रमशः क्या हैं?
A. p तथा 0 B. 0 तथा p C. 1 तथा 0 D. p तथा p
उत्तर: A
A: q∨r=1 से बायाँ p; दाएँ दोनों meets 0 हैं।
B: दोनों evaluated sides उलटी हैं।
C: p का top से meet p है, top नहीं।
D: यह diamond में distributivity गलत मानता है।
LT04. Divisor lattice D(12) में 3 का complement कौन है?
A. 1 B. 4 C. 6 D. 12
उत्तर: B
A: gcd(3,1)=1 पर lcm=3, 12 नहीं।
B: gcd(3,4)=1 तथा lcm(3,4)=12।
C: gcd(3,6)=3, lcm=6; दोनों tests fail।
D: Join 12 है पर meet 3, bottom 1 नहीं।
LT05. Divisibility में सभी positive divisors का कौन सा lattice Boolean है?
A. D(8) B. D(12) C. D(30) D. D(18)
उत्तर: C
A: 8 में repeated prime है; divisor 2 का complement नहीं।
B: 12 में squared prime है; divisor 2 का complement नहीं।
C: 30 squarefree है; हर prime शामिल या अनुपस्थित, इसलिए set complements मिलते हैं।
D: 18 में 3² है; divisor 3 का complement नहीं।
LT06. Bounded distributive lattice में complements के बारे में क्या निश्चित है?
A. हर element का ठीक एक है। B. हर element के कम-से-कम दो हैं। C. किसी element का complement नहीं हो सकता। D. एक element का अधिकतम एक है।
उत्तर: D
A: Existence के लिए complemented property अलग चाहिए।
B: Complement मौजूद होने पर distributivity uniqueness देती है।
C: Bottom और top एक-दूसरे के complement हैं।
D: b,c यदि a के complements हैं तो distributivity से b=b∧c=c।
स्रोत और दायरा
यह सीमित विस्तार GATE 2026 CS syllabus के Section 1 में relations, lattices या groups की गहराई बढ़ाता है। यह संपूर्ण Discrete Mathematics coverage का दावा नहीं है। परिभाषाएँ, उदाहरण, प्रमाण और अभ्यास मौलिक प्रस्तुति हैं।
Official GATE 2026 CS syllabus, Section 1
स्रोत जाँचा गया: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन