Boolean algebra and Karnaugh maps
مُقدَّم| 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$.
Match each Boolean law to what it says.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
These laws let you simplify Boolean expressions algebraically before building the circuit.
By the absorption law, A + A·B simplifies to ____.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
If A is true the whole expression is true whatever B is, and if A is false both terms are false. B cannot affect the result.
قوانين دي مورغان
- قوانين دي مورغان هما القاعدتان اللتان يطلب منك الامتحان استخدامهما باسمهما:
- الوصفة بالكلمات: نفي الكل، تبديل AND بـ OR، نفي كل مُعامل (operand).
- أهميتها العملية تكمن في أنها تسمح بإعادة كتابة أي تعبير باستخدام بوابات NAND فقط أو NOR فقط، والشريحة المبنية من بوابة مكررة واحدة أرخص في التصنيع.

تعبيران، جدول حقيقة واحد
Boolean algebra
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables.
By De Morgan's law, $\overline{A \cdot B}$ equals:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select جميعها that apply.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative.
مثال محلول: تبسيط، وحساب عدد البوابات
- بسّط $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$.
- دائماً انهِ بما يوفره التبسيط: قلة البوابات، مما يعني دائرة أرخص وأسرع وأقل استهلاكاً للطاقة.
Simplify $A\cdot B + A\cdot\overline{B}$.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B needs two ANDs, one NOT and one OR. How many gates does its simplified form need?
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved.
خريطة كارناوغ
- خريطة كارنوف تبسط التعبير عن طريق تجميع الأصفار 1 المجاورة المستخرجة من جدول الحقيقة.
- الصفوف والأعمدة مُعلَّمة بترتيب كود غري (Gray code)،
00, 01, 11, 10، بحيث تختلف الخلايا المتجاورة في متغير واحد بالضبط. هذا هو السر الكامل: يجعل الجبر مرئياً عبر التجاور. - ضع 1 في كل خلية يكون فيها الإخراج 1، ثم ابحث عن مجموعات مستطيلة من 1s whose sides are powers of two: 1, 2, 4, 8. المجموعات يمكن أن تلتف حول الحواف.

كلما كان المستطيل أكبر، كان الحد أبسط
A Karnaugh map simplifies a Boolean expression by:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work.
قراءة المجموعة
- داخل المجموعة، المتغير الذي يبقى ثابتاً يبقى في الحد؛ المتغير الذي يتغير يختفي.
- لذلك مجموعة من 2 تحذف متغيراً واحداً، ومجموعة من 4 تحذف اثنين، ومجموعة من 8 تحذف ثلاثة. كلما كانت المجموعة أكبر، كان الحد أبسط.
- غطِ كل 1 باستخدام أقل عدد ممكن من المجموعات الكبرى قدر الإمكان، ثم اجمع حدود المجموعات بـ OR. المجموعات قد تتداخل، والتداخل غالباً ما يسمح بتكوين مجموعة أكبر.
In a Karnaugh map, a larger group of adjacent 1s eliminates more variables, giving a simpler term (a group of 2 drops one variable, a group of 4 drops two).
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes.
Put the steps of simplifying with a Karnaugh map in order.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 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 بأقل عدد ممكن من المجموعات الكبرى قدر الإمكان