جدول کارنو

نمونه‌ای از یک جدول کارنو

جدول کارنو روشی است برای ساده سازی توابع جبر بول^[۱] که بوسیله موریس کارنو^[۲] در سال ۱۹۵۳ ارائه شد. این روش کامل شده دیاگرام ویچ است که بوسیله ادوارد ویچ^[۳] در سال ۱۹۵۲ ارائه شده بود. جدول کارنو نیاز به محاسبات طولانی را کاهش داده و اجازه مشخص کردن و حذف کردن سریع وضعیت رقابتی^[۴] را می‌دهد.

مقادیر بولی از جدول درستی^[۵] و با توجه به اصول کد گری^[۶] به جدول کارنو انتقال می‌یابند. داده‌ها در جدول کارنو که ۲ⁿ سلول دارد چیده می‌شوند و مینترم‌ها ^[۷] بر اساس اصول جبر بول ساخته می‌شوند.

[ویرایش] مثال

مثال زیر یک تابع ساده نشده جبر بول را با متغیرهای بولی A،B،C،D نشان می‌دهد.
$f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)$
جدول صحت تابع به صورت زیر ساخته می‌شود:

#	$A$	$B$	$C$	$D$	$f(A, B, C, D)$
۰	۰	۰	۰	۰	۰
۱	۰	۰	۰	۱	۰
۲	۰	۰	۱	۰	۰
۳	۰	۰	۱	۱	۰
۴	۰	۱	۰	۰	۰
۵	۰	۱	۰	۱	۰
۶	۰	۱	۱	۰	۱
۷	۰	۱	۱	۱	۰
۸	۱	۰	۰	۰	۱
۹	۱	۰	۰	۱	۱
۱۰	۱	۰	۱	۰	۱
۱۱	۱	۰	۱	۱	۱
۱۲	۱	۱	۰	۰	۱
۱۳	۱	۱	۰	۱	۱
۱۴	۱	۱	۱	۰	۱
۱۵	۱	۱	۱	۱	۰

متغیرها می‌توانند در ۱۶ حالت مختلف ترکیب شوند پس جدول ما ۱۶ سلول دارد. متناظر با مینترم‌هایی که تابع در آنها یک است، خانه‌های جدول را نیز مانند شکل یک می‌کنیم. مابقی خانه‌های جدول را نیز صفر قرار می‌دهیم. سپس باید سلول‌های جدول را به دسته‌های دوتایی، چهارتایی یا هشت تایی تقسیم کنیم. دقت کنید که فقط سلول‌هایی که همسایه هستند قابل انتخاب هستند. در ضمن سلول‌های بالایی با پایینی و سلول‌های راستی با چپی نیز همسایه هستند و قابل دسته بندی هستند. در این مثال سلول‌های قرمز و قهوه‌ای را می‌توان با هم دسته بندی کرد. اگر این عمل را انجام دهیم جواب نهایی ساده تر می‌شود ولی اجباری در این کار نیست.
پس از عملیات دسته بندی باید مینترم متناظر به هر دسته را بنویسیم که در این مثال:

سلول‌های آبی: ^'BCD
سلول های قهوه ای و سبز: ^'AB
سلول های قرمز و قهوه ای: ^'AC

سپس تابع بولی ساده شده را بر اساس حاصل جمع حاصل ضرب ها می نویسیم:
'f(a،b،c،d)=BCD^' + AB^' + AC