مدار بولی

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

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

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

تعریف رسمی والمر با معرفی یک مجموعه اصلی B از توابع بولی برای ارائه یک تعریف رسمی از مدارهای بولی مربوط به گیت‌های مجاز در مدل مداری شروع کرد. سپس یک مدار بولی بر پایه B (با n ورودی و m خروجی) به عنوان یک گراف بدون دور مسقیم نامحدود تعریف گردید. هر راس به یک تابع اصلی یا یکی از ورودی‌ها ارتباط دارد، و دقیقاً یک مجموعه m نودی به عنوان خروجی وجود دارد. همچنین لبه‌ها باید نظم داشته باشند، تا بتوان بین استدلال‌های مختلف از توابع بولی مشابه تمایز قائل شد. در موارد خاص، فرمول گزاره ایی یا عبارت بولی یک مدار بولی با یک نود خروجی که در آن تمامی نودهای دیگر با ورودی یک شده‌اند، می‌باشد؛ بنابراین، یک مدار بولی می‌تواند به عنوان یک نتیجه کلی می‌تواند در نظر گرفته شود که به زیر فرمول‌های به اشتراک گذاشته شده و خروجی‌های چندگانه اجازه می‌دهد. شکل کمتداول برای مدارهای بولی مجموعه ایی از (ABD,OR,NOT) است، که به واسطه آن‌ها کلیه توابع بولی دیگر می‌توانند ساخته شوند. پیچیدگی محاسباتی بررسی مدار مشکل ارزش مدار، مشکل محاسبه خروجی یک مدار بولی با توجه به رشته ورودی داده شده، در واقع همان مشکل تصمیم‌گیری P-complete hsj. بنابراین این مشکل به عنوان یک مشکل ذاتاً متوالی در نظر گرفته می‌شود، بدین معنی که به احتمال زیاد کارآمد نیست، و برای حل آن از الگوریتم بسیار موازی استفاده می‌شود. مقیاس‌های پیچیدگی همچنین پیچیدگی مدار را ببینید مقیاس پیچیدگی مهم متعددی در مدارهای بولی می‌توانند تعریف شوند، از قبیل عمق مدار، اندازه مدار، و تعداد تناوب‌های بین گیت‌های AND و OR. برای مثال، پیچیدگی اندازه یک مدار منطقی، تعداد گیت‌های بکار برده شده در آن است. کلاس‌های پیچیدگی کلاس‌های پیچیدگی مهم متعددی در رابطه با مدارهای بولی تعریف شده‌اند، از قبیل NC. NC به عنوانیک مجموعه از توابع بولی تعریف شده‌است که به وسیلهٔ مدارهای بولی یکسان از اندازه چندجمله‌ای و عمق چند الگوریتمی می‌تواند تصمیم‌گیری شود. در اینجا یکسان بدین معنی است که در خانواده مدار باید شرایطی موجود باشد که یک توصیف از یک مدار فقط از طریق تعداد ورودی‌های آن مدار بتواند محاسبه شود.