CS285: العلاقات - دليل دراسة شامل

١. مقدمة في العلاقات الثنائية

تعريف: العلاقة الثنائية (Binary Relation)

العلاقة الثنائية R من المجموعة A إلى المجموعة B هي مجموعة جزئية R ⊆ A × B.

بكلام ثاني: العلاقة الثنائية من A إلى B هي مجموعة أزواج مرتبة أول عنصر فيها من A وثاني عنصر من B.

نقطة مهمة: العلاقات أعم من الدوال. الدالة هي حالة خاصة من العلاقات حيث يرتبط كل عنصر من A بعنصر واحد بالضبط من B.

الترميز

• إذا كان (a,b) ∈ R ، نكتب: a R b (نقرأ "a مرتبط بـ b")
• إذا كان (a,b) ∉ R ، نكتب: a R̸ b (نقرأ "a غير مرتبط بـ b")
• عبارات بديلة: "a يرتبط b تحت العلاقة R"

مثال ١: علاقة الطالب - المقرر

نفرض A = {1, 2, 3} تمثل طلاب

نفرض B = {a, b} تمثل مقررات

R = {(1,a), (1,b), (2,a), (3,b)}

معنى هذا:

الطالب ١ مسجل في المقررات a و b
الطالب ٢ مسجل في المقرر a
الطالب ٣ مسجل في المقرر b

علاقة خاصة: علاقة الهوية (Identity Relation)

علاقة الهوية (I_A)

علاقة الهوية على المجموعة A هي: I_A = {(a,a) | a ∈ A}

كل عنصر مرتبط بنفسه فقط.

مثال: علاقة الهوية

إذا كانت A = {1, 2, 3, 4}، إذن:

I_A = {(1,1), (2,2), (3,3), (4,4)}

طرق تمثيل العلاقات

طريقة السرد (Roster Notation): قائمة بالأزواج المرتبة {(1,2), (3,4), ...}
طريقة بناء المجموعة (Set Builder): {(a,b) | شرط}
الرسم البياني الموجه (Graph/Digraph): تمثيل مرئي بنقاط وأسهم
جدول/مصفوفة: تمثيل بمصفوفة صفر-واحد

٢. خصائص العلاقات

العلاقات على مجموعة A (حيث R: A → A) تقدر تكون فيها خصائص خاصة:

الخاصية ١: الانعكاسية (Reflexivity)

علاقة انعكاسية (Reflexive)

العلاقة R على A تكون انعكاسية إذا (a,a) ∈ R لكل عنصر a ∈ A

بمعنى: كل عنصر مرتبط بنفسه.

علاقة لا انعكاسية (Irreflexive)

العلاقة R على A تكون لا انعكاسية إذا (a,a) ∉ R لكل عنصر a ∈ A

بمعنى: ما في عنصر مرتبط بنفسه.

مهم: "لا انعكاسية" ≠ "ليست انعكاسية"

العلاقة تقدر تكون لا انعكاسية ولا انعكاسية.
مثال: R = {(1,2), (2,1), (1,1)} على A = {1,2} هي ليست انعكاسية (لأن (2,2) ناقص) و ليست لا انعكاسية (لأن فيها (1,1)).

أمثلة على الأعداد الصحيحة

R₁ = {(a,b) | a ≤ b} - انعكاسية (كل عدد ≤ نفسه)

R₂ = {(a,b) | a > b} - لا انعكاسية (مافي عدد > نفسه)

R₃ = {(a,b) | a = b أو a = -b} - انعكاسية

R₄ = {(a,b) | a = b} - انعكاسية

الخاصية ٢: التناظر (Symmetry)

علاقة متناظرة (Symmetric)

العلاقة R على A تكون متناظرة إذا:

(a,b) ∈ R → (b,a) ∈ R لكل a, b ∈ A

إذا كان (a,b) موجود، لازم (b,a) يكون موجود أيضًا.

علاقة غير متناظرة (Antisymmetric)

