تبسيط مستوى البوابات المنطقية
تغطي هذه الوحدة طرق تبسيط التعبيرات البولينية لتقليل عدد البوابات المنطقية باستخدام الجبر البوليني وخرائط كارنوف (K-Maps) للمتغيرات المتعددة، بالإضافة إلى استخراج المضامين الأولية والأساسية.
Gate-Level Minimization
This module covers methods for simplifying Boolean expressions to reduce logic gates using Boolean algebra and Karnaugh Maps (K-Maps) for multiple variables, as well as deriving prime and essential prime implicants.
أهداف التعلم
- تعلم كيفية معالجة التعبيرات البولينية لتقليل عدد البوابات المنطقية المطلوبة.
- معرفة كيفية استنتاج وتبسيط خريطة كارنوف للدوال البولينية ذات 2 و 3 و 4 متغيرات.
- معرفة كيفية استخراج المضامين الأولية (Prime Implicants) للدالة البولينية.
- Learn how to manipulate Boolean expression to reduce the required number of logic gates.
- Know how to derive and simplify a Karnaugh map for Boolean functions of 2, 3, and 4 variables.
- Know how to derive the prime implicants of a Boolean function.
1 الحدود القصوى والدنيا (Maxterms & Minterms)
1 Maxterms & Minterms
الحد الأقصى (Maxterm) هو تعبير جمع (OR) تظهر فيه جميع المتغيرات مرة واحدة، وهو المكمل للحد الأدنى (Minterm) المقابل له.
A Maxterm is a sum term where all variables appear once, and it is the exact complement of its corresponding Minterm.
الحد الأقصى (Maxterm) هو مصطلح جمع (Sum Term) يحتوي على جميع المتغيرات في الدالة، سواء كانت مكملة أو غير مكملة.
العلاقة الأساسية بين الحدود الدنيا والقصوى هي أن الحد الأدنى والحد الأقصى اللذين يحملان نفس الرمز السفلي هما مكملان لبعضهما البعض بناءً على نظرية دي مورغان.
يمكن التعبير عن الدالة البولينية كحاصل ضرب للحدود القصوى (Product of Maxterms) من خلال عمل AND لجميع الصفوف التي تقيم إلى 0 في جدول الحقيقة.
A Maxterm is a Sum Term in which all variables appear once (complemented or not).
The fundamental relationship between minterms and maxterms is that a minterm and maxterm with the same subscript are complements of each other, verifiable via DeMorgan's theorem.
A Boolean function can also be expressed as a Product of Maxterms by ANDing all rows that should evaluate to 0.
لماذا نستخدم الحدود القصوى؟
في بعض الأحيان، يكون عدد الأصفار في جدول الحقيقة أقل بكثير من عدد الآحاد، مما يجعل التعبير عن الدالة بصيغة حاصل ضرب المجاميع (POS) أكثر كفاءة وأقل تكلفة في بناء الدوائر المنطقية مقارنة بصيغة مجموع حواصل الضرب (SOP).
Why use Maxterms?
Sometimes a truth table has significantly fewer 0s than 1s. In such cases, expressing the function as a Product of Sums (POS) using Maxterms yields a simpler, more cost-effective logic circuit than the Sum of Products (SOP) form.
| Minterm | Maxterm | |
|---|---|---|
| العملية المنطقية الأساسية Primary Logic Operation | حاصل ضرب (AND) Product (AND) | مجموع (OR) Sum (OR) |
| الرمز Symbol | m (حرف صغير) m (lowercase) | M (حرف كبير) M (uppercase) |
| التقييم في جدول الحقيقة Evaluation in Truth Table | يقيم إلى 1 Evaluates to 1 | يقيم إلى 0 Evaluates to 0 |
إذا كانت الدالة تحتوي على 4 متغيرات، فما هو الحد الأقصى M10؟ If a function has 4 variables (W,X,Y,Z), what is the Maxterm M10?
الرقم 10 بالنظام الثنائي هو 1010. في الحدود القصوى، 1 تعني المتغير مكمل و 0 تعني غير مكمل. إذن M10 = W' + X + Y' + Z.
10 in binary is 1010. For Maxterms, 1 means complemented and 0 means uncomplemented. Thus, M10 = W' + X + Y' + Z.
2 التبسيط البوليني والازدواجية (Boolean Simplification & Duality)
2 Boolean Simplification & Duality
التبسيط يقلل عدد البوابات، والازدواجية (Dual) تُستخرج بتبديل AND بـ OR، و 1 بـ 0 والعكس.
Simplification reduces gate count, and the Dual of a function is found by swapping AND with OR, and 1s with 0s.
عند تنفيذ معادلة بولينية باستخدام البوابات المنطقية، يتطلب كل حد (Term) بوابة، ويمثل كل متغير (Literal) مدخلاً لتلك البوابة.
التبسيط الجبري يهدف إلى تقليل عدد الحدود والمتغيرات، مما يؤدي إلى دوائر أصغر وأسرع.
مبدأ الازدواجية (Duality) ينص على أنه يمكن الحصول على النظير المزدوج لأي تعبير عن طريق تغيير
- كل AND إلى OR،
- وكل OR إلى AND،
- وكل 1 إلى 0،
- وكل 0 إلى 1،
مع الحفاظ على المتغيرات كما هي دون نفي.
When implementing a Boolean equation with logic gates, each term requires a gate, and each literal designates an input.
Algebraic simplification aims to reduce terms and literals, leading to smaller, faster circuits.
The principle of Duality states that the dual of an expression is obtained by changing
- AND to OR,
- OR to AND,
- 1s to 0s,
- and 0s to 1s,
while leaving the variables themselves uncomplemented.
الفرق بين الازدواجية (Dual) والمكمل (Complement) هو أن المكمل يتطلب نفي المتغيرات (حسب دي مورغان)، بينما الازدواجية تغير العمليات والثوابت فقط.
الازدواجية مفيدة جداً في إثبات النظريات البولينية، حيث أن إثبات نظرية ما يثبت تلقائياً نظيرتها المزدوجة.
The difference between a Dual and a Complement is that the complement requires negating the variables (via DeMorgan's), while the dual only changes operators and constants.
Duality is extremely powerful in Boolean proofs; proving a theorem automatically proves its dual.
ما هو النظير المزدوج (Dual) للتعبير X + 0 = X ؟ What is the dual of the expression X + 0 = X?
بتغيير + إلى نقطة (AND) و 0 إلى 1، نحصل على X . 1 = X.
By changing + to . (AND) and 0 to 1, we get X . 1 = X.
3 طريقة خريطة كارنوف (K-Map Method)
3 The Karnaugh Map (K-Map) Method
خريطة كارنوف هي تمثيل رسومي لجدول الحقيقة، تُستخدم لتبسيط الدوال البولينية بمجرد النظر من خلال تجميع المربعات المتجاورة.
A K-Map is a pictorial form of a truth table used to visually simplify Boolean functions by grouping adjacent squares.
توفر خريطة كارنوف إجراءً مباشراً لتقليل الدوال البولينية. تتكون الخريطة من مربعات، يمثل كل منها حداً أدنى (Minterm).
يتم ترتيب المربعات بتسلسل يشبه كود غراي (Gray Code)، حيث تتغير قيمة بت واحد فقط بين أي عمودين أو صفين متجاورين. هذا الترتيب يضمن أن المربعات المتجاورة تختلف في متغير واحد فقط، مما يسمح بتبسيط التعبيرات عند تجميعها.
الخرائط شائعة الاستخدام تتكون من 2، 3، أو 4 متغيرات (تحتوي على 4، 8، و 16 مربعاً على التوالي).
The K-map provides a straightforward procedure for minimizing Boolean functions. It consists of squares, each representing one minterm.
The squares are arranged in a Gray code sequence, meaning only one bit changes value between adjacent rows or columns. This ensures that physically adjacent squares differ by only one variable, allowing for algebraic simplification when grouped.
Common maps handle 2, 3, or 4 variables (having 4, 8, and 16 squares respectively).
الخاصية الأهم في خريطة كارنوف هي 'التجاور الدائري' (Wrap-around adjacency). المربعات الموجودة في الحواف اليمنى واليسرى (أو العليا والسفلى) تعتبر متجاورة لأنها تختلف في متغير واحد فقط.
عند زيادة عدد المتغيرات إلى 5 أو 6، تصبح الخريطة ثلاثية الأبعاد أو معقدة جداً (32 أو 64 مربعاً)، وهنا نلجأ عادةً إلى الخوارزميات الحاسوبية مثل Quine-McCluskey بدلاً من الحل اليدوي.
A critical property of K-maps is wrap-around adjacency. Squares on the extreme left and right edges (or top and bottom) are considered adjacent because their minterms differ by only one variable.
When scaling to 5 or 6 variables (32 or 64 squares), the 2D geometry becomes cumbersome, and algorithmic methods like Quine-McCluskey are preferred over manual K-maps.
لماذا لا نستخدم التسلسل الثنائي العادي (00, 01, 10, 11) في تسمية صفوف وأعمدة خريطة كارنوف؟ Why don't we use standard binary sequence (00, 01, 10, 11) for K-map rows and columns?
لأن الانتقال من 01 إلى 10 يغير بتين في نفس الوقت، مما يدمر خاصية التجاور التي تعتمد على تغير متغير واحد فقط لتمكين التبسيط المنطقي.
Because transitioning from 01 to 10 changes two bits simultaneously, destroying the adjacency property which requires only one variable to change for logical simplification.
4 المضامين الأولية والأساسية (Prime & Essential Implicants)
4 Prime & Essential Prime Implicants
المضمون الأولي هو أكبر مجموعة ممكنة من الآحاد المتجاورة، ويكون 'أساسياً' إذا كان يغطي رقم 1 لا تغطيه أي مجموعة أخرى.
A prime implicant is the largest possible group of adjacent 1s; it becomes 'essential' if it covers a 1 that no other group covers.
المضمون الأولي (Prime Implicant) هو مصطلح ضرب يتم الحصول عليه من خلال دمج أقصى عدد ممكن من المربعات المتجاورة في الخريطة (يجب أن يكون العدد من مضاعفات 2: 1، 2، 4، 8...).
إذا كان هناك مربع (Minterm) مغطى بمضمون أولي واحد فقط، فإن هذا المضمون يسمى 'مضمون أولي أساسي' (Essential Prime Implicant).
عند تبسيط الدالة، يجب أن نضمن
- تغطية جميع الحدود الدنيا،
- وتقليل عدد الحدود،
- وعدم وجود حدود زائدة.
A prime implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map (must be a power of 2: 1, 2, 4, 8...).
If a minterm in a square is covered by ONLY ONE prime implicant, that prime implicant is said to be essential.
When choosing squares, we must ensure
- all minterms are covered,
- the number of terms is minimized,
- and there are no redundant terms.
الخطوة الأولى في التبسيط المنهجي هي تحديد جميع المضامين الأولية الأساسية وإضافتها إلى المعادلة النهائية.
بعد ذلك، ننظر إلى الآحاد المتبقية التي لم تتم تغطيتها، ونختار الحد الأدنى من المضامين الأولية غير الأساسية لتغطيتها.
هذا يضمن الحصول على أبسط تعبير جبري ممكن (أقل عدد من البوابات والمداخل).
The systematic approach to minimization requires first identifying all Essential Prime Implicants and including them in the final expression.
Then, for any remaining uncovered 1s, we select the minimum number of non-essential prime implicants needed to cover them.
This guarantees the simplest algebraic expression (fewest gates and inputs).
| Prime Implicant | Essential Prime Implicant | |
|---|---|---|
| التعريف Definition | أكبر مجموعة ممكنة من المربعات المتجاورة Largest possible group of adjacent squares | مضمون أولي يغطي مربعاً لا يغطيه غيره A prime implicant covering a uniquely covered square |
| التواجد في الحل النهائي Presence in Final Solution | قد يُستبعد إذا تمت تغطية عناصره بمجموعات أخرى May be omitted if its 1s are covered elsewhere | يجب أن يكون موجوداً دائماً Must ALWAYS be included |
هل يمكن أن تتكون الدالة المبسطة النهائية من مضامين أولية غير أساسية فقط؟ Can a final simplified function consist entirely of non-essential prime implicants?
نعم، في بعض الحالات (مثل نمط رقعة الشطرنج أو الحلقات المتداخلة)، قد يكون كل 1 مغطى بأكثر من مضمون أولي، مما يعني عدم وجود مضامين أساسية، ويجب اختيار مجموعة فرعية تغطي الخريطة بأقل تكلفة.
Yes, in certain cyclic patterns, every 1 might be covered by multiple prime implicants, meaning none are strictly essential. You must then choose a minimal subset that covers all 1s.