کارنوی چهارمتغیره و ایمپلیکانت‌ها

نقشهٔ ۴×۴

چهار متغیر ($w,x,y,z$) یعنی شانزده خانه: سطرها با wx و ستون‌ها با yz، هر دو با ترتیب گری (۰۰، ۰۱، ۱۱، ۱۰). قانون‌های جدیدی که اضافه می‌شود:

• گروه‌های ۸تایی هم مجازند (یک سطر/ستون کامل یا نیم‌نقشه).
• پیچش جدی‌تر می‌شود: چهار گوشهٔ نقشه با هم همسایه‌اند و یک گروه چهارتایی می‌سازند!
• هر گروه ۲تایی یک لیترال، ۴تایی دو لیترال و ۸تایی سه لیترال را حذف می‌کند.

ایمپلیکانت اول و ضروری

• ایمپلیکانت: هر گروه معتبر (هر جملهٔ ضربی که تابع را پوشش می‌دهد).
• ایمپلیکانت اول: گروهی که نتوان آن را بزرگ‌تر کرد و همچنان معتبر ماند — یعنی حذف هیچ لیترال دیگری ممکن نیست.
• ایمپلیکانت ضروری: ایمپلیکانت اولی که تنها پوشش‌دهندهٔ دست‌کم یک مین‌ترم باشد. این‌ها حتماً در جواب نهایی هستند.

روش پوشش: اول ضروری‌ها را بردار (چون مجبوری)، بعد بقیهٔ مین‌ترم‌ها را با کمترین ایمپلیکانت‌های اولِ باقی‌مانده بپوشان. جوابی که همهٔ مین‌ترم‌ها را با کمترین جمله بپوشاند، حداقل است.

چه چیزهایی گروه نیست؟

سه خطای رایج: گروه مورب (فقط مستطیل مجاز است)، گروهی که صفر را هم شامل شود (فقط یک‌ها — مگر در POS که برعکس است)، و گروهی که از خانه‌های تکراریِ غیرمجاور ساخته شده. هر گروه باید دقیقاً یک مستطیلِ توان‌دویی از یک‌ها باشد.