العلاقة R على A تكون غير متناظرة إذا:

(a,b) ∈ R ∧ (b,a) ∈ R → a = b

بطريقة ثانية: إذا كان (a,b) موجود و a ≠ b ، إذن (b,a) ما ينبغي يكون موجود.

مهم: التناظر وغير التناظر مو عكس بعض!

العلاقة تقدر يكون فيها الخاصيتين (مثل R = {(a,b) | a = b})
العلاقة تقدر ما يكون فيها ولا خاصية
العلاقة لا تقدر تكون متناظرة وغير متناظرة إذا كان فيها زوج (a,b) مع a ≠ b

أمثلة على الأعداد الصحيحة

R₁ = {(a,b) | a = b} - متناظرة وغير متناظرة

R₂ = {(a,b) | a > b} - ليست متناظرة، غير متناظرة

R₃ = {(a,b) | a = b+1} - ليست متناظرة، غير متناظرة

الخاصية ٣: التعدي (Transitivity)

علاقة متعدية (Transitive)

العلاقة R تكون متعدية إذا:

(a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R لكل a, b, c

إذا كان في طريق من a إلى b ومن b إلى c، لازم يكون في اتصال مباشر من a إلى c.

مثال: اختبار التعدي

A = {1, 2}

R₁ = {(1,1), (1,2), (2,1), (2,2)} - متعدية

التحقق: (1,2) و (2,1) في R₁ و (1,1) في R₁ ✓

R₂ = {(1,1), (1,2), (2,1)} - غير متعدية

ليش؟ (2,1) و (1,2) في R₂ لازم (2,2) موجود، لكنه ناقص ✗

جدول ملخص

الخاصية	التعريف	التحقق البصري
انعكاسية	∀a: (a,a) ∈ R	كل عناصر القطر في المصفوفة = ١
لا انعكاسية	∀a: (a,a) ∉ R	كل عناصر القطر في المصفوفة = ٠
متناظرة	(a,b) ∈ R → (b,a) ∈ R	المصفوفة متناظرة (M = M^T)
غير متناظرة	(a,b) ∈ R ∧ (b,a) ∈ R → a = b	كل ١ مقابل ١ عبر القطر تكون من ٠
متعدية	(a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R	كل مثلث في الرسم البياني مكتمل

٣. تمثيل العلاقات

الطريقة ١: مصفوفات صفر-واحد

تمثيل المصفوفة

لتمثيل العلاقة R بمصفوفة M_R = [m_ij]:

m_ij = 1 إذا كان (a_i, b_j) ∈ R

m_ij = 0 إذا كان (a_i, b_j) ∉ R

مثال: تمثيل بمصفوفة

A = {1, 2, 3}, B = {1, 2}

R = {(2,1), (3,1), (3,2)}

المصفوفة M_R:

	1	2
1	0	0
2	1	0
3	1	1

تحديد الخصائص من المصفوفات

انعكاسية:

كل عناصر القطر الرئيسي (من فوق-يسار إلى تحت-يمين) = ١

لا انعكاسية:

كل عناصر القطر الرئيسي = ٠

متناظرة:

المصفوفة تساوي منقولتها: M = M^T

كل ١ تنعكس عبر القطر

غير متناظرة:

إذا m_ij = 1 و i ≠ j ، إذن m_ji = 0

أي ١ في موقع (i,j) مقابلها (j,i) تكون ٠

الطريقة ٢: الرسوم البيانية الموجهة (Digraphs)

تمثيل الرسم البياني الموجه

رسم بياني موجه G = (V_G, E_G) حيث:

V_G مجموعة الرؤوس (العقد) - تمثل عناصر المجموعة A
E_G مجموعة الأقواس - تمثل الأزواج المرتبة في R
نرسم سهم من العقدة a إلى العقدة b إذا (a,b) ∈ R

مثال: رسم بياني موجه

R = {(1,1), (2,2), (3,3), (4,4), (1,3), (1,2), (1,4), (2,4)}

على المجموعة {1, 2, 3, 4}

الشكل: كل رقم له حلقة على نفسه (انعكاسي)، وأسهم من ١ إلى ٢, ٣, ٤ ومن ٢ إلى ٤.

تحديد الخصائص من الرسم البياني

انعكاسية:

كل رأس عنده حلقة (قوس على نفسه)

لا انعكاسية:

مافي أي رأس عنده حلقة

متناظرة:

كل قوس له قوس مقابل في الاتجاه المعاكس (أسهم ثنائية الاتجاه)

غير متناظرة:

مافيه رأسين مختلفين بينهم أسهم في الاتجاهين

متعدية:

إذا كان في مسار من x إلى y و من y إلى z، لازم يكون في قوس مباشر من x إلى z

٤. دمج العلاقات

العملية ١: الاتحاد والتقاطع

الاتحاد (R₁ ∪ R₂):

M_R₁∪R₂ = M_R₁ ∨ M_R₂

OR على مستوى العناصر: m_ij = 1 إذا كان العنصر في R₁ أو R₂

التقاطع (R₁ ∩ R₂):

M_R₁∩R₂ = M_R₁ ∧ M_R₂

AND على مستوى العناصر: m_ij = 1 إذا كان العنصر في R₁ و R₂

مثال: الاتحاد والتقاطع

A = {1, 2, 3}

R₁ = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2)}

