نقشهٔ کارنو: ایده و دو و سه متغیره

مسئله‌ای که کارنو حل می‌کند

ساده‌سازی جبری (فصل ۲) به «دیدن الگو» وابسته است و برای چهار متغیر خسته‌کننده می‌شود. نقشهٔ کارنو همان الگوی پوشش ($xy+x{y}^{\prime }=x$) را به یک کار دیداری تبدیل می‌کند: خانه‌هایی که فقط در یک لیترال فرق دارند را کنار هم می‌چینی تا پوشش‌ها خودشان را نشان دهند.

چرا ترتیب گری؟

اگر ستون‌ها را ۰۰، ۰۱، ۱۱، ۱۰ بچینی (گری)، هر دو ستون کنار هم فقط یک بیت فرق دارند. حالا هر دو خانهٔ افقیِ کنار هم، دو مین‌ترمی‌اند که در یک لیترال فرق می‌کنند — یعنی دقیقاً الگوی پوشش. نقشه چیزی نیست جز «جدول درستی‌ای که پوشش‌ها در آن همسایه‌اند».

روش پنج‌قدمه

1. بچین: به‌ازای هر مین‌ترم تابع، در خانهٔ همان شماره ۱ بگذار (بقیه صفر).
2. گروه بساز: یک‌ها را در گروه‌های مستطیلیِ ۱، ۲، ۴ یا ۸تایی (توان‌های ۲) بپوشان؛ هر گروه باید تا جای ممکن بزرگ باشد.
3. بپیچ: لبه‌های نقشه به هم وصل‌اند — ستون اول و آخر همسایه‌اند، سطر اول و آخر همسایه‌اند.
4. بخوان: از هر گروه، لیترال‌هایی که در کل گروه ثابت مانده‌اند را AND کن؛ لیترالی که عوض شده حذف می‌شود.
5. جمع بزن: OR همهٔ گروه‌ها، جواب ساده‌شده است.

مثال ذهنی سه‌متغیره

تابع $F=\Sigma m(0,1,4,5)$: سطرهای ۰۰۰، ۰۰۱، ۱۰۰، ۱۰۱. در نقشهٔ سه‌متغیره (سطرها x، ستون‌ها yz با ترتیب گری)، این چهار خانه دو ستونِ ۰۰ و ۰۱ را پر می‌کنند و یک گروه چهارتایی می‌سازند که در آن فقط $y^{\prime }$ ثابت است. پس $F=y^{\prime }$ — سه متغیر به یک لیترال رسید!

خودت امتحان کن: کاوشگر کارنو

نقشهٔ آماده (۱، ۳، ۵، ۷) جوابش z است — خودت بررسی‌اش کن. بعد نقشه را پاک کن و تابع خودت را بچین: آیا گروهی که می‌سازی با عبارت پیشنهادی کاوشگر یکی است؟