الجبر البولياني والبوابات المنطقية
مقدمة في الشفرات الثنائية، المسجلات، المنطق الثنائي، والتعريف البديهي للجبر البولياني باستخدام مسلمات هنتنغتون.
Boolean Algebra and Logic Gates
Introduction to binary codes, registers, binary logic, and the axiomatic definition of Boolean algebra using Huntington postulates.
أهداف التعلم
- اكتساب فهم أساسي للمسلمات المستخدمة لتكوين الهياكل الجبرية.
- فهم النظريات والمسلمات الأساسية للجبر البولياني.
- معرفة كيفية تطبيق نظريات دي مورغان.
- Gain a basic understanding of postulates used to form algebraic structures.
- Understand the basic theorems and postulates of Boolean algebra.
- Know how to apply DeMorgan’s theorems.
1 الشفرات الثنائية وحساب عدد البتات
1 Binary Codes and Number of Bits Required
الشفرة الثنائية المكونة من n بت يمكنها تمثيل 2^n قيمة مختلفة، ونحتاج إلى دالة السقف لحساب الحد الأدنى من البتات.
An n-bit binary code can represent 2^n distinct values, and we use the ceiling function to find the minimum bits needed.
إشارات الأنظمة الرقمية لها قيمتان متمايزتان فقط. لتمثيل معلومات العالم الحقيقي بدقة أكبر، نحتاج إلى أكثر من قيمتين.
الشفرة الثنائية (Binary Code) المكونة من n بت هي مجموعة من n بتات يمكن أن تحتوي على 2^n قيمة متمايزة.
لتمثيل M من العناصر، فإن الحد الأدنى لعدد البتات n المطلوبة يحقق العلاقة: 2^n ≥ M > 2^(n-1). يمكن حسابها باستخدام المعادلة: n = ⌈log2 M⌉ حيث ⌈x⌉ هي دالة السقف (أصغر عدد صحيح أكبر من أو يساوي x).
Digital system signals have two distinct values only. To represent real-world information more accurately, we need more than two values.
An n-bit binary code is a group of n bits that can have 2^n distinct values.
Given M elements to be represented, the minimum number of bits, n, needed satisfies: 2^n ≥ M > 2^(n-1). This is calculated as n = ⌈log2 M⌉, where ⌈x⌉ is the ceiling function (the integer greater than or equal to x).
لماذا نستخدم دالة السقف؟ لأن عدد البتات يجب أن يكون عدداً صحيحاً.
إذا كان لدينا 10 عناصر (مثل الأرقام العشرية)، فإن log2(10) ≈ 3.32. لا يمكننا استخدام 3.32 بت، ولا يمكننا استخدام 3 بتات لأنها تمثل 8 عناصر فقط (وهو أقل من 10).
لذلك نأخذ السقف وهو 4 بتات، مما يعطينا 16 احتمالاً، نستخدم 10 منها ونهمل 6.
Why use the ceiling function? Because the number of bits must be an integer.
If we have 10 elements (like decimal digits), log2(10) ≈ 3.32. We can't use 3.32 bits, and 3 bits only give 8 combinations (too few).
So we take the ceiling, which is 4 bits, giving 16 combinations, using 10 and leaving 6 unused.
إذا كان لدينا آلة تحتوي على 50 حالة مختلفة، فما هو الحد الأدنى لعدد البتات المطلوبة لتمثيل هذه الحالات؟ If a machine has 50 distinct states, what is the minimum number of bits required to represent these states?
نحتاج إلى 6 بتات، لأن 2^5 = 32 (غير كافٍ) و 2^6 = 64 (كافٍ لتمثيل 50 حالة).
We need 6 bits, because 2^5 = 32 (not enough) and 2^6 = 64 (enough to represent 50 states).
2 النظام العشري المشفر ثنائياً (BCD)
2 Binary Coded Decimal (BCD)
نظام يمثل كل رقم عشري (0-9) باستخدام 4 بتات، ويسهل التحويل بين العشري والثنائي للإنسان.
A system that represents each decimal digit (0-9) using 4 bits, making decimal-to-binary conversion easier for humans.
في النظام العشري المشفر ثنائياً (BCD)، يتم تمثيل كل رقم عشري (من 0 إلى 9) بواسطة 4 بتات. المجموعات من (0000 إلى 1001) تعتبر تركيبات صالحة، بينما المجموعات من (1010 إلى 1111) أي من 10 إلى 15 تعتبر تركيبات غير صالحة.
- الميزة: يسهل على الأشخاص الذين يستخدمون النظام العشري التعامل مع بيانات الإدخال/الإخراج للكمبيوتر، حيث يسهل التحويل ذهاباً وإياباً إلى BCD.
- العيب: يحتاج رقم BCD إلى بتات أكثر من قيمته الثنائية المكافئة.
يجب عدم الخلط بين تحويل الرقم العشري إلى ثنائي، وبين تشفير الرقم العشري بشفرة BCD.
In Binary Coded Decimal (BCD), each decimal digit is represented by 4 bits. Combinations for (0 - 9) are valid, while combinations for (10 - 15) are invalid.
- Advantage: Computer input/output data are handled by people who use the decimal system, making it easier to convert back and forth to BCD.
- Disadvantage: A BCD number needs more bits than its equivalent binary value.
Do NOT mix up conversion of a decimal number to a binary number with coding a decimal number with a BINARY CODE.
الفرق بين التحويل والتشفير جوهري.
التحويل (Conversion) للرقم 13 يعطينا (1101) بالنظام الثنائي. أما التشفير (Coding) بـ BCD للرقم 13 فيعني تشفير الرقم 3 (0011) والرقم 1 (0001) بشكل منفصل، ليصبح (0001 0011).
هذا يستهلك 8 بتات بدلاً من 4 بتات في التحويل المباشر، مما يفسر عيب استهلاك مساحة أكبر.
The difference between conversion and coding is fundamental.
Conversion of 13 to binary is (1101)2. Coding 13 in BCD means coding 3 (0011) and 1 (0001) separately, resulting in (0001 0011)BCD.
This consumes 8 bits instead of 4, illustrating the disadvantage of needing more bits.
| BCD (Binary Coded Decimal) | Direct Binary Conversion | |
|---|---|---|
| سهولة التحويل للإنسان Ease of conversion for humans | سهل جداً (كل رقم عشري يُترجم لـ 4 بتات) Very easy (each digit maps to 4 bits) | صعب للأرقام الكبيرة (يتطلب عمليات قسمة متكررة) Harder for large numbers (requires repeated division) |
| كفاءة استهلاك البتات Bit efficiency | يستهلك بتات أكثر (مثال: 13 تحتاج 8 بتات) Consumes more bits (e.g., 13 needs 8 bits) | كفاءة عالية (مثال: 13 تحتاج 4 بتات فقط) Highly efficient (e.g., 13 needs only 4 bits) |
لماذا تعتبر التركيبات من 1010 إلى 1111 غير صالحة في نظام BCD؟ Why are the combinations from 1010 to 1111 considered invalid in BCD?
لأن نظام BCD يمثل الأرقام العشرية الفردية فقط (من 0 إلى 9). الأرقام من 10 إلى 15 تتطلب خانتين عشريتين، وبالتالي يتم تمثيلها بمجموعتين من 4 بتات في BCD.
Because BCD only represents single decimal digits (0 to 9). Numbers 10 to 15 require two decimal digits, and thus would be represented by two 4-bit groups in BCD.
3 شفرة غراي
3 Gray Code
شفرة ثنائية يتغير فيها بت واحد فقط عند الانتقال من رقم إلى الرقم الذي يليه، مما يقلل من استهلاك الطاقة.
A binary code where only one bit changes from one code to the next, reducing power consumption.
شفرة غراي (Gray Code) هي ترتيب للأنظمة الرقمية الثنائية بحيث تختلف قيمتان متتاليتان في بت واحد (خانة ثنائية واحدة) فقط. تختلف هذه الشفرة عن العد الثنائي التقليدي.
من أهم مميزاتها أنها تستهلك طاقة أقل لأن عدد الترانزستورات التي تعمل وتتوقف (on and off) يكون أقل عند الانتقال بين الحالات المتتالية.
Gray Code is an ordering of the binary numeral system such that two successive values differ in only one bit. It is different from standard Binary counting.
A major advantage is that less power is consumed since fewer transistors go on and off when transitioning between consecutive states.
في العد الثنائي العادي، الانتقال من 3 (0011) إلى 4 (0100) يتطلب تغيير 3 بتات في نفس الوقت. في الأنظمة الفيزيائية، لا تتغير البتات في نفس اللحظة تماماً، مما قد يسبب حالات عابرة خاطئة (Glitches).
شفرة غراي تحل هذه المشكلة بتغيير بت واحد فقط، مما يجعلها مثالية للمستشعرات الميكانيكية والأنظمة التي تتطلب موثوقية عالية في قراءة التغيرات المتتالية.
In standard binary, moving from 3 (0011) to 4 (0100) requires 3 bits to change simultaneously. In physical systems, bits don't change at the exact same microsecond, which can cause transient erroneous states (glitches).
Gray code solves this by changing only one bit at a time, making it ideal for mechanical encoders and systems requiring high reliability in reading sequential changes.
ما هي شفرة غراي للرقم العشري 2 بناءً على الجدول المرفق؟ What is the Gray code for the decimal number 2 based on the provided table?
شفرة غراي للرقم 2 هي 0011 (بينما الثنائي العادي هو 0010).
The Gray code for 2 is 0011 (whereas standard binary is 0010).
4 شفرة آسكي (ASCII)
4 ASCII Code
شفرة قياسية أمريكية تستخدم 7 بتات لتمثيل 128 حرفاً ورمزاً مختلفاً.
American Standard Code for Information Interchange using 7 bits to represent 128 different characters and symbols.
شفرة آسكي (ASCII) تقف لـ American Standard Code for Information Interchange. هي شفرة مكونة من 7 بتات، مما يعني أنها تستطيع تمثيل 128 عنصراً مختلفاً (من 0 إلى 127).
يتم تعيين رقم لكل حرف أو رمز. على سبيل المثال، شفرة ASCII للحرف الكبير 'A' هي '1000001' والتي تعادل الرقم العشري 65.
ASCII Code stands for American Standard Code for Information Interchange. It is a 7-bit code, meaning each letter or symbol is assigned a number from 0 to 127.
For example, the ASCII code for uppercase 'A' is '1000001', which is 65 in decimal.
استخدام 7 بتات كان كافياً لتمثيل الأبجدية الإنجليزية (كبيرة وصغيرة)، الأرقام، وعلامات الترقيم، بالإضافة إلى رموز التحكم (مثل SOH, ETX, ACK).
لاحقاً تم توسيعها إلى 8 بتات (Extended ASCII) لدعم لغات ورموز إضافية، مما مهد الطريق لظهور Unicode.
Using 7 bits was sufficient to represent the English alphabet (upper and lower case), digits, punctuation, and control characters (like SOH, ETX, ACK).
It was later extended to 8 bits (Extended ASCII) to support additional languages and symbols, paving the way for Unicode.
إذا كان الحرف 'A' يمثله الرقم 65، فما هو الرقم العشري الذي يمثل الحرف 'B'؟ If the letter 'A' is represented by 65, what decimal number represents the letter 'B'?
الرقم 66، لأن الحروف مرتبة تسلسلياً في شفرة ASCII.
The number 66, because letters are arranged sequentially in ASCII.
5 المسجلات والتخزين الثنائي
5 Registers and Binary Storage
المسجل هو مجموعة من الخلايا الثنائية؛ مسجل بحجم n خلية يمكنه تخزين n بت وتمثيل 2^n حالة مختلفة.
A register is a group of binary cells; an n-cell register can store n bits and represent 2^n possible states.
المسجل (Register) هو مجموعة من الخلايا الثنائية. المسجل الذي يحتوي على n من الخلايا يمكنه تخزين أي كمية منفصلة من المعلومات التي تحتوي على n بت.
حالة المسجل هي مجموعة (n-tuple) من الآحاد والأصفار (1's and 0's)، حيث يحدد كل بت حالة خلية واحدة في المسجل.
على سبيل المثال، مسجل بحجم 16 بت يمكن أن يكون في واحدة من 2^16 حالة ممكنة، ويمكنه تخزين أي رقم ثنائي من 0 إلى (2^16 - 1). تنتقل المعلومات بين المسجلات في وحدات الذاكرة، ووحدات المعالجة، ووحدات الإدخال.
A register is a group of binary cells. A register with n cells can store any discrete quantity of information that contains n bits.
The state of a register is an n-tuple of 1’s and 0’s, with each bit designating the state of one cell in the register.
For example, a 16-bit register can be in one of 2^16 possible states and can store any binary number from 0 to 2^16 – 1. Information is transferred among registers in memory units, processor units, and input units.
المسجلات هي أسرع أنواع الذاكرة في الكمبيوتر لأنها مدمجة مباشرة داخل وحدة المعالجة المركزية (CPU).
عمليات نقل البيانات بين المسجلات (Register Transfer) وعمليات التحويل الثنائي (مثل الجمع الموضح في الشرائح) تشكل الأساس لعمليات المعالج الدقيقة (Microoperations).
Registers are the fastest type of memory in a computer because they are built directly into the CPU.
Data transfers between registers (Register Transfer) and binary transformations (like the addition shown in the slides) form the basis of CPU microoperations.
ما هو أكبر رقم عشري يمكن تخزينه في مسجل بحجم 8 بت؟ What is the largest decimal number that can be stored in an 8-bit register?
أكبر رقم هو 255، والذي يُحسب بالمعادلة (2^8 - 1).
The largest number is 255, calculated as (2^8 - 1).
6 المنطق الثنائي والبوابات المنطقية
6 Binary Logic and Logic Gates
يتعامل المنطق الثنائي مع متغيرات تأخذ قيمتين (0 و 1) وثلاث عمليات أساسية: AND و OR و NOT.
Binary logic deals with variables taking two values (0 and 1) and three basic operations: AND, OR, and NOT.
يتعامل المنطق الثنائي مع متغيرات تأخذ قيمتين منفصلتين (صواب/خطأ، نعم/لا، 1/0) وعمليات تحمل معنى منطقياً. هناك ثلاث عمليات منطقية أساسية:
- AND (الضرب المنطقي): يُمثل بنقطة (.) أو بدون مشغل. z = x . y يعني أن z = 1 فقط إذا كان x = 1 و y = 1.
- OR (الجمع المنطقي): يُمثل بعلامة (+). z = x + y يعني أن z = 1 إذا كان x = 1 أو y = 1 أو كلاهما.
- NOT (المتمم): يُمثل بشرطة (') أو خط علوي. z = x' يعني عكس قيمة x (إذا كان x=1 فإن z=0 والعكس).
البوابات المنطقية (Logic Gates) هي دوائر إلكترونية تعمل على إشارة إدخال واحدة أو أكثر لإنتاج إشارة إخراج بناءً على هذه العمليات.
Binary logic deals with variables that take on two discrete values (true/false, yes/no, 1/0) and operations that assume logical meaning. There are three basic logical operations:
- AND: Represented by a dot (.) or absence of an operator. z = x . y means z = 1 if and only if x = 1 and y = 1.
- OR: Represented by a plus sign (+). z = x + y means z = 1 if x = 1 or y = 1 or both.
- NOT: Represented by a prime (') or overbar. z = x' means the complement of x (if x=1, z=0 and vice versa).
Logic gates are electronic circuits that operate on one or more input signals to produce an output signal based on these operations.
هذه العمليات الثلاث تشكل مجموعة كاملة وظيفياً (Functionally Complete Set)، مما يعني أنه يمكن بناء أي دائرة رقمية معقدة (مثل المعالجات والذواكر) باستخدام هذه البوابات الثلاث فقط.
يتم تمثيل سلوك هذه البوابات باستخدام جداول الحقيقة (Truth Tables) التي تسرد جميع الاحتمالات الممكنة للمدخلات والمخرجات المقابلة.
These three operations form a functionally complete set, meaning any complex digital circuit (like CPUs and memory) can be built using only these three gates.
The behavior of these gates is represented using Truth Tables, which list all possible input combinations and their corresponding outputs.
إذا كان لدينا بوابة AND بـ 3 مداخل، متى يكون المخرج 1؟ If we have a 3-input AND gate, when is the output 1?
يكون المخرج 1 فقط عندما تكون جميع المداخل الثلاثة تساوي 1.
The output is 1 only when all three inputs are equal to 1.
7 الجبر البولياني ومسلمات هنتنغتون
7 Boolean Algebra and Huntington Postulates
نظام جبري طوره جورج بول وتم تعريفه رسمياً بمسلمات هنتنغتون الستة التي تحكم العمليات المنطقية.
An algebraic system developed by George Boole, formally defined by the six Huntington postulates governing logical operations.
الجبر البولياني هو نظام رياضي استنتاجي يُعرّف بمجموعة من العناصر، ومجموعة من المشغلات، وعدد من المسلمات (Postulates). في عام 1904، صاغ E. V. Huntington المسلمات التالية لتعريف الجبر البولياني على مجموعة B مع المشغلين (+) و (.) :
- الانغلاق (Closure): النظام مغلق بالنسبة لـ (+) و (.).
- عنصر محايد (Identity): 0 هو المحايد لـ (+) حيث x+0=x. و 1 هو المحايد لـ (.) حيث x.1=x.
- التبديل (Commutative): x+y = y+x و x.y = y.x.
- التوزيع (Distributive): (.) يتوزع على (+) والعكس: x.(y+z) = (x.y)+(x.z) و x+(y.z) = (x+y).(x+z).
- المتمم (Complement): لكل x يوجد x' بحيث x+x'=1 و x.x'=0.
- يوجد على الأقل عنصران مختلفان x ≠ y.
Boolean algebra is a deductive mathematical system defined with a set of elements, operators, and postulates. In 1904, E. V. Huntington formulated postulates for Boolean algebra on a set B with operators (+) and (.):
- Closure: Closed with respect to (+) and (.).
- Identity element: 0 for (+) such that x+0=x; 1 for (.) such that x.1=x.
- Commutative: x+y = y+x and x.y = y.x.
- Distributive: (.) is distributive over (+), and (+) is distributive over (.): x.(y+z) = (x.y)+(x.z) and x+(y.z) = (x+y).(x+z).
- Complement: For every x, there exists x' such that x+x'=1 and x.x'=0.
- There exist at least two elements x ≠ y.
من المثير للاهتمام أن قانون التجميع (Associative Law) ليس جزءاً من مسلمات هنتنغتون الأساسية، ولكنه ينطبق على الجبر البولياني ويمكن اشتقاقه من المسلمات الأخرى.
كما أن قانون التوزيع لـ (+) على (.) غير موجود في الجبر العادي (حيث لا يمكنك قول 2+(3*4) = (2+3)*(2+4))، لكنه صحيح وأساسي في الجبر البولياني.
Interestingly, the Associative law is not included in Huntington's postulates, but it holds for Boolean algebra and can be derived from the others.
Also, the distributive law of (+) over (.) is valid in Boolean algebra (x+(y.z) = (x+y).(x+z)), which is NOT true in ordinary algebra.
| Boolean Algebra | Ordinary Algebra | |
|---|---|---|
| قانون التوزيع لـ (+) على (.) Distributive law of + over . | صالح: x+(y.z) = (x+y).(x+z) Valid: x+(y.z) = (x+y).(x+z) | غير صالح Invalid |
| المعكوسات (الطرح والقسمة) Inverses (Subtraction & Division) | لا يوجد معكوسات جمعية أو ضربية No additive or multiplicative inverses | موجودة وتسمح بالطرح والقسمة Exist, allowing subtraction and division |
| عملية المتمم (Complement) Complement operation | موجودة (x') Exists (x') | غير موجودة Does not exist |
لماذا لا يحتوي الجبر البولياني على عمليات الطرح أو القسمة؟ Why does Boolean algebra not have subtraction or division operations?
لأن الجبر البولياني لا يمتلك معكوسات جمعية (Additive inverses) أو معكوسات ضربية (Multiplicative inverses) كما في الجبر العادي.
Because Boolean algebra does not have additive or multiplicative inverses like ordinary algebra does.
8 الجبر البولياني ثنائي القيم
8 Two-Valued Boolean Algebra
تطبيق للجبر البولياني يقتصر على عنصرين فقط B = {0, 1}، وهو الأساس لجميع الدوائر الرقمية الحديثة.
An application of Boolean algebra restricted to only two elements B = {0, 1}, forming the basis of all modern digital circuits.
الجبر البولياني ثنائي القيم (Two-Valued Boolean Algebra) يُعرّف على مجموعة تتكون من عنصرين فقط، B = {0, 1}، مع قواعد للمشغلين الثنائيين (+) و (.). هذه القواعد هي بالضبط نفس عمليات AND و OR و NOT المنطقية.
يمكن إثبات صحة جميع مسلمات هنتنغتون لهذه المجموعة باستخدام جداول الحقيقة. على سبيل المثال، إثبات قانون التوزيع يتم عن طريق إنشاء جدول حقيقة لجميع الاحتمالات الممكنة للمتغيرات x, y, z ومقارنة النواتج.
Two-Valued Boolean Algebra is defined on a set of two elements, B = { 0, 1 }, with rules for the two binary operators + and . . These rules are exactly the same as the AND, OR, and NOT operations.
We can show that the Huntington postulates are valid for this set using truth tables. For example, the distributive law is proven by forming a truth table of all possible values of x, y, and z and showing both sides of the equation yield the same result.
التحقق من المسلمات باستخدام جداول الحقيقة يُعرف بـ 'الإثبات بالاستنفاد' (Proof by Exhaustion).
بما أن عدد الاحتمالات محدود جداً (مثلاً 8 احتمالات لـ 3 متغيرات 2^3)، يمكننا بسهولة حساب كل حالة للتأكد من تطابق الطرفين الأيمن والأيسر للمعادلة، وهو ما يثبت صحة المسلمة في هذا النظام الثنائي.
Verifying postulates using truth tables is known as 'Proof by Exhaustion'.
Since the number of combinations is strictly limited (e.g., 8 combinations for 3 variables, 2^3), we can easily compute every single case to ensure the left and right sides of an equation match, thus proving the postulate holds in this two-valued system.
كيف نثبت أن x + x' = 1 في الجبر البولياني ثنائي القيم؟ How do we prove that x + x' = 1 in Two-Valued Boolean Algebra?
بما أن x يمكن أن يكون 0 أو 1 فقط: إذا كان x=0 فإن 0 + 0' = 0 + 1 = 1. وإذا كان x=1 فإن 1 + 1' = 1 + 0 = 1. في كلتا الحالتين النتيجة 1.
Since x can only be 0 or 1: if x=0, 0 + 0' = 0 + 1 = 1. If x=1, 1 + 1' = 1 + 0 = 1. In both cases, the result is 1.