कैननिकल सामान्य रूप

This article is about canonical forms particularly in Boolean algebra. It is not to be confused with Canonical form or Normal form.

{{anchor|Minterm|Maxterm}बूलियन बीजगणित (तर्क) में, किसी भी बूलियन समारोह को कैनोनिकल वियोगी सामान्य रूप (डिसजंक्टिव नॉर्मल फॉर्म) में व्यक्त किया जा सकता है। या मिनिटर्म कानूनी फॉर्म और इसका डुअल कैनोनिकल संयोजक सामान्य रूप (कॉन्जक्टिव नॉर्मल फॉर्म) या मैक्सटर्म कैनोनिकल फॉर्म। अन्य विहित रूपों में प्रमुख इम्प्लिकेंट्स या ब्लेक विहित रूप (और इसके दोहरे) का पूरा योग, और बीजगणितीय सामान्य रूप (जिसे ज़ेगाल्किन या रीड-मुलर भी कहा जाता है) शामिल हैं।

Minterms को उत्पाद कहा जाता है क्योंकि वे चर के एक सेट के तार्किक AND होते हैं, और maxterms को योग कहा जाता है क्योंकि वे चर के सेट के तार्किक OR होते हैं। डी मॉर्गन के कानूनों द्वारा व्यक्त किए गए उनके पूरक-समरूपता संबंध के कारण ये अवधारणाएं दोहरी हैं।

किसी भी बूलियन फ़ंक्शन के दो दोहरे विहित रूप न्यूनतम शब्दों का योग और अधिकतम शब्दों का गुणनफल हैं। 'सम ऑफ प्रोडक्ट्स' ('एसओपी' या 'एसओपी') शब्द का व्यापक रूप से विहित रूप के लिए उपयोग किया जाता है जो कि टकसालों का एक संयोजन (ओआर) है। इसका डुअल डी मॉर्गन कैनोनिकल फॉर्म के लिए 'सम्स का प्रोडक्ट' ('पीओएस' या 'पीओएस') है जो कि मैक्सटर्म्स का एक संयोजन (AND) है। इन कार्यों के सरलीकरण के लिए ये रूप उपयोगी हो सकते हैं, जो सामान्य रूप से बूलियन सूत्रों के अनुकूलन और विशेष रूप से डिजिटल सर्किट में बहुत महत्वपूर्ण है।

मिन्टर्स

के बूलियन फंक्शन के लिए $n$ चर ${x_{1},\dots ,x_{n}}$, एक उत्पाद शब्द जिसमें प्रत्येक $n$ चर एक बार प्रकट होते हैं (या तो इसके पूरक या अपूर्ण रूप में) को 'मिन्टरम' कहा जाता है। इस प्रकार, एक मिन्टरम एन वेरिएबल्स की एक तार्किक अभिव्यक्ति है जो केवल पूरक ऑपरेटर और कंजंक्शन ऑपरेटर को नियोजित करता है।

उदाहरण के लिए, $abc$, $ab'c$ और $abc'$ तीन वेरिएबल्स के बूलियन फ़ंक्शन के लिए 8 minterms के 3 उदाहरण हैं $a$, $b$, और $c$. इनमें से अंतिम का पारंपरिक पठन a AND b AND NOT-c है।

वहाँ 2 हैⁿ n वेरिएबल्स के न्यूनतम पद, चूँकि मिनिटर्म एक्सप्रेशन में एक वेरिएबल या तो इसके प्रत्यक्ष या इसके पूरक रूप में हो सकता है—हर चर के लिए दो विकल्प।

इंडेक्सिंग minterms

Minterms को अक्सर चर के पूरक पैटर्न के बाइनरी एन्कोडिंग द्वारा क्रमांकित किया जाता है, जहां चर मानक क्रम में लिखे जाते हैं, आमतौर पर वर्णानुक्रम में। यह सम्मेलन मूल्य 1 को प्रत्यक्ष रूप में निर्दिष्ट करता है ($x_{i}$) और 0 पूरक रूप में ($x'_{i}$); minterm तो है $\sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})$. उदाहरण के लिए, मिंटर्म $abc'$ 110 नंबर है₂ = 6₁₀ और निरूपित $m_{6}$.

कार्यात्मक तुल्यता

एक दिया गया minterm n इनपुट वेरिएबल्स के सिर्फ एक संयोजन के लिए एक सही मान (यानी, 1) देता है। उदाहरण के लिए, मिनट टर्म 5, a b' c, केवल तभी सत्य होता है जब a और c दोनों सत्य होते हैं और b गलत होता है—इनपुट व्यवस्था जहां a = 1, b = 0, c = 1 का परिणाम 1 होता है .

किसी तार्किक फलन की सत्य तालिका को देखते हुए, फलन को उत्पादों के योग के रूप में लिखना संभव है। यह वियोगात्मक सामान्य रूप का एक विशेष रूप है। उदाहरण के लिए, यदि एक योजक सर्किट के एक बिट स्थिति के तर्क के अंकगणितीय योग बिट यू के लिए सत्य तालिका दी गई है, तो एक्स और वाई के कार्य के रूप में और कैरी इन, सीआई:

ci	x	y	u(ci,x,y)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

यह देखते हुए कि जिन पंक्तियों का आउटपुट 1 है, वे दूसरी, तीसरी, पांचवीं और आठवीं हैं, हम यू को न्यूनतम शब्दों के योग के रूप में लिख सकते हैं $m_{1},m_{2},m_{4},$ और $m_{7}$. अगर हम इसे सत्यापित करना चाहते हैं: $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)$ तीन चरों के सभी 8 संयोजनों के लिए मूल्यांकन किया गया तालिका से मेल खाएगा।

मैक्सटर्म्स

के बूलियन फंक्शन के लिए n चर ${x_{1},\dots ,x_{n}}$, एक योग अवधि जिसमें प्रत्येक n चर एक बार प्रकट होता है (या तो इसके पूरक या अपूर्ण रूप में) को मैक्सटर्म कहा जाता है। इस प्रकार, एक अधिकतम की एक तार्किक अभिव्यक्ति है n वेरिएबल्स जो केवल पूरक ऑपरेटर और संयोजन ऑपरेटर को नियोजित करते हैं। मैक्सटर्म मिनिटर्म विचार के दोहरे हैं (यानी, सभी मामलों में एक पूरक समरूपता प्रदर्शित करना)। ANDs और पूरक का उपयोग करने के बजाय, हम ORs और पूरक का उपयोग करते हैं और इसी तरह आगे बढ़ते हैं।

उदाहरण के लिए, निम्नलिखित तीन चरों के आठ अधिकतम पदों में से दो हैं:

ए + बी' + सी

ए' + बी + सी

फिर से 2 हैंⁿ की अधिकतम शर्तें n चर, क्योंकि अधिकतम अभिव्यक्ति में एक चर इसके प्रत्यक्ष या इसके पूरक रूप में भी हो सकता है - प्रति चर दो विकल्प।

इंडेक्सिंग मैक्सटर्म्स

प्रत्येक मैक्सटर्म को विपरीत पारंपरिक बाइनरी एन्कोडिंग के आधार पर एक इंडेक्स असाइन किया जाता है जो कि मिंटर्म्स के लिए उपयोग किया जाता है। मैक्सटर्म सम्मेलन मान 0 को प्रत्यक्ष रूप में निर्दिष्ट करता है $(x_{i})$ और 1 पूरक रूप में $(x'_{i})$. उदाहरण के लिए, हम इंडेक्स 6 को मैक्सटर्म को असाइन करते हैं $a'+b'+c$ (110) और उस अधिकतम पद को एम के रूप में निरूपित करें₆. इसी प्रकार एम₀ इन तीन चरों में से है $a+b+c$ (000) और एम₇ है $a'+b'+c'$ (111).

कार्यात्मक तुल्यता

यह स्पष्ट है कि maxterm n इनपुट चरों के केवल एक संयोजन के लिए एक गलत मान (अर्थात, 0) देता है। उदाहरण के लिए, मैक्सटर्म 5, a′ + b + c′, तभी गलत है जब a और c दोनों सत्य हैं और b गलत है—इनपुट व्यवस्था जहां a = 1, b = 0, c = 1 का परिणाम 0 होता है।

यदि किसी को एक तार्किक फलन की सत्य सारणी दी गई है, तो फलन को योगों के गुणनफल के रूप में लिखना संभव है। यह संयोजक सामान्य रूप का एक विशेष रूप है। उदाहरण के लिए, यदि एक योजक सर्किट के एक बिट स्थिति के तर्क के कैरी-आउट बिट सह के लिए सत्य तालिका दी गई है, तो एक्स और वाई के कार्य के रूप में और कैरी इन, सीआई:

ci	x	y	co(ci,x,y)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

यह देखते हुए कि जिन पंक्तियों का आउटपुट 0 है, वे पहली, दूसरी, तीसरी और पाँचवीं हैं, हम co को maxterms के उत्पाद के रूप में लिख सकते हैं $M_{0},M_{1},M_{2}$ और $M_{4}$. अगर हम इसे सत्यापित करना चाहते हैं:

$co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+y)(ci'+x+y)$

तीन चरों के सभी 8 संयोजनों के लिए मूल्यांकन किया गया तालिका से मेल खाएगा।

द्वैतीकरण

मिन्टरम का पूरक संबंधित मैक्सटरम है। डी मॉर्गन के कानून का उपयोग करके इसे आसानी से सत्यापित किया जा सकता है। उदाहरण के लिए: $M_{5}=a'+b+c'=(ab'c)'=m_{5}'$

गैर-प्रामाणिक PoS और SoP रूपों

अक्सर ऐसा होता है कि कैनोनिकल मिन्टरम फॉर्म को समकक्ष एसओपी फॉर्म में सरल बनाया जा सकता है। इस सरलीकृत रूप में अभी भी उत्पाद शर्तों का योग शामिल होगा। हालाँकि, सरलीकृत रूप में, कम उत्पाद शब्द और/या कम चर वाले उत्पाद शब्द होना संभव है। उदाहरण के लिए, निम्नलिखित 3-चर फ़ंक्शन:

a	b	c	f(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

कैनोनिकल मिन्टरम प्रतिनिधित्व है: $f=a'bc+abc$, लेकिन इसका एक समान सरलीकृत रूप है: $f=bc$. इस तुच्छ उदाहरण में, यह स्पष्ट है कि $bc=a'bc+abc$, लेकिन सरलीकृत रूप में दोनों कम उत्पाद शब्द हैं, और शब्द में कम चर हैं।

किसी फ़ंक्शन के सबसे सरलीकृत एसओपी प्रतिनिधित्व को न्यूनतम एसओपी फॉर्म के रूप में संदर्भित किया जाता है।

इसी तरह, एक कैनोनिकल मैक्सटर्म फॉर्म में सरलीकृत पीओएस फॉर्म हो सकता है।

जबकि इस उदाहरण को सामान्य बीजगणितीय विधियों को लागू करके सरल बनाया गया था [$f=(a'+a)bc$], कम स्पष्ट मामलों में अधिकतम चार चर वाले फ़ंक्शन के न्यूनतम PoS/SoP रूप को खोजने के लिए एक सुविधाजनक तरीका एक कर्णघ मानचित्र का उपयोग कर रहा है।

बूलियन कार्यों के इष्टतम कार्यान्वयन को खोजने के लिए न्यूनतम पीओएस और एसओपी फॉर्म महत्वपूर्ण हैं और तर्क सर्किट को कम करना।

आवेदन उदाहरण

ऊपर दिए गए minterms और maxterms के लिए नमूना सत्य सारणी बाइनरी नंबरों के अतिरिक्त एकल बिट स्थिति के लिए कैनोनिकल फॉर्म स्थापित करने के लिए पर्याप्त हैं, लेकिन डिजिटल लॉजिक को डिज़ाइन करने के लिए पर्याप्त नहीं हैं जब तक कि आपके गेट्स की सूची में AND और OR शामिल न हो। जहां प्रदर्शन एक मुद्दा है (अपोलो गाइडेंस कंप्यूटर के रूप में), ट्रांजिस्टर लॉजिक में निहित पूरक क्रिया के कारण उपलब्ध भागों के NAND और NOR होने की अधिक संभावना है। मूल्यों को वोल्टेज राज्यों के रूप में परिभाषित किया गया है, एक जमीन के पास और एक डीसी आपूर्ति वोल्टेज वी के पास_cc, उदा. +5 वीडीसी। यदि उच्च वोल्टेज को 1 सही मान के रूप में परिभाषित किया जाता है, तो NOR गेट सबसे सरल संभव उपयोगी तार्किक तत्व है।

विशेष रूप से, एक 3-इनपुट NOR गेट में 3 बाइपोलर जंक्शन ट्रांजिस्टर शामिल हो सकते हैं, जिनके उत्सर्जक सभी ग्राउंडेड होते हैं, उनके संग्राहक एक साथ बंधे होते हैं और V से जुड़े होते हैं।_cc भार प्रतिबाधा के माध्यम से। प्रत्येक आधार एक इनपुट सिग्नल से जुड़ा होता है, और सामान्य संग्राहक बिंदु आउटपुट सिग्नल प्रस्तुत करता है। कोई भी इनपुट जो इसके आधार पर 1 (उच्च वोल्टेज) है, अपने ट्रांजिस्टर के उत्सर्जक को उसके संग्राहक तक छोटा कर देता है, जिससे लोड प्रतिबाधा के माध्यम से प्रवाह होता है, जो संग्राहक वोल्टेज (आउटपुट) को जमीन के बहुत करीब लाता है। वह परिणाम अन्य निविष्टियों से स्वतंत्र है। केवल जब सभी 3 इनपुट सिग्नल 0 (कम वोल्टेज) होते हैं, तो सभी 3 ट्रांजिस्टर के उत्सर्जक-संग्राहक प्रतिबाधा बहुत अधिक रहती है। तब बहुत कम धारा प्रवाहित होती है, और भार प्रतिबाधा के साथ वोल्टेज-विभक्त प्रभाव संग्राहक बिंदु पर वी के बहुत निकट एक उच्च वोल्टेज लगाता है।_cc.

विहित रूप में किसी फ़ंक्शन को लागू करने का प्रयास करते समय इन गेट सर्किट की पूरक संपत्ति एक कमी की तरह लग सकती है, लेकिन एक क्षतिपूर्ति बोनस है: केवल एक इनपुट वाला ऐसा गेट पूरक फ़ंक्शन को लागू करता है, जो डिजिटल लॉजिक में अक्सर आवश्यक होता है।

यह उदाहरण अपोलो भागों की सूची मानता है: केवल 3-इनपुट NOR गेट्स, लेकिन यह मानकर कि 4-इनपुट NOR गेट्स भी उपलब्ध हैं (अपोलो में, उन्हें 3-इनपुट NORs के जोड़े से मिश्रित किया गया था) द्वारा चर्चा को सरल बनाया गया है।

===NOR गेट्स === के विहित और गैर-विहित परिणाम 8 NOR गेट्स का एक सेट, यदि उनके इनपुट 3 इनपुट वेरिएबल्स ci, x, और y के प्रत्यक्ष और पूरक रूपों के सभी संयोजन हैं, तो हमेशा मिन्टर्म उत्पन्न करते हैं, कभी भी मैक्सटर्म नहीं- यानी सभी संयोजनों को संसाधित करने के लिए आवश्यक 8 गेट्स में से 3 इनपुट चरों में से, केवल एक का आउटपुट मान 1 है। ऐसा इसलिए है क्योंकि एक NOR गेट, इसके नाम के बावजूद, इसके इनपुट संकेतों के पूरक के रूप में (डी मॉर्गन के नियम का उपयोग करके) देखा जा सकता है।

यह कोई समस्या नहीं है इसका कारण minterms और maxterms का द्वंद्व है, यानी प्रत्येक maxterm समान-अनुक्रमित minterm का पूरक है, और इसके विपरीत।

उपरोक्त न्यूनतम उदाहरण में, हमने लिखा $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}$ लेकिन इसे 4-इनपुट NOR गेट के साथ निष्पादित करने के लिए हमें इसे राशियों (PoS) के उत्पाद के रूप में पुन: स्थापित करने की आवश्यकता है, जहां योग विपरीत अधिकतम पद हैं। वह है,

$u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).$

Truth tables

ci x y M0 M3 M5 M6 AND u(ci,x,y) 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1

ci x y m0 m3 m5 m6 NOR u(ci,x,y) 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1

उपरोक्त मैक्सटर्म उदाहरण में, हमने लिखा है $co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}$ लेकिन इसे 4-इनपुट NOR गेट के साथ करने के लिए हमें समान minterms के NOR की समानता पर ध्यान देने की आवश्यकता है। वह है,

$co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).$

Truth tables

ci x y M0 M1 M2 M4 AND co(ci,x,y) 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

ci x y m0 m1 m2 m4 NOR co(ci,x,y) 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1

कैनोनिकल रूपों के अतिरिक्त विचार किए गए डिजाइन ट्रेड-ऑफ्स

कोई यह मान सकता है कि एक योजक चरण को डिजाइन करने का काम अब पूरा हो गया है, लेकिन हमने इस तथ्य को संबोधित नहीं किया है कि सभी 3 इनपुट चर को उनके प्रत्यक्ष और पूरक दोनों रूपों में प्रकट होना है। इस संबंध में जोड़ x और y के बारे में कोई कठिनाई नहीं है, क्योंकि वे जोड़ के दौरान स्थिर हैं और इस प्रकार सामान्य रूप से लैच सर्किट में आयोजित होते हैं जो नियमित रूप से प्रत्यक्ष और पूरक दोनों आउटपुट होते हैं। (NOR गेट्स से बना सबसे सरल लैच सर्किट फ्लिप-फ्लॉप बनाने के लिए क्रॉस-युग्मित फाटकों की एक जोड़ी है: प्रत्येक का आउटपुट दूसरे के इनपुट में से एक के रूप में वायर्ड होता है।) पूरक फॉर्म बनाने की भी कोई आवश्यकता नहीं है। राशि यू। हालाँकि, एक बिट स्थिति से बाहर ले जाने को प्रत्यक्ष और पूरक दोनों रूपों में अगली बिट स्थिति में ले जाने के रूप में पारित किया जाना चाहिए। ऐसा करने का सबसे सीधा तरीका 1-इनपुट NOR गेट के माध्यम से co को पास करना और आउटपुट co′ को लेबल करना है, लेकिन यह सबसे खराब संभावित स्थान पर एक गेट विलंब जोड़ देगा, दाएं से बाएं की ओर बढ़ने की गति को धीमा कर देगा। एक अतिरिक्त 4-इनपुट NOR गेट जो co' के विहित रूप का निर्माण करता है (विपरीत minterms से co के रूप में) इस समस्या को हल करता है।

$co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).$

Truth tables

ci x y M3 M5 M6 M7 AND co'(ci,x,y) 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0

ci x y m3 m5 m6 m7 NOR co'(ci,x,y) 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0

इस तरह से पूर्ण गति बनाए रखने के लिए व्यापार-बंद में एक अप्रत्याशित लागत (एक बड़े गेट का उपयोग करने के अलावा) शामिल है। अगर हम उस 1-इनपुट गेट का उपयोग सह के पूरक के लिए करते, तो मिनट टर्म का कोई फायदा नहीं होता $m_{7}$, और इसे उत्पन्न करने वाले द्वार को समाप्त किया जा सकता था। फिर भी, यह अभी भी एक अच्छा व्यापार है।

अब हम उन कार्यों को ठीक उनके SoP और PoS विहित रूपों के अनुसार लागू कर सकते थे, NOR गेट्स को निर्दिष्ट कार्यों में बदलकर। 1-इनपुट NOR गेट के माध्यम से अपना आउटपुट पास करके एक NOR गेट को OR गेट में बनाया जाता है; और इसे 1-इनपुट NOR गेट के माध्यम से इसके प्रत्येक इनपुट को पास करके AND गेट में बनाया जाता है। हालाँकि, यह दृष्टिकोण न केवल उपयोग किए जाने वाले फाटकों की संख्या को बढ़ाता है, बल्कि संकेतों को संसाधित करने वाले फाटकों की संख्या को भी दोगुना कर देता है, जिससे प्रसंस्करण गति आधी हो जाती है। नतीजतन, जब भी प्रदर्शन महत्वपूर्ण होता है, कैनोनिकल रूपों से परे जा रहा है और बूलियन बीजगणित कर असंवर्धित NOR गेट्स को काम करने के लिए अच्छी तरह से सार्थक है।

टॉप-डाउन बनाम बॉटम-अप डिज़ाइन

हमने अब देखा है कि कैसे कुछ बूलियन बीजगणित के साथ विहित रूप में एक योजक चरण को डिज़ाइन करने के लिए minterm/maxterm उपकरणों का उपयोग किया जा सकता है, प्रत्येक आउटपुट के लिए सिर्फ 2 गेट देरी की लागत। इस फ़ंक्शन के लिए डिजिटल सर्किट को डिज़ाइन करने का यह टॉप-डाउन तरीका है, लेकिन क्या यह सबसे अच्छा तरीका है? चर्चा ने सबसे तेज़ को सर्वश्रेष्ठ के रूप में पहचानने पर ध्यान केंद्रित किया है, और संवर्धित विहित रूप उस मानदंड को त्रुटिपूर्ण रूप से पूरा करता है, लेकिन कभी-कभी अन्य कारक प्रबल होते हैं। डिज़ाइनर के पास फाटकों की संख्या को कम करने का प्राथमिक लक्ष्य हो सकता है, और / या अन्य फाटकों के सिग्नल के फैनआउट को कम करने के बाद से बड़े फैनआउट्स एक खराब बिजली आपूर्ति या अन्य पर्यावरणीय कारकों के लचीलेपन को कम करते हैं। ऐसे मामले में, एक डिज़ाइनर कैनोनिकल-फ़ॉर्म डिज़ाइन को आधार रेखा के रूप में विकसित कर सकता है, फिर नीचे-ऊपर विकास का प्रयास कर सकता है, और अंत में परिणामों की तुलना कर सकता है।

बॉटम-अप विकास में ध्यान देना शामिल है कि u = ci XOR (x XOR y), जहां XOR का अर्थ विशिष्ट या [सच है जब या तो इनपुट सत्य है लेकिन नहीं जब दोनों सत्य हैं], और वह co = ci x + x y + y ci। इस तरह के एक विकास में सभी में बारह NOR गेट लगते हैं: छह 2-इनपुट गेट और दो 1-इनपुट गेट, 5 गेट देरी में यू का उत्पादन करने के लिए, साथ ही तीन 2-इनपुट गेट और एक 3-इनपुट गेट 2 गेट देरी में सह का उत्पादन करने के लिए। कैनोनिकल बेसलाइन ने 2 गेट देरी में यू, सह और सह का उत्पादन करने के लिए आठ 3-इनपुट एनओआर गेट्स और तीन 4-इनपुट एनओआर गेट्स लिए। यदि सर्किट इन्वेंट्री में वास्तव में 4-इनपुट NOR गेट्स शामिल हैं, तो टॉप-डाउन कैनोनिकल डिज़ाइन गेट काउंट और गति दोनों में विजेता की तरह दिखता है। लेकिन अगर (हमारे सुविधाजनक अनुमान के विपरीत) सर्किट वास्तव में 3-इनपुट NOR गेट हैं, जिनमें से प्रत्येक 4-इनपुट NOR फ़ंक्शन के लिए दो की आवश्यकता होती है, तो कैनोनिकल डिज़ाइन 14 गेट लेता है जबकि बॉटम-अप दृष्टिकोण के लिए 12, लेकिन अभी भी योग अंक यू काफी तेजी से पैदा करता है। फैनआउट तुलना को इस प्रकार सारणीबद्ध किया गया है:

Variables	Top-down	Bottom-up
x	4	1
x'	4	3
y	4	1
y'	4	3
ci	4	1
ci'	4	3
M or m	4@1,4@2	N/A
x XOR y	N/A	2
Misc	N/A	5@1
Max	4	3

बॉटम-अप डेवलपमेंट के विवरण में co' का आउटपुट के रूप में उल्लेख है लेकिन co का नहीं। क्या उस डिज़ाइन को कभी भी निष्पादन के प्रत्यक्ष रूप की आवश्यकता नहीं है? अच्छा, हाँ और नहीं। प्रत्येक चरण में, co' की गणना केवल ci', x' और y' पर निर्भर करती है, जिसका अर्थ है कि कैरी प्रोपेगेशन रिपल्स बिट पोजीशन के साथ-साथ कैनोनिकल डिज़ाइन में बिना किसी विकास के तेजी से बढ़ता है। यू की गणना, जिसके लिए 1-इनपुट एनओआर द्वारा सीआई से सीआई की आवश्यकता होती है, धीमी है लेकिन किसी भी शब्द की लंबाई के लिए डिज़ाइन केवल एक बार उस दंड का भुगतान करता है (जब सबसे बाईं ओर का अंक विकसित होता है)। ऐसा इसलिए है क्योंकि वे गणनाएँ ओवरलैप होती हैं, प्रत्येक कितनी मात्रा में अपनी छोटी पाइपलाइन को प्रभावित किए बिना जब अगली बिट स्थिति के योग बिट की गणना की जा सकती है। और, सुनिश्चित करने के लिए, सबसे बाएं बिट स्थिति के सह' को संभवतः तर्क के हिस्से के रूप में पूरक होना होगा, यह निर्धारित करने के लिए कि अतिरिक्त अतिप्रवाह हुआ है या नहीं। लेकिन 3-इनपुट NOR गेट्स का उपयोग करते हुए, बॉटम-अप डिज़ाइन एक गैर-तुच्छ शब्द लंबाई पर समानांतर जोड़ करने के लिए लगभग उतना ही तेज है, गेट काउंट में कटौती करता है, और कम फैनआउट का उपयोग करता है ... इसलिए यदि गेट काउंट होता है तो यह जीत जाता है और/या fanout सर्वोपरि हैं!

हम बॉटम-अप डिज़ाइन की सटीक सर्किटरी छोड़ देंगे, जिसमें ये सभी कथन इच्छुक पाठक के लिए एक अभ्यास के रूप में सत्य हैं, एक और बीजगणितीय सूत्र द्वारा सहायता प्राप्त है: u = ci(x XOR y) + ci′(x XOR y) )']'। इस तरह से योग के गठन से कैरी प्रसार को डिकॉप्लिंग करना एक रिपल कैरी योजक के ऊपर कैरी-लुकहेड योजक के प्रदर्शन को बढ़ाता है।

