الجبر البولياني ومخططات كارناوغ
| English | العربية |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | الجبر البولياني |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | قوانين دي مورغان |
| Karnaugh map/ˈkɑːnɔː mæp/ | خريطة كارنو |
| truth table/truːθ ˈteɪbl/ | جدول الحقيقة |
| absorption/əbˈsɔːpʃn/ | امتصاص |
| Gray code/ɡreɪ kəʊd/ | رمز غراي |
رسالة الماجستير التي بنى عليها العصر الرقمي
- في عام 1937، لاحظ طالب عمره 21 عاماً يُدعى كلاود شانون أن مفاتيح التبديل الهاتفي التي كان يدرسها تقوم بنفس عمل الجبر الذي اخترعه جورج بول قبل ثمانين عاماً للتفكير في الحقائق والأكاذيب.
- إذا كانت المفتاح متغيراً بولياً، فإن الدائرة هي تعبير، وتبسيط التعبير يزيل البوابات من الدائرة. قلة البوابات تعني رخصاً وسرعة واستهلاكاً أقل للطاقة.
- وُصفت رسالته بأنها الأهم في القرن. كل ما في هذه الصفحة هو تلك الفكرة الواحدة المستخدمة كأداة.
- هذا الدرس هو الجبر البولي، وقوانين دي مورغان، وخريطة كارناوغ التي تؤدي نفس الوظيفة بالعين المجردة.
الرموز والقوانين
+تعني OR،·تعني AND وغالباً ما تُترك ضمنية، والخط العلوي يعني NOT. جدول الحقيقة يصف نفس الشيء بشكل شامل.- الهوية: $A + 0 = A$ و $A \cdot 1 = A$. الصفرية (Null): $A + 1 = 1$ و $A \cdot 0 = 0$.
- التكرارية (Idempotent): $A + A = A$. العكسية (Inverse): $A + \overline{A} = 1$ و $A \cdot \overline{A} = 0$.
- الامتصاص: $A + A\cdot B = A$، لأنه إذا كان $A$ صحيحاً تكون العبارة كاملة صحيحة بغض النظر عن $B$.
طابق كل قانون بولياني بما يقول.
تسمح هذه القوانين بتبسيط التعبيرات البوليانية جبرياً قبل بناء الدائرة.
وفقاً لقانون الامتصاص، A + A·B يُبسط إلى ____.
إذا كانت A صحيحة، فإن التعبير بأكمله صحيح بغض النظر عن B، وإذا كانت A خاطئة، فإن كلا الحدين خاطئان. لا يمكن لـ B أن يؤثر على النتيجة.
قوانين دي مورغان
- قوانين دي مورغان هما القاعدتان اللتان يطلب منك الامتحان استخدامهما باسمهما:
- الوصفة بالكلمات: نفي الكل، تبديل AND بـ OR، نفي كل مُعامل (operand).
- أهميتها العملية تكمن في أنها تسمح بإعادة كتابة أي تعبير باستخدام بوابات NAND فقط أو NOR فقط، والشريحة المبنية من بوابة مكررة واحدة أرخص في التصنيع.
تعبيران، جدول حقيقة واحد
الجبر البولياني
A·B, A+B, Ā …
الجبر البولياني هو مجرد هذه الأبواب مكتوبة كتعبيرات — قارن جداول الحقيقة.
وفقاً لقانون دي مورغان، $\overline{A \cdot B}$ يساوي:
نفي الكل، تبديل AND→OR، نفي كل مؤثر: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
ما هي الخطوات المطلوبة لتطبيق قانون دي مورغان على تعبير؟ حدد كل ما ينطبق.
نفي الكل، تبديل العامل، نفي كل جزء. الترتيب غير مهم، لأن AND و OR عمليتان التبديل.
مثال محلول: تبسيط، وحساب عدد البوابات
- بسّط $Z = A\cdot B + A\cdot\overline{B}$ واشرح ما يوفره.
- أخرج $A$ كعامل مشترك: $Z = A\cdot(B + \overline{B})$.根据 العكسية $B + \overline{B} = 1$، إذن $Z = A \cdot 1 = A$.
- الأصلية تحتاج بوابتي AND، وبوابة NOT، وبوابة OR: أربع بوابات. التعبير المبسط لا يحتاج أي شيء، فقط المدخل $A$.
- دائماً انهِ بما يوفره التبسيط: قلة البوابات، مما يعني دائرة أرخص وأسرع وأقل استهلاكاً للطاقة.
بسط $A\cdot B + A\cdot\overline{B}$.
استخراج A كعامل مشترك: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B يحتاج إلى بوابتين AND وبوابة NOT واحدة وبوابة OR واحدة. كم عدد البوابات التي يحتاجها شكله المبسط؟
يُبسط إلى A فقط، لذا يكون المخرج هو المدخل ولا حاجة لأي بوابة على الإطلاق. تم توفير أربع بوابات.
خريطة كارناوغ
- خريطة كارنوف تبسط التعبير عن طريق تجميع الأصفار 1 المجاورة المستخرجة من جدول الحقيقة.
- الصفوف والأعمدة مُعلَّمة بترتيب كود غري (Gray code)،
00, 01, 11, 10، بحيث تختلف الخلايا المتجاورة في متغير واحد بالضبط. هذا هو السر الكامل: يجعل الجبر مرئياً عبر التجاور. - ضع 1 في كل خلية يكون فيها الإخراج 1، ثم ابحث عن مجموعات مستطيلة من 1s whose sides are powers of two: 1, 2, 4, 8. المجموعات يمكن أن تلتف حول الحواف.
كلما كان المستطيل أكبر، كان الحد أبسط
يُبسط خريطة كارنوف التعبير البولياني من خلال:
تقوم بتجميع 1s المتجاورة (بنظام كود جري) في مستطيلات مضاعفات للعدد 2؛ كل مجموعة تصبح حدًا مبسطًا.
لماذا تُسمى صفوف وأعمدة خريطة كارنوف بـ 00, 01, 11, 10 بدلاً من 00, 01, 10, 11؟
ترتيب Gray code يحول التجاور الجبري إلى تجاور فيزيائي. في ترتيب العد، لن تعمل قاعدة التجميع ببساطة.
قراءة المجموعة
- داخل المجموعة، المتغير الذي يبقى ثابتاً يبقى في الحد؛ المتغير الذي يتغير يختفي.
- لذلك مجموعة من 2 تحذف متغيراً واحداً، ومجموعة من 4 تحذف اثنين، ومجموعة من 8 تحذف ثلاثة. كلما كانت المجموعة أكبر، كان الحد أبسط.
- غطِ كل 1 باستخدام أقل عدد ممكن من المجموعات الكبرى قدر الإمكان، ثم اجمع حدود المجموعات بـ OR. المجموعات قد تتداخل، والتداخل غالباً ما يسمح بتكوين مجموعة أكبر.
في خريطة كارنوف، المجموعة الأكبر من 1s المتجاورة تلغي متغيرات أكثر، مما يعطي حدًا أبسط (مجموعة من 2 تلغي متغيرًا واحدًا، ومجموعة من 4 تلغي اثنين).
تقوم بتجميع 1s المتجاورة في مستطيلات مضاعفات للعدد 2 بنظام كود جري؛ كلما كانت المجموعة أكبر، أصبح الحد أبسط.
ضع خطوات التبسيط باستخدام خريطة كارنوف بالترتيب.
Gray code، آحاد، أكبر المجموعات، احذف ما يتغير، اجمع الحدود عبر OR. استخدم أقل عدد ممكن وأكبر مجموعات تغطي كل 1.
مثال محلول: قراءة خريطة ذات متغيرين
- خريطة كارنوف لـ $A$ و $B$ تحتوي على 1s في الخلايا $\overline{A}B$ و $AB$. أبسط.
- الأصفاران 1 متجاوران: يشاركان عمود $B = 1$، لذا يتم جمعهما كمستطيل من 2.
- داخل تلك المجموعة $B$ يبقى 1 طوال الوقت، بينما $A$ يتغير من 0 إلى 1. المتغير الذي يتغير يختفي.
- إذن التعبير الكامل هو ببساطة $Z = B$. قارن ذلك بمجموع الحدود غير المبسّن، $\overline{A}B + AB$، الذي يحتاج بوابة NOT، وبوابتي AND، وبوابة OR.
أي طريقة تستخدم؟
- الجبر البولي دقيق ويعمل لأي عدد من المتغيرات، لكن يجب أن تكتشف أي قانون ينطبق.
- خريطة كارناوغ آلية ومن الصعب الخطأ فيها لـ متغيرين إلى أربعة متغيرات، وهو ما يضعه الامتحان، وهي تظهر لك أكبر تجميع مباشرة.
- كلاهما يعطي نفس النتيجة. فائدة الخريطة هي أن التبسيط يصبح بحثاً بصرياً، وليس البحث عن قانون.
علامات ضائعة
- دي مورغان هو نفي الكل، تبديل العامل، نفي كل جزء. تغيير العامل فقط هو نصف الإجابة الكلاسيكي الخاطئ.
- صفوف خريطة كارناوغ يجب أن تكون بترتيب كود غري
00, 01, 11, 10. في ترتيب العد الثنائي يكون التجاور خاطئاً وي فشل التجميع. - أحجام المجموعات قوى للعدد 2 وقد تلتف حول الحواف. مجموعة من ثلاثة ليست مجموعة صالحة.
- قل ما الغرض من التبسيط: قلة البوابات، مما يعني رخصاً وسرعة واستهلاكاً أقل للطاقة.
لقد فهمت الأمر
- يعيد الجبر البولي كتابة التعبير إلى حدود أقل، لذا تحتاج الدائرة إلى بوابات أقل
- دي مورغان: $\overline{A + B} = \overline{A} \cdot \overline{B}$ و $\overline{A \cdot B} = \overline{A} + \overline{B}$؛ الامتصاص: $A + AB = A$؛ $A\cdot B + A\cdot\overline{B} = A$
- خريطة كارنوف تجمع الأصفار 1 المجاورة من جدول الحقيقة، مع الصفوف والأعمدة بترتيب كود جري بحيث differs in one variable
- المتغير الذي يتغير داخل المجموعة يختفي، لذا المجموعات الأكبر تعطي حدوداً أبسط: غطِ كل 1 بأقل عدد ممكن من المجموعات الكبرى قدر الإمكان