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

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

 

'''تعریف رسمی'''

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

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

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

== منابع ==

{{پانویس}}