خريطة كارنوف

مثال يوضح كيفية اختصار التعابير الرياضية الطويلة الناتجة من الطريقة التقليدية باستخدام طريقة كارنوف:
¬AB¬C¬D ∨ A¬B¬C¬D ∨ A¬B¬CD ∨ A¬BC¬D ∨ A¬BCD ∨ AB¬C¬D ∨ ABC¬D v ABCD = AC ∨ B¬C¬D ∨ A¬B

خَرِيطَةُ كَارْنُوف أو جدول كارنوف أو مخطط كارنوف أو مخطط كارنو فايتش (بالإنجليزية Karnaugh map) نسبة لواضعه عالم الرياضيات الأميركي موريس كارنوف عام 1952 والذي أدخل عليها تحسينات إدوارد فيتش Edward Veitch في عام 1953، هي خريطة تستعمل في الرياضيات الثنائية أو ما يسمى أيضا بالجبر المنطقي وذلك لاختصار بعض الجمل أو التعابير المنطقية.^[1] عادة ما يستعمل جدول كارنوف في المعادلات التي تحتوي على متغيرين وأربع متغيرات. نظريا يمكن استعماله لعدد أكبر من المتغيرات ولكن ذلك ليس متداولا حيث توجد لمثل هذه الحالات طرق أكثر فعالية للاختزال. تعتبر الفائدة الأكبر لخريطة كارنوف تقليلها لعدد الدارات المنطقية اللازمة لتشغيل عملية ما (توفير التكاليف)، كما أنها تقلل نسبة الخطأ في حساب لطريقة الفصل الطبيعي (Disjunctive normal form) للتعابير المنطقية، حيث يكون مخرج خريطة كارنوف أبسط وأقل احتمالا للخطأ.

الخصائص[عدل]

عن طريق خريطة كارنوف يمكن تحويل أي صيغة منطقية منفصلة إلى صيغة أخرى مختزلة. لتنفيذ الاختزال يتم البدء بوضع جدول الحقيقة والذي يتم كتابة كل العناصر التي لها قيمة مساوية ل "1" عبر صيغها المنطقية وربطها بصيغة «أو» المنطقية، مكونةً تعبيرات الفصل الطبيعي (Disjunctive normal form). بعدها يتم تفعيل خريطة كارنوف لاختزال التعابير الناتجة بتعابير أقصر وأبسط. يمكن الوصول إلى أكثر من صيغة مختزلة، مع أهمية أخذ الطريقة الأكثر اختزالاً، حيث يمكن بناء الدارة أو البوابة المنطقية عبرها.

شرح تطبيقي ومثال في كيفية استعمال الجدول[عدل]

نعتبر الدالة المنطقية $Y=Y\left(X_{1},X_{2},X_{3},X_{4}\right)$ وكذلك الدالة المنطقية $Y=Y\left(X_{1},X_{2}\right)$ . ولنفترض أنه لدينا جدول الحقيقة لكل من الدالتين كما هو مبين في الجدولين أسفله:

جدول الدالة Y بأربع متغيرات
Y	$X_{1}$	$X_{2}$	$X_{3}$	$X_{4}$	رقم السطر
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

جدول الدالة G بثلاث متغيرات
Y	$X_{1}$	$X_{2}$	$X_{3}$	رقم السطر
0	0	0	0	0
1	1	0	0	1
0	0	1	0	2
1	1	1	0	3
1	0	0	1	4
0	1	0	1	5
1	0	1	1	6
0	1	1	1	7

يمكن أن نفهم الجدولين أعلاه بهذه الطريقة: أنه لدينا مثلا جهاز إلكتروني بأربع متغيرات أو متغيرين اثنين أي مداخل. مثلا أربع أزرار يمكن أن تكون مضغوطة (أي تساوي 1) أو غير مضغوطة (تساوي 0). نسمي هذه الأزرار $X_{1}...X_{4}$ كما يمكن فهم $Y$ على أنه مخرج هذا الجهاز الإلكتروني مثلا ديود مضيئ حيث 1 = مضيء و 0 = منطفئ.