R₂ = {(1,1), (1,2), (1,3), (1,4)}

R₁ ∪ R₂ = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2), (1,3), (1,4)}

R₁ ∩ R₂ = {(1,1), (1,2)}

العملية ٢: التركيب (Composition)

التركيب (S ∘ R):

إذا كانت R: A → B و S: B → C ، فإن S ∘ R: A → C

(a,c) ∈ S ∘ R إذا وُجد b بحيث (a,b) ∈ R و (b,c) ∈ S

المصفوفة: M_S∘R = M_R ⊙ M_S (ضرب بوليان)

مهم: M_S∘R = M_R ⊙ M_S ≠ M_S ⊙ M_R

الترتيب يهم في التركيب!

الضرب البولياني (Boolean Product):
زي ضرب المصفوفات العادي، لكن:
• نستخدم ∨ (OR) بدل + (الجمع)
• نستخدم ∧ (AND) بدل × (الضرب)

مثال: التركيب

R = {(1,1), (1,2), (2,5), (3,4)}

S = {(1,6), (2,1), (4,0)}

S ∘ R:

(1,1) في R و (1,6) في S → (1,6) في S∘R
(1,2) في R و (2,1) في S → (1,1) في S∘R
(3,4) في R و (4,0) في S → (3,0) في S∘R

S ∘ R = {(1,6), (1,1), (3,0)}

العملية ٣: قوى العلاقات

القوى:

R¹ = R

Rⁿ⁺¹ = Rⁿ ∘ R

المصفوفة: M_Rⁿ = M_R^[n] (القوة البوليانية)

مثال: القوى

R = {(1,1), (2,1), (3,2), (4,3)}

R² = R ∘ R = {(1,1), (2,1), (3,1), (4,2)}

R³ = R² ∘ R = {(1,1), (2,1), (3,1), (4,1)}

٥. إغلاق العلاقات

مفهوم الإغلاق (Closure):

لأي خاصية X ، "إغلاق X" لمجموعة A هو أصغر مجموعة عظمى (superset) للمجموعة A تحقق الخاصية X.

نضيف أقل عدد من العناصر إلى R عشان نخليها تحقق الخاصية.

١. الإغلاق الانعكاسي (Reflexive Closure)

الإغلاق الانعكاسي لـ R:

نضيف (a,a) إلى R لكل a ∈ A إذا ماكانت موجودة.

الصيغة: R ∪ I_A

حيث I_A = {(a,a) | a ∈ A} هي علاقة الهوية

مثال: الإغلاق الانعكاسي

