🤹🏿 🧔🏽 🧢 الخصائص الكمية للعلاقات 📈 🤦🏽 🤜🏾

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

مثال بسيط. منذ عدة سنوات في الكتاب [1 ص 207] صادفت مثل هذه الفقرة.

لا تزال نظرية المجموعات المرتبة جزئيًا تحتوي على العديد من المشكلات التي لم يتم حلها. حتى مسألة عدد هذه المجموعات التي يمكن بناؤها من عدد معين من العناصر لا توجد حتى الآن إذا كان n≥6. نجحت الحسابات المباشرة فقط في إثبات أنه إذا كان S (n) هو عدد المجموعات المرتبة جزئيًا ، فإن S (2) = 3 ، S (3) = 19 ، S (4) = 219 ، S (5) = 4231 ، والأرقام S تم العثور على (ن) للمجموعات غير المتشابهة فقط لـ n = 4 و n = 5 عناصر: Sn (4) = 16 و Sn (5) = 63.

حول هذا يكتب رئيس قسم جامعة موسكو الحكومية Rybnikov K.A. كنت أرغب في التعمق في هذا الأمر ، وبدا أنه يمكنني محاولة البحث عن حل ، على الأقل بطريقة ما توسيع القائمة ، والأهم من ذلك - سرد الطلبات الجزئية ، انظر تناثرها في الواقع مع خصائصها. فقط لتعليق النتائج على الحائط. أعترف أنه تم بذل الكثير من الجهد لتطوير برنامج بحث وإنشاء نموذج عملي للترتيب الجزئي وكتابة برنامج وتصحيحه ، كانت أجهزة الكمبيوتر تدور حول الخوارزميات المبرمجة لعشرات الساعات. تتبادر ملاحظة شخص ما (من العظماء) إلى أن أساس الرياضيات يجب ألا يكون رقمًا ، بل أمرًا ، ومن المفترض إذن أن العديد من النظريات قد تلقت براهين أبسط وأكثر شفافية.

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

ما تمكنت من فتحه (الحصول عليه) أقدمه أدناه في النص. بالمناسبة ، تزامنت نتائج الباحثين الأجانب الآخرين مع نتائجنا ، لكنهم أبلغوا فقط عن الرقم S (n) ولم يذكروا تعداد الطلبات الجزئية.

بدأنا صغيرًا. القائمة الكاملة للعلاقات الثنائية لأي مجموعة حاملة n معروفة ويمكن الحصول عليها بسهولة. كانوا يبحثون عن إجابة للأسئلة: كم عدد العلاقات مع خاصية واحدة ثابتة ، مع زوج من الخصائص ، وثلاثية ، وما إلى ذلك ، بالنسبة إلى n معطى ، وما إلى ذلك. والحقيقة هي أنه مع وجود هذه البيانات ، كان من الممكن بناء ليس التعداد ، ولكن إنشاء خوارزميات مباشرة لتعداد مثل هذه العلاقات التي باتباع قاعدة الحلاقة أوكام ، فإنها لا تنتج جوهرات إضافية.

هنا سنتحدث عن الحصول على مثل هذه النتائج للعلاقات الثنائية (BR).

لذلك ، هناك حاملة مجموعة n لـ BO وقائمة كاملة لجميع BOs ، بالإضافة إلى قائمة بخصائص BO:

- الانعكاسية. الانعكاسية. انعكاس جزئي

- تناظر؛ عدم التناسق. عدم التناسق. عدم التناسق.

- عبورية؛ مكافحة العبور.

- ترتيب ضعيف ترتيب صارم طلب جزئى؛ الكمال (الخطي) ؛

- تسامح؛

- التكافؤ

- التقلبات الدورية

- الاكتمال.

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

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

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

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

انعكاسية

العلاقة α = <، A> على المجموعة A = {

а_{1}, а_{2}, . . ., а_{n}

${_1,_2,...,_n}$ } انعكاسي (له خاصية الانعكاس) إذا كان كل زوج (

а_{i}, а_{i}

$_ i, _ i$ ) يرضي هذه العلاقة. هنا M هو رسم بياني (وليس رسم بياني) للعلاقة

а_{i} α а_{i}, а_{i} є A, i = 1 (1) | A |

$_ i α _ i , _i є A , i = 1(1)|A|$ ...

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

а_{i} є A, i = 1 (1) | A |

$_i є A , i = 1(1)|A|$ لم تتم

а_{i} α а_{i}

$_ i α _ i$ ... في هذه الحالة ، لا تحتوي مصفوفة العلاقة المضادة للانعكاس α على القطر الرئيسي على وحدة واحدة ، أي هناك أصفار ، والرسم البياني المقابل ليس له حلقات في أي قمة.

أخيرًا ، العلاقة α غير عاكسة إذا كان للبعض

а_{i} є A, а_{i} α а_{i}

$_i є A ,_ i α _ i$ تم إعدامه ، لكن بالنسبة للآخرين لم يتم تنفيذه. سوف نعتبر هذه العلاقات انعكاسية جزئيًا. تحتوي مصفوفة العلاقة غير العاكسة على القطر الرئيسي على جزء منها ، جزئيًا - أصفار. لا يحتوي الرسم البياني لهذه العلاقة غير العاكسة على حلقات في جميع الرؤوس.

المثال الكلاسيكي للعلاقة الانعكاسية هو القطر الرئيسي لتمثيل المصفوفة ، نسبة الوحدة (E = Δ) ، أي علاقة المساواة (في الكتالوج رقم 68). يتكون الرسم البياني لهذه النسبة من نقاط (أزواج) ملقاة على القطر الرئيسي للمصفوفة والأزواج المقابلة

(i, i) А, i = 1 (1) | A |

$( i , i ) , i =1(1)|A|$ ، لا يحتوي الرسم البياني على أي نقاط أخرى.

تمثيل المصفوفة لهذه النسبة يتوافق مع مصفوفة الهوية (E). يتكون الرسم البياني للعلاقة القطرية من الرؤوس المقابلة للعناصر من المجموعة A التي تم تخصيص الحلقات لها. غالبًا ما يتم الإشارة إلى العلاقة القطرية بواسطة

