علاقات. الجزء الأول

تستخدم النظرية الشكلية للنمذجة العلاقات الجبرية ، بما في ذلك في تواقيع نماذج الهياكل الجبرية ، التي تصف الأشياء المادية والتقنية والمعلوماتية الحقيقية ، وعمليات عملها. من بين هذه الأخيرة ، على سبيل المثال ، أدرج قواعد البيانات (قواعد البيانات العلائقية (RDBs)). أنا أعتبر أن مجال صنع القرار لا يقل أهمية ، والذي يتكون من عنصرين إحصائيين رئيسيين وجبريين ، يعتمدان كليًا على نظرية العلاقات. المستوى التعليمي للمتخصصين في هذه النظرية قريب من الصفر.



افتح الكتاب المدرسي الخاص بالتخصص وسترى هناك ، في أحسن الأحوال ، حول المعادلات ، والتي يتم تفسيرها من قبل المؤلفين بطريقة غريبة للغاية. أسأل شخصًا سبق أن دافع عن شركة DTN: هل تفكر في علاقة التكافؤ من خلال عدم الإشارة إلى حامل العلاقة ، ولا إلى علاقة معينة ، كيف تبدو في سجلك؟ الجواب: كيف يبدو - عادة. اتضح أن لديه فكرة غامضة للغاية عن كل هذا.



أجد صعوبة في تسمية المنشورات المتعلقة بتصميم ReDB ، باستثناء المقالات الأجنبية. في التسعينيات ، كان معارضًا ، وكتب مراجعة لأطروحة ، والتي تعتبر قواعد بيانات هرمية وشبكية وعلائقية. ولكن مرة واحدة في السنة ، قبل عام ونصف ، جاء العمل مرة أخرى إلى المراجعة ، يكتب المؤلف بالفعل فقط عن DB ، حول تطبيع علاقات DB ، لكنه لم يُظهر أي حداثة نظرية. تقوم العديد من الجامعات بتدريس مقرر دراسي حول قواعد البيانات ، ولكن ليس حول كيفية إنشائها ، وإنشاء نظام DBMS ، ولكن كقاعدة عامة ، حول كيفية تشغيل قاعدة بيانات جاهزة (أجنبية).



القس. الموظفون ليسوا على استعداد لتعليم متخصصي تكنولوجيا المعلومات لإنشاء نظم إدارة قواعد البيانات ونظام التشغيل ولغات البرمجة المحلية ، ناهيك عن LSI و VLSI و LSI المخصص هنا ، على ما يبدو ، غادر القطار لفترة طويلة ولفترة طويلة. لذلك عبثًا تنفخ بعض الخدود بالفخر (اقرأ التكبر) ، ويمكن رؤية ذلك من التعليقات على منشورات الآخرين ، وأظهر لنفسك أنه يمكنك ذلك ، ولا تنغمس في الترجمات غير المجدية وإعادة كتابة شخص آخر من أجل الفخر - "التقييم" و "الكرمة" لا يؤثر فقط على الافتقار إلى الإبداع ، بل يؤثر في التعليم والتربية البسيطة.



المجال الثاني الذي يرتبط ارتباطًا وثيقًا بالعلاقات هو اتخاذ القرار. كل واحد منا مشغول بهذا باستمرار. لن نرفع إصبعنا دون قرار واعٍ أو فاقد للوعي. قليلون يفهمون ، ويكتبون أقل عن الحلول يعتمد قرار أي صانع قرار (صانع القرار) على تفضيل البدائل. ونموذج التفضيل هو بالتحديد هذا النوع من العلاقات ، والذي يسمى "فضاء علاقات التفضيل". لكن من يدرسهم. عندما أتيت إلى "متخصص" في العلاقات بسؤال عن عدد العلاقات من كل نوع ، فهو لا يعرف الإجابة ، "قتل" بسؤال مضاد ، لماذا تحتاجه؟

مفهوم العلاقة

أعتقد أن مصطلح "موقف" مألوف لدى كل قارئ ، لكن السؤال عن تعريفه سوف يربك أكثر. هناك اسباب كثيرة لهذا. هم في الغالب في المعلمين الذين ، إذا استخدموا العلاقات في عملية التدريس ، لم يركزوا على هذا المصطلح ، على ما يبدو لم يذكروا أمثلة لا تنسى.