R = {(1,1), (1,2), (2,1), (3,2)} على A = {1, 2, 3}

النواقص: (2,2) و (3,3)

الإغلاق الانعكاسي = {(1,1), (1,2), (2,1), (3,2), (2,2), (3,3)}

٢. الإغلاق التناظري (Symmetric Closure)

الإغلاق التناظري لـ R:

نضيف (b,a) إلى R لكل (a,b) في R إذا ماكان (b,a) موجود.

الصيغة: R ∪ R^-1

حيث R^-1 = {(b,a) | (a,b) ∈ R} هي العلاقة العكسية

مثال: الإغلاق التناظري

R = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2)}

النواقص من الأزواج العكسية: (2,1) و (1,3)

الإغلاق التناظري = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2), (2,1), (1,3)}

٣. الإغلاق المتعدي (Transitive Closure)

الإغلاق المتعدي لـ R:

نضيف (a,c) إلى R بشكل متكرر لكل (a,b) و (b,c) في R إذا (a,c) مو موجود.

الصيغة: R* = R ∪ R² ∪ R³ ∪ ... ∪ Rⁿ

حيث n = |A| (حجم المجموعة A)

المصفوفة: M_R* = M_R ∨ M_R^[2] ∨ ... ∨ M_R^[n]

مثال: الإغلاق المتعدي

R = {(1,1), (1,2), (2,1), (3,2)} على A = {1, 2, 3}

R² = R ∘ R = {(1,1), (1,2), (2,1), (2,2), (3,1)}

R³ = R² ∘ R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)}

الإغلاق المتعدي R* = R ∪ R² ∪ R³

= {(1,1), (1,2), (2,1), (3,2), (2,2), (3,1)}

ملخص: حساب الإغلاقات

نوع الإغلاق	الصيغة	ماذا نضيف
انعكاسي	R ∪ I_A	كل الأزواج (a,a)
تناظري	R ∪ R^-1	عكس كل زوج
متعدي	R ∪ R² ∪ ... ∪ Rⁿ	كل المسارات بطول ≥ ٢

٦. علاقات التكافؤ (Equivalence Relations)

علاقة تكافؤ:

علاقة التكافؤ على مجموعة A هي أي علاقة ثنائية على A تحقق:

انعكاسية (Reflexive)
متناظرة (Symmetric)
متعدية (Transitive)

فكرة أساسية: علاقات التكافؤ تقسّم المجموعة A إلى مجموعات جزئية (أقسام) العناصر داخل كل قسم متكافئة مع بعضها.

مثال ١: تكافؤ على الأعداد الحقيقية

R = {(a,b) | a - b عدد صحيح} على الأعداد الحقيقية

تحقق الانعكاسية: a - a = 0 وهو عدد صحيح ✓

تحقق التناظر: إذا كان a - b عدد صحيح، فإن b - a = -(a-b) أيضًا عدد صحيح ✓

تحقق التعدي: إذا كان a - b و b - c عددين صحيحين، فإن a - c = (a-b)+(b-c) عدد صحيح ✓

النتيجة: R علاقة تكافؤ!

مثال ٢: التطابق نمط n (Congruence Modulo n)

R = {(a,b) | a ≡ b (mod n)} - "a تطابق b نمط n"

معناها أن n يقسم (a - b)

هذه علاقة تكافؤ وتقسّم الأعداد الصحيحة إلى n أصناف تكافؤ:

[0] = {..., -6, -3, 0, 3, 6, ...} (في نمط ٣)
[1] = {..., -5, -2, 1, 4, 7, ...}
[2] = {..., -4, -1, 2, 5, 8, ...}

تطبيقات علاقات التكافؤ

أمثلة شائعة:

المساواة (=): أبسط علاقة تكافؤ
نفس العمر: الناس اللي أعمارهم متساوية
نفس تاريخ الميلاد: الناس اللي انولدوا في نفس اليوم
التطابق نمط n: الأعداد اللي باقي قسمتها على n متساوي
المثلثات المتشابهة: مثلثات زواياها متساوية