Δ_{А}

$Δ_$ ...

في حالة العلاقة الانعكاسية ، يكون الرسم البياني المقابل انعكاسيًا أيضًا ، في حالة العلاقة المضادة للانعكاس ، يكون الرسم البياني الخاص به مضادًا للانعكاس. إذا كان من المعروف بالنسبة لعلاقة ما أنها انعكاسية ، فإن المكمل ᾱ يكون دائمًا مضادًا للانعكاس ، و

α \cap ᾱ = \emptyset, α \cap Δ_{А} = Δ_{А}

$α ∩ ᾱ =∅ , α ∩ Δ_ = Δ_$ ...

بالنسبة للعلاقة المضادة للانعكاس β ، هذا صحيح

β \cap Δ_{А} = \emptyset

$β ∩Δ_= ∅$ ...

مثال 1 . العلاقة ≤ (لا أكثر) على المجموعة N انعكاسية ، والعلاقة <(أقل) على نفس المجموعة هي مضادة للانعكاس.

موقف "كونك ابنًا" هو موقف مناهض للتأمل ، حيث لا يوجد أحد هو ابنه.

لأغراض عملية ، من الضروري أحيانًا حساب عدد العلاقات الانعكاسية المتاحة في المجموعة الكاملة من العلاقات المعطاة في المجموعة A مع العلاقة الأساسية | A | = ن.

دعونا نوضح كيف يمكن إجراء مثل هذا الحساب. سننظر على المستوى في مصفوفة العلاقة الانعكاسية الثنائية α. يحتوي دائمًا على جميع النقاط القطرية.

النقاط المتبقية المقابلة للأزواج (i ، j) ، عدد n × n - n = n (n - 1) ، يمكن تضمينها في تكوين مختلف ورقم k ، k = 0 (1) (n × n - n)في العلاقات الممكنة ، والتي ، بالطبع ، ستكون انعكاسية. من خلال جمع مجموعات k من n (n-1) على k ، يتم تحديد العدد الإجمالي للعلاقات الانعكاسية

حيث K = n (n-1) / 2 هو عدد الأقواس (الحواف) في الرسم البياني n- رأس بدون حلقات.

يُعرَّف عدد العلاقات غير العاكسة على أنه الفرق بين العدد الإجمالي للعلاقات في A وعدد العلاقات الانعكاسية.

ويترتب على هذا التعبير أن مجموعة العلاقات غير العاكسة تحتوي في

(2^{n} - 1)

$(2^n -1)$ مرات أكثر من العلاقات الانعكاسية. يتم إنشاء هذا الفائض في النسب من خلال مجموعة متنوعة من مجموعات النقاط القطرية فقط في الرسم البياني ، في حين يتم تكرار التركيبات وعدد النقاط المتبقية ببساطة.

عدد العلاقات المضادة للانعكاس من مجموعة العلاقات غير الانعكاسية يساوي تمامًا عدد العلاقات الانعكاسية ، أي

2^{n^{2} - n}

$2^{n^2-n}$ ... ينتج هذا من حقيقة أنه يمكن إنشاء تطابق واحد لواحد بين العلاقات الانعكاسية والمضادة للانعكاس: من كل علاقة انعكاسية ، عن طريق إزالة جميع نقاط القطر ، يمكن الحصول على علاقة انعكاسية واحدة والعكس صحيح.

تناظر

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

العلاقة α = <Å، A> في المجموعة A متماثلة (لها خاصية التناظر فيما يتعلق بالخط المستقيم الذي يتزامن مع القطر الرئيسي للرسم البياني M) إذا كان لبعض الأزواج

(i, j) є A \times A

$(i, j) є A×A$ من

а_{i} α а_{j}

$_i α _j$ ينبغي

а_{j} α а_{i}

$_j α _i$ ... بمعنى آخر ، لأي زوج

((а_{i}, а_{j}) є Å)

$((_i, _j) є Å)$ نفذت إما في كلا الاتجاهين ، أو لا على الإطلاق.

على الرسم البياني للعلاقة المتماثلة ، إذا كان زوج من الرؤوس i و j متصلين بقوس (i ، j) ، فإنه يكون بالضرورة متصلاً بقوس (j ، i). الرسم البياني للعلاقة المتماثلة هو رسم بياني عادي المنحى متماثل ، أو ببساطة غير موجه.

النسبة α غير متماثلة إذا كانت من

а_{i} α а_{j}

$_i α _j$ و

а_{j} α а_{i}

$_j α _i$ يتبع ذلك i = j.

لا تحتوي مصفوفة النسبة غير المتماثلة بالضرورة على جميع العناصر الموجودة على القطر الرئيسي وتحتوي على تلك الموجودة في أحد الموضعين المتماثلين بالنسبة للقطر الرئيسي: فوق القطر أو أسفل القطر. يتكون الرسم البياني لهذه العلاقة من رؤوس ذات حلقات لكل منها أو بعضها ، وإذا كان هناك زوج من الرؤوس (i ، j) في الرسم البياني متصلًا ، فإنه دائمًا ما يكون قوسًا لاتجاه واحد فقط. لاحظ أنه بالنسبة للعلاقة المتماثلة وغير المتماثلة ، يمكن تضمين بعض النقاط القطرية فيها أم لا.

إذا كانت العلاقة غير المتماثلة لا تحتوي على نقطة قطرية واحدة ، فإنهم يقولون إن هذه العلاقة غير متماثلة ، أي إنه دائمًا مضاد للانعكاس.

مثال 2... العلاقة (≤) على المجموعة N غير متماثلة ، والعلاقة (<) على نفس المجموعة غير متماثلة. في الواقع ، في الحالة الأولى من

а_{i} \leq а_{j}

$_i ≤_j$ و

а_{j} \leq а_{i}

$_j ≤_i$ يمكن أن تتبع فقط

i = j

$i = j$ ... علاقة المساواة (=) على N متناظرة ، والعلاقة α = A × A متماثلة أيضًا.

