مدار بولی: تفاوت میان نسخه‌ها

یک مدار بولی یک مدل ریاضی برای مدارهای منطقی دیجیتال در نظریه پیچیدگی محاسباتی و مدار پیچیدگی می باشدمی‌باشد. یک خانواده مدارهای بولی با هر طول ورودی ممکن، می تواندمی‌تواند بر روی زبان رسمی اثر بگذارد. مدارات بولی نیز به عنوان یک مدل رسمی برای منطق ترکیبی در الکترونیک دیجیتال استفاده می شوندمی‌شوند.

مدارات بولی به بواسطه گیت هایگیت‌های منطقی تشکیل دهنده آنها تعریف شده اندشده‌اند. به عنوان مثال، یک مدار می تواندمی‌تواند شامل گیت هایگیت‌های باینری AND و OR و گیت هایگیت‌های یکانی ( تک ورودی) NOT باشد، و یا به طور کامل توسط گیت هایگیت‌های باینری NAND پیاده سازیپیاده‌سازی شده باشد. هر گیت برخی از توابع بولی را پیاده می کندمی‌کند که تعداد ثابتی از بیتها را به عنوان ورودی و خروجی یک بیت در بر می گیردمی‌گیرد.

مدارات بولی یک مدل برای بسیاری از قطعات دیجیتالی مورد استفاده در مهندسی کامپیوتر، از جمله مالتی پلکسرها، جمع کننده ها،جمع‌کننده‌ها، و واحد حساب و منطق ارائه می کنندمی‌کنند.

والمر با معرفی یک مجموعه اصلی B از توابع بولی برای ارائه یک تعریف رسمی از مدارهای بولی مربوط به گیت هایگیت‌های مجاز در مدل مداری شروع کرد. سپس یک مدار بولی بر پایه B ( با n ورودی و m خروجی ) به عنوان یک گراف بدون دور مسقیم نامحدود تعریف گردید. هر راس به یک تابع اصلی و یا یکی از ورودی هاورودی‌ها ارتباط دارد، و دقیقادقیقاً یک مجموعه m نودی به عنوان خروجی وجود دارد. همچنین لبه هالبه‌ها باید نظم داشته باشند ،باشند، تا بتوان بین استدلال هایاستدلال‌های مختلف از توابع بولی مشابه تمایز قائل شد.

در موارد خاص، فرمول گزاره ایی یا عبارت بولی یک مدار بولی با یک نود خروجی که در آن تمامی نودهای دیگر با ورودی یک شدهشده‌اند، اند، می باشد.می‌باشد؛ بنابراین، یک مدار بولی می تواندمی‌تواند به عنوان یک نتیجه کلی می تواندمی‌تواند در نظر گرفته شود که به زیر فرمول هایفرمول‌های به اشتراک گذاشته شده و خروجی هایخروجی‌های چندگانه اجازه می دهدمی‌دهد.

شکل کمتداول برای مدارهای بولی مجموعه ایی از (ABD,OR,NOT) است، که به واسطه آنها کلیه توابع بولی دیگر می توانندمی‌توانند ساخته شوند.

مشکل ارزش مدار، مشکل محاسبه خروجی یک مدار بولی با توجه به رشته ورودی داده شده، در واقع همان مشکل تصمیم گیریتصمیم‌گیری P-complete hsj. بنابراین این مشکل به عنوان یک مشکل ذاتاذاتاً متوالی در نظر گرفته می شود،می‌شود، بدین معنی که به احتمال زیاد کارآمد نیست، و برای حل آن از الگوریتم بسیار موازی استفاده می شودمی‌شود.

'''مقیاس هایمقیاس‌های پیچیدگی'''

مقیاس پیچیدگی مهم متعددی در مدارهای بولی می توانندمی‌توانند تعریف شوند، از قبیل عمق مدار، اندازه مدار، و تعداد تناوب هایتناوب‌های بین گیت هایگیت‌های AND و OR. برای مثال، پیچیدگی اندازه یک مدار منطقی، تعداد گیت هایگیت‌های بکار برده شده در آن است.

'''کلاس هایکلاس‌های پیچیدگی'''

کلاس هایکلاس‌های پیچیدگی مهم متعددی در رابطه با مدارهای بولی تعریف شده اند،شده‌اند، از قبیل NC. NC به عنوانیک مجموعه از توابع بولی تعریف شده استشده‌است که بوسیله مدارهای بولی یکسان از اندازه چندجمله‌ای و عمق چند الگوریتمی میمی‌تواند تواند تصمیم گیریتصمیم‌گیری شود. در اینجا یکسان بدین معنی است که در خانواده مدار باید شرایطی موجود باشد که یک توصیف از یک مدار فقط از طریق تعداد ورودی هایورودی‌های آن مدار بتواند محاسبه شود.

* {{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | isbn = 3-540-64310-9}}