في ذاكرتي هناك العديد من الأمثلة التي لا تنسى لمدى الحياة. حول التعيينات والعلاقات. سأتحدث عن التعيينات أولاً. هناك دلاء من الطلاء. في واحد أبيض ، والآخر - أسود. ويوجد صندوق مكعبات (كثير). الوجوه لها أرقام منقوشة. كم عدد الطرق التي يمكنك من خلالها تلوين وجوه المكعبات بلونين؟ الإجابة غير متوقعة - ما يصل إلى 6 بت الأرقام الثنائية ، أو 2 ⁶= 64. اسمحوا لي أن أشرح بمزيد من التفصيل f: 2 → 6 2 كائنات معروضة في 6. كل سطر من الجدول عبارة عن عرض منفصل لـ fi.



لنقم ببناء جدول مكون من 6 أعمدة وستتطابق الألوان مع الرقم أبيض - صفر ، أسود - واحد ، وأوجه المكعب عبارة عن أعمدة. نبدأ بحقيقة أن جميع الوجوه الستة بيضاء - وهذا متجه صفري سداسي الأبعاد. السطر الثاني هو أسود ذو وجه واحد ، أي أن البتة الأقل أهمية يتم ملؤها بالرقم 1. وهكذا حتى يتم استنفاد الأرقام الثنائية المكونة من 6 بتات. نضع المكعبات في صف طويل مشترك. يبدو أن كل واحد منهم لديه رقم من 0 إلى 63.



الآن يتم عكس العرض. عبوة من الأوراق (كثيرة) و 6 ألوان (أقلام فلوماستر).

ضع علامة على وجهي الأوراق الورقية باستخدام أقلام فلوماستر بألوان مختلفة. كم عدد الأوراق المطلوبة. الجواب f: 6 → 2 أو 6 ² = 36. هذه تعيينات عشوائية.



دعنا ننتقل إلى العلاقات. لنبدأ بمجموعة مجردة - حامل العلاقة

= {a1، a2، a3، ...، an}.

يمكنك أن تقرأ عنها هنا . لفهم أفضل ، سنقوم بتقليل المجموعة إلى 3 عناصر ، أي أ = {a1، a2، a3}. الآن نقوم الديكارتي الضرب × = ² ،

× = {(A1، A1)، (A1، A2)، (A1 و A3)، (A2، A1)، (A2، A2)، (A2، A3 )، (a3، a1)، (a3، a2)، (a3، a3)}.



حصلنا على 9 أزواج مرتبة من العناصر من A × A ، في زوج يكون العنصر الأول من العامل الأول ، والعنصر الثاني من العامل الثاني. لنحاول الآن الحصول على كل المجموعات الفرعية من المربع الديكارتي A × A. أولا ، مثال بسيط.



مثال 1... المجموعة أ = {أ ، ب ، ج ، د} من 4 عناصر معطاة. اكتب كل مجموعاتها الفرعية. B (A) = {Ø}؛ {a}؛ {b}؛ {c}؛ {d}؛ {ab}؛ {ac}؛ {ad}؛ {bc}؛ {bd}؛ {cd}؛ { abc}؛ {abd}؛ {acd}؛ {bcd}؛ {abcd}؛ 2 ⁴ = 16 مجموعة فرعية. هذه هي القيمة المنطقية B (A) للمجموعة A وتتضمن مجموعة فرعية فارغة.



ستحتوي المجموعات الفرعية من A × A على عدد مختلف من العناصر (أزواج): واحد ، اثنان ، ثلاثة ، وهكذا حتى جميع الأزواج التسعة ، نقوم أيضًا بتضمين المجموعة الفارغة (Ø) في هذه القائمة. كم عدد المجموعات الفرعية الموجودة؟ كثير ، أي 2 ⁹ = 512 عنصرًا.



التعريف . أي مجموعة فرعية من المنتج الديكارتي (لدينا مربع) من مجموعة تسمى علاقة . لاحظ أن العمل يستخدم نفس المجموعة. إذا كانت المجموعات مختلفة ، فلا توجد علاقة ، ولكن هناك مراسلات...