بالنسبة لأي نسبة متماثلة α ، فهي صحيحة دائمًا

α = α^{- 1}

$α = α^{-1}$ و

α^{- 1}

$α^{-1}$ متماثل أيضا. لعلاقة غير متماثلة ،

α \cap α^{- 1} \subseteq ∆_{A}

$α ∩ α^{-1}⊆∆_A$ ... العلاقة العامة ، التي يحتوي الرسم البياني لها على نقاط متماثلة وغير متماثلة ، ليست متماثلة. هذه العلاقة غير متكافئة ، لكنها ليست غير متماثلة وليست غير متكافئة.

تتجلى خاصية التناظر أيضًا في العلاقات n-ary. العلاقة R على المجموعة

Х = x_{1}, x_{2}, \dots, x_{n}

$= { x_1, x_2,…,x_n}$ هي علاقة n-ary متماثلة إذا كانت مع العنصر

< x_{i 1}, x_{i 2}, \dots, x_{i n} > є R

$<x_{i1}, x_{i2}, …,x_{in}>є R$ يحتوي على أي تسلسلات

< x_{j 1}, x_{j 2}, \dots, x_{j n} >

$< x_{j1}, x_{j2},…, x_{jn}>$ تشكلت من خلال تبديل أعضاء المجموعة X.

لاحظ أيضًا أن العلاقة غير المتماثلة دائمًا ما تكون مضادة للانعكاس ؛ تكون العلاقة الثنائية غير العاكسة والمتعدية غير متماثلة دائمًا. بالنسبة للممارسة ولإجراء العمليات الحسابية ، فإن عدد العلاقات التي لها خاصية معينة تتعلق بتماثل الرسم البياني مهم. دعونا نحسب هذه النسب لمجموعة عشوائية A من أصل | A | = ن.

في تفكيرنا سنعتمد على خاصية الانعكاسية ، والتي ، مثل العديد من الآخرين ، لم تدرس بعد بعمق كافٍ. حتى التحليل السطحي لمجموعة جميع العلاقات يسمح لنا باستنتاج أنه يمكن دائمًا تقسيمها إلى

2^{n}

$2^n$ الطبقات من نفس الحجم ، وتكوين العلاقات التي تشكل هذه الطبقات تخضع لنمط معين.

مجموعات العلاقات في جميع الفئات لها نفس الهيكل ، وتختلف فقط في عدد وتكوين النقاط القطرية ، والتي يتم تحديد مجموعة متنوعة منها من خلال الرقم

2^{n}

$2^n$ ... دعونا نحدد حالة قطري علاقة لـ n ثابت بعدد النقاط وتكوينها والانتماء إلى علاقة معينة. من الواضح أنه ، بالنسبة إلى الثابت ، يتم تحديد مجموعة حالات ملء خلايا القطر بواسطة القيمة المنطقية

2^{∆}

$2^∆$ ، حيث ∆ هي المجموعة الكاملة من النقاط المائلة للرسم البياني للمربع الديكارتي للعلوية | ∆ | = ن.

وهكذا ، في نظرية العلاقات ، تم دراسة ودراسة حالتين متطرفتين فقط تقليديًا: إما أن يتم تضمين جميع نقاط القطر في العلاقة وتكون انعكاسية ، أو لا تحتوي العلاقة على أي نقطة قطرية ، ومن ثم فهي مضادة للانعكاس.

سوف نسمي جميع الحالات الوسيطة ذات نقطة قطرية واحدة ، مع اثنين ، وهكذا ، الانعكاسية الجزئية من الدرجة k k = 0 (1) n ، والعلاقات من هذا النوع انعكاسية جزئيًا. لذا فإن العلاقة الانعكاسية الجزئية للرتبة الصفرية هي علاقة مضادة للانعكاس ، وجزئيًا العلاقة الانعكاسية للنظام n هي مجرد علاقة انعكاسية.

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

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

C_{n}^{2}

$C_n^2$ ... دعونا نشير إلى مجموعة هذه الأزواج بالرمز S.

ثم سيتم تحديد المجموعة الكاملة من العلاقات المتماثلة والانعكاسية بواسطة Boolean

2^{S}

$2^S$ ... سيتم النظر في الكثير من هذه العلاقات بمزيد من التفصيل بعد ذلك بقليل ، لكننا نقول هنا إنها تشكل مساحة من اللامبالاة أو التسامح. من الواضح أن عدد نسب التسامح يتم تحديده بواسطة قوة منطقية

2^{S}

$2^S$ ، بمعنى آخر.

2^{C_{n}^{2}}

$2^{C_n^2}$ ...

أدناه في الجدول. يوضح الشكل 1 قيم عدد نسب التفاوت للقيم الأولية n من مقطع من الأرقام الطبيعية.

الجدول 1 . عدد BOs المتسامح

أصبح من السهل الآن حساب العلاقة الأساسية لجميع العلاقات المتماثلة ، لأن وجود أو عدم وجود نقاط قطرية لا يغير خصائص التناظر. يتم الإشارة إلى مجموعة العلاقات المتماثلة بالرمز SM. ثم يتم تحديد أصل هذه المجموعة لـ n ثابت بواسطة الصيغة

| S M | = 2^{n} \cdot 2^{C_{n}^{2}} = 2^{C_{n + 1}^{2}},

$|SM| = 2^n·2^{C_n^2} = 2^{C_{n+1}^2},$

حيث n هو عدد النقاط القطرية للنسبة. الطاولة 2 يوضح القيم | SM | لبعض ن.

الجدول 2 . عدد BOs المتماثل

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

يمكن تحديد أصل هذه المجموعة من التعبيرات

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

حيث K =

C_{n}^{2}

$C_n^2$ ...

نحصل على الصيغة المختصرة لحساب العلاقة الأساسية للمجموعة AS - العلاقات غير المتماثلة من أجل أصل معين للناقل | A | = ن. بحكم التعريف ، جميع علاقات المجموعة AS مضادة للانعكاس ؛ لذلك ، فإن القطر الرئيسي في مصفوفة العلاقات فارغ ، ويمكن تحديد موقع عناصر الوحدة فقط في نصف المواضع المتبقية من المصفوفة ، أي في

