جدول أو خريطة أو مخطط كارنو فايتش أو مخطط كارنو كما يسمى عادة هي خريطة تستعمل في الرياضيات الثنائية أو ما يسمى أيضا بالجبر المنطقي و ذلك لإختصار بعض الجمل أو التعابير المنطقية. عادة ما يستعمل جدول كارنو في المعادلات التي تحتوي بين متغيران و أربع متغيرات. نظريا طبعا يمكن إستعماله لعدد أكبر من المتغيرات و لكن ذلك ليس متداولا حيث أنه في هذه الحالات هناك طرق أكثر فعالية للإختزال.
فهرس |
شرح تطبيقي و مثال في كيفية استعمال الجدول
لنعتبر الدالة المنطقية 
و كذلك الدالة المنطقية 
. و لنفترض أنه لدينا جدول الحقيقة لكل من الدالتين كما هو مبين في الجدولين أسفله:
| Y | X1 | X2 | X3 | X4 | رقم السطر |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 2 |
| 1 | 1 | 1 | 0 | 0 | 3 |
| 1 | 0 | 0 | 1 | 0 | 4 |
| 0 | 1 | 0 | 1 | 0 | 5 |
| 0 | 0 | 1 | 1 | 0 | 6 |
| 0 | 1 | 1 | 1 | 0 | 7 |
| 1 | 0 | 0 | 0 | 1 | 8 |
| 0 | 1 | 0 | 0 | 1 | 9 |
| 0 | 0 | 1 | 0 | 1 | 10 |
| 1 | 1 | 1 | 0 | 1 | 11 |
| 1 | 0 | 0 | 1 | 1 | 12 |
| 0 | 1 | 0 | 1 | 1 | 13 |
| 0 | 0 | 1 | 1 | 1 | 14 |
| 1 | 1 | 1 | 1 | 1 | 15 |
| Y | X1 | X2 | X3 | X4 | رقم السطر |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 2 |
| 1 | 1 | 1 | 0 | 0 | 3 |
| 1 | 0 | 0 | 1 | 0 | 4 |
| 0 | 1 | 0 | 1 | 0 | 5 |
| 1 | 0 | 1 | 1 | 0 | 6 |
| 0 | 1 | 1 | 1 | 0 | 7 |
يمكن أن نفهم الجدولين أعلاه بهذه الطريقة: أنه لدينا مثلا جهاز إلكتروني بأربع متغيرات أو متغيرين إثنين أي مداخل. مثلا أربع أزرار يمكن أن تكون مضغوطة (أي تساوي 1) أو غير مضغوطة (تساوي 0). نسمي هذه الأزرار X1...X4 كما يمكن فهم Y على أنه مخرج هذا الجهاز الإلكتروني مثلا ديود مضيئ حيث 1 = مضيء و 0 = منطفئ.
السطر الأول في الجدول الأول (أي الجهاز ذو أربع أزرار) يقول أنه إذا كانت كل المتغيرات Xi صفرا أي إذا كانت كل الأزرار غير مضغوطة فإن الديود يكون مضيئا. الآن نطرح السؤال ما هي العلاقة بين مداخل النظام أي المتغيرات X و مخرجه Y ? العلاقة مبينة في الجداول أعلاه و لكننا نريد أن نكتب جملة أو معادلة تعتمد على الجبر البولي و تصف لنا هذه العلاقة. يمكن في هذه الحالة مباشرة من الجدول كتابة المعادلة أو التعبير و ذلك بطريقتين تسمي الأشكال النمطية أو القياسية Normalformen:
- إما أن نكتبها بنمط صيغة التقاطع القياسية أو الصيغة القياسية للتقاطع konjunktive Normalform
- أو نكتبها بنمط صيغة الاجتماع القياسية أو الصيغة القياسية للاجتماع disjunktive Normalform
المشكلة في هذين النمطين هو أن المعادلات و التعبيرات قابلة للإختزال.
لسائل أن يسأل لماذا يشكل ذلك مشكلة? و لماذا نريد الحصول على معادلة مختزلة قدر الإمكان? أحد الأسباب هو ،إن عدنا إلى جهازنا الإلكتروني, أن كل عملية ضرب أو جمع في المعادلة تقابلها في الجهاز وحدة تقوم بذلك (قلابات أو معالج بيانات أو دائرة كهربائية مثلا). و استعمال عدد كبير من هذه الوحدات يفضي إلى بناء أجهزة غير مربحة تجاريا لكثر المكونات المستعملة كما أنها تكون معرضة أكثر للعطب و كبيرة الحجم و هذه كلها خصائص لا نريدها في أجهزتنا الرقمية الحديثة.
عن طريق جدول كارنو فايتش يمكننا مباشرة كتابة تعبير أو معادلة (في الحقيقة هي ليست معادلة بالمعنى الرياضي للكلمة) مختصرة.
ما يجب الإنتباه إليه عند استعمال جدول كارنو:
- جدول كارنو لا يعطينا معادلة مختزلة لأقصى حد. أي أنه من الممكن أنه بعد استعمال هذه الطريقة أنه يكون هناك قابلية للإختزال
- ترتيب المتغيرات يجب أن يكون مثل ما هو في جدول الحقيقة حتى يقابل ذلك الترتيب في مخطط كارنو أو جدول كارنو.( الأسباب تعود إلى بنية المخطط و الجبر البولي). في حالة تغيير تسلسل المتغيرات أي مثلا X1 X2 X3 X4 عوض X4 X3 X2 X1 فإن مخطط كارنو يتغير (ترقيم الخانات الأزرق) و لكن يمكن فهم ذلك بشيء من التأمل.
- لا يمكن إختزال أو تجميع إلا عدد يساوي قوات 2 من الخانات أو المربعات أي 1,2,4,8 إلخ...
خريطة كارنوف...(Karnaugh map) :
خريطة كارنوف أو خريطة K هي طريقة مرئية لتبسيط التعبيرات الجبرية وتماثل جدول الحقيقة لأنها تعطي لنا كل القيم المحتملة للمداخل ونتيجة الخرج لكل قيمة . وبدلاَ من تنظيمها على شكل أعمدة وصفوف مثل جدول الحقيقة . فإن خريطة كارنوف عبارة عن مصفوفة (array) من الخلايا (cells) ، وتمثل كل خلية القيمة الثنائية لإحدى تشكيلات المداخل. وعدد الخلايا في خريطة كارنوف يساوي عدد التشكيلات المحتملة للمداخل. وخريطة كارنوف يمكن استخدامها مع تعبيرات بوليانية لها متغيران .. ثلاثة.. و حتى سبعة. ونكتفي بأربعة متحولات فقط لتوضيح أساسيات التبسيط . وسنورد لمحة بسيطة عن خمسة وستة متحولات ...
التبسيط باستخدام خريطة كارنوف Simplification using Karnaugh-map :
عدد الخلايا في خريطة كارنوف يعتمد على عدد التشكيلات المتغيرات (المداخل), وكمثال على ذلك الشكل (1-1),فهناك متغيران فقط هما(A,B).. وبناءَ على ذلك فإن خريطة كارنوف تحتوي على أربعة تشكيلات (00,01,10,11)
وكل خلية في خريطة كارنوف ذات المتغيرين تمثل واحد من الأربعة تشكيلات للدخل وعملياَ علامات الدخل (Input Labels) توضع خارج الخلايا كما خو موضح بالشكل (1-2) وتطبق على كل من الصف والعمود للخلايا ، فمثلاَ الصف الذي أمامه A' يطبق على الخلايا العليا ، بينما الذي أمامه A يطبق على الخلايا السفلى . ونرى في أعلى الخريطة المتغير B' يطبق على الخلايا التي على اليسار, بينما النتغير B يطبق على الخلايا التي على اليمين ،وكمثال .. فإن الخلية السفلى التي على اليمين تمثل تشكيلة الدخل AB
الشكل (1-3-أ) ، (1-3- ب) يوضحان هيئة خريطة كارنوف لثلاث متغيرات (8 خلايا), وأربعة متغيرات (16 خلية)
وبعد التعرف على كيفية إنشاء خريطة كارنوف ، سوف نرى كيف يمكن أن تستخدم لتبسيط الدوال المنطقية ، وكمثال على ذلك نفترض أننا نريد تصميم دالة منطقية لها جدول الحقيقة الموضح في الشكل (1-4- أ).
الخطوة الأولى : الحصول على التعبير البولياني من جدول الحقيقة ،وذلك بكتابة التشكيلة التي أمامها (1) في الخرج وبعد ذلك نجمع هذه التشكيلات باستخدام بوابة OR كما في الشكل(1-4- ب) والدالة المنطقية المكافئة لهذه المعادلة موضحة في الشكل(1-4- ج).
الخطوة الثانية : تمثيل هذا التعبير البولياني على خريطة كارنوف لمتغيرين كما نرى في الشكل (1-4- د) .
عند تمثيل التعبير البولياني على خريطة كارنوف يجب أن نتذكر أن كل خلية تمثل تشكيلة من التشكيلات الأربع المحتملة للمدخلات في خدول الحقيقة . الخرج (1) في جدول الحقيقة يجب أن يظهر (1) في الخلية المكافئة له على خريطة كارنوف ، والخرج (0) في جدول الحقيقة يجب أن يظهر (0) في الخلية المكافئة له على خريطة كارنوف, وبناءً على ذلك فإن (1) سوف يظهر في الخلية السفلى على اليسار (يمثل'AB) ، وفي الخلية السفلى على اليمين (يمثل AB). والتشكيلات الأخرى للدخل (A'B' ، A'B) وكلاهما يعطي (0) في الخرج ، وبناءً عليه يجب وضع (0) في هاتين الخليتين العلويتين.
تبسيط المعادلات البوليانية بصفة عامة يمكن الحصول عليه عن طريق تطبيق قاعدة المتممات (Complements) ، والتي تقول أن A'+A=1 . والآن وبعد تمثيل المعادلة البوليانية على خريطة كارنوف كما في الشكل (1-4- د) ، الخطوة الثانية هي تجميع الحدود ثم نحدد العامل المشترك بينها ، فإذا نظرنا إلى خريطة كارنوف في الشكل(1-4- د) فسوف نرى أن الخلايا المتجاورة (adjacent cells) تختلف في متغير واحد فقط ، وهذا يعني أننا لو حركنا أي منهما من مكانه إلى الخلية المجاورة له رأسياً أو أفقياً ، فلن يحدث تغيير إلاَ في متحول واحد فقط ، وبتجميع الخلايا المتجاورة المحتوية على (1) كما نرى من الشكل (1-4- ھ) فإنه يمكن تبسيط الخلايا باستخدام قاعدة المتممات وجعلها حد واحد ، وفي هذا المثال الخلايا AB',AB تحتوي على B' ، B وبالتالي يتم حذف هذه المتممات ، وتكون النتيجة A كما يلي : Y = AB'+AB (الأزواج المجمعة) ('Y = A(B+B Y = A*1 = A
هذا التحليل يمكن استنتاجه بدراسة جدول الحقيقة للدالة الموضحة في الشكل (1-4- أ) والذي نرى فيه أن الخرج (Y) يتبع تماماً الدخل (A), وبناءً على ذلك تكون الدالة المكافئة كما هو موضح في الشكل (1-4- و).
كيفية التجميع في مخططات كارنوف:
الآحاد (1's) في خريطة كارنوف يمكن أن تجمع كأزواج (مجموعة من أثنين أو مجموعات من أربعة أو ثمانية أو ستة عشر وهكذا لكل قوى 2 . الشكل (1-6) يوضح بعض الأمثلة للتجميع. وكيف أن خريطة كارنوف تستخدم لتبسيط التعبيرات البوليانية الكبيرة ، لاحظ أن المجموعات الكبيرة أي التي تحتوي على عدد كبير من الآحاد (1's) تعطي لنا حد صغير وعليه تكون البوابات المستخدمة في التصميم لها مدخلات قليلة . ولهذا السبب يجب أن نبدأ بالبحث عن المجموعات التي تحتوي على أكبر عدد من الآحاد ، فإن لم نجد نبحث عن أقل وهكذا .
أمثلة:
مثال (1-1): صمم دالة منطقية في أبسط صورة لجدول الحقيقة الموضح في الشكل (1-5- أ) مبيناً كل خطوة في عملية التبسيط. الحل: لدينا هنا ثلاث متغيرات ، والخطوة الأولى هي رسم خريطة كارنوف لثلاث متغيرات ، كما هو موضح في الشكل (1-5- ب). الخطوة الثانية أن ننظر إلى الخرج الذي يساوي (1) في جدول الحقيقة في الشكل (1-5- أ) ثم نقوم بوضع هذه الآحاد في الخلايا المكافئة لها على خريطة كارنوف كما هو موضح في الشكل (1-5- ب) ، وبعد وضع (0) في الخلايا الفارغة المتبقية ، نجمع الآحاد في شكل أزواج كما في الشكل (1-5- ب) ، ثم نحدد من خلال الصف والعمود المتغيرات المشتركة في هذه المجموعات (الأزواج) لنرى أي متغيَر سوف يتم حذفه تبعاَ لقاعدة المتممات ففي المجموعة التي على اليمين A', A يتم حذفهم والنتيجة B'C ، وفي المجموعة التي على اليسار يتم حذف C,C' والنتيجة 'AB والحدود السابقة المبسَطة سوف تشكل لنا المعادلة البوليانية المكافئة بعد التبسيط والدالَة المنطقية كما نرى في الشكل (1-5- ج) ، وفي هذا المثال نرى أن المعادلة الأصلية تتكون ون أربعة حدود كل حد منها يمثل بوابة AND بثلاث مداخل مجمعين على بوابة OR بأربعة مداخل أي أن عدد المداخل الكلية يساوي 16 مدخلاً ، وبعد التبسيط أصبحت الدالَة تتكون من حدين كل منهما ممثل ببوابة AND بمدخلين مجمعين على بوابة OR بمدخلين أيضاً ، وبالتالي يصبح عدد المداخل الكلية للدالَة بعد التبسيط يساوي 6 مداخل كما نرى في الشكل (1-5- ج).
مثال (1-2) : اكتب التعبير الجبري الذي يمثله جدول الحقيقة المبين في الشكل (1-7- أ) ثم قم بتبسيطه باستخدام خريطة كانوف .
الخطوة الأولى.. للحصول على التعبير الجبري هي كتابة الحدود التي تعطي الخرج (Y) في جدول الحقيقة والمساوي للقيمة (1) كما في الشكل (1-7- أ) . وبتجميع هذه الحدود يمكننا استنتاج التعبير الجبري وهو كما يلي :
Y = A'B'C'D + A'B'CD + A'BC'D + A'BCD + AB'CD + ABCD
و الخطوة التالية..هي رسم خريطة كارنوف لأربغة متغيرات كما نرى في الشكل (1-7- ب) ، ونقوم بوضع الآحاد التي في عمود الخرج (Y) من جدول الحقيقة في الخلايا المكافئة لها على خريطة كارنوف .
وبالنظر إلى خريطة كارنوف في الشكل (1-7- ب) نجد أنه يمكن تجميع الآحاد في مخموعتين كل مجموعة تحتوي على أربعة من الآحاد (1's) ، وبالتالي فإن الشكل المربع العلوي والذي يحتوي على أربعة آحاد ... المتغيَر B والمتغيَر B' يمكن حذفهما وبالمثل المتغيَر C و المتغيَر C' وتكون النتيجة A'D ، وكذلك بالنسبة للشكل المستطيل على الخريطة والذي يحتوي على أربعة آحاد فإنه يمكن كلاً من المتغيرات A،A،B'،B' والنتيجة هي CDوالتعبير الجبري المبسط على ذلك يكون : Y = A'D + CD
لمحة بسيطة عن خرائط كارنوف بخمسة وستة متحولات :
خرائط خمسة متحولات :
يتمتع مخطط كارنوف لخمسة متحولات بنفس الخواص التي تتمتع بها المخططات السابقة من حيث اعتبار المربعات المتجاورة متصلة و المربعات الموجودة في أقصى يسار الجدول متصلة مع المربعات الموجودة في أقصى اليمين والمربعات الموجودة في أعلى الجدول متصلة مع المربعات الموجودة في أسفل الجدول . حيث نعتبر في المخطط الأول A=0 ، وفي المخطط الثاني A=1 .
أمثلة:
خرائط ستة متحولات :
يتمتع مخطط كارنوف لست متحولات بنفس الخواص التي تتمتع بها المخططات السابقة أيضاً . بالإضافة إلى صفات الاتصال التي يتمتع بها كل مخطط على حدى ... تعتبر المربعات المتماثلة من ناحية الموقع في المخططات المتجاورة متصلة سواء بالاتجاه الأفقي أو الشاقولي . فمثلاً المربع m5 يعتبر متصلاً مع m21 .
يتضح مما سبق أنه كلما ازداد عدد المتحولات كلما أصبح شكل المخطط أكثر تعقيداً وتوزعاً . وكلما أصبحت الفائدة من استخدام مخطط K لاظهار الحدود المتصلة بشكل مرئي ضئيل . لذلك بشكل عام حينما يزداد عدد المتحولات عن ستة يفضل استخدام طرق أخرى الجبر المنطقي . المنطق الرياضي
المراجع:
- كتاب جبر المنطق ... للدكتور هيثم عرابي.... منشورات جامعة حلب.
- كتاب نظم منطقية ... للدكتور فادي فوز.... منشورات جامعة حلب.