إذا كان ناتجًا ديكارتيًا لعاملين ، فإن العلاقة تكون ثنائية ، وإذا كان الرقم 3 داخليًا ، و 4 فهو رباعي ، و n هو n-ary. Arity هو عدد الأماكن في العلاقة. يتم إعطاء العلاقات أسماء الأحرف الكبيرة R و H و P و S ... دعونا نتحدث عن العلاقات الثنائية (BO) ، لأنها تلعب دورًا مهمًا للغاية في نظرية العلاقات. في الواقع يمكن اختزال كل الآخرين في العلاقات الثنائية.



يتم وضع رمز العلاقة على يسار العناصر R (x ، y) أو بينهما x R y ؛ x، y є A.

تعريف المجموعة المكونة من كل المجموعات الفرعية للمجموعة A تسمى Boolean. تتكون منطقتنا من 2 ^{| A × A |} العناصر هنا | A × A | هي أصل المجموعة.



يمكن تعيين العلاقات في تمثيلات مختلفة على A = {a1، a2، a3، a4}:

• تعداد العناصر R1 = {(a1، a2)، (a1، a3)، (a2، a3) (a2، a4) (a3، a2) (a3، a4}
• ثنائي ن = ناقل 16 بت ؛ <0110001101010000> ؛
• مصفوفة؛

الشكل 1.2. أ) 4 × 4 مصفوفة ذات علاقة ثنائية ب) ترقيم خلايا المصفوفة



هنا ، يتم استخدام أرقام الخلايا ، مليئة بالأرقام الموجودة في الشكل. 1 ب)

- تمثيل المتجهات. يتم تكوين المتجه الثنائي لتمثيل العلاقة الثنائية من العناصر {0،1} على النحو التالي:



سيبدو المثال المدروس لتعيين علاقة في شكل متجه كما يلي:





- التمثيل البياني. دعونا نربط عناصر المجموعة

A = {x1، x2، z3، ...، xn} بالنقاط على المستوى ، أي ، رؤوس الرسم البياني G = [Q، R].