السطر الأول في الجدول الأول (أي الجهاز ذو أربع أزرار) يقول أنه إذا كانت كل المتغيرات $X_{i}$ صفرا أي إذا كانت كل الأزرار غير مضغوطة فإن الديود يكون مضيئا. الآن نطرح السؤال ما هي العلاقة بين مداخل النظام أي المتغيرات X ومخرجه Y ? العلاقة مبينة في الجداول أعلاه ولكننا نريد أن نكتب جملة أو معادلة تعتمد على الجبر البولي وتصف لنا هذه العلاقة. يمكن في هذه الحالة مباشرة من الجدول كتابة المعادلة أو التعبير وذلك بطريقتين تسمي الأشكال النمطية أو القياسية Normalformen:

إما أن نكتبها بنمط صيغة التقاطع القياسية أو الصيغة القياسية للتقاطع konjunktive Normalform
أو نكتبها بنمط صيغة الاجتماع القياسية أو الصيغة القياسية للاجتماع disjunktive Normalform

المشكلة في هذين النمطين هو أن المعادلات والتعبيرات قابلة للاختزال.

لسائل أن يسأل لماذا يشكل ذلك مشكلة? ولماذا نريد الحصول على معادلة مختزلة قدر الإمكان? أحد الأسباب هو، إن عدنا إلى جهازنا الإلكتروني، أن كل عملية ضرب أو جمع في المعادلة تقابلها في الجهاز وحدة تقوم بذلك (قلابات أو معالج بيانات أو دائرة كهربائية مثلا). واستعمال عدد كبير من هذه الوحدات يفضي إلى بناء أجهزة غير مربحة تجاريا لكثر المكونات المستعملة كما أنها تكون معرضة أكثر للعطب وكبيرة الحجم وهذه كلها خصائص لا نريدها في أجهزتنا الرقمية الحديثة.

عن طريق جدول كارنو فايتش يمكننا مباشرة كتابة تعبير أو معادلة (في الحقيقة هي ليست معادلة بالمعنى الرياضي للكلمة) مختصرة.

ما يجب الانتباه إليه عند استعمال جدول كارنو:

جدول كارنو لا يعطينا معادلة مختزلة لأقصى حد. أي أنه من الممكن أنه بعد استعمال هذه الطريقة أنه يكون هناك قابلية للاختزال
ترتيب المتغيرات يجب أن يكون مثل ما هو في جدول الحقيقة حتى يقابل ذلك الترتيب في مخطط كارنو أو جدول كارنو.(الأسباب تعود إلى بنية المخطط والجبر البولي). في حالة تغيير تسلسل المتغيرات أي مثلا X1 X2 X3 X4 عوض X4 X3 X2 X1 فإن مخطط كارنو يتغير (ترقيم الخانات الأزرق) ولكن يمكن فهم ذلك بشيء من التأمل.
لا يمكن اختزال أو تجميع إلا عدد يساوي قوات 2 من الخانات أو المربعات أي 1,2,4,8 إلخ...

خريطة كارنوف[عدل]

خريطة كارنوف أو خريطة K هي طريقة مرئية لتبسيط التعبيرات الجبرية وتماثل جدول الحقيقة لأنها تعطي لنا كل القيم المحتملة للمداخل ونتيجة الخرج لكل قيمة. وبدلاَ من تنظيمها على شكل أعمدة وصفوف مثل جدول الحقيقة. فإن خريطة كارنوف عبارة عن مصفوفة (array) من الخلايا (cells)، وتمثل كل خلية القيمة الثنائية لإحدى تشكيلات المداخل. وعدد الخلايا في خريطة كارنوف يساوي عدد التشكيلات المحتملة للمداخل. وخريطة كارنوف يمكن استخدامها مع تعبيرات بوليانية لها متغيران.. ثلاثة.. وحتى سبعة. ونكتفي بأربعة متحولات فقط لتوضيح أساسيات التبسيط. وسنورد لمحة بسيطة عن خمسة وستة متحولات...

التبسيط باستخدام خريطة كارنوف[عدل]

عدد الخلايا في خريطة كارنوف يعتمد على عدد التشكيلات المتغيرات (المداخل), وكمثال على ذلك الشكل (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 لاظهار الحدود المتصلة بشكل مرئي ضئيل. لذلك بشكل عام حينما يزداد عدد المتحولات عن ستة يفضل استخدام طرق أخرى الجبر المنطقي. المنطق الرياضي