Дискретно-непрерывная математика (стр. 39 )

Позднее, при обсуждении понятия совершенного порядка, мы вер­немся к исследованию нескольких интересных свойств совершенной антисимметрии.

Замечание. Любое совершенное антисимметричное отношение, оче­видно, будет и антисимметричным отношением.

Пример 1. На рис. 12.8 представлено совершенное антисимметрич­ное отношение. На рис. 12.9 показан обычный антисимметричный граф, связанный с этим отношением.

Рис. 12.8 Рис. 12 9

Пример 2. Рассмотрим две области D1 и D2 в R+ × R+, указанные на рис. 12.10.

Рис. 12 10

Отношение определенное на R+ функцией принадлежности

(12.9)

есть антисимметричное отношение, которому соответствует обычный антисимметричный граф.

2.13. Нечеткие отношения порядка

Нечетким отношением порядка называется бинарное отношение, которое: 1) рефлексивно (согласно 6.7)); 2) транзитивно (согласно (6.8) или (6.9)); 3) антисимметрично (согласно (12.1)) (будем также говорить просто отношение порядка, если это не приводит к недоразу­мению).

Можно также дать следующее определение: антисимметричное не­четкое отношение предпорядка называется нечетким отношением по­рядка. Следовательно, приводимое отношение и такое, что каждый класс подобия содержит только один элемент.

Пример 1. На рис. 13.1 и 13.2 представлены нечеткие отношения порядка. Можно проверить, что они действительно рефлексивны, тран-зитивны и антисимметричны.

Рис. 13.1 Рис. 13.2

Пример 2. Отношение, определенное в (9.4) и представленное на рис. 9.2, есть нечеткое отношение порядка.

Пример 3. Отношение где х, y N (рис. 13.3), есть нечеткое

отношение порядка.

Рис. 13.3

Теорема 1. Каждое нечеткое отношение строгого порядка индуци­рует порядок (в смысле теории множеств) на своем универсуме посред­ством отношения

(13.1)

Этот порядок будем обозначать

Доказательство. Достаточно рассмотреть обычный антисимметричный граф, связанный с данным нечетким отношением порядка.

Примеры. На рис. 13.4 и 13.5 представлены соответственно обыч­ные антисимметричные графы, со­ответствующие нечетким отноше­ниям порядка на рис. 13.1 и 13.2.

Рис. 13.4 Рис. 13.5

На рис. 13.6 изображен счетный бесконечный обычный граф, соот­ветствующий отношению на рис. 13.3.

Рис. 13.6

Нечеткое отношение полного порядка (Оно называется отношением линейного порядка (по ), если этот порядок совершенный. Линейный порядок можт определить с помощью более строгого условия антисимметричности:

).

Нечеткое отношение на­зывается полным порядком (или полностью упорядоченным нечет­ким отношением), если соответствующий ему обычный граф представляет полный порядок.

Рассмотрим пример на рис. 13.5. Используя обозначение

(13.2)

[т. е. если (х, у) G и (у, х) G], имеем

(13.3)

Нечеткие отношения частичного порядка. Нечеткое отношение на­зывается частичным порядком (нечетким отношением частичного по­рядка), если соответствующий ему обычный граф представляет частич­ное упорядочение.

В примере на рис. 13.4 изображен такой случай. Имеем

(13.4)

Отношение совершенного порядка. Если понятие антисимметрич­ности, определенное (12.1), заменить понятием совершенной антисим­метричности (12.8), то получим отношение совершенного порядка.

Все эти отношения порядка обладают своими интересными свойст­вами, которые мы рассмотрим ниже

Отношения нестрогого и строгого порядка. Подобно тому, как это делается в теории обычных множеств, можно различать отношения не­строгого (транзитивного, рефлексивного, антисимметричного) порядка и отношения строгого (транзитивного, антирефлексивного, антисиммет­ричного) порядка. Отношение нестрогого порядка в общем случае бу­дет называться отношением порядка, а отношение строгого порядка будет доопределяться с помощью прилагательного. Такое отношение мож­но также называть нерефлексивным отношением порядка.

Нестрогий порядок, как мы уже указывали, будем обозначать

(13.5)

а строгий порядок —

(13.6)

Приведем несколько примеров строгих нечетких отношений по­рядка.

Пример 1. На рис. 13.7 приведен пример отношения строгого по­рядка, одновременно оно есть и отношение совершенного порядка.

Рис. 13.7

Кроме того, этот порядок полный. Можно проверить, что

A<B<C<D. (13.7)

Пример 2. Рассмотрим где х, у R и

(13.8)

Это отношение представляет собой строгий и совершенный порядок (можно проверить, что при у = х имеем Кроме того,

этот порядок полный. Можно считать, что это отношение представля­ет (довольно грубо) утверждение:

Важное общее замечание. Все определения, связанные с отношения­ми порядка в обычных множествах, можно непосредственно перено­сить на нечеткие отношения порядка; для этого в качестве промежуточ­ного понятия достаточно воспользоваться понятием соответствующего обычного графа. Таким образом, оказывается, что для нечет­ких отношений порядка можно изучать сле­дующие классические понятия: наибольший и наименьший элемент; мажоранта и мино­ранта; верхний и нижний пределы; макси­мальная цепь; фильтрующее множество; диа­грамма Хассе; полурешетка и решетка.

Некоторыми из этих понятий мы восполь­зуемся, когда это понадобится для наших целей. Теперь вернемся к понятию приводи­мого нечеткого предпорядка для того, чтобы привести одну важную теорему.

Теорема 2. Для данного приводимого нечеткого отношения пред­порядка существует по крайней мере один класс подобия, и классы по­добия сами образуют нечеткое отношение порядка, если для построе­ния последнего используется понятие сильнейшего пути от одного класса к другому.

Доказательство. Отношение, образованное из классов по­добия, обязательно антисимметрично, так как в противном случае не­которые классы должны были бы пересекаться.

Пример 1. Вернемся к примеру на рис. 11.2. Для отношения поряд­ка между этими классами (рис. 13.8, а) соответствующий ему обычный

граф изображен на рис. 13.8, б. Как видно из рисунка, это полный порядок

(13.9)

Рис. 13.8

Теперь, имея в своем распоряжении обычный граф, устанавливаю­щий обычное отношение порядка между классами подобия, можно оп­ределить нечеткое отношение порядка, существующее между класса-

ми, получая это отношение нахождением сильнейшего пути для каж­дого класса. Для примеров на рис. 11.1, 11.2 и 13.8 результаты приве­дены на рис. 11.2; аналогично мы воспроизводим на рис. 13.9 резуль­таты для рис. 13.8.

Рис. 13.9

Для примера, представленного на рис. 11.1, определение сильней­шего пути, существующего между K1 и К2, К1 и К3 и, наконец, между К2 и К3, не представляет труда. Класс K1 = {А, В, С, Е, F} и класс

К2={D} соединяют путями, величины которых приведены в следующем столбце:

Сильнейший путь (не единственный) имеет значение 0,3. Для путей от К2 к K1, очевидно, имеем

и сильнейший путь (не единственный) имеет значение 0,2.

Для путей от К1 к K3= {G} имеем