ارسم قوسًا في الرسم البياني من (xi) إلى (xj) إذا وفقط إذا كان الزوج (xi، xj) є R (بالنسبة إلى i = j ، يتحول القوس (xi، xi) إلى حلقة عند الرأس (xi) مثال (الشكل. 1 أ) تمثيل العلاقة الثنائية أ [4 × 4] بواسطة رسم بياني موضح في الشكل 2.2.



الشكل 2.2. تمثيل العلاقة بواسطة رسم بياني موجه.



كتالوج العلاقات الثنائية (ن = 3)



يُنظر إلى كبير على مسافة. للتعرف على تنوعهم ، كان عليّ إنشاء كتالوج علاقة ثنائية يدويًا عبر مجموعة من 3 عناصر ، والتي تضمنت جميع العلاقات (أكثر من 500 علاقة). بعد ذلك ، جاء أو استمر في العلاقة.



من الواضح أن الكتالوج سيتضمن 2 ^{3 × 3} = 2 ⁹العلاقات ، وسيتم تجهيز كل منها بمجموعة من الخصائص المتأصلة. يوجد أدناه (الجدول 3) قائمة كاملة بجميع العلاقات الـ 512 عبر المجموعة A ، | A | = 3 من ثلاثة عناصر. يتم أيضًا تقديم نتائج حساب عدد النسب (الجدول 2) ، ممثلة بمجموعات من أرقام الخلايا في المربع الديكارتي 3 × 3 ، من الفئات الفرعية المختلفة لقيم مختلفة من أصل مجموعة الناقل (ن = 3). لكل علاقة ، يشار إلى خصائصها الأساسية والانتماء إلى النوع (الجدول 3). يتم الكشف عن الاختصارات المستخدمة في الكتالوج في الجدول 2

الجدول 2. الخصائص الكمية للفهرس لن مختلفة





من الملائم شرح جوهر العمليات مع العلاقات وتقنياتها باستخدام أمثلة بسيطة ومفهومة بشكل خاص للعلاقات الثنائية. يمكن أن تشمل العمليات علاقتين و / أو أكثر. العمليات التي يتم إجراؤها على العلاقات الفردية هي عمليات أحادية. على سبيل المثال ، عمليات عكس (الحصول على معكوس) علاقة ، أخذ علاقة مكملة ، تضييق (تحديد) العلاقة. مثال سوف يوضح كيفية استخدام الكتالوج.



مثال 2 . ضع في اعتبارك السطر Npr = 14 من جدول الكتالوج. لها الشكل



أول 9 أحرف من السطر (على يمين المساواة) عبارة عن متجه ثنائي يقابل مجموعة من 9 إلى 2 ، أي رقم الخلية الأولى (العد من اليسار إلى اليمين) هو رقم الخلية الخامسة من مصفوفة العلاقة الثنائية ، أي العناصر a1a1 = a2a2 = 1. تحتوي هذه المجموعة على رقم تسلسلي Ncc = 4 ورقم من خلال Npr = 14 في قائمة جميع العلاقات. يحتوي باقي هذا السطر على أصفار أو آحاد. تشير الأصفار إلى عدم وجود خاصية مقابلة لاسم عمود الصفر ، وتشير الأصفار إلى وجود هذه الخاصية في العلاقة المدروسة.

الخصائص والخصائص الكمية للعلاقات

دعونا ننظر في أهم خصائص العلاقات ، والتي ستسمح لنا بتسليط الضوء بشكل أكبر على أنواع (فئات) العلاقات المستخدمة في قواعد البيانات العلائقية في نظرية الاختيار واتخاذ القرار والتطبيقات الأخرى. فيما يلي ، سنشير إلى العلاقة بالرمز [R ، Ω]. R هو اسم العلاقة ، هي المجموعة الحاملة للعلاقة.



1. الانعكاسية. تسمى العلاقة [R، Ω] انعكاسية إذا كان كل عنصر من عناصر المجموعة في علاقة R بنفسها (الشكل 2.3). يحتوي الرسم البياني لـ BO الانعكاسي على حلقات (أقواس) في جميع الرؤوس ، وتحتوي مصفوفة العلاقة على (E) الوحدة القطرية الرئيسية.





الشكل 2.3. الموقف الانعكاسي



2. عدم الانعكاس . تسمى العلاقة [R، Ω] بمضاد الانعكاس إذا لم يكن هناك عنصر من المجموعة في العلاقة R بنفسها (الشكل 2.4). تسمى العلاقة المضادة للانعكاس صارمة.





الشكل 2.4. الموقف المضاد



للانعكاس 3. الانعكاسية الجزئية. تسمى العلاقة [R، Ω]

انعكاسية جزئية إذا كان عنصر واحد أو أكثر من المجموعة ليس في علاقة R بنفسها (الشكل 2.5).





4. التماثل. تسمى العلاقة [R، Ω] متناظرة إذا كانت العلاقة مع زوج مرتب (x، y) تحتوي أيضًا على زوج مرتب (y، x) (الشكل 2.6).





5. عدم التناسق. تسمى العلاقة [R ، Ω] غير المتماثلة إذا ، لأي زوج مرتب (x ، y) є R ، زوج مرتب

(y ، x) єR ، فقط في الحالة x = y. لمثل هذه النسب R∩R ^-1 ⊆ E (الشكل 2.7).





6. عدم التماثل. تسمى العلاقة [R ، Ω] غير متناظرة إذا كانت مضادة للانعكاس ولأي زوج مرتب (x ، y) є R زوج مرتب (y ، x) ∉ R ، للعلاقات R ∩ R ^-1 = Ø (الشكل 2.8).





7. العبور. تسمى العلاقة [R ، Ω] متعدية إذا ، لأي أزواج مرتبة (x ، y) ، (y ، z) є R ، فيما يتعلق R ، يوجد زوج مرتب (x ، z) є R أو إذا كان R × R⊆R (الشكل. 2.9).





8. دورية. تسمى العلاقة [R، Ω] دورية إذا كانت لعناصرها {x1، x2، z3، ...، xn} مجموعة فرعية من العناصر {xi، xi + 1، ... xr، ...، xj، xi}، من أجله يمكن للمرء أن يكتب التسلسل xiRxi + 1R ... RxjRxi. يسمى هذا التسلسل دورة أو حلقة (الشكل 2.10).





9. الحدة. تسمى العلاقات التي لا توجد بها ملامح لا دورية. بالنسبة للعلاقات غير الدورية ، تكون العلاقة R ^k ∩R = Ø مرضية لأي ك> 1 (الشكل 2.11).







10. الاكتمال (الاتصال). تسمى العلاقة [R ، Ω] كاملة (متصلة) إذا كان أي عنصرين (y ، z) є أحدهما مرتبطًا بالآخر (الشكل 2.12). الخطية. العلاقات الخطية هي علاقات كاملة إلى الحد الأدنى.





الشكل 2.12. العلاقة الخطية



لذلك ، لقد أثبتنا أن العلاقات ، ككائنات رياضية ، لها خصائص معينة ، تم تعريفها مسبقًا. في الفقرة التالية ، سننظر في جوهر ومظهر بعض الخصائص:

1. الانعكاسية x є A (xRx).
2. مضاد الانعكاس x є A ¬ (xRx).
3. التناظر x ، y є A (xRy → yRx).
4. عدم التناسق (xRy & yRx → x = y).
5. عبورية؛ x ، y ، z є A (xRy & yRz → xRz).
6. دورية س ، ص є أ ؛ ...
7. الاكتمال x، y є (xRy، yRx) ؛
8. الاتصال (x ≠ y → xRy، yRx).
9. الخطية x ، y є (xRy ، yRx).

يعتبر تحليل مساحة العلاقات مهمة معقدة للنظرية ، وتجدر الإشارة إلى أنها بعيدة عن الاكتمال. يجب أن تتضمن النتائج الرئيسية اختيار مجموعات فرعية من العلاقات التي تشكل مساحات كاملة من العلاقات مع كل النتائج المترتبة على ذلك.



العلاقات الكمية لهذه المساحات المنفصلة ذات أهمية

نظرية وعملية كبيرة. يتم النظر أدناه في بعض جوانب الخصائص الكمية المرتبطة بخصائص العلاقات من أنواع مختلفة.

عمليات على العلاقات

مثل معظم أنظمة الأرقام ذات العلاقات ، يتم تنفيذ العمليات التالية:

• أحادي.
• الثنائية؛
• ن اري.

فيما يلي جداول جمع Boolean وضربها ومتغيرين x1 و x2 ، إضافة mod 2 وجمع ثنائي:





أعلاه ، تم تقديم مفهوم العلاقة الثنائية ، كمجموعة فرعية من أزواج مرتبة من منتج ديكارتي للمجموعات ، كما تم النظر في خصائص العلاقات. بالإضافة إلى ذلك ، تم ذكر العلاقات الثنائية وتمثيل المصفوفة للعلاقات. دعونا الآن نفكر في مفهوم العلاقة بمزيد من التفصيل ، بالإضافة إلى ذلك ، ننظر في العمليات الأساسية للعلاقات الثنائية ، وهي أهم مجموعة للعلاقات.



بالنسبة لهم ، يجب استيفاء الشروط التالية:

• يجب أن يتطابق نطاق المعاملات في العملية ؛
• يجب أن تكون نتيجة العملية علاقة من نفس المنطقة.

بالنسبة للعلاقات الثنائية و n-ary ، يجب استيفاء ما يلي: يجب أن تتطابق منطقة وصول المعامل الأول مع منطقة أصل المعامل الثاني.



عمليات أحادية على العلاقات قلب



العلاقات . معكوس العلاقة R هو النسبة R ^-1 ، المحددة بالشرط xR ^-1 y <=> yRx. بشكل أكثر صحة ، يجب أن تسمى هذه العملية الانعكاس الزائف ، حيث أن p · p ^-1 ≠ E =.



دع العلاقة تُكتب في شكل سرد للأزواج المرتبة المتضمنة فيها. إذا تم تبادل المكونات في كل زوج ، فإن الأزواج الجديدة تشكل النسبة P ^-1 ، والتي تسمى معكوس P.



العلاقة العكسية للعلاقة P هي العلاقة التي تتكون من أزواج (ai aj) والتي من أجلها (aj ai) є P ^-1 . بالنسبة للعلاقات في شكل مصفوفة ، يتم الحصول على العلاقات العكسية عن طريق تبديل المصفوفة P.



9. العلاقة المزدوجة (P ^d ) إلى العلاقة P هي العلاقة التي تشكلها جميع الأزواج التي تنتمي إلى العلاقة العالمية ولا تنتمي إلى العلاقة العكسية (بالإضافة إلى معكوس):



P ^d = {(ai aj) | ((ai aj) єA × A) & (ai aj) ∉ P ^-1 )} = (A × A) \ P ^-1 .