C_{n}^{2} = (n^{2} - n) : 2

${C_n^2} =(n^2-n):2$ الخلايا.

لذا ، افترض أن العلاقة غير المتماثلة تحتوي على عناصر ك (نقاط ، أزواج مرتبة) 0 ≤ ك ≤

C_{n}^{2}

${C_n^2}$ ... من الواضح أن عدد العلاقات مع هذا العدد من العناصر سيكون مساويًا لعدد التركيبات من

C_{n}^{2}

$C_n^2$ بواسطة k.

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

2^{n}

$2^n$ الفرص.

في هذا الطريق،

C_{n}^{2}

$C_n^2$ هو عدد اختيارات k أزواج من المواقف من

C_{n}^{2} = K

$C_n^2 = K$ الأزواج المتاحة في تمثيل العلاقات بالمصفوفة ، و

2^{n}

$2^n$ - عدد الفرص لترتيب عناصر k في المواضع في كل زوج. يتم تعريف عدد العلاقات التي تحتوي على عناصر k على أنها ناتج عدد التحديدات لأزواج المواضع من خلال عدد الخيارات لترتيب عناصر k ، أي

2^{k} C_{K}^{k}

$2^kC_K^k$ ...

يتم الحصول على العدد الإجمالي للعلاقات في المجموعة AS بجمع المنتجات التي تم الحصول عليها عبر جميع قيم k من صفر إلى الحد الأقصى المسموح به K =

C_{n}^{2} = K

$C_n^2 = K$ ، بمعنى آخر.

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

حيث K =

C_{n}^{2}

$C_n^2$ ...

مثال 3. دع عدد العناصر الأساسية لمجموعة الدعم | A | = 5. احسب عدد العلاقات غير المتماثلة باستخدام الصيغة الموجودة. دعونا نحدد قيمة الحد الأعلى K في المجموع ، K =

C_{n}^{2}

$C_n^2$ = 10. يتم عرض بيانات الحساب للمبلغ في الجدول. 3.

الجدول 3 . خصائص BO

هناك طريقة أخرى لحساب العلاقة الأساسية لمجموعة AS. يعتمد على حساب عدد التعيينات لمجموعة أزواج من المواضع المتماثلة في مجموعة من الحالات التي يمكن أن يكون فيها كل زوج. في علاقة غير متكافئة ، هناك

K = C_{n}^{2}

$K = C_n^2$ أزواج من المواقف.

يمكن شغل كل موضع في زوج من الخلايا بمقدار 0 أو 1 ، ولكن بالنسبة لزوج من المواضع ، توجد حالات S = 3 ، والتي نشير إليها على النحو التالي:

- 1 ، إذا تم وضع العنصر (1) فوق القطر ؛

- 2 ، إذا تم وضع العنصر (1) تحت القطر ؛

- 3 إذا كان كلا الموضعين فارغين (تحتلها الأصفار).

وبالتالي ، يمكن أن يكون زوج من المواضع المتماثلة (في مصفوفة العلاقة) في كل

علاقة في واحدة من ثلاث حالات. معادلة حساب جميع التعيينات الممكنة لمجموعة أزواج المواضع (المشار إليها بالرمز K) في المجموعة S من الحالات هي:

φ : K \to S => | A S | = | S |^{| K |}

$φ: K → S =>|AS| =|S|^{|K|}$

مثال 4 . لشروط المثال السابق له شكل | A | = 5 ، ك = | ك | =

K = C_{5}^{2} = 10,

$K = C_5^2 = 10,$ | S | = 3 إذن

| A S | = 3^{1} 0 = 59049

$|AS| = 3^10 = 59049$ ...

ينتج عن الحساب طريقتان مختلفتان تتطابقان ، مما يقنع مرة أخرى بصحة الصيغ التي تم الحصول عليها. وهكذا حصلنا على العلاقة

3^{C_{n}^{2}} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k},

$3^{C_n^2} = Σ_{k=0}^K C_K^k·2^k,$

حيث K =

C_{n}^{2} .

$C_n^2.$

دعونا نستسلم في الجدول. 4 أرقام للعلاقات غير المتماثلة | AS | لقيم n الصغيرة.

الجدول 4. عدد BOs غير المتماثلة

بوجود صيغة لتحديد عدد العلاقات غير المتماثلة ، يمكن للمرء الحصول على صيغة أخرى - لحساب عدد العلاقات غير المتماثلة ، نظرًا لأن وجود أو عدم وجود نقاط قطرية لا يغير خصائص عدم تناسق العلاقة.

لذلك ، نشير إلى مجموعة العلاقات غير المتماثلة بالرمز ANS ، ثم سيتم تحديد العلاقة الأساسية لهذه المجموعة من خلال الصيغة

| A N S | = 2^{n}

$|ANS| =2^n$

| A N S | = 2^{n} Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k + n} = 2^{n} 3^{C_{n}^{2}},

$|ANS| =2^n Σ_{k=0}^K C_K^k·2^k =Σ_{k=0}^K C_K^k·2^{k+n} =2^n3^{C_n^2},$

حيث K =

C_{n}^{2}

$C_n^2$

يوجد أدناه جدول. 5 تحتوي على قيم (ANS) لـ n = 3 (1) 5.

الجدول 5 . عدد BOs غير المتماثل

فيما يلي ، نحتاج إلى مفاهيم ملائمة لتقديمها هنا.

الجزء المتماثل من العلاقة الثنائية يسمى (ويشار إليه

α^{(S)}

$α^{(S)}$ ) موقف سلوك

α^{(S)} = α \cap α^{- 1}

$α^{(S)} =α∩α^{-1}$ والنسبة

α^{(а)} = α {\α}^{(S)}

$α^{()} = α \α^{(S)}$ (يعني

α^{(а)}

$α^{()}$ ) يسمى الجزء غير المتماثل. في الحالة الخاصة عندما تكون النسبة α متماثلة ،

α^{(S)} = α