== डिजिटल सर्किट डिजाइन == में आवेदन बूलियन बीजगणित का एक अनुप्रयोग डिजिटल सर्किट डिज़ाइन है, जिसका एक लक्ष्य फाटकों की संख्या को कम करना और दूसरा बसने के समय को कम करना है।

दो चर के सोलह संभावित कार्य हैं, लेकिन डिजिटल लॉजिक हार्डवेयर में, सबसे सरल गेट सर्किट उनमें से केवल चार को लागू करते हैं: तार्किक संयोजन (AND), तार्किक संयोजन (समावेशी OR), और उन (NAND और NOR) के संबंधित पूरक।

अधिकांश गेट सर्किट 2 से अधिक इनपुट चर स्वीकार करते हैं; उदाहरण के लिए, स्पेसबोर्न अपोलो गाइडेंस कंप्यूटर, जिसने 1960 के दशक में इंटीग्रेटेड सर्किट के अनुप्रयोग का बीड़ा उठाया था, केवल एक प्रकार के गेट के साथ बनाया गया था, एक 3-इनपुट NOR, जिसका आउटपुट तभी सही होता है जब सभी 3 इनपुट गलत होते हैं।

यह भी देखें

• बूलियन बीजगणित विषयों की सूची

अग्रिम पठन

• Bender, Edward A.; Williamson, S. Gill (2005). A Short Course in Discrete Mathematics. Mineola, NY: Dover Publications, Inc. ISBN 0-486-43946-1.
  The authors demonstrate a proof that any Boolean (logic) function can be expressed in either disjunctive or conjunctive normal form (cf pages 5–6); the proof simply proceeds by creating all 2^N rows of N Boolean variables and demonstrates that each row ("minterm" or "maxterm") has a unique Boolean expression. Any Boolean function of the N variables can be derived from a composite of the rows whose minterm or maxterm are logical 1s ("trues")
• McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits. NY: McGraw–Hill Book Company. p. 78. LCCN 65-17394. Canonical expressions are defined and described
• Hill, Fredrick J.; Peterson, Gerald R. (1974). Introduction to Switching Theory and Logical Design (2nd ed.). NY: John Wiley & Sons. p. 101. ISBN 0-471-39882-9. Minterm and maxterm designation of functions

बाहरी संबंध

• Boole, George (1848). Translated by Wilkins, David R. "The Calculus of Logic". Cambridge and Dublin Mathematical Journal. III: 183–198.