العلاقات الثنائية والعكسية في المجموع تحتوي على جميع أزواج المنتج الديكارتي A × A وليس لها أزواج مشتركة ، فهي مثل العلاقات P و P تشكيل قسم A × A





لاحظ أنه لأي علاقة P غير راضٍ P P = ^d .



تضييق (PA1). تسمى العلاقة [R1، A1] تقييد العلاقة [R، A] بالمجموعة Ω1 إذا كانت 1⊆ Ω و R1 = R∩Ω1 × Ω1. النسبة PA1 في المجموعة A1 ⊆ A هي النسبة PA1 في المجموعة A1 ، والتي تكونت من جميع الأزواج التي تنتمي إلى العلاقة P والتي تعد في نفس الوقت جزءًا من المنتج الديكارتية A1 × A1. بمعنى آخر ، PA1 هو تقاطع العلاقات P و A1 × A1. دع A1 = {a1، a3، a4} ، ثم بالنسبة للعلاقات P و Q في شكل مصفوفة ، فإن علاقات التضييق سيكون لها الشكل:





العمليات الثنائية



التي تتطلب علاقتين على الأقل هي n-ary (n-ary). فقط العلاقات من نفس المجال يمكن أن تشارك في مثل هذه العمليات. أمثلة على هذه العمليات: التقاطع ، الاتحاد ، الاختلاف ، الاختلاف المتماثل في العلاقات ، وغيرها. إذا كانت العملية تستخدم أكثر من علاقتين ، فسيتم إجراؤها بالتسلسل لأول اثنين ، ثم للعلاقة النهائية والثالثة ، إلخ.