$α^{(S)} = α$ و

α^{(S)}

$α^{(S)}$ متماثل دائما إذا كانت α غير متماثلة ، إذن

α^{(а)} = α

$α^{()}= α$ و

α^{(а)}

$α^{()}$ دائما غير متماثل.

الانتقال (لاتيني ترانزيتيفوس - انتقالي ، من العبور - انتقالي)

- إحدى خصائص العلاقات. العلاقة = <M ، A> المحددة في المجموعة A متعدية إذا وجدت

а_{i}, а_{j}, а_{k} є A

$_i, _ j, _k є A$ الشرط مستوفى: من

а_{i} α а_{j}

$_iα _ j$ و

а_{j} α а_{k}

$_jα _k$ ينبغي

а_{i} α а_{k}

$_iα _ k$ ...

بمعنى آخر ، من أجل علاقة متعدية من وجود العناصر في تكوينها (

а_{i} α а_{k}

$_iα _ k$ ) و (

а_{k} α а_{j}

$_kα _ j$ ) يتبع أنه يحتوي على العنصر (

а_{i} α а_{j}

$_iα _ j$ ). بالنسبة إلى الرسم البياني للعلاقة ، تعني هذه الخاصية أنه إذا كان زوج من الرؤوس (

а_{i} α а_{j}

$_iα _ j$ ) بواسطة مسار موجه يمر عبر قمة الرأس k ويتكون من قوسين متتاليين (

а_{i} α а_{k}

$_iα _ k$ ) ، (

а_{k} α а_{j}

$_kα _ j$ ) ، ثم ترتبط القمم نفسها مباشرة بقوس واحد (

а_{i} α а_{j}

$_iα _ j$ ). لعناصر المصفوفة [

а_{i j}

$_{ij}$ ] لعلاقة متعدية α من

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ ينبغي

а_{i j} = 1

$_{ij} = 1$ ...

يفترض تعريف خاصية الانتقال للعلاقات الثنائية أن العلاقة تحتوي على ثلاثة عناصر على الأقل (أزواج مرتبة). وكيف تتجلى هذه الخاصية في علاقة مكونة من عنصر واحد أو فارغة أو تحتوي على عنصرين فقط؟

جميع العلاقات المفردة والفارغة متعدية. يمكن أن تكون العلاقة المكونة من عنصرين متعدية وغير متعدية إذا كانت الأزواج المتضمنة فيها تحتوي على عنصر مشترك j. يتم توجيه أقواس الرسم البياني المقابلة للأزواج المرتبة في اتجاه واحد (تشكل مسارًا موجهًا غير انتقالي).

على سبيل المثال ، دع (

а_{i}, а_{j}

$_i, _ j$ ) є α و (

а_{j}, а_{k}

$_j, _ k$ ) є α. يتطلب التعريف المصاغ: لكي تكون العلاقة α متعدية ، يجب أن تحتوي على زوج ثالث (قوس) فيها ، أي (

а_{i}, а_{k}

$_i, _ k$ ) ، ولكن نظرًا لعدم وجودها ، لم يتم استيفاء خاصية الانتقال لـ α.

إذا كانت العلاقة ، كما في السابق ، تحتوي على زوجين فقط مع عنصر مشترك

а_{j} є A

$_j є A$ ، ولكن مثل هذا العنصر المشترك

а_{j} є A

$_j є A$ في نفس الوضع في كلا الزوجين (

а_{j}, а_{i}

$_j, _ i$ ) ، (

а_{j}, а_{k}

$_j, _ k$ ) أو (

а_{i}, а_{j}

$_i, _ j$ ) ،

(

а_{k}, а_{j}

$_k, _ j$ ) ، ويتم توجيه الأقواس الموجودة على الرسم البياني في اتجاهات مختلفة ، فإن هذه العلاقة تعد متعدية ، حيث إن إدراج الزوج الثالث في العلاقة غير مطلوب.

ستكون العلاقة متعدية أيضًا في حالة عدم وجود عناصر مشتركة بين زوجين. أمثلة على العلاقات متعدية: "المساواة" (=) ، حيث أن i = k ، k = j تعني i = j ؛ "أنا أكبر من j" ؛ في الهندسة - "توازي الخطوط المستقيمة". أمثلة على العلاقات غير متعدية: "عمودية الخطوط المستقيمة" في الهندسة ؛ "أنا لا يساوي j".

في الأدبيات المتعلقة بالعلاقات ، يمكن للمرء أن يجد مفاهيم مختلفة تميز الانتقال: انتقالية ضعيفة ، انتقالية قوية ، انتقالية سلبية ، مقاومة انتقالية ، مقاومة ضعيفة للانتقالية ، انتقالية معممة ، إغلاق متعدوالبعض الآخر. تجري هنا محاولة لتنظيم الظلال المتنوعة لمظهر خاصية الانتقال في العلاقات.

لعلاقة متعدية α ، العلاقة

α^{- 1}

$α^{–1}$ هي أيضًا متعدية دائمًا. تقاطع عدد اعتباطي من العلاقات متعدية هو علاقة متعدية. إذا أخذنا في الاعتبار العلاقة ᾰ ، وهي تقاطع جميع العلاقات المتعدية التي تحتوي على العلاقة α ، فإن ᾰ تسمى الإغلاق الانتقالي للعلاقة α.

يمكن إنشاء الإغلاق المتعدي لأي علاقة α وفقًا للقاعدة من

а_{i} ᾰ а_{j}

$_i ᾰ _j$ يتبع:

(\exists а_{к 1}, а_{к 2}, \dots, а_{к s}) (а_{i} α а_{к 1} Λ а_{к 1} α а_{к 2} Λ \dots Λ а_{к s} α а_{j})

$(∃_{1}, _{2}, …,_{s})( _iα _{1}Λ_{1}α _{2}Λ… Λ _{s}α _j)$ ...

العلاقة ᾰ هي أصغر علاقة متعدية تحتوي على α. إذا كانت α متعدية ، فإنها تتزامن مع إغلاقها الانتقالي α = ᾰ والعكس صحيح.

