बूलियन परिपथ

File:Three input Boolean circuit.jpg

उदाहरण बूलियन सर्किट। $\wedge$ h> नोड AND गेट्स हैं, द $\vee$ नोड या द्वार हैं, और $\neg$ गेट नहीं नहीं हैं

कम्प्यूटेशनल जटिलता सिद्धांत और सर्किट जटिलता में, बूलियन सर्किट संयोजन तर्क डिजिटल इलेक्ट्रॉनिक्स के लिए गणना का एक गणितीय मॉडल है। बूलियन सर्किट के एक परिवार द्वारा एक औपचारिक भाषा तय की जा सकती है, प्रत्येक संभावित इनपुट लंबाई के लिए एक सर्किट।

बूलियन सर्किट को उनके पास मौजूद तर्क द्वार्स के संदर्भ में परिभाषित किया गया है। उदाहरण के लिए, एक सर्किट में बाइनरी फ़ंक्शन AND और OR गेट्स और एकात्मक ऑपरेशन NOT गेट्स हो सकते हैं, या पूरी तरह से बाइनरी NAND गेट्स द्वारा वर्णित हो सकते हैं। प्रत्येक गेट कुछ बूलियन समारोह से मेल खाता है जो इनपुट के रूप में अंश्स की एक निश्चित संख्या लेता है और एक बिट को आउटपुट करता है।

बूलियन सर्किट कंप्यूटर इंजीनियरिंग में उपयोग किए जाने वाले कई डिजिटल घटकों के लिए एक मॉडल प्रदान करते हैं, जिसमें बहुसंकेतक्स, योजक (इलेक्ट्रॉनिक्स) और अंकगणितीय तर्क इकाइयां शामिल हैं, लेकिन वे अनुक्रमिक तर्क को बाहर करते हैं। वे एक अमूर्त हैं जो वास्तविक डिजिटल लॉजिक सर्किट को डिजाइन करने के लिए प्रासंगिक कई पहलुओं को छोड़ देते हैं, जैसे कि मेटास्टेबिलिटी (इलेक्ट्रॉनिक्स), प्रशंसक बाहर, खतरा (तर्क), शक्ति अनुकूलन (EDA)ईडीए), और प्रसार विलंब परिवर्तनशीलता।

औपचारिक परिभाषा

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

बूलियन सर्किट के लिए एक सामान्य आधार सेट {AND गेट, OR गेट, नॉट गेट} है, जो कार्यात्मक पूर्णता है, i। इ। जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है।

कम्प्यूटेशनल जटिलता

पृष्ठभूमि