بمعنى آخر ، يتم تعريف هذه العمليات لعلاقات. في العمليات على العلاقات ، يُفترض أن مجالات تحديد العلاقات (المعاملات والنتيجة) تتطابق ، وتتطابق جوانب العلاقات ، وتكون نتيجة العملية مرة أخرى علاقة من نفس المجال. كأمثلة ، سننظر في العمليات على العلاقات الثنائية P و Q المحددة في مجموعة منفصلة

= {a1، a2، a3، a4} بواسطة المصفوفات المنطقية (كقاعدة عامة ، الأصفار لا تتناسب مع المصفوفة):





1. التقاطع (P ∩ Q) هو علاقة تتكون من كل أزواج العناصر من A التي تم تضمينها في كلا العلاقتين ، أي مشترك بين P و Q ،

P ∩ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) є Q)}.



يتم الحصول على مصفوفة النسبة P Q كتقاطع منطقي للمصفوفات P و Q:





في حالة عدم وجود مثل هذه الأزواج المشتركة ، يُقال أن تقاطع العلاقات فارغ ، أي إنها علاقة باطلة. تقاطع العلاقات R1 و R2 (R1∩R2) هو العلاقة التي يحددها تقاطع المجموعات الفرعية المقابلة من A × A.



2. الاتحاد (PUQ). اتحاد العلاقات R1 و R2 (R1UR2) هو العلاقة التي يحددها اتحاد المجموعات الفرعية المقابلة من A × A. النسبة المكونة من جميع الأزواج التي تشكل إما النسبة P أو النسبة Q ، أي عن طريق أزواج تنتمي إلى واحد على الأقل من العلاقات (الرابط ∨ - أو الرابط الموحد)

PUQ = {(ai aj) | ((ai aj) є P) ∨ ((ai aj) є Q)}.



إذا لم تكن هناك أزواج أخرى في المجموعة A × A لم يتم تضمينها في العلاقة PUQ ، وكان تقاطعها صفراً ، فيُقال إن العلاقات P و Q تشكلان علاقة كاملة A × A عند الجمع بينهما ، ويكون نظامهما قسمًا لهذه العلاقة الكاملة. يتم تكوين اتحاد مصفوفات العلاقة كمجموع منطقي لمصفوفات العلاقة:





3. الفرق (P \ Q) هو النسبة التي تشكلها تلك الأزواج من P غير المدرجة في العلاقة Q

P \ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) ∉Q)}.



الفرق في العلاقات في تمثيل المصفوفة





4. تكاثر العلاقات. قد تحتوي الأزواج المرتبة التي تشكل علاقة أو لا تحتوي على نفس العناصر. من بين الأزواج التي تحتوي على عناصر متطابقة في تكوينها ، دعنا نفرد هذه الأزواج المرتبة ، والتي نسميها المجاورة (المجاورة) والتي تحتوي على العنصر الأول في الزوج الثاني ، والعنصر الثاني في الزوج الأول هو نفسه. لنحدد منتج الأزواج المجاورة كزوج مرتب:

(ai ak) ∙ (ak aj) => (ai aj).



فيما يتعلق بنظرية الرسم البياني ، فإن ما ورد أعلاه يعني أن الأزواج المجاورة تشكل طريقًا من النقطة (ai) إلى النقطة (aj) في العبور عبر النقطة (ak) ، وتتألف من قوسين متجاورين. ناتج هذه الأقواس هو القوس الثالث من النقطة (ai) إلى النقطة (aj) ، والذي ينفذ الانتقال بين النقاط القصوى للمسار في نفس الاتجاه ، متجاوزًا النقطة الوسيطة (ak). يقال إن القوس (ai aj) يغلق هذه النقاط مباشرة.



5. الفرق المتماثل (P∆Q) - النسبة التي تشكلها الأزواج المتضمنة في PUQ الموحدة ، ولكنها غير مدرجة في التقاطع P∩Q. يوضح شكل آخر من أشكال التعريف اسم العملية: يتم تشكيل P∆Q بواسطة الأزواج المرتبة التي تمثل اتحاد الفروق P \ Q و Q \ P. وبالتالي ، يمكن كتابة التعبير عن الاختلاف المتماثل بطريقتين مختلفتين:

P∆ Q = (PU Q) \ (P ∩ Q) = (P \ Q) U (Q \ P).



مصفوفة الفرق المتماثل هي:





ويترتب على السجل الأخير أن عملية الاختلاف المتماثل تسمح بتبديل المعاملات ، أي أنها تبادلية.



5. التركيب أو المنتج (P ∙ Q) - العلاقة المكونة من جميع الأزواج والتي لها:

P ∙ Q = {(ai aj) | ((ai ak) є P) & ((ak aj) є Q)}.



بعبارة أخرى ، كل زوج مرتب في العلاقة الناتجة هو نتيجة مضاعفة الأزواج المتجاورة ، والتي ينتمي الزوج الأول منها إلى علاقة العامل الأول ، والثاني - إلى علاقة العامل الثانية. عملية التكوين ليست تبادلية.



التركيب (◦Q) على مجموعة M هو علاقة R محددة على نفس المجموعة M التي تحتوي على زوج (x ، y) عندما يكون هناك Z є M مثل (x، z) є P و (z، y) є س.



في تمثيل المصفوفة للعلاقات ، تكون مصفوفة تكوين العلاقات مساوية للمنتج المنطقي لمصفوفات العلاقات الأصلية:





حالة خاصة لتكوين العلاقات هي مربع العلاقة.



يمكن أن يُظهر باستخدام الاستقراء أن الدرجة n من العلاقة يتم تعريفها بشكل متكرر بواسطة الصيغة: P ⁿ = P ^n-1 ◦ ، وهذا يعني أن الزوج (x ، y) є P ⁿ في الحالة عندما يكون هناك سلسلة في المصفوفة العناصر: مثل (xi، xi + 1) є P، 1 <i <n - 1.



عملية التركيب لها خاصية الارتباط (مثل منتج المصفوفات).



تكوين العلاقات في المجموعة M هو نتيجة لتكوين العلاقات الزوجية لأي ترتيب للأقواس. منطقة تعيين نتيجة التكوين لا تتغير.



يتكون تكوين المصفوفات المنطقية للعلاقات كنتيجة للمنتج المنطقي لمصفوفات هذه العلاقات.



الجدول 3. فهرس العلاقات الثنائية (ن = 3). قابل للنقر