فحص سريع لعلاقات التكافؤ

قائمة التدقيق:
☑ انعكاسية: (a,a) لكل a؟
☑ متناظرة: إذا (a,b) يوجب (b,a)؟
☑ متعدية: إذا (a,b) و (b,c) يوجب (a,c)؟

إذا كل الثلاثة نعم → علاقة تكافؤ!

📝 مرجع سريع

التحقق السريع من الخصائص

عشان تفحص إذا...	بالمصفوفة	بالرسم البياني
انعكاسية	كل القطر = ١	حلقة عند كل رأس
متناظرة	M = M^T	كل الأسهم ثنائية الاتجاه
متعدية	تحقق M^[2] ⊆ M	كل مثلث مكتمل
تكافؤ	انعكاسية + متناظرة + R² ⊆ R	الخصائص الثلاثة

أخطاء شائعة - تجنبها

⚠️ تنبيه:

لا تخلط بين "ليست انعكاسية" و "لا انعكاسية".
لا تخلط بين "ليست متناظرة" و "غير متناظرة".
تذكّر: ترتيب التركيب يهم! S ∘ R ≠ R ∘ S
في الإغلاق المتعدي، قد تحتاج قوى كثيرة (حتى Rⁿ).
العمليات البوليانية: ∨ تعني OR، ∧ تعني AND (مو الجمع والضرب العادي).

صيغ لازم تحفظها

صيغ أساسية:
• الإغلاق الانعكاسي: R ∪ I_A
• الإغلاق التناظري: R ∪ R^-1
• الإغلاق المتعدي: R* = R ∪ R² ∪ R³ ∪ ... ∪ Rⁿ
• التركيب: M_S∘R = M_R ⊙ M_S
• الاتحاد: M_R₁∪R₂ = M_R₁ ∨ M_R₂
• التقاطع: M_R₁∩R₂ = M_R₁ ∧ M_R₂

📋 المحتويات

١. مقدمة في العلاقات الثنائية

الترميز

علاقة خاصة: علاقة الهوية (Identity Relation)

طرق تمثيل العلاقات

٢. خصائص العلاقات

الخاصية ١: الانعكاسية (Reflexivity)

علاقة انعكاسية (Reflexive)

علاقة لا انعكاسية (Irreflexive)

الخاصية ٢: التناظر (Symmetry)

علاقة متناظرة (Symmetric)

علاقة غير متناظرة (Antisymmetric)

الخاصية ٣: التعدي (Transitivity)

علاقة متعدية (Transitive)

جدول ملخص

٣. تمثيل العلاقات

الطريقة ١: مصفوفات صفر-واحد

تحديد الخصائص من المصفوفات

انعكاسية:

لا انعكاسية:

متناظرة:

غير متناظرة:

الطريقة ٢: الرسوم البيانية الموجهة (Digraphs)

تحديد الخصائص من الرسم البياني

انعكاسية:

لا انعكاسية:

متناظرة:

غير متناظرة:

متعدية:

٤. دمج العلاقات

العملية ١: الاتحاد والتقاطع

العملية ٢: التركيب (Composition)

العملية ٣: قوى العلاقات

٥. إغلاق العلاقات

١. الإغلاق الانعكاسي (Reflexive Closure)

الإغلاق الانعكاسي لـ R:

٢. الإغلاق التناظري (Symmetric Closure)

الإغلاق التناظري لـ R:

٣. الإغلاق المتعدي (Transitive Closure)

الإغلاق المتعدي لـ R:

ملخص: حساب الإغلاقات

٦. علاقات التكافؤ (Equivalence Relations)

تطبيقات علاقات التكافؤ

أمثلة شائعة:

فحص سريع لعلاقات التكافؤ

📝 مرجع سريع

التحقق السريع من الخصائص

أخطاء شائعة - تجنبها

صيغ لازم تحفظها