مقالات أخرى في الدورة
تستخدم النظرية الشكلية للنمذجة العلاقات الجبرية ، بما في ذلك في تواقيع نماذج الهياكل الجبرية ، والتي تصف الأشياء المادية والتقنية الحقيقية وعمليات عملها. هذا المنشور هو استمرار للنشر السابق ، والذي يُفضل قراءته ، حيث يتم وصف العديد من المفاهيم والمصطلحات المستخدمة هنا.
لا يتم تقديم العرض التقديمي بالطريقة التقليدية (السهم) ، ولكن بالطريقة التي كان عليّ أن أتخيلها وأتقن هذا المطبخ بأكمله من الكتب المدرسية / الكتيبات ومن مقالات المجلات. أنا أعتبر الكتالوج الذي قمت بإنشائه مفيدًا بشكل خاص ، فهو يسمح لك بتحديد أي مساحة تقريبًا وتقديم عناصره في شكل مناسب: مصفوفة ، رسم بياني ، إلخ. يمكنك أن ترى على الفور ما تتعامل معه والخصائص (تمت كتابتها بالفعل) غالبًا لا تحتاج إلى التحقق.
مفهوم العلاقة
أعتقد أن مصطلح "موقف" مألوف لدى كل قارئ ، لكن السؤال عن تعريفه سيشوش أكثر. هناك اسباب كثيرة لهذا. غالبًا ما يكونون في المعلمين الذين ، إذا استخدموا العلاقات في عملية التدريس ، لم يركزوا على هذا المصطلح ، ولم يقدموا أمثلة لا تُنسى. عزا بعض المعلقين على المقال التعليقات إلى حساباتهم الخاصة وأضافوا سلبيات. لكن لا يمكنك إخفاء الخياطة في كيس. لم تكن هناك منشورات جادة ، ولا. اسأل نفسك ، هل عملت مع أي مساحة علاقة؟ وأجب بصراحة على نفسك. ماذا يمكنك أن تخبر العالم عن هذه المساحة؟ لتبدأ ، على الأقل ضع قائمة بعناصرها وحدد خصائصها. حتى أنك تنظر إلى نظام إدارة قواعد البيانات من خلال عيون مبتكريها ، لكنهم لا يرون كل شيء أيضًا ، أو لا يعرضون كل شيء ، على سبيل المثال ، في الدوائر المصغرة.
سأفعل القليل من التكرار هنا. يجب أن يبدأ المرء بمجموعة الملخص A = {a1، a2، a3، ...، an}. يمكنك أن تقرأ عنها هنا . لفهم أفضل ، سنقوم بتقليل المجموعة إلى 3 عناصر ، أي أ = {a1، a2، a3}. الآن نقوم بتنفيذ الضرب الديكارتي × = 2 ونعد صراحةً جميع عناصر المربع الديكارتي
× = {(a1، a1)، (a1، a2)، (a1، a3)، (a2، a1)، (a2، a2 )، (a2، a3)، (a3، a1)، (a3، a2)، (a3، a3)}.
حصلنا على 9 أزواج مرتبة من العناصر من A × A ، في زوج يكون العنصر الأول من العامل الأول ، والعنصر الثاني من العامل الثاني. لنحاول الآن الحصول على كل المجموعات الفرعية من المربع الديكارتي A × A. ستحتوي المجموعات الفرعية على عدد مختلف من الأزواج: واحد ، اثنان ، ثلاثة ، وهكذا حتى جميع الأزواج التسعة ، نقوم أيضًا بتضمين المجموعة الفارغة ∅ في هذه القائمة. كم عدد المجموعات الفرعية الموجودة؟ كثير ، أي 2 9= 512 عنصرًا.
التعريف . تسمى مجموعة فرعية من مجموعة مربعة ديكارتية علاقة ثنائية. إذا كان المربع الديكارتي لعاملين ، تكون النسبة ثنائية ، وإذا كان الرقم 3 داخليًا ، و 4 فهو رباعي ، و n هو n-ary. Arity هو عدد الأماكن في عنصر العلاقة.
التعريف . تسمى المجموعة المكونة من كل المجموعات الفرعية للمجموعة أ منطقية. يتكون المنطقي من 2 | A | العناصر هنا | أ | هي أصل المجموعة.
يمكن تعريف العلاقات بطرق مختلفة:
- تعداد العناصر R1 = {(a2، a2)، (a2، a3)، (a3، a1)} ؛ R2 = {(a3، a3)}
- ناقل ثنائي <000011100> ؛ <000000001>
- مصفوفة؛
- الرسم البياني وطرق أخرى.
بعد ذلك ، ننتقل إلى النظر في فضاءات العلاقات ، على افتراض أن المفهوم وخصائص العلاقات والعمليات معها مألوفة للقارئ على الأقل إلى حد نشرنا في الرابط.
مساحات العلاقات الثنائية
دعنا نوضح مبدئيًا أن العلاقات يمكن أن تكون صارمة (هذه كلها علاقات مضادة للانعكاس) أو غير صارمة (جميع العلاقات الأخرى). سنركز على علاقة اللامبالاة والتفضيل ، وتنقسم الأخيرة إلى تفضيلات ضعيفة وتفضيلات صارمة (لسبب ما ، ليست قوية). بشكل عام ، لا يوجد ترتيب في العلم بالمصطلحات وعلى الأرجح لن يكون هناك. في علم التشفير ، على سبيل المثال ، إزالة تشفير من برنامج تشفير في وجود مفتاح هو فك التشفير ، وبدون مفتاح فك التشفير. يبدو أن وحدة فك ترميز فك ، ولكن لا.
مساحة العلاقات الثنائية مع مجموعة الناقل هي مجموعة فرعية عشوائية من مجموعة العلاقات الثنائية المعطاة على. ضع في اعتبارك المساحات الرئيسية لعلاقات التفضيل (الشكل 2.15).
ر- فضاء كل علاقات التفضيل الضعيف ، يفي بشرط الانعكاس والاكتمال.
QT - تفضيلات ضعيفة تفي بشرط شبه انتقالية.
QO هي مساحة أشباه الأوامر الخطية ، أي العلاقات المتعدية من QT.
TO هي مساحة كل الطلبات المثالية ، أي العلاقات من QO غير المتماثلة.
SP هو فضاء جميع علاقات التفضيل الصارم ؛ فهي ترضي خصائص الانعكاسية المضادة والتناظر.
RO- العلاقات ذات الترتيب الجزئي الصارم ، أو التفضيلات الصارمة المتعدية. نظرًا لأن العلاقات ذات الترتيب الجزئي الصارم تعد متعدية ، فمن الطبيعي استخدامها لتمثيلها من خلال الرسوم البيانية المصغرة ، أي تلك التي تم حذف أقواس الانتقال فيها. تسمى هذه الرسوم البيانية المختصرة مخططات Hasse.
QS هي مساحة الاستعلامات ، أي الطلبات الجزئية الصارمة التي تكون العلاقة I = ¬ (PUP -1 ) معادلة لها.
TSO هي مساحة الأوامر الخطية الصارمة ، أي تلك الطلبات الجزئية التي يتم استيفاء خاصية الاكتمال لها.
وتجدر الإشارة إلى أن هناك عددًا إجماليًا من هذه العلاقات! .. على سبيل المثال ، بالنسبة إلى n = 3 ، فإن عدد العلاقات المثالية هو 6 ، وكلها موضحة في الشكل. 2.13.
تي- فضاء كل علاقات التسامح (اللامبالاة) ، لها خصائص التناظر والانعكاسية.
TOT هو مساحة علاقات التسامح الموجهة بشكل انتقالي ، أي العلاقات التي يتم تمثيل مكمل I على أنها اتحاد للعلاقات متعدية معكوسة بشكل متبادل ، أي
¬I = R∩R -1 .
أنا هو فضاء كل علاقات التكافؤ ، أي العلاقات المتماثلة ، الانعكاسية والمتعدية.
هـ - فضاء علاقات المساواة ، ويتكون من علاقة واحدة ممثلة بمصفوفة قطرية. توجد علاقة رأس برأس بين المسافات R و P و I ، يتم تحديدها من خلال تعيين علاقات التفضيل.
الشكل 2.15 مخطط مسافات العلاقات الثنائية
تُستخدم الروابط التي تم الكشف عنها بين المسافات لنقل مشاكل اتخاذ القرار (DM) من مساحة إلى أخرى ، حيث يمكن حلها بطريقة أبسط ، ثم يتم إرجاع الحل الناتج إلى الفضاء الأصلي ، حيث تمت صياغة DP.
تظهر هذه العلاقات بشكل تخطيطي في الشكل. 2.14. مسافات العلاقات الثنائية (أنواع العلاقات) موضحة في الشكل. 2.15.
علاقات التكافؤ
التعريف . تسمى العلاقة الثنائية σ ⊆ A × A ، والتي لها ثلاث خصائص للانعكاسية والتناظر والعبور ، علاقة التكافؤ الثنائية (BOE). يشار إلى علاقة التكافؤ σ (x ، y) ، (x ، y) ∊σ ، xσy ، x≈y. من الملائم استخدام تمثيل مصفوفة (جدولي) للعلاقة. أدناه في الشكل 2.24 هو مجرد تمثيل مصفوفة. فوق المجموعة المكونة من 4 عناصر ، يوجد 15 BOEs ، والتي تم تصويرها جميعًا.
تمثيل وتحليل هيكل علاقات التكافؤ (ن = 4)
ربما يكون التكافؤ من العلاقات الثنائية هو BO الأكثر شيوعًا. نادرًا ما يدير العلم بدون هذا المفهوم ، ولكن حتى عند استخدام التكافؤات للإشارة إلى أي أسئلة ، قد يكون من الصعب فهم ما قصده المؤلف. حتى مع التعريف الصحيح والتعداد الصحيح للخصائص المتأصلة في هذه العلاقة الثنائية ، تظل صعوبات الإدراك قائمة.
لنبدأ بمثال على المعادلات ، والذي يوضح حدود عددهم.
مثال 1 . يجب ألا يكون هناك ثلاثة مكعبات. دعنا نضع قائمة بالخصائص التي تتمتع بها المكعبات والاستخدام العملي لها (خصائص المكعبات) يجعلها نوعًا ما قابلة للتبادل. دعونا نخصص أرقامًا للمكعبات ، ونمثل خصائصها في الجدول 1.
لكل من الخصائص ، تنشأ فئات BOE وفئات التكافؤ. استمرارًا في قائمة الخصائص ، لن نحصل على علاقات تكافؤ جديدة. لن يكون هناك سوى تكرارات للبناء بالفعل ، ولكن لعلامات أخرى. دعونا نظهر العلاقة بين بنك انجلترا والمجموعات.
ضع في اعتبارك مجموعة من ثلاثة عناصر A = {1،2،3} واحصل على كل الأقسام الممكنة في جميع الأجزاء. ①1 | 2 | 3 ؛ ②12 | 3 ؛ ③13 | 2 ؛ ④ 1 | 23 ؛ ⑤123. آخر انقسام إلى جزء واحد. أرقام الأقسام و BOs في الدوائر.
التعريف . قسم من المجموعة A هو عائلة i ، i = 1 (1) I ، من مجموعات فرعية منفصلة زوجية غير فارغة من ، والتي يشكل اتحادها المجموعة الأصلية الكاملة = Ui ، i∩j = ∅ ، ∀ i ≠ j. تسمى المجموعات الفرعية i فئات التكافؤ لتقسيم المجموعة الأصلية.
هذه كلها أقسام من المجموعة (5 قطع). يوضح تحليل BO أنه لا يوجد سوى 5 علاقات تكافؤ مختلفة. هل هذه مصادفة؟ يمكننا ربط كل قسم بمصفوفة من تسع خلايا (3 × 3 = 9) ، تحتوي كل منها إما على زوج مرتب من العناصر من المجموعة أ ، أو تظل الخلية فارغة إذا لم يكن هناك كائن للزوج المقابل. يتم تمييز صفوف وأعمدة المصفوفة بعناصر المجموعة A ، ويتوافق تقاطع الصف والعمود مع زوج مرتب (i ، j). إنه ليس زوجًا يتناسب مع خلية المصفوفة ، ولكنه ببساطة واحد أو صفر ، ومع ذلك ، غالبًا لا تتم كتابة الصفر على الإطلاق.
لا ، الصدفة ليست صدفة. اتضح أن كل قسم من المجموعة يكون في مراسلات فردية مع بنك إنجلترا ، ويمكن أن يكون أصل المجموعة أي | A | = ن.
ربما تكون هذه العلاقة هي الأكثر شيوعًا من حيث الاستخدام في التداول العلمي ، لكن مزيج الخصائص المحققة في هذا الصدد يحد بشكل كبير من انتشارها.
لذلك من بين جميع العلاقات الثنائية المجردة على مجموعة من ثلاثة عناصر (هناك 2 9 = 512 علاقة في المجموع ) ، هناك خمسة فقط معادلات - ناقلات للخصائص المطلوبة ، أقل من واحد بالمائة.
لـ | A | = 4 علاقات موجودة 2 16= 65536 ، ولكن لا يوجد سوى 15 معادلاً. هذا نوع نادر جدًا من العلاقات. من ناحية أخرى ، تنتشر علاقات التكافؤ في المشكلات التطبيقية. أينما توجد وتعتبر مجموعات من كائنات مختلفة جدًا وأقسام مختلفة من هذه المجموعات (وليس الأرقام) إلى أجزاء ، تنشأ علاقات التكافؤ. يمكن أن يطلق عليها نماذج رياضية (جبرية) لمثل هذه الأقسام ، والتي تصنف مجموعات من الكائنات وفقًا لمعايير مختلفة.
يُطلق على الحد الأدنى من أقسام المجموعة A المكونة من مجموعات فرعية من عنصر واحد A = U {a} والقسم A المكون من المجموعة {A} نفسها أقسام تافهة (غير مناسبة).
شعرية P (4): جميع أقسام المجموعة A = {a1، a2، a3، a4} = {1،2،3،4}
يتوافق الحد الأدنى من التقسيم مع علاقة التكافؤ P15 ، والتي تسمى المساواة أو علاقة الوحدة. تحتوي كل فئة معادلة على عنصر واحد. بالنسبة إلى قسم من المجموعة A ، والذي يتضمن المجموعة A نفسها فقط ، هناك علاقة تكافؤ تحتوي على جميع عناصر المربع الديكارتي A × A.
أقرب نوع من علاقات التكافؤ هو علاقات التسامح . تحتوي مجموعة علاقات التسامح على جميع علاقات التكافؤ. بالنسبة للناقل A هناك ثلاثة عناصر من التسامح 8. ولكل منها خصائص الانعكاسية والتناظر.
عندما تتحقق خاصية العبور ، تتحول خمسة من التسامح الثمانية إلى معادلات (الشكلان 2.24 و 2.25).
التعريف . تسمى مجموعة فئات التكافؤ [أ] σ لعناصر المجموعة أ مجموعة حاصل القسمة (يُشار إليها بالرمز A / of) للمجموعة أ بالتكافؤ σ.
التعريف . التعيين الطبيعي (القانوني) f: A → A / هو تعيين f مثل f (a) = [a] σ.
علاقات التسامح وتحليلها
تم ذكر هذه BOs بالفعل سابقًا ، ولكن هنا سننظر فيها بمزيد من التفصيل. يعلم الجميع مفاهيم التشابه ، والتشابه ، والتشابه ، وعدم التمييز ، وإمكانية تبادل الأشياء. يبدو أنهما متشابهان في المحتوى ، لكنهما ليسا نفس الشيء. عندما يتم الإشارة إلى التشابه فقط للكائنات ، فمن المستحيل تقسيمها إلى فئات واضحة بحيث تكون الكائنات داخل الفئة متشابهة ، ولا يوجد تشابه بين الكائنات من الفئات المختلفة. في حالة التشابه ، تنشأ حالة غامضة بدون حدود واضحة. من ناحية أخرى ، يمكن أن يؤدي تراكم الاختلافات الطفيفة في الأشياء المتشابهة إلى كائنات مختلفة تمامًا.
في الجزء السابق ، ناقشنا المعنى الهادف لعلاقة التشابه (التكافؤ) بين الأشياء. نفس القدر من الأهمية هو الموقف عندما يكون من الضروري إثبات تشابه الأشياء.
دع شكل الأجسام الهندسية يتم دراستها. إذا كان التشابه في شكل الأشياء ، على سبيل المثال ، المكعبات ، يعني قابليتها للتبادل الكامل في موقف تعليمي معين ، فإن التشابه هو قابلية التبادل الجزئي (عندما يكون من بين المكعبات متوازيات السطوح التي تشبهها إلى حد كبير) ، أي إمكانية التبادل مع بعضها (مقبول في هذه الحالة ) الخسائر.
إن أكبر مقياس للتشابه هو عدم قابلية التمييز ، وليس التماثل على الإطلاق ، كما قد يبدو للوهلة الأولى. الهوية هي خاصية مختلفة نوعيا. لا يمكن النظر إلى الهوية إلا على أنها حالة خاصة من عدم قابلية التمييز والتشابه.
النقطة المهمة هي أن الكائنات التي لا يمكن تمييزها (وكذلك الأشياء المماثلة والمتشابهة) لا يمكن تقسيمها إلى فئات بحيث لا تختلف العناصر في كل فئة ، ومن الواضح أن عناصر الفئات المختلفة مختلفة.
في الواقع ، سننظر في مجموعة النقاط (س ، ص) على المستوى. دع القيمة d لها قيمة أقل من حد قابلية العين للحل ، أي أن d هي المسافة التي تندمج عندها نقطتان تقعان على هذه المسافة في نقطة واحدة ، أي لا يمكن تمييزه بصريًا (على المسافة المختارة للطائرة من المراقب). ضع في اعتبارك الآن n من النقاط مستلقية على خط مستقيم واحد ومتباعدة (كل منها من المجاورة) على مسافة d.
لا يمكن التمييز بين كل زوج من النقاط المتجاورة ، ولكن إذا كانت n كبيرة بدرجة كافية ، فستكون النقطتان الأولى والأخيرة بعيدتين عن بعضهما البعض وسيكون من الممكن تمييزهما بالتأكيد.
تتمثل الطريقة التقليدية لدراسة التشابه أو عدم القابلية للتمييز في تحديد درجة التشابه أولاً ، ثم فحص الموضع النسبي للأشياء المتشابهة. عالم الرياضيات الإنجليزي زيمان ، الذي درس نماذج من الجهاز البصري ، اقترح تعريفًا بديهيًا للتشابه. وبالتالي ، أصبح من الممكن دراسة خصائص التشابه بغض النظر عن كيفية تحديدها بالضبط في موقف معين: المسافة بين الأشياء ، أو مصادفة بعض الميزات ، أو الرأي الشخصي للمراقب.
دعونا نقدم شرحا لمفهوم التشابه أو عدم التمييز.
التعريف . تسمى العلاقة T على المجموعة M علاقة التسامح أو التسامح إذا كانت انعكاسية ومتماثلة.
تتضح صحة هذا التعريف من حقيقة أن الموضوع لا يمكن تمييزه بوضوح عن نفسه ، وبطبيعة الحال ، يبدو مثل نفسه (وهذا يعطي انعكاسية العلاقة). لا يؤثر ترتيب النظر في كائنين في الاستنتاج النهائي حول التشابه أو الاختلاف بينهما (التناظر).
من المثال مع عدم القدرة على التمييز البصري للنقاط على المستوى ، نرى أن انتقالية التسامح لم تتحقق لجميع أزواج الكائنات.
من الواضح أيضًا أنه نظرًا لأن التشابه هو حالة خاصة من التشابه ، فيجب أن يكون التكافؤ حالة خاصة من التسامح. بمقارنة تعريفات التكافؤ والتسامح ، نحن مقتنعون بأن هذا هو الحال. المبدأ الفلسفي: "الخاص أغنى من العام" تم تأكيده بوضوح. خاصية إضافية - الانتقال يجعل بعض علاقات التسامح المتكافئة. توأمان متشابهان لدرجة أنهما يمكنهما إجراء الاختبارات لبعضهما البعض دون مخاطر. ومع ذلك ، إذا كان اثنان من الطلاب متشابهين فقط ، فإن هذه الحيلة ، رغم أنها ممكنة ، تنطوي على مخاطرة.
يحمل كل عنصر في المجموعة معلومات معينة حول عناصر مشابهة له. ولكن ليس كل المعلومات كما في حالة العناصر المتطابقة. هنا ، من الممكن أن يحتوي أحد العناصر على درجات مختلفة من المعلومات بالنسبة إلى عنصر آخر.
لنأخذ في الاعتبار أمثلة حيث يتم تعيين التسامح بطرق مختلفة.
مثال 2 . تتكون المجموعة M من كلمات روسية مكونة من أربعة أحرف - الأسماء الشائعة في الحالة الاسمية. سوف نسمي هذه الكلمات متشابهة إذا كانت تختلف بما لا يزيد عن حرف واحد. تمت صياغة المشكلة المعروفة "تحويل الذبابة إلى فيل" بعبارات دقيقة على النحو التالي. ابحث عن سلسلة من الكلمات تبدأ بكلمة "fly" وتنتهي بكلمة "elephant" ، أي كلمتين متجاورتين متشابهتين بالمعنى الوارد في التعريف المقدم للتو. حل هذه المشكلة:
فلاي - مورا - تورا - تارا - كارا - سكوير - كافيه - كافير - مشير - سكيف - خطاف - تمساح - موعد نهائي - جريان - تأوه - فيل.
مثال 3... لنفترض أن p هو عدد طبيعي. نشير بواسطة Sp إلى مجموعة جميع المجموعات الفرعية غير الفارغة للمجموعة M = {1 ، 2 ، ... ، p}. العلاقة "لها عنصر مشترك واحد على الأقل" في المجموعة Sp هي علاقة تسامح. ثم يطلق على مجموعتين فرعيتين من هذا القبيل اسم متسامح إذا كان لديهما عنصر مشترك واحد على الأقل. من السهل أن نرى أن انعكاسية العلاقة وتناسقها قد تحققا.
المجموعة Sp تسمى (p –1) البسيط الأبعاد. يعمم هذا المفهوم مفهوم المقطع والمثلث ورباعي السطوح على الحالة متعددة الأبعاد. يتم تفسير الأرقام 1 ، 2 ، 3 ، ... ، p كرؤوس من البسيط. مجموعات فرعية مكونة من عنصرين - كحواف ، وثلاثة عناصر - كأوجه مسطحة (ثنائية الأبعاد) ، ومجموعات فرعية أخرى من عنصر k - مثل الوجوه (k –1) ذات الأبعاد. عدد جميع عناصر (مجموعات فرعية) Sp يساوي 2 ص - 1.
التسامح مع المجموعات الفرعية (الوجوه) يعني أن لديهم رؤوس مشتركة.
التعريف . المجموعة M مع علاقة التسامح المعطاة عليها تسمى مساحة التسامح. وبالتالي ، فإن مساحة التسامح هي زوج (M ، τ).
مثال 4 . يمكن تعميم مساحة التسامح Sp على الحالة اللانهائية. دع H مجموعة عشوائية. إذا كانت SH هي مجموعة كل المجموعات الفرعية غير الفارغة للمجموعة H ، فإن علاقة التسامح T على SH تُعطى بالشرط: X T Y إذا X∩Y ≠ ∅. إن تناسق هذه العلاقة وانعكاساتها واضح. تم تعيين فضاء SH على أنه <H ، T> ويسمى فضاء التسامح "العالمي".
مثال 5... لنفترض أن p هو عدد طبيعي. نشير بواسطة Bp إلى مجموعة جميع نقاط فضاء البعد p الذي تكون إحداثياته مساوية لـ 0 أو 1. يتم تحديد التسامح في Bp بواسطة القاعدة: x ify إذا كان x و y يحتويان على عنصر واحد على الأقل متزامن (تنسيق). العدد الإجمالي للعناصر في Bp هو 2 r . لكل عنصر x = (a1، a2، ...، ap) من المجموعة Bp ، يوجد عنصر واحد فقط y = (1 - a1، 1 - a2، ...، 1 - ap) لا يتسامح معه.
من الواضح أن Bp تتكون من جميع رؤوس المكعب ذي البعد p.
مثال 6 . فكر في فضاء التسامح ، الذي تأخذ مكوناته أي قيم حقيقية.
على وجه الخصوص ، هذه هي مجموعة جميع النقاط x = (a1، a2) في المستوى الديكارتي. يعني التسامح من نقطتين أن لديهم إحداثي واحد على الأقل. هذا يعني أن نقطتي التسامح إما على عمودي مشترك أو على أفقي مشترك.
بالنسبة لقيم p الأخرى ، يمكن تفسير الفضاء على أنه مجموعة من النقاط في فضاء البعد p. على وجه الخصوص ، يمكن اعتبار كل عنصر x دالة عددية محددة في مجموعة الأعداد الطبيعية {1 ، 2 ، 3 ، ...} ، والتي تخصص لكل رقم طبيعي i: 1 ≤ i ≤ p رقم حقيقي ai (تسلسل رقمي محدد). ثم يعني التسامح بين دالتين x و y أنهما متساويتان عند نقطة واحدة على الأقل.
علاقات الترتيب الجزئي وتحليلها
المجموعات المطلوبة هي مجموعات مع تقديم علاقة ترتيب عليها. التعريف . تسمى المجموعة أ وعلاقة الأمر الثنائي R عليها (≤) مرتبة جزئيًا إذا كانت العلاقة تحمل (كما في BOE) ثلاثة شروط (شرط واحد مختلف):
- الانعكاسية ∀ x ∊ A (xRx) ؛ (مضاد الانعكاسية ∀ x ∊ A ¬ (xRx)) ؛
- التماثل المضاد ∀ ، y ∊ (Ry yRx → x = y) ؛
- الانتقال ∀ x ، y ، z ∊ A (xRy & yRz → xRz).
مع موقف مضاد للانعكاس ، ينشأ ترتيب جزئي صارم . المجموعة B (A) لجميع المجموعات الفرعية للمجموعة A ، مرتبة بإدراج العناصر ، هي مجموعة مرتبة جزئيًا (PN). غالبًا ما تسمى المجموعة المرتبة جزئيًا (B (A) ،) Boolean.
يغطي العنصر x∊A POZA A عنصر y∊A إذا كانت x> y ولا يوجد z∊A مثل x> z> y. زوج من العناصر x ، y∊A يسمى قابل للمقارنة إذا كان x ≥ y أو x ≤ y.
إذا كان كل زوج من عناصره في PLA A قابلاً للمقارنة ، فإن A يسمى مجموعة أو سلسلة مرتبة خطيًا . إذا كان بعض الطاعون B يتكون فقط من عناصر لا تضاهى مع بعضها البعض ، فإن المجموعة B تسمى antichain
... تسمى السلسلة في PLAG A "مشبعة" إذا كان لا يمكن دمجها في أي سلسلة أخرى غير نفسها.
يتم تعريف antichain المشبع بالمثل. السلسلة القصوى (antichain) هي سلسلة (antichain) تحتوي على أقصى عدد من العناصر.
يسمى عنصر m من PLM A بالحد الأدنى إذا لم يكن هناك عنصر في بخلاف m وهذا هو ≤m. ويطلق على M عنصر من الطاعون A القصوى إذا لم يكن هناك عنصر س "أكبر" من M، وغيرها من M وهذا أن x ≥ M.
أحد العناصر yεA من الطاعون ويسمى القصوى إذا ∀ xε أ س ≤ ذ. يسمى العنصر y∊ A PLAG A الأصغرإذا ∀ x∊A x ≥ y. بالنسبة للعناصر الأكبر والأصغر ، من المعتاد استخدام التعيينات 1 و 0 على التوالي. يطلق عليهم حدود عالمية. يحتوي أي طاعون A على عنصر واحد على الأكثر أصغر وأكبر عنصر على الأكثر. في PLA A ، يُسمح بالعديد من العناصر الدنيا والقصوى ، ومن
الملائم تصوير PLA A النهائي بمخطط Hasse ، وهو رسم بياني موجه ، ويتم توزيع رؤوسه على مستويات الرسم التخطيطي وتتوافق مع عناصر من A ، ويتم توجيه كل قوس لأسفل ويتم رسمه إذا وفقط إذا كان العنصر تغطي x∊A العنصر y∊A.
لا يتم رسم الأقواس المتعدية. تحتوي مستويات مخطط Hasse على عناصر من نفس الرتبة ، أي متصلة بالحد الأدنى من عناصر PCM بمسارات متساوية الطول (حسب عدد الأقواس).
لنفترض أن B مجموعة فرعية غير فارغة من PLA A ، ثم عنصر x∊A يسمى الحد الأعلى الدقيق (يُشار إليه بالرمز sup A B) للمجموعة B إذا كانت x ≥ y لكل y∊B وإذا كان يتبع حقيقة العلاقة z ≥ y لكل yB ، أن z ≥ x.
الحد الأدنى الدقيق (المشار إليه بواسطة inf A B) للمجموعة B هو عنصر x∊A إذا كان x ≤ y لجميع y∊B وإذا كان الشرط z ≤ y لجميع y∊ B يعني ضمناً أن z ≤ x.
مثال 7 . تم
إعطاء مجموعتين عدديتين محددتين A = {0،1،2، ...، 21} و B = {6،7،10،11}.
يظهر CHUM (A ، ≤) في الشكل. 2.26.
المجموعة B Δ لجميع الحدود العليا لـ تسمى المخروط العلوي للمجموعة B. المجموعة ∇من جميع الوجوه السفلية لـ B يسمى المخروط السفلي لـ B.
أي مجموعة فرعية من PLA هي أيضًا PLP فيما يتعلق بالترتيب الموروث. إذا كانت المجموعة تحتوي على أكبر و / أو أصغر العناصر ، فهي الحد الأقصى (الحد الأدنى ، على التوالي). والعكس ليس صحيحا. يحتوي Boolean على أصغر عنصر واحد (Ø) وأكبر عنصر واحد.
في المجموعة المحددة ، أصغر عنصر هو صفر (0) ويتزامن مع العنصر الأدنى فقط ، ولا يوجد عنصر أكبر. الحد الأقصى للعناصر هو {19 ، 20 ، 21}. الحد الأعلى الدقيق لـ B = {6،7،10،11} هو العنصر 21 (هذا هو أصغر عنصر في المخروط العلوي).
الوضع العام. دعونا نعطي مجموعة ، التي هي أصلها *******. من بين جميع العلاقات الثنائية الممكنة في هذه المجموعة ، نفرد علاقات التفضيل الثنائي وعلاقات الأوامر الجزئية الصارمة المرتبطة بها.
تختلف الطلبات الجزئية عن الطلبات الجزئية الصارمة فقط من حيث أنها تحتوي على عناصر إضافية (في تمثيل المصفوفة - قطري) (i ، ai) = 1 ، i = 1 (1) n ، وعدد هذه الأوامر وغيرها في المجموعة الكاملة من العلاقات نفس الشيء. حتى الآن ، لم يتم العثور على تبعيات (صيغة ، خوارزمية) من شأنها أن تسمح لأحد بحساب وتعداد عدد الطلبات الجزئية لأي n.
قام مؤلفون مختلفون بتحديد ونشر النتائج التالية عن طريق الحساب المباشر (الجدول 2.12).
مكنت التجارب الحسابية للمؤلف من الحصول ليس فقط على العدد ، ولكن أيضًا على شكل (تمثيل) الطلبات الجزئية في قوى مختلفة من الناقل المضاعف للعلاقات. اختنقت الطابعة عند طباعة مثل هذه القوائم الضخمة ، لكن ليس الجمال فقط يتطلب تضحيات ، فالعلم أيضًا لا يرفضها.
يوضح الجدول 2.12: n = | A | - أصل مجموعة الناقل ؛ السطر الثاني هو رقم جميع العلاقات الثنائية في المجموعة أ ؛ والمزيد
| في (ن) | - عدد فئات العلاقات غير المتشابهة ؛
| (ن) | - عدد العلاقات الجزئية ؛
| Gn (n) | - عدد فئات العلاقات النظامية الجزئية غير المتشابهة ؛
| جل (ن) | = ن! - عدد علاقات الترتيب الخطية.
كما ترون ، في الجدول لـ n الصغيرة ، على سبيل المثال ، G (n = 4) ، هناك 219 فقط ، يتم تقديم البيانات ، والتي تنمو قيمها بسرعة كبيرة مع زيادة n ، مما يعقد بشكل كبير تحليلهم الكمي (والنوعي) المباشر حتى باستخدام الكمبيوتر.
يوضح الجدول أدناه إمكانية إنشاء Γ (ن = 4) لجميع الطلبات الجزئية من تقاطع كل منها مع كل أمر جزئي خطي. ولكن في هذه الحالة ، تظهر العناصر الزائدة عن الحاجة (المتكررة) ، والتي يمكن قطعها يدويًا (إعادة الحساب) بالنسبة لـ n الصغيرة. اتضح 300 مصفوفة ، ولكن لا يوجد سوى 219 مصفوفة فيما بينها ، ولم يتم الحصول على الصيغ العامة. على المستوى العالمي ، الوضع مشابه ، على الرغم من أنني لم أر أي منشورات حول عمليات نقل PLM من قبل المؤلفين الغربيين. خوارزمياتنا أصلية ورائدة تمامًا.
سأقدم مخططًا ممكنًا لحل مشكلة تعداد عناصر مساحة الطلبات الجزئية (ن = 4).
يتم إنشاء مجموعة الأوامر الجزئية الصارمة في الترتيب المعجمي للأوامر الخطية (ن = 4) من خلال تقاطعها المتبادل.
العديد من التعريفات الهامة للرياضيات للمفاهيم التي توجد غالبًا في النصوص.
التعريف . الفترة المغلقة هي مجموعة من النموذج {x: a ≤ x ≤ b}؛ الفاصل الزمني المفتوح غير مغلق ، وفترة نصف مفتوحة ، أي مجموعة من النموذج {x: a <x ≤ b} ، حيث a <b ، أو النموذج {x: a ≤ x <b} ليست مفتوحة ولا مغلقة.
التعريف . تتكون حدود الفاصل الزمني التعسفي لخط حقيقي في الهيكل المعتاد للأرقام الحقيقية فقط من نهايات هذا الفاصل ، بغض النظر عما إذا كان هذا الفاصل مفتوحًا أم مغلقًا أم نصف مفتوح. إن حدود مجموعة الأعداد المنطقية ، وكذلك حدود مجموعة جميع الأعداد غير النسبية ، هي مجموعة الأعداد الحقيقية بأكملها.
تعريف... كل مجموعة مرتبة خطيًا ، في أي مجموعة فرعية غير فارغة يوجد بها أصغر عنصر ، تسمى حسن الترتيب.
التعريف . يُطلق على العائلة R سلسلة (أحيانًا برج ، أو عش) إذا وفقط إذا كان ، لأي من عناصرها A و B ، إما A B أو B A. وهذا الشرط يعادل التأكيد على أن الأسرة R مرتبة خطيًا عن طريق التضمين أو ، في المصطلحات المقبولة - أن الأسرة R مع علاقة التضمين هي سلسلة.
P r و n c و p m a إلى s و m al n حول s t و H a u s d o r f a. بالنسبة لأي عائلة من المجموعات A وأي عش R يتكون من عناصر من العائلة A ، يوجد عش أقصى M في A يحتوي على R.
نظرية مهمة حول المجموعات وعائلاتهم (J.L. Kelly "الهيكل العام" ص 55).
نظرية. (أ) PRINTSIpMakSIMALN حول ELEMENT. يوجد عنصر أقصى في عائلة A من مجموعة إذا كان هناك عنصر في A يحتوي على عنصر عشوائي لهذا العش لكل عش في A.
(ب) عنصر PRINTSIpMINIMALNO. يوجد أصغر عنصر في عائلة A إذا كان لكل عش في A عنصر في A موجود في كل عنصر من هذا العش.
(ج) Lemma T yuk و. كل مجموعة من مجموعات الأحرف المحددة لها عنصر أقصى.
(د) LEMMA KURATOVSKOGO. كل سلسلة في مجموعة مرتبة (جزئيًا) موجودة في سلسلة قصوى.
(ه) ليما تسون. إذا كانت كل سلسلة من مجموعة مرتبة جزئياً مقيدة من أعلى ، فإن هذه المجموعة تحتوي على أقصى عنصر.
(و) من A إلى s و o m واختيار. دع Xα عبارة عن مجموعة غير فارغة لكل عنصر a من مجموعة الفهارس A. ثم توجد وظيفة c على A مثل أن c (a) ∊ Xα لكل a من A.
(g) افترض Tserm إلو. بالنسبة لأي عائلة A من المجموعات غير الفارغة المنفصلة ، هناك مجموعة C بحيث تتكون AUC لكل A من A من نقطة واحدة بالضبط.
(ح) PRINTS و P بترتيب التسليم الكامل. يمكن طلب كل مجموعة بالكامل.