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

This article is about विशेष रूप से बूलियन बीजगणित में कैनोनिकल रूप. It is not to be confused with कैनोनिकल रूप or सामान्य रूप.

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

मिनिटर्म को उत्पाद कहा जाता है क्योंकि वे वेरिएबल्स के समुच्चय के लॉजिक एएनडी होते हैं, और मैक्सटर्म को योग कहा जाता है क्योंकि वे वेरिएबल्स के समुच्चय के लॉजिक ओआर होते हैं। डी मॉर्गन के नियमों द्वारा व्यक्त किए गए उनके पूरक-समरूपता संबंध के कारण इन अवधारणाओं की पुनरावृत्ति होती हैं।

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

मिनिटर्म

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

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

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

क्रमबद्ध मिनिटर्म

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

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

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

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

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 है, वे दूसरी, तीसरी, पांचवीं और आठवीं हैं, हम u को न्यूनतम शब्दों के योग के रूप में लिख सकते हैं I $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 वेरिएबल्स प्रकट होता है (या तो इसके पूरक या अपूर्ण रूप में) को मैक्सटर्मकहा जाता है। इस प्रकार,अधिकतमकी लॉजिक अभिव्यक्ति है I n वेरिएबल्स जो केवल पूरक संचालक और संयोजन संचालक को नियोजित करते हैं। मैक्सटर्म मिनिटर्म विचार के पुनरावृत्ति हैं (जैसे, सभी स्तिथियों में पूरक समरूपता प्रदर्शित करना)। ANDs और पूरक का उपयोग करने के अतिरिक्त, हम ओआरएस और पूरक का उपयोग करते हैं और इसी प्रकार आगे बढ़ते हैं।

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

a + b′ + c

a′ + b + c

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

क्रमबद्ध मैक्सटर्म्स

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

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

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

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

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 को मैक्सटर्म के उत्पाद के रूप में लिख सकते हैं $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}'$

गैर-प्रामाणिक पीओएस और एसओपी रूपों

प्रायः ऐसा होता है कि कैनोनिकल मिनिटर्म फॉर्म को समकक्ष एसओपी फॉर्म में सरल बनाया जा सकता है। इस सरलीकृत रूप में अभी भी उत्पाद नियमं का योग सम्मलित होगा। चूँकि, सरलीकृत रूप में, कम उत्पाद शब्द या उत्पाद शब्द कम वेरिएबल्स वाले हो सकते हैं। उदाहरण के लिए, निम्नलिखित 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$, किन्तु सरलीकृत रूप में दोनों कम उत्पाद शब्द हैं,और शब्द में कम वेरिएबल्स हैं।

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

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

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

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

आवेदन उदाहरण

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

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

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

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

एनओआर गेट्स के कैनोनिकल और गैर-कैनोनिकल परिणाम

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

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

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

सत्य सारणी

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 एनओआर 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-इनपुट एनओआर गेट के साथ करने के लिए हमें समान मिनिटर्म के एनओआर की समानता पर ध्यान देने की आवश्यकता है। वह $co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).$ है I

सत्य सारणी

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 एनओआर 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 के बारे में कोई कठिनाई नहीं है, क्योंकि वे जोड़ के समय स्थिर हैं और इस प्रकार सामान्य रूप से लैच सर्किट में आयोजित होते हैं जो नियमित रूप से प्रत्यक्ष और पूरक दोनों आउटपुट होते हैं। (एनओआर गेट्स से बना सबसे सरल लैच सर्किट फ्लिप-फ्लॉप बनाने के लिए क्रॉस-युग्मित गेट्स की जोड़ी है: प्रत्येक का आउटपुट दूसरे के इनपुट के रूप में जुड़ा होता है।) पूरक फॉर्म बनाने की भी कोई आवश्यकता नहीं है। चूँकि, राशि u बिट स्थिति से बाहर ले जाने को प्रत्यक्ष और पूरक दोनों रूपों में अगली बिट स्थिति में ले जाने के रूप में पारित किया जाना चाहिए। ऐसा करने का सबसे सरल उपाय1-इनपुट एनओआर गेट के माध्यम से co को निकट करना और आउटपुट co′ को लेबल करना है, किन्तु यह सबसे अकथनीय संभावित स्थान पर गेट विलंब जोड़ देगा, दाएं से बाएं की ओर बढ़ने की गति को धीमा कर देगा। अतिरिक्त 4-इनपुट एनओआर गेट जो co' के कैनोनिकल रूप का निर्माण करता है (विपरीत मिनिटर्म से 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}).$

सत्य सारणी

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 एनओआर 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-इनपुट गेट का उपयोग co के पूरक के लिए करते, तो मिनिटर्म का कोई लाभ नहीं होता है I $m_{7}$,और इसे उत्पन्न करने वाले द्वार को समाप्त किया जा सकता था। फिर भी, यह अभी भी उत्तम व्यापार है।

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

टॉप-डाउन के प्रति बॉटम-अप डिज़ाइन

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

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

वेरिएबल्स	टॉप-डाउन	बॉटम-अप
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' पर निर्भर करती है, जिसका अर्थ है कि कैरी प्रोपेगेशन रिपल्स बिट पोजीशन के साथ-साथ कैनोनिकल डिज़ाइन में बिना किसी विकास के तीव्रता से बढ़ता है। u की गणना, जिसके लिए 1-इनपुट एनओआर द्वारा ci से ci की आवश्यकता धीमी है किन्तु किसी भी शब्द की लंबाई के लिए डिज़ाइन केवल भुगतान करता है (जब सबसे बाईं ओर का अंक विकसित होता है)। ऐसा इसलिए है क्योंकि वे गणनाएँ ओवरलैप होती हैं, प्रत्येक के द्वारा कितनी मात्रा में अपनी छोटी पाइपलाइन को प्रभावित किए बिना जब अगली बिट स्थिति के योग की गणना की जा सकती है, और सुनिश्चित करने के लिए, सबसे बाएं बिट स्थिति के co' को संभवतः तर्क के भाग के रूप में पूरक होना होगा, यह निर्धारित करने के लिए कि अतिरिक्त अतिप्रवाह हुआ है या नहीं हुआ है। किन्तु 3-इनपुट एनओआर गेट्स का उपयोग करते हुए, बॉटम-अप डिज़ाइन गैर-तुच्छ शब्द लंबाई पर समानांतर जोड़ करने के लिए लगभग उतनी ही तीव्रता से गेट की गणना में कमी करता है, और कम फैनआउट का उपयोग करता है I इसलिए यदि गेट होता है तो यह विजयी होता है, और फनौट(fanout) सर्वोपरि होता हैं I

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

डिजिटल सर्किट डिजाइन में आवेदन

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

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

अधिकांश गेट सर्किट 2 से अधिक इनपुट वेरिएबल्स स्वीकार करते हैं; उदाहरण के लिए, स्पेसबोर्न अपोलो गाइडेंस कंप्यूटर, जिसने 1960 के दशक में इंटीग्रेटेड सर्किट का अनुप्रयोग किया जाता है, जिसे गेट के साथ बनाया गया था, 3-इनपुट एनओआर, जिसका आउटपुट तभी उचित होता है जब सभी 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.