خريطة كارنوف
المحتويات

تعريفًا بالموضوع، خَرِيطَةُ كَارْنُوف أو جدول كارنوف أو مخطط كارنوف أو مخطط كارنو فايتش (بالإنجليزية Karnaugh map) نسبة لواضعه عالم الرياضيات الأميركي موريس كارنوف عام 1952 والذي أدخل عليها تحسينات إدوارد فيتش Edward Veitch في سنة 1953، هي خريطة تستعمل في الرياضيات الثنائية أو ما يسمى كذلك بالجبر المنطقي وذلك لاختصار بعض الجمل أو التعابير المنطقية. عادة ما يستعمل جدول كارنوف في المعادلات التي تحتوي على متغيرين وأربع متغيرات. نظريا يمكن استعماله لعدد أكبر من المتغيرات ولكن ذلك ليس متداولا حيث توجد لمثل هذه الحالات طرق أكثر فعالية للاختزال. تعتبر الفائدة الأكبر لخريطة كارنوف تقليلها لعدد الدارات المنطقية اللازمة لتشغيل عملية ما (توفير التكاليف)، كما أنها تقلل نسبة الخطأ في حساب لطريقة الفصل الطبيعي (Disjunctive normal form) للتعابير المنطقية، حيث يكون مخرج خريطة كارنوف أبسط وأقل احتمالا للخطأ. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
Y = A*1 = A
وفي هذا الصدد، هذا التحليل يمكن استنتاجه بدراسة جدول الحقيقة للدالة الموضحة في الشكل (1-4- أ) والذي نرى فيه أن الخرج (Y) يتبع تماماً الدخل (A), وبناءً على ذلك تكون الدالة المكافئة كما هو موضح في الشكل (1-4- و).
Y = A'D + CD
لمحة بسيطة عن خرائط كارنوف بخمسة وستة متحولات
خرائط خمسة متحولات
من جانب آخر، يتمتع مخطط كارنوف لخمسة متحولات بنفس الخواص التي تتمتع بها المخططات السابقة من حيث اعتبار المربعات المتجاورة متصلة والمربعات الموجودة في أقصى يسار الجدول متصلة مع المربعات الموجودة في أقصى اليمين والمربعات الموجودة في أعلى الجدول متصلة مع المربعات الموجودة في أسفل الجدول.
حيث نعتبر في المخطط الأول A=0، وفي المخطط الثاني A=1.
أمثلة:
كيفية التجميع في مخططات كارنوف
ومن ناحية أخرى، الخطوة الأولى.. للحصول على التعبير الجبري هي كتابة الحدود التي تعطي الخرج (Y) في جدول الحقيقة والمساوي للقيمة (1) كما في الشكل (1-7- أ).
من جهة ثانية، والحدود السابقة المبسَطة سوف تشكل لنا المعادلة البوليانية المكافئة بعد التبسيط والدالَة المنطقية
مثال (1-1):
في هذا الإطار، صمم دالة منطقية في أبسط صورة لجدول الحقيقة الموضح في الشكل (1-5- أ) مبيناً كل خطوة في عملية التبسيط.
إضافةً إلى ذلك، وبتجميع هذه الحدود يمكننا استنتاج التعبير الجبري وهو كما يلي:
الحل:
وعلى صعيد آخر، كما نرى في الشكل (1-5- ج)، وفي هذا المثال نرى أن المعادلة الأصلية تتكون ون أربعة حدود كل حد منها يمثل بوابة AND بثلاث مداخل مجمعين على بوابة OR بأربعة مداخل أي أن عدد المداخل الكلية يساوي 16 مدخلاً، وبعد التبسيط أصبحت الدالَة تتكون من حدين كل منهما ممثل ببوابة AND بمدخلين مجمعين على بوابة OR بمدخلين كذلك، وبالتالي يصبح عدد المداخل الكلية للدالَة بعد التبسيط يساوي 6 مداخل كما نرى في الشكل (1-5- ج).
من جهة ثانية، وكيف أن خريطة كارنوف تستعمل لتبسيط التعبيرات البوليانية الكبيرة، لاحظ أن المجموعات الكبيرة أي التي تحتوي على عدد كبير من الآحاد (1's) تعطي لنا حد صغير وعليه تكون البوابات المستعملة في التصميم لها مدخلات قليلة. ولهذا السبب يجب أن نبدأ بالبحث عن المجموعات التي تحتوي على أكبر عدد من الآحاد، فإن لم نجد نبحث عن أقل وهكذا.
كذلك، و الخطوة التالية..هي رسم خريطة كارنوف لأربغة متغيرات كما نرى في الشكل (1-7- ب)، ونقوم بوضع الآحاد التي في عمود الخرج (Y) من جدول الحقيقة في الخلايا المكافئة لها على خريطة كارنوف.
أمثلة:
مثال (1-2):
في هذا الإطار، لدينا هنا ثلاث متغيرات، والخطوة الأولى هي رسم خريطة كارنوف لثلاث متغيرات، كما هو موضح في الشكل (1-5- ب).
كذلك، وبالنظر إلى خريطة كارنوف في الشكل (1-7- ب) نجد أنه يمكن تجميع الآحاد في مخموعتين كل مجموعة تحتوي على أربعة من الآحاد (1's)، وبالتالي فإن الشكل المربع العلوي والذي يحتوي على أربعة آحاد... المتغيَر B والمتغيَر B' يمكن حذفهما وبالمثل المتغيَر C والمتغيَر C' وتكون النتيجة A'D، وكذلك بالنسبة للشكل المستطيل على الخريطة والذي يحتوي على أربعة آحاد فإنه يمكن كلاً من المتغيرات A،A،B'،B' والنتيجة هي CDوالتعبير الجبري المبسط على ذلك يكون:
من جانب آخر، اكتب التعبير الجبري الذي يمثله جدول الحقيقة المبين في الشكل (1-7- أ) ثم قم بتبسيطه باستخدام خريطة كانوف.
Y = A'B'C'D + A'B'CD + A'BC'D + A'BCD + AB'CD + ABCD
ومن ناحية أخرى، الآحاد (1's) في خريطة كارنوف يمكن أن تجمع كأزواج (مجموعة من اثنين أو مجموعات من أربعة أو ثمانية أو ستة عشر وهكذا لكل قوى 2. الشكل (1-6) يوضح بعض الأمثلة للتجميع.
من جانب آخر، الخطوة الثانية أن ننظر إلى الخرج الذي يساوي (1) في جدول الحقيقة في الشكل (1-5- أ) ثم نقوم بوضع هذه الآحاد في الخلايا المكافئة لها على خريطة كارنوف كما هو موضح في الشكل (1-5- ب)، وبعد وضع (0) في الخلايا الفارغة المتبقية، نجمع الآحاد في شكل أزواج كما في الشكل (1-5- ب)، ثم نحدد من خلال الصف والعمود المتغيرات المشتركة في هذه المجموعات (الأزواج) لنرى أي متغيَر سوف يتم حذفه تبعاَ لقاعدة المتممات ففي المجموعة التي على اليمين A', A يتم حذفهم والنتيجة B'C، وفي المجموعة التي على اليسار يتم حذف C,C' والنتيجة 'AB
خريطة كارنوف
إضافةً إلى ذلك، وخريطة كارنوف يمكن استخدامها مع تعبيرات بوليانية لها متغيران.. ثلاثة.. وحتى سبعة. ونكتفي بأربعة متحولات فقط لتوضيح أساسيات التبسيط. وسنورد لمحة بسيطة عن خمسة وستة متحولات...
من جانب آخر، خريطة كارنوف أو خريطة K هي طريقة مرئية لتبسيط التعبيرات الجبرية وتماثل جدول الحقيقة لأنها تعطي لنا كل القيم المحتملة للمداخل ونتيجة الخرج لكل قيمة.
علاوةً على ذلك، وبدلاَ من تنظيمها على شكل أعمدة وصفوف مثل جدول الحقيقة. فإن خريطة كارنوف عبارة عن مصفوفة (array) من الخلايا (cells)، وتمثل كل خلية القيمة الثنائية لإحدى تشكيلات المداخل. وعدد الخلايا في خريطة كارنوف يساوي عدد التشكيلات المحتملة للمداخل.
خرائط ستة متحولات
من جهة ثانية، وكلما أصبحت الفائدة من استخدام مخطط K لاظهار الحدود المتصلة بشكل مرئي ضئيل. لذلك بشكل عام حينما يزداد عدد المتحولات عن ستة يفضل استخدام طرق أخرى الجبر المنطقي.
فمثلاً المربع m5 يعتبر متصلاً مع m21.
كذلك، يتمتع مخطط كارنوف لست متحولات بنفس الخواص التي تتمتع بها المخططات السابقة كذلك.
- المنطق الرياضي
- مواضيع ذات صلة
- اختصار التوابع المنطقية بطريقة كوين ماكلوسكي
وفي هذا الصدد، يتضح مما سبق أنه كلما ازداد عدد المتحولات كلما أصبح شكل المخطط أكثر تعقيداً وتوزعاً.
وفي السياق ذاته، فضلًا عن صفات الاتصال التي يتمتع بها كل مخطط على حدى... تعتبر المربعات المتماثلة من ناحية الموقع في المخططات المتجاورة متصلة سواء بالاتجاه الأفقي أو الشاقولي.
شرح تطبيقي ومثال في كيفية استعمال الجدول
ومن جهة أخرى، ترتيب المتغيرات يجب أن يكون مثل ما هو في جدول الحقيقة حتى يقابل ذلك الترتيب في مخطط كارنو أو جدول كارنو.(الأسباب تعود إلى بنية المخطط والجبر البولي). في حالة تغيير تسلسل المتغيرات أي مثلا X1 X2 X3 X4 عوض X4 X3 X2 X1 فإن مخطط كارنو يتغير (ترقيم الخانات الأزرق) ولكن يمكن فهم ذلك بشيء من التأمل.
ومن ناحية أخرى، عن طريق جدول كارنو فايتش يمكننا مباشرة كتابة تعبير أو معادلة (في الحقيقة هي ليست معادلة بالمعنى الرياضي للكلمة) مختصرة.
علاوةً على ذلك، المشكلة في هذين النمطين هو أن المعادلات والتعبيرات قابلة للاختزال.
من جانب آخر، لا يمكن اختزال أو تجميع إلا عدد يساوي قوات 2 من الخانات أو المربعات أي 1,2,4,8 إلخ...
علاوةً على ذلك، لسائل أن يسأل لماذا يشكل ذلك مشكلة? ولماذا نريد الحصول على معادلة مختزلة قدر الإمكان? أحد الأسباب هو، إن عدنا إلى جهازنا الإلكتروني، أن كل عملية ضرب أو جمع في المعادلة تقابلها في الجهاز وحدة تقوم بذلك (قلابات أو معالج بيانات أو دائرة كهربائية مثلا). واستعمال عدد كبير من هذه الوحدات يفضي إلى بناء أجهزة غير مربحة تجاريا لكثر المكونات المستعملة كما أنها تكون معرضة أكثر للعطب وكبيرة الحجم وهذه كلها خصائص لا نريدها في أجهزتنا الرقمية الحديثة.
في هذا الإطار، السطر الأول في الجدول الأول (أي الجهاز ذو أربع أزرار) يقول أنه إذا كانت كل المتغيرات صفرا أي إذا كانت كل الأزرار غير مضغوطة فإن الديود يكون مضيئا. الآن نطرح السؤال ما هي العلاقة بين مداخل النظام أي المتغيرات X ومخرجه Y ? العلاقة مبينة في الجداول أعلاه ولكننا نريد أن نكتب جملة أو معادلة تعتمد على الجبر البولي وتصف لنا هذه العلاقة. يمكن في هذه الحالة مباشرة من الجدول كتابة المعادلة أو التعبير وذلك بطريقتين تسمي الأشكال النمطية أو القياسية Normalformen:
في هذا الإطار، يمكن أن نفهم الجدولين أعلاه بهذه الطريقة: أنه لدينا مثلا جهاز إلكتروني بأربع متغيرات أو متغيرين اثنين أي مداخل. مثلا أربع أزرار يمكن أن تكون مضغوطة (أي تساوي 1) أو غير مضغوطة (تساوي 0). نسمي هذه الأزرار كما يمكن فهم على أنه مخرج هذا الجهاز الإلكتروني مثلا ديود مضيئ حيث 1 = مضيء و 0 = منطفئ.
من جانب آخر، أو نكتبها بنمط صيغة الاجتماع القياسية أو الصيغة القياسية للاجتماع disjunktive Normalform
وفي هذا السياق، نعتبر الدالة المنطقية وكذلك الدالة المنطقية . ولنفترض أنه لدينا جدول الحقيقة لكل من الدالتين كما هو مبين في الجدولين أسفله:
ما يجب الانتباه إليه عند استعمال جدول كارنو:
وفي هذا الصدد، جدول كارنو لا يعطينا معادلة مختزلة لأقصى حد. أي أنه من الممكن أنه بعد استعمال هذه الطريقة أنه يكون هناك قابلية للاختزال
في هذا الإطار، إما أن نكتبها بنمط صيغة التقاطع القياسية أو الصيغة القياسية للتقاطع konjunktive Normalform
الخصائص
وفي هذا السياق، عن طريق خريطة كارنوف يمكن تحويل أي صيغة منطقية منفصلة إلى صيغة أخرى مختزلة. لتنفيذ الاختزال يتم البدء بوضع جدول الحقيقة والذي يتم كتابة كل العناصر التي لها قيمة مساوية ل "1" عبر صيغها المنطقية وربطها بصيغة «أو» المنطقية، مكونةً تعبيرات الفصل الطبيعي (Disjunctive normal form). بعدها يتم تفعيل خريطة كارنوف لاختزال التعابير الناتجة بتعابير أقصر وأبسط. يمكن الوصول إلى أكثر من صيغة مختزلة، مع أهمية أخذ الطريقة الأكثر اختزالاً، حيث يمكن بناء الدارة أو البوابة المنطقية عبرها.
التبسيط باستخدام خريطة كارنوف
كذلك، وبعد التعرف على كيفية إنشاء خريطة كارنوف، سوف نرى كيف يمكن أن تستعمل لتبسيط الدوال المنطقية، وكمثال على ذلك نفترض أننا نريد تصميم دالة منطقية لها جدول الحقيقة الموضح في الشكل (1-4- أ).
إضافةً إلى ذلك، عند تمثيل التعبير البولياني على خريطة كارنوف يجب أن نتذكر أن كل خلية تمثل تشكيلة من التشكيلات الأربع المحتملة للمدخلات في جدول الحقيقة. الخرج (1) في جدول الحقيقة يجب أن يظهر (1) في الخلية المكافئة له على خريطة كارنوف، والخرج (0) في جدول الحقيقة يجب أن يظهر (0) في الخلية المكافئة له على خريطة كارنوف،
وفي السياق ذاته، الشكل (1-3-أ)، (1-3- ب) يوضحان هيئة خريطة كارنوف لثلاث متغيرات (8 خلايا),
وأربعة متغيرات (16 خلية)
في هذا الإطار، تبسيط المعادلات البوليانية بصفة عامة يمكن الحصول عليه عن طريق تطبيق قاعدة المتممات (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
كذلك، الخطوة الثانية: تمثيل هذا التعبير البولياني على خريطة كارنوف لمتغيرين كما نرى في الشكل (1-4- د).
كذلك، وكل خلية في خريطة كارنوف ذات المتغيرين تمثل واحد من الأربعة تشكيلات للدخل وعملياَ علامات الدخل (Input Labels) توضع خارج الخلايا كما هو موضح بالشكل (1-2) وتطبق على كل من الصف والعمود للخلايا، فمثلاَ الصف الذي أمامه A' يطبق على الخلايا العليا، بينما الذي أمامه A يطبق على الخلايا السفلى. ونرى في أعلى الخريطة المتغير B' يطبق على الخلايا التي على اليسار، بينما النتغير B يطبق على الخلايا التي على اليمين، وكمثال.. فإن الخلية السفلى التي على اليمين تمثل تشكيلة الدخل AB
ومن جهة أخرى، الخطوة الأولى: الحصول على التعبير البولياني من جدول الحقيقة، وذلك بكتابة التشكيلة التي أمامها (1) في الخرج وفيما بعد نجمع هذه التشكيلات باستخدام بوابة OR كما في الشكل (1-4- ب) والدالة المنطقية المكافئة لهذه المعادلة موضحة في الشكل (1-4- ج).
من جانب آخر، عدد الخلايا في خريطة كارنوف يعتمد على عدد التشكيلات المتغيرات (المداخل), وكمثال على ذلك الشكل (1-1), فهناك متغيران فقط هما (A,B). وبناءَ على ذلك فإن خريطة كارنوف تحتوي على أربعة تشكيلات (00,01,10,11)
من جهة ثانية، وبناءً على ذلك فإن (1) سوف يظهر في الخلية السفلى على اليسار (يمثل'AB)، وفي الخلية السفلى على اليمين (يمثل AB). والتشكيلات الأخرى للدخل (A'B'، A'B) وكلاهما يعطي (0) في الخرج، وبناءً عليه يجب وضع (0) في هاتين الخليتين العلويتين.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