From Wikipedia, the free encyclopedia
الگوریتم کواین-مککلاسکی روشی است که برای کمینه کردن توابع بولی توسط ویلارد کواین، منطقدان آمریکایی و ادوارد مککلاسکی ایجاد شد. این روش از لحاظ تابعی با جدول کارنو یکسان است، ولی حالت جدولی این روش را برای استفاده در الگوریتمهای کامپیوتری کارآمدتر میکند. علاوه بر این، این روش بهطور قطعی میتواند بیان کند که آیا به کمینه استفاده از توابع بولی رسیدهایم یا نه. این روش گاهی با روش جدولی نیز نام برده میشود.
این الگوریتم از دو قسمت تشکیل شدهاست:
1- یافتن تمامی دلالتکنندههای نخستین (Prime Implicant)
۲- تمامی آن دلالتکنندهها را در جدول دلالتکنندههای نخستین قرار دهیم تا دلالتکنندههای ضروری را بیابیم.
اگرچه این الگوریتم در مقایسه با جدول کارنو برای دادههای با بیشتر از ۴ متغیر عملیتر است، این الگوریتم به دلیل این که مسئلهای که حل میکند انپی سخت است، محدودیت دارد و زمان اجرایی آن به صورت نمایی رشد میکند. میتوان نشان داد که برای تابعی با n متغیر، مقدار کران بالا برای دلالتکنندههای نخستین برابر exp(3،n)/n است. بهطور مثال اگر n=32 حدوداً exp(10،15)*6.5 دلالتکنندهی نخستین خواهیم داشت.
کوچک کردن یک تابع دلخواه
A | B | C | D | f | ||
---|---|---|---|---|---|---|
m0 | ۰ | ۰ | ۰ | ۰ | ۰ | |
m1 | ۰ | ۰ | ۰ | ۱ | ۰ | |
m2 | ۰ | ۰ | ۱ | ۰ | ۰ | |
m3 | ۰ | ۰ | ۱ | ۱ | ۰ | |
m4 | ۰ | ۱ | ۰ | ۰ | ۱ | |
m5 | ۰ | ۱ | ۰ | ۱ | ۰ | |
m6 | ۰ | ۱ | ۱ | ۰ | ۰ | |
m7 | ۰ | ۱ | ۱ | ۱ | ۰ | |
m8 | ۱ | ۰ | ۰ | ۰ | ۱ | |
m9 | ۱ | ۰ | ۰ | ۱ | x | |
m10 | ۱ | ۰ | ۱ | ۰ | ۱ | |
m11 | ۱ | ۰ | ۱ | ۱ | ۱ | |
m12 | ۱ | ۱ | ۰ | ۰ | ۱ | |
m13 | ۱ | ۱ | ۰ | ۱ | ۰ | |
m14 | ۱ | ۱ | ۱ | ۰ | x | |
m15 | ۱ | ۱ | ۱ | ۱ | ۱ |
بهسادگی میتوان سادهشدهی عبارت بالا را با توجه به جدول بالا، با جمع زدن مینترمها (minterm) یافت. بهنوعی که آن تابع به صورت یک عبارت واحد نشان داده میشود:
بهطور قطع این عبارت سادهترین حالت نیست و برای ساده کردن آن میبایست مینترمها را در جدول مربوطه قرار داد و همچنین ترمهای غیرمهم نیز در این جدول قرار داد و سپس این دو را با یکدیگر ترکیب کرد:
تعداد ۱ها | مین ترم | نمایش در مبنای ۲ |
---|---|---|
۱ | m4 | ۰۱۰۰ |
m8 | ۱۰۰۰ | |
۲ | m9 | ۱۰۰۱ |
m10 | ۱۰۱۰ | |
m12 | ۱۱۰۰ | |
۳ | m11 | ۱۰۱۱ |
m14 | ۱۱۱۰ | |
۴ | m15 | ۱۱۱۱ |
حال باید به ترکیب در جدول پرداخت. اگر دو مینترم فقط در یک رقم با یکدیگر تفاوت داشتند، آن دو را در هم ادغام کرده و جای رقم متفاوت، «-» را قرار میدهیم. و آنها که مورد استفاده قرار نمیگیرند را با «*» مشخص میکنیم.
تعداد ۱ها | مین ترم | نمایش مبنای ۲ | دلالت کنندهٔ به اندازه ۲ | دلالت کنندهٔ به اندازه ۴ |
---|---|---|---|---|
۱ | m4 | ۰۱۰۰ | m(4،12) -100* | --m(8،9،10،11) 10* |
m8 | ۱۰۰۰ | -m(8،9) 100 | m(8،10،12،14) 1--0* | |
m(8،10) 10-0 | --m(8،9،10،11) 10* | |||
m(8،12) 1-00 | ||||
۲ | m9 | ۱۰۰۱ | -m(8،9) 100 | --m(8،9،10،11) 10* |
m(9،11) 10-1 | m(10،11،14،15) 1-1-* | |||
m10 | ۱۰۱۰ | m(8،10) 10-0 | --m(8،9،10،11) 10* | |
-m(10،11) 101 | --m(8،9،10،11) 10* | |||
m(10،14) 1-10 | ||||
m12 | ۱۱۰۰ | m(4،12) -100* | -- | |
m(8،12) 1-00 | ||||
m(12،14) 11-0 | -- | |||
۳ | m11 | ۱۰۱۱ | m(9،11) 10-1 | --m(8،9،10،11) 10* |
-m(10،11) 101 | --m(8،9،10،11) 10* | |||
m(11،15) 1-11 | ||||
m14 | ۱۱۱۰ | m(10،14) 1-10 | ||
m(12،14) 11-0 | -- | |||
۴ | m15 | ۱۱۱۱ | m(11،15) 1-11 | -- |
m(14،15) 111- | - |
تا به اینجا در جدولی که داشتهایم، دیگر نمیتون مینترمها را بیشتر از این با هم ترکیب کرد. پس در اینجا جدولی را برای دلالتکنندههای نخستین ضروری درست میکنیم. در این جدول، از مینترمهایی که در قبل داشتیم و آز آنها در ترکیب جدید استفاده نشده استفاده میکنیم. در این قسمت ترمهای غیرمهم را حذف میکنیم، چون اهمیتی ندارند.
۴ | ۸ | ۱۰ | ۱۱ | ۱۲ | ۱۵ | => | A | B | C | D | ||
m(4،12)* | X | X | -۱۰۰ | => | - | ۱ | ۰ | ۰ | ||||
m(8،9،10،11) | X | X | X | ۱۰-- | => | ۱ | ۰ | - | - | |||
m(8،10،12،14) | X | X | X | ۱--۰ | => | ۱ | - | - | ۰ | |||
m(10،11،14،15)* | X | X | X | ۱-۱- | => | ۱ | - | ۱ | - |
با توجه به جدول بالا، میتوان دو عبارت ساده را برای تابع مد نظر در نظر گرفت. هر دوی این نمایشها درست هستند:
این دو تابع سادهشده، در اصل همان تابع ابتدایی هستند:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.