Лекции по "Развитию операционных систем"

Пример 3.8.  Отношение равенства на множестве целых чисел есть отношение эквивалентности.

,

Пример 3.9.  Отношение «одного роста» есть отношение эквивалентности на множестве людей X.

,

Пример 3.10.  Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (mÎ¥) и запишем , если равны остатки этих чисел от деления их на m, т.е. разность (x-y) делится на m.

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т.к. для "x΢ имеем x-x=0, и, следовательно, оно делится на m;

это отношение симметрично, т.к. если (x-y) делится на m, то и (y-x) тоже делится на m;

это отношение транзитивно, т.к. если (x-y)  делится на m, то для некоторого целого t1 имеем , а если (y-z) делится на m, то для некоторого целого t2 имеем , отсюда , т.е. (x-z) делится на m.

,

Определение 3.7.  Отношение r на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.

Пример 3.11.  Отношение x£y на множестве действительных чисел есть отношение частичного порядка.                                                                                                 ,

Пример 3.12.  Во множестве подмножеств некоторого универсального множества U отношение AÍB есть отношение частичного порядка.

,

Пример 3.13.  Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

,

Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта.

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т.е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P, которое можно определить как «aPb, a, bÎA Û объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т.е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование, т.е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.