مدار بولی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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


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

موارد مشابه

منابع[ویرایش]

  • Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.