एक विशेष सर्किट निश्चित आकार के इनपुट पर ही कार्य करता है। हालाँकि, औपचारिक भाषाएँ (स्ट्रिंग (कंप्यूटर विज्ञान) | निर्णय समस्याओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं को एक सर्किट द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (ट्यूरिंग मशीन मॉडल के विपरीत, जिसमें एक भाषा है पूरी तरह से एक ट्यूरिंग मशीन द्वारा वर्णित)। इसके बजाय एक सर्किट परिवार द्वारा एक भाषा का प्रतिनिधित्व किया जाता है। एक सर्किट परिवार सर्किट की अनंत सूची है $(C_{0},C_{1},C_{2},...)$, कहाँ $C_{n}$ है $n$ इनपुट चर। कहा जाता है कि एक सर्किट परिवार एक भाषा तय करता है $L$ अगर, हर स्ट्रिंग के लिए $w$, $w$ भाषा में है $L$ अगर और केवल अगर $C_{n}(w)=1$, कहाँ $n$ की लम्बाई है $w$. दूसरे शब्दों में, एक भाषा तारों का समूह है, जो सर्किट पर लागू होने पर उनकी लंबाई के अनुरूप होती है, जो 1 का मूल्यांकन करती है।

जटिलता उपाय

See also: Circuit complexity

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

सर्किट के आकार की जटिलता और समय की जटिलता के बीच एक स्वाभाविक संबंध है। सहज रूप से, कम समय की जटिलता वाली भाषा (यानी, ट्यूरिंग मशीन पर अपेक्षाकृत कुछ अनुक्रमिक संचालन की आवश्यकता होती है), इसमें एक छोटी सर्किट जटिलता भी होती है (अर्थात, अपेक्षाकृत कुछ बूलियन संचालन की आवश्यकता होती है)। औपचारिक रूप से, यह दिखाया जा सकता है कि यदि कोई भाषा में है ${\mathsf {TIME}}(t(n))$, कहाँ $t$ एक कार्य है $t:\mathbb {N} \to \mathbb {N}$, तो इसमें सर्किट जटिलता है $O(t^{2}(n))$.

जटिलता वर्ग

Main article: Complexity classes § Boolean circuits

बूलियन सर्किट के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है पी/पॉली, भाषाओं का वह समूह जो बहुपद-आकार के सर्किट परिवारों द्वारा तय किया जा सकता है। यह सीधे इस तथ्य से अनुसरण करता है कि भाषाओं में ${\mathsf {TIME}}(t(n))$ सर्किट जटिलता है $O(t^{2}(n))$ वह पी (जटिलता)$\subseteq$पी/पॉली। दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणना की जा सकने वाली किसी भी समस्या की गणना बहुपद-आकार के सर्किट परिवार द्वारा भी की जा सकती है। आगे यह मामला है कि समावेशन उचित है (यानी पी$\subsetneq$पी/पॉली) क्योंकि ऐसी अनिर्णीत समस्याएं हैं जो पी/पॉली में हैं। पी/पॉली में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह P बनाम NP से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि एनपी में कोई ऐसी भाषा है जो पी/पॉली में नहीं है तो पी$\neq$ई.जी. P/poly बहुपद पदानुक्रम के गुणों की जांच करने में भी मदद करता है। उदाहरण के लिए, यदि एनपी (जटिलता) ⊆ पी/पॉली, तो पीएच गिर जाता है $\Sigma _{2}^{\mathsf {P}}$. पी/पॉली और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण पी/पॉली#Importance of P/poly|Importance of P/poly पर उपलब्ध है। पी / पॉली में दिलचस्प विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित सलाह (जटिलता) के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है।

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

सर्किट मूल्यांकन

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

पूर्णता

लॉजिक सर्किट सरल लॉजिक ऑपरेशंस, AND, OR और NOT (और उनके संयोजन, जैसे गैर-अनुक्रमिक फ्लिप-फ्लॉप या सर्किट नेटवर्क) का भौतिक प्रतिनिधित्व करते हैं, जो एक गणितीय संरचना बनाते हैं जिसे बूलियन बीजगणित के रूप में जाना जाता है। वे इस मायने में पूर्ण हैं कि वे कोई भी नियतात्मक एल्गोरिथम निष्पादित कर सकते हैं। हालाँकि, ऐसा होता है कि यह सब कुछ नहीं है। भौतिक दुनिया में हम यादृच्छिकता का भी सामना करते हैं, परिमाणीकरण प्रभावों द्वारा नियंत्रित छोटी प्रणालियों में उल्लेखनीय है, जिसे क्वांटम यांत्रिकी के सिद्धांत द्वारा वर्णित किया गया है। लॉजिक सर्किट किसी भी यादृच्छिकता का उत्पादन नहीं कर सकते हैं, और इस अर्थ में वे एक अपूर्ण लॉजिक सेट बनाते हैं। इसका उपाय तर्क नेटवर्क, या कंप्यूटर, जैसे कि संभाव्य ट्यूरिंग मशीन में एक तदर्थ यादृच्छिक बिट जनरेटर को जोड़ने में पाया जाता है। एक हालिया काम रैंडम फ्लिप-फ्लॉप नामक एक अंतर्निहित यादृच्छिक लॉजिक सर्किट की एक सैद्धांतिक अवधारणा पेश की है, जो सेट को पूरा करती है। यह आसानी से यादृच्छिकता को पैक करता है और नियतात्मक बूलियन लॉजिक सर्किट के साथ इंटर-ऑपरेबल है। हालांकि, बूलियन बीजगणित के समकक्ष एक बीजगणितीय संरचना और विस्तारित सेट के लिए सर्किट निर्माण और कटौती के संबंधित तरीके अभी तक अज्ञात हैं।

यह भी देखें

• सर्किट संतुष्टि
• लॉजिक गेट
• बूलियन तर्क
• स्विचिंग लेम्मा

फुटनोट्स

श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत श्रेणी:डिजिटल सर्किट श्रेणी:कंप्यूटर विज्ञान में तर्क