الگوریتم کواین-مک‌کلاسکی

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

این الگوریتم از دو قسمت تشکیل شده‌است:

1- یافتن تمامی دلالت‌کننده‌های نخستین (Prime Implicant)

۲- تمامی آن دلالت‌کننده‌ها را در جدول دلالت‌کننده‌های نخستین قرار دهیم تا دلالت‌کننده‌های ضروری را بیابیم.

پیچیدگی 
اگرچه این الگوریتم در مقایسه با جدول کارنو برای داده‌های با بیشتر از ۴ متغیر عملی‌تر است، این الگوریتم به دلیل این که مسئله‌ای که حل می‌کند ان‌پی سخت است، محدودیت دارد و زمان اجرایی آن به صورت نمایی رشد می‌کند. می‌توان نشان داد که برای تابعی با n متغیر، مقدار کران بالا برای دلالت‌کننده‌های نخستین برابر exp(3،n)/n است. به‌طور مثال اگر n=32 حدوداً exp(10،15)*6.5 دلالت‌کننده‌ی نخستین خواهیم داشت.

مثال

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

کوچک کردن یک تابع دلخواه

به‌سادگی می‌توان ساده‌شده‌ی عبارت بالا را با توجه به جدول بالا، با جمع زدن مین‌ترم‌ها (minterm) یافت. به‌نوعی که آن تابع به صورت یک عبارت واحد نشان داده می‌شود:

به‌طور قطع این عبارت ساده‌ترین حالت نیست و برای ساده کردن آن می‌بایست مین‌ترم‌ها را در جدول مربوطه قرار داد و همچنین ترم‌های غیرمهم نیز در این جدول قرار داد و سپس این دو را با یکدیگر ترکیب کرد:

حال باید به ترکیب در جدول پرداخت. اگر دو مین‌ترم فقط در یک رقم با یکدیگر تفاوت داشتند، آن دو را در هم ادغام کرده و جای رقم متفاوت، «-» را قرار می‌دهیم. و آن‌ها که مورد استفاده قرار نمی‌گیرند را با «*» مشخص می‌کنیم.

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

با توجه به جدول بالا، می‌توان دو عبارت ساده را برای تابع مد نظر در نظر گرفت. هر دوی این نمایش‌ها درست هستند:

این دو تابع ساده‌شده، در اصل همان تابع ابتدایی هستند:

منابع 
۱. نلسون، کتاب تحلیل و طراحی مدارهای دیجیتال

پیوندها 
 پیاده سازی الگوریتم کواین مک کلاسکی با جستجوی تمام راه حل‌ها.
 All دربارهٔ کواین مک کلاسکی.
 کوچک کنندهٔ جدول کارنو.
 ارائه‌ای بر الگوریتم کواین مک کلاسکی
 Python پیاده سازی
 پیاده سازی الگوریتم کواین مک کلاسکی 
 مقاله اول و مقاله دوم
 بول‌های کوچک
 ماژول پرل
 برای مشاهدهٔ مثالی کامل با توضیحات مفصل به آدرس روبرو مراجعه فرمایید visit: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm

جبر بولی
مقاله‌های ایجاد شده توسط ایجادگر
ویلارد کواین