عند تمثيل علاقة ثنائية متعدية بواسطة رسم بياني موجه ، من الممكن ليس تمثيل digraph بأكمله ، ولكن فقط هيكلها المتعدِّد ، أي لم يتم رسم الأقواس التي تربط بداية ونهاية كل مسار أطول من واحد. في هذه الحالة ، نقول إن الهيكل العظمي المتعدية للرسم البياني مأخوذ من أجل العلاقة α . هذه العملية هي في الأساس عكس عملية الإغلاق الانتقالي ، حيث يتم توصيل بداية ونهاية كل شبكة بواسطة قوس.

في الحالة العامة ، لا يتم الاكتفاء بخاصية العبور فيما يتعلق بعملية دمج العلاقات. الجمع بين علاقتين متعدية

α_{1}

$α_1$ و

α_{2}

$α_2$ متعدٍ فقط إذا كان أحدهما متعدٍ بالنسبة للآخر. لزوج من العلاقات الثنائية

α_{1}

$α_1$ و

α_{2}

$α_2$ يمكن للمرء أن يأخذ بعين الاعتبار عابرة أحدهما بالنسبة للآخر.

وبالتالي

α_{1}

$α_1$ غير متعدية فيما يتعلق

α_{2}

$α_2$ بالشروط التالية:

1) من

(а_{i}, а_{k}) є α_{1} и (а_{k}, а_{j}) є α_{2}

$( _i, _k) є α_1 ( _k, _j) є α_2$ ينبغي

(а_{i}, а_{j}) є а_{1}

$(_i, _j) є _1$ ؛

2) من

(а_{i}, а_{k}) є α_{2} и (а_{k}, а_{j}) є α_{1}

$( _i, _k) є α_2 ( _k, _j) є α_1$ ينبغي

(а_{i}, а_{j}) є α_{1}

$( _i, _j) є α_1$ ...

في حالة متى

α_{1} = α_{2} = α

$α_1= α_2=α$ العبور النسبي هو العبور المعتاد.

يُعرف البيان التالي عن خصائص العبور والتماثل وعدم تناسق العلاقة. إذا كانت العلاقة الثنائية متعدية ، فإن الجزء المتماثل منها

α^{(S)}

$α^{(S)}$ و

α^{(а)}

$α^{()}$ الجزء غير المتماثل هو أيضًا متعد.

العكس هو الصحيح فقط إذا

α^{(S)}

$α^{(S)}$ ،

α^{(а)}

$α^{()}$ متعد و

α^{(а)}

$α^{()}$ نسبي عابر

α^{(S)}

$α^{(S)}$ ... بشكل عام ، من التعدي

α^{(S)}

$α^{(S)}$ و

α^{(а)}

$α^{()}$ لا تتبع عبودية α.

إن تكوين العلاقة متعدية α مع نفسها يرضي العلاقة α · α ⊆ α. تكون العلاقة α متعدية سالبًا (غير متعدية) إذا كان مكملها متعدٍ ، أي ᾱ. في مصفوفة هذه العلاقة [

α_{i j}

$α_{ij}$ ] من عند

α_{i k} = 0

$α_{ik} = 0$ و

α_{k j} = 0

$α_{kj} = 0$ ينبغي

α_{i j} = 0

$α_{ij} = 0$ ... لا تستبعد العبور السلبي لـ α حقيقة أن α نفسها يمكن أن تكون متعدية أيضًا.

في هذه الحالة ، يُقال أن α علاقة متعدية بشدة . عناصر المصفوفة [

α_{i j}

$α_{ij}$ ] مثل هذا الموقف يتميز بحقيقة ذلك

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ ينبغي

а_{i j} = 1

$_{ij} = 1$ ، من

а_{i k} = а_{k j} = 0

$_{ik} = _{kj} =0$ ينبغي

а_{i j} = 0

$_{ij} = 0$ ...

جنبًا إلى جنب مع العلاقات المتعدية بشدة ، فإننا نعتبر العلاقات متعدية بشكل ضعيف (شبه متعدية) ، والتي تشمل تلك العلاقات التي تكون فيها الشروط من

а_{i} α^{(S)} а_{К}

$_iα^{(S)}_$ و

а_{К} α а_{j}

$_α_j$ ينبغي

а_{i} α а_{j}

$_iα_j$ ... تنبع انتقائها من عدم التماثل والعبور السلبي.

تكون العلاقة α كاملة بشكل عابر إذا كانت لأي من δ من

а_{K 1} α а_{K 2}, а_{K 2} α а_{K 3}, \dots, а_{K (δ - 1)} α а_{K δ}

$_{K1}α_{K2}, _{K2}α_{K3},…, _{K(δ-1)}α_{Kδ}$ و

فيما يلي مقارنة

а_{K 1}

$_{K1}$ و

а_{K δ}

$_{Kδ}$ ، بمعنى آخر. يتم تنفيذها إما

а_{K 1} α а_{K δ}

$_{K1}α_{Kδ}$ أو

а_{K δ} α а_{K 1}

$_{Kδ}α_{K1}$ ...

دورية

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

تكون العلاقة = <، A> دورية إذا أمكن تكوين سلسلة واحدة على الأقل من النموذج من عناصر المجموعة أ

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{K δ}, а_{K δ} α а_{K i}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$ الطول التعسفي δ. يحتوي الرسم البياني M للإغلاق متعد لعلاقة دورية على زوج واحد على الأقل (

а_{i}, а_{i}

$_i, _i$ ) ، وبالنسبة للعلاقة غير الدورية ، لا تحتوي α على أي زوج من هذا القبيل.

العلاقة = <، A> هو احلقي إذا لأي δ≥1 حالة من

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{j}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_j$ ينبغي

а_{i} \neq а_{j}

$_i ≠ _j$ ... في المصفوفة [

α_{i j}

$α_{ij}$ ] علاقة غير دورية من

а_{i K 1} а_{K 1 K 2} . . . а_{K (δ - 1) j} = 1

$_{iK1}_{K1K2}..._{K(δ-1)j}=1$ يتبع i ≠ j. دائمًا ما تكون العلاقة غير الدورية غير متكافئة ، لكن العكس ليس صحيحًا. بمعنى آخر ، إذا كانت بعض القمم

а_{i}

$_i$ و

а_{j}

$_j$ الرسم البياني α العلاقات غير الدورية متصلة بالطريقة ؛ ثم لا يوجد قوس في الرسم البياني (

а_{j}, а_{i}

$_j, _i$ ). الدورات الانتقالية

هي أمثلة كلاسيكية للرسوم البيانية بهذه الخاصية . يمكن إعادة ترقيم رؤوس هذه الرسوم البيانية ، والتي تحتها لأي قوس (

а_{i}, а_{j}

$_i, _j$ ) عدد الرأس j أكبر من الرأس i.

إذا كانت α عبارة عن علاقة ثنائية متعدية مضادة للانعكاس ، فهي لا دورية. إن عدم تكرار العلاقة واكتمالها المتعددي يعني تجاوزها.

الاكتمال

خاصية الاكتمال (الكمال ، الخطية). تنقسم المجموعة الكاملة من العلاقات إلى غير مكتملة وكاملة ، ومن بينها ، بدورها ، علاقات كاملة بقوة تبرز. سوف نوضح خاصية اكتمال العلاقات من خلال النظر في الرسوم البيانية للعلاقات.

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

العلاقة = <، A> كاملة (كاملة ، خطية) إذا وفقط إذا كانت جميع عناصر المجموعة A قابلة للمقارنة أو متساوية مع بعضها البعض. وبالتالي ، فإن الموقف العام هو انعكاس. بمعنى آخر ، لأي عنصرين

а_{i}

$_i$ و

а_{j}

$_j$ معرض

(а_{i} α а_{j} V а_{j} α а_{i} V а_{i} = а_{j})

$(_i α _j V _j α _i V _i = _j)$ ...

إذا كان هناك زوج واحد على الأقل في العلاقة α

а_{i}

$_i$ ،

а_{j}

$_j$ عناصر لا تضاهى وغير متكافئة ، إذن هذه العلاقة غير كاملة. لأي نسبة إجمالية α ،

∆ U α U α^{- 1} = A \times A

$∆UαUα^{-1}=A×A$ او من

а_{i} ᾱ а_{j}

$_i ᾱ _j$ ينبغي

а_{j} α а_{i}

$_j α _i$ ... تكتمل العلاقة الثنائية α إذا وفقط إذا

а^{(a)} = а^{(d)}

$^{(a)} =^{(d)}$ ، بمعنى آخر. عندما يتطابق الجزء غير المتماثل مع العلاقة المزدوجة (البند 9) . تكتمل

العلاقة الثنائية α بقوة عندما يتزامن الرسم البياني الخاص بها مع A × A. الرسم البياني لهذه العلاقة هو رسم بياني كامل يرتبط فيه كل زوج من الرؤوس بحافة ، ولكل رأس حلقة. يسمى هذا الرسم البياني بالرسم البياني الكامل بقوة. النسبة الإجمالية α ترضي دائمًا العلاقات

ᾱ \subset α^{- 1}

$ᾱ ⊂ α^{-1}$ و

α^{- 1} \subset ᾱ \cup (α \cap α^{- 1})

$α^{-1}⊂ᾱ ∪(α∩α^{-1})$ ... موقف سلوك

α \cup (ᾱ \cap α^{d}) = α \cup (ᾱ)^{(S)}

$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$ دائما كاملة.

إذا

α_{1}

$α_1$ و

α_{2}

$α_2$ علاقة كاملة ، إذن

α_{1} \cdot α_{2}

$α_1·α_2$ ممتلئ. في المصفوفة [

α_{i j}

$α_{ij}$ ] علاقة كاملة

α_{i j} = 1

$α_{ij} = 1$ أو

α_{j i} = 1

$α_{ji} = 1$ لأي تساوي i أو j أو كلاهما صحيح. العلاقة α مكتملة بشكل ضعيف (ضعيفة الاتصال) إن وجدت

а_{i}, а_{j} є A

$_i,_j є A$ مثل ذلك

а_{i} \neq а_{j}

$_i ≠ _j$ أو

а_{i} α а_{j}

$_i α _j$ أو

а_{j} α а_{i}

$_j α _i$ ...

في المصفوفة [

α_{i j}

$α_{ij}$ ] لعلاقة كاملة بشكل ضعيف لأي i ≠ j ، أو

α_{i j} = 1

$α_{ij} = 1$ أو

α_{j i} = 1

$α_{ji} = 1$ ، أو كلاهما صحيح. تكون العلاقة α كاملة بشكل عابر إذا ، من أجل n تعسفي من

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (n - 1)} α а_{i n}

$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ يتبع المقارنة

а_{i 1} \equiv а_{i n}

$_{i1}≡ _{in}$ أولئك.

а_{i 1} α а_{i n}

$_{i1}α _{in}$ أو

а_{i n} α а_{i 1}

$_{in}α _{i1}$ ...

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

إذا وقع زوجان أو أكثر من المواضع المتماثلة على خط واحد (خط مستقيم) في مصفوفة النسبة ، فإن عدد الخطوط ، مع ذلك ، يظل مساويًا لعدد هذه الأزواج من المواضع. يتم تعريف العدد الإجمالي لأزواج المواقف لـ n التعسفي على أنه

C_{n}^{2} = L

$C_n^2 = L$ ...

لذلك ، في المصفوفة لعلاقة تعسفية على المجموعة A ، هناك مجموعة L من المقاطع المتوازية (الخطوط). دعنا نحدد المواضع النهائية للقطاعات (الخطوط) بالرموز L - اليسار و P - اليمين. متوفر أيضًا | L | رقائق يمكن وضعها في مواضع في نهايات السطور. يتمثل التحدي في تحديد عدد الطرق التي يمكن من خلالها ترتيب | L | رقائق بحيث توجد شريحة واحدة على الأقل في كل سطر.

من الواضح أنه يمكن تقليل المشكلة لتحديد عدد F من التعيينات f: L → π من المجموعة L من الخطوط في مجموعة π المواضع (n = {A، P}). من المعروف أن عدد هذه التعيينات يتم تحديده بواسطة الصيغة

F = | п |^{| L |}

$F = ||^{|L|}$ ... يمكن أن يكون لرسم الخرائط المحدد (الصورة) الشكل <P، P، L، L، L،…، L، P> لتسلسل مؤشرات | لام | المواقف. يتوافق الرمز L مع الموضع الموجود أسفل القطر الرئيسي ، والرمز P المتماثل له فوق القطر.

من تعريف النسبة الإجمالية ، يتبع ذلك أن الرسم البياني الخاص بها يحتوي على K نقطة على الأقل ، K =

C_{n}^{2}

$C_n^2$ الموقع: بحيث تشغل شريحة واحدة على الأقل جميع الخطوط. يمكن تشغيل عدد النقاط k على الرسم البياني ، بالإضافة إلى الحد الأدنى للعدد المطلوب ، من خلال القيمة k = 0 (1) K =

C_{n}^{2}

$C_n^2$ ...

لكل عدد ثابت من نقاط k ، يتم تحديد مجموعة خيارات المواضع التي يمكن وضعها فيها حسب القيمة

C_{К}^{k}

$C_^k$ ، حيث K هي مجموعة المواقف الشاغرة. نظرًا لأن نقاط k الإضافية تملأ خطوط k تمامًا ، ثم لضمان خاصية اكتمال النسبة ، يبقى ملء مواضع K - k برقائق (نقاط من مجموعة الحد الأدنى المطلوب) ، وعدد هذه الحشوات هو

2^{К - k}

$2^{-k}$ ...

اختيار المواضع لـ k نقاط إضافية وطرق تعبئة خطوط K-k بالرقائق مستقلة. لذلك ، يتم تحديد العدد الإجمالي لإمكانيات وضع نقاط K + k في مواضع 2 ∙ K بحيث تشغل جميع الخطوط بنقطة واحدة على الأقل بواسطة التعبير

C_{К}^{k} \cdot 2^{К - k}, k = 0 (1) К .

$C_^k ·2^{-k}, k = 0(1).$

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

مثال 5 . يتم تحديد مجموعة متنوعة من المواقف لوضع النقاط القطرية من خلال الرقم

2^{n}

$2^n$ ... ثم يتم تحديد أصل مجموعة جميع العلاقات الكاملة لـ n ثابت بواسطة الصيغة

П = 2^{n} \cdot \sum_{k = 0}^{К} C_{К}^{k} 2^{К - k} = \sum_{k = 0}^{К} C_{К}^{k} 2^{К + n - k}

$= 2^n·∑_{k=0}^C_^k2^{-k} = ∑_{k=0}^C_^k2^{ + n - k}$ ...

للعلاقات مع ثلاث خصائص مطلوبة

لعلاقات التكافؤ مع ثلاث خصائص مطلوبة. هناك نتيجة ملحوظة: كل علاقة تكافؤ على مجموعة من العناصر n هي في تطابق واحد لواحد مع قسم من هذه المجموعة. يتم تحديد عدد هذه العلاقات من خلال الصيغة

B_{n} = \sum_{m = 0}^{n} S (n, m)

$B_n = ∑_{m=0}^nS(n, m)$ ، حيث S (n، m) هو رقم ستيرلنغ من النوع الثاني ، Bn هو رقم

الجرس ، أو في شكل متكرر

B_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} B_{k} .

$B_{n+1} = ∑_{k=0}^nC_n^kB_k.$

بالنسبة للمجموعات المرتبة (الطلبات الجزئية) ، فإن هذه الصيغ ليست مفتوحة ويتم تحديد عددها من خلال الحسابات المباشرة ، أي النمذجة. بالنسبة للقيم الصغيرة لـ n ، يتم عرض البيانات في

الجدول 6 . الخصائص الكمية للعلاقات الثنائية

يوضح الجدول 6.: n = | A | - أصل مجموعة الناقل ؛

2^{n^{2}}

$2^{n^2}$ - عدد جميع العلاقات الثنائية في المجموعة أ ؛

| في (ن) | - عدد فئات العلاقات غير المتشابهة ؛

| (ن) | - عدد العلاقات الجزئية ؛

| Gn (n) | - عدد الفئات عبارة عن علاقات غير متشابهة بترتيب جزئي ؛

| جل (ن) | = ن! - عدد علاقات الترتيب الخطية.

خاتمة

في هذا العمل ، تم إجراء تحليل مفصل للخصائص الأساسية وهيكل النسبة الثنائية ، والتي على أساسها كان من الممكن الحصول على الخصائص الكمية لـ BO مع خاصية واحدة أو أكثر. تم العثور وتقديم النسب الأصلية لعدد بعض أنواع العلاقات مع خاصيتين وثلاث خصائص مطلوبة. تفتح هذه النتائج إمكانية نمذجة ودراسة BO والعلاقات ذات الأهمية العليا.

قائمة الأدب المستخدم

ايجنر م. نظرية الاندماج - م: مير ، 1982.
Birkhoff G. نظرية الهياكل. - م: إلينوي ، 1952. - 408 ص.
Noden P. ، Kitte K. الخوارزميات الجبرية. - م: مير ، 1999. - 720 ص.
ريبنيكوف ك. مقدمة في التحليل الاندماجي. م: إد. جامعة موسكو الحكومية ، 1972. -256 ثانية.
ستانلي ر. التوافقية العددية. المجلد .1- م: مير ، 1990. - 440 ص.
ستانلي ر. التوافقية العددية. T.2.- م: مير ، 2005. - 767 ثانية.
شيخانوفيتش يو. مقدمة في الرياضيات الحديثة. المفاهيم الأولية .- M: Nauka ، 1965. - 376p.

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

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

انعكاسية

تناظر

الانتقال (لاتيني ترانزيتيفوس - انتقالي ، من العبور - انتقالي)

دورية

الاكتمال

خاتمة

قائمة الأدب المستخدم

More articles: