1. ما هي خريطة كارنو
خريطة كارنو هي جدول صواب أُعيد رسمه على هيئة شبكة. قدّمها موريس كارنو في مختبرات بِل عام 1953 وسيلةً لتبسيط دارات التبديل بالنظر، وما زالت أسرع طريقة لتصغير دالة بوليانية صغيرة يدوياً: لا جبر، ولا قوانين تُحفظ، بل مستطيلات فحسب.
كل خلية في الخريطة تحمل سطراً واحداً من جدول الصواب. وما يجعل الخريطة أكثر من مجرد إعادة ترتيب هو الترتيب الذي تُوضع به تلك السطور: الخليتان المتجاورتان تختلفان في متغيّر واحد بالضبط.
هذه الخاصية وحدها تؤدي العمل كله. فإذا كانت خليتان متجاورتان صادقتين معاً، فالمتغيّر الذي يتبدّل بينهما لا يمكن أن يكون سبب صدق العبارة، فيسقط ويغطي حدٌّ واحد الخليتين معاً. وهكذا يصير التبسيط مسألة رسم أكبر ما يمكن من المستطيلات.
2. لماذا يبدو ترتيب الأعمدة غريباً
أعمدة خريطة كارنو لا تعدّ 00 ثم 01 ثم 10 ثم 11، بل تسير 00، 01، 11، 10 - وهو ترميز غراي المنعكس، ترتيب يختلف فيه كل قيمة عن التالية ببتّ واحد. فالعدّ الثنائي كان سيضع 01 بجوار 10، وهما مختلفتان ببتّين، فلا تقول الخلايا المتجاورة شيئاً.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
الحواف متجاورة أيضاً. فالعمود الأول والعمود الأخير يختلفان في متغيّر واحد، وكذلك الصف الأعلى والصف الأدنى، ولذلك تستطيع المجموعة أن تخرج من حافة وتكمل عند الأخرى - وهذا سبب كون أركان الخريطة الأربعة في خريطة بأربعة متغيّرات مجموعةً واحدة. خريطة كارنو مرسومة في الحقيقة على سطح طارة، والورقة المستوية مجرّد تيسير.
3. تجميع الآحاد
لقراءة أقصر مجموع جداءات من الخريطة، غطِّ كل خلية تحمل 1 بمجموعات مستطيلة، وفق أربع قواعد:
- المجموعة مستطيل من 1 أو 2 أو 4 أو 8 … خلية - قوة للعدد اثنين على كل ضلع.
- يجوز للمجموعة أن تلتفّ حول حواف الخريطة أفقياً أو رأسياً أو في الاتجاهين معاً.
- يجوز للمجموعات أن تتداخل. تغطية خلية مرتين لا تكلّف شيئاً، أما ترك خلية دون تغطية فيغيّر الدالة.
- اجعل كل مجموعة أكبر ما يمكن، ثم استخدم أقلّ عدد من المجموعات يكفي لتغطية كل الآحاد.
كل مجموعة تصير حدّاً واحداً. وتُقرأ بالسؤال عن المتغيّرات التي تبقى ثابتة في المجموعة كلها: تلك تظهر في الحدّ - كما هي حيث تساوي 1، ومنفيّة حيث تساوي 0 - وكل متغيّر يتبدّل يسقط. مجموعة من خليتين تفقد متغيّراً واحداً، ومن أربع تفقد اثنين، ومن ثمانٍ تفقد ثلاثة. والعبارة الدنيا هي فصل هذه الحدود.
4. مثال محلول
لنأخذ (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). خريطتها بأربعة متغيّرات: A وB على الصفوف، وC وD على الأعمدة.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
مجموعتان تغطّيان كل الآحاد. الأولى كتلة من أربع خلايا عند تقاطع الصفين اللذين فيهما A = 0 مع العمودين اللذين فيهما C = 1: يتبدّل داخلها كلٌّ من B وD فيسقطان، ويكون الحدّ ¬A ∧ C. والثانية هي الصف كله حيث A وB تساويان 1، ممتداً على الأعمدة الأربعة: يتبدّل فيه C وD فيبقى A ∧ B.
إذن الصيغة الدنيا هي (¬A ∧ C) ∨ (A ∧ B). أما الحدّ الثالث في العبارة الأصلية، B ∧ C ∧ D، فقد تلاشى: كل خلية كان يغطّيها كانت مغطّاة أصلاً بإحدى المجموعتين. هكذا يبدو الامتصاص حين تراه بعينك.
5. اللوازم الأوّلية والأساسية
المجموعة التي لا يمكن تكبيرها أكثر تُسمّى لازماً أوّلياً. وحصر اللوازم الأوّلية هو النصف السهل من المسألة؛ أما اختيار ما يُبقى منها فهو النصف الذي يُخطَأ فيه.
إذا كانت خلية ما لا يغطّيها سوى لازم أوّلي واحد، فذلك اللازم أساسي: لا يمكن لأي صيغة دنيا الاستغناء عنه، إذ لا شيء آخر يغطّي تلك الخلية. خذ اللوازم الأساسية أولاً، ثم غطِّ ما تبقّى بأقلّ عدد ممكن من المجموعات الباقية.
الأسلوب الجشع - أن تأخذ في كل مرة أكبر مجموعة متاحة - مغرٍ ولا ينجح دائماً. ففي جدول دوري لا يكون فيه أي لازم أساسياً وتُغطّى كل خلية مرتين، قد ينتهي الاختيار الجشع بحدّ زائد عن أفضل إجابة. أما خريطة هذا الموقع فتفحص كل الخيارات المتبقّية فحصاً شاملاً، وهو أمر لا يكلّف شيئاً عند أربعة متغيّرات.
6. تجميع الأصفار بدلاً من ذلك
كل ما سبق ينطبق على الأصفار بالقدر نفسه. غطِّها بالمستطيلات ذاتها، واقرأ كل مجموعة بنفي حدودها الأوّلية - المتغيّر الذي يساوي 1 في المجموعة كلها يظهر منفيّاً، والذي يساوي 0 يظهر كما هو - ثم اربط المجموعات بـ ∧ بدل ∨.
والناتج جداء مجاميع: عطف من فصول يكون كاذباً في الخلايا التي تكذب فيها العبارة تماماً، ومن ثمّ صادقاً في كل ما عداها. وأيّ الصيغتين أقصر يتوقف على الدالة - فالعبارة قليلة الآحاد يقصر فيها مجموع الجداءات، والقليلة الأصفار يقصر فيها جداء المجاميع - لذا يجدر أن تقرأ الصيغتين من الخريطة قبل أن تختار.
7. خرائط أكبر وخلايا لا تهمّ
يمكن رسم خمسة وستة متغيّرات على هيئة خريطتين أو أربع خرائط بأربعة متغيّرات مكدّسة فوق بعضها، مع اعتبار الخلايا المتقابلة في الطبقات المتجاورة متجاورة. وهذا ينجح، غير أن التجاور الذي جعل الطريقة مرئية يصير شيئاً يُتذكَّر لا شيئاً يُرى. وفيما وراء ذلك تؤدي خوارزمية كواين-مكلاسكي العمل نفسه في صورة جدول: فهي الصيغة الآلية لهذا التجميع بعينه، وهي ما يعمل خلف الخرائط هنا.
يضيف تصميم العتاد فكرة أخرى. فبعض تركيبات الدخل لا تحدث أبداً - فالرقم العشري المرمّز ثنائياً لا يكون 1010 - ولذلك لا يعني المصمّم ما تفعله الدارة بها. تُعلَّم تلك الخلايا بحرف X ويجوز قراءتها بأي القيمتين، أيّهما يكبّر المجموعات. أما خرائط هذه الحاسبة فتُبنى من صيغة تمنح كل إسناد قيمة، فلا توجد فيها خلية لا تهمّ.
8. جرّبها بنفسك
اكتب في الحاسبة عبارة من متغيّرين إلى أربعة، فتُرسم خريطتها تحت جدول الصواب، وكل مجموعة محاطة بلونها الخاص والصيغة الدنيا مكتوبة أسفلها. بدّل إلى جداء المجاميع لترى الأصفار مجمّعة بدلاً من الآحاد.