1. Классификация антисимметричных отношений
2. Классификация рефлексивных отношений
2.1. Отношения квазипорядка
2.2. Отношения нестрогого частичного порядка
2.3. Отношения нестрого упорядочения
2.4. Нестрогий качественный порядок
2.5. Нестрогий слабый порядок
2.6. Нестрогий порядок
3. Двойственность отношений строгого и нестрогого порядка
4. Обзор свойств различных видов отношений
Строгим порядком (строгим предпочтением, сильным порядком, строгим линейным порядком) называется антирефлексивное, транзитивное, слабосвязное бинарное отношение (12).
Строгий порядок является частным случаем слабого порядка (строгого частичного предпочтения) с дополни-тельным условием слабосвязности.
Пример: Отношение "строго меньше" на множестве целых чисел.
Эти бинарные отношения позволяют сравнивать элементы некоторого множества, но не по сходству, а путем расположения элементов групп в некотором порядке, т.е. путем частичного упорядочивания.
Квазипорядком (нестрогим частичным предпочтением) называется рефлексивное и транзитивное бинарное отношение (3).
Пример: "быть братом" (Иван-Петр, Андрей-Анна)
1. Пересечение квазипорядков остается квазипорядком.
2. Симметричная часть квазипорядка обладает свойствами рефлексивности, симметричности и транзитивности и поэтому является отношением эквивалентности. Rс = R /\ Rинв
3. С помощью этого пересечения можно выделить группы эквивалентных между собой вариантов, тогда между выделенными группами может быть установлено отношение нестрогого частичного порядка, порожденное исходным отношением.
4. Асимметричная часть квазипорядка является транзитивным и антирефлексивным отношением = качественный порядок.
Отношением нестрогого частичного порядка (4) называется отношение, имеющее свойства рефлексивности, антисимметричности и транзитивности.
Нестрогий частичный порядок является антисимметричным квазипорядком
Пример: отношение "быть частью", определенное для множеств (и их подмножеств)
1. Пересечение нестрогих частичных порядков остается нестрогим частичным порядком .
2. Симметричная часть нестрогого частичного порядка является диагональю.
3. Асимметричная часть нестрогого частичного порядка является (строгим) качественным порядком.
4. В теории интеллектуальных систем важную роль играют частично упорядоченные множества – домены вместе с определенными на них отношениями нестрогого частичного порядка.
5. Частично упорядоченные множества с дополнительным свойством существования у каждой пары элементов верхней и нижней граней называются решетками. Частным случаем решеток являются булевы алгебры.
Нестрогим упорядочением называется рефлексивное отношение, обладающее свойством слабосвязности (5).
Нестрогое упорядочение можно определить также как полносвязное отношение.
Отношение нестрогого упорядочения можно представить как результат объединения некоторых отношений толерантности и доминирования.
1. Пересечение и объединение полносвязных отношений остается полносвязным отношением.
2. Симметричная часть нестрогого частичного упорядочения является толерантностью.
3. Асимметричная часть нестрогого частичного упорядочения является доминированием.
4. Для полносвязных отношений необходимым условием транзитивности является негатранзитивность отношения.
5. Для полносвязных отношений свойство транзитивности является достаточным условием негатранзитивности отношения.
Бинарное отношение R называется нестрогим качественным порядком, если оно негатранзитивно и полносвязно (6).
Нестрогий качественный порядок является негатранзитивным нестрогим упорядочиванием.
Отношение нестрогого качественного порядка можно представить как результат объединения некоторых отношений толерантности и качественного порядка.
1. Симметричная часть нестрогого качественного порядка является толерантностью. НТ?
2. Асимметричная часть нестрогого качественного порядка транзитивна, поэтому является отношением качественного порядка.
3. Таким образом, отношение нестрогого качественного порядка можно представить как результат объединения отношений толерантности и качественного порядка, порожденных исходным отношением.
4. Двойственное отношение обладает свойствами асимметричности и транзитивности поэтому является отношением качественного порядка.
Нестрогим слабым порядком называется полносвязное транзитивное и негатранзитивное отношение (7).
Нестрогим слабым порядком называется полносвязное транзитивное отношение.
Нестрогим слабым порядком называется транзитивное нестрогое упорядочение.
1. Симметричная часть нестрогого слабого порядка является эквивалентностью.
2. Асимметричная часть Rас нестрогого слабого порядка транзитивна, поэтому является отношением качественного порядка.
3. Таким образом, отношение нестрогого слабого порядка можно представить как результат объединения отношений эквивалентности и слабого порядка, порожденных исходным отношением.
4. Нестрогий слабый порядок можно представить в виде множества частично упорядоченных слоев, каждый из которых является классом эквивалентности.
Нестрогим порядком (нестрогим линейным порядком) называется антисимметричное, транзитивное, полносвязное бинарное отношение (8).
Нестрогим порядком называется антисимметричный нестрогий слабый порядок.
Нестрогим порядком называется антисимметричное нестрогое упорядочение.
1. Симметричная часть нестрогого порядка является диагональю.
2. Асимметричная часть Rас нестрогого порядка транзитивна и слабосвязна, поэтому является отношением строгого порядка.
3. Двойственное отношение обладает свойствами асимметричности, негатранзитивности и слабосвязности поэтому является отношением строгого порядка. Кроме того оно совпадает с Rас.
4. Таким образом, отношение нестрогого порядка можно представить как результат объединения диагонали и строгого порядка, порожденных исходным отношением.
