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

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

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

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

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

پیچیدگی

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

مثال

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

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

$f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,$

	A	B	C	D		f
m0	۰	۰	۰	۰		۰
m1	۰	۰	۰	۱		۰
m2	۰	۰	۱	۰		۰
m3	۰	۰	۱	۱		۰
m4	۰	۱	۰	۰		۱
m5	۰	۱	۰	۱		۰
m6	۰	۱	۱	۰		۰
m7	۰	۱	۱	۱		۰
m8	۱	۰	۰	۰		۱
m9	۱	۰	۰	۱		x
m10	۱	۰	۱	۰		۱
m11	۱	۰	۱	۱		۱
m12	۱	۱	۰	۰		۱
m13	۱	۱	۰	۱		۰
m14	۱	۱	۱	۰		x
m15	۱	۱	۱	۱		۱

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

$f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'CD'+AB'CD+ABC'D'+ABCD.$

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

تعداد ۱ها	مین ترم	نمایش در مبنای ۲
۱	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

۱-۱-

=>

۱

-

۱

-

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

$f_{A,B,C,D}=BC'D'+AB'+AC\$

$f_{A,B,C,D}=BC'D'+AD'+AC.\$

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

$f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD.\$

منابع

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

پیوندها

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