1. Классификация антисимметричных отношений
1.1. Отношения доминирования
1.2. Качественный порядок
1.3. Слабый порядок
1.4. Строгий порядок
2. Классификация рефлексивных отношений
2.1. Отношения квазипорядка
2.2. Отношения нестрогого частичного порядка
2.3. Отношения нестрого упорядочения
2.4. Нестрогий качественный порядок
2.5. Нестрогий слабый порядок
2.6. Нестрогий порядок
Доминированием (строгим упорядочением) называется антисимметричное отношение, обладающее свойством антирефлексивности (9).
То есть доминированием является любое асимметричное отношение.
Говорят, что х доминирует у, если х в каком либо смысле превосходит у. Так х может быть командой, победившей команду у, лицом, являющимся родителем лица у и т.д.
1. Пересечение отношений доминирования остается отношением доминирования.
2. Граф отношения доминирования не содержит ни петель, ни колец , но может содержать циклы большей длины, чем 2.
3. Важнейшим видом отношений доминирования являются ациклические отношения.
4. Например, ациклическими отношениями являются строгий порядок и его обобщения (слабый порядок, качественный порядок).
5. Двойственными к отношениям доминирования являются отношения нестрогого упорядочения.
Качественный порядок является транзитивным отношением доминирования.
Качественным порядком (10) называется отношение, имеющее свойства антирефлексивности, асимметричности и транзитивности.
Свойство асимметричности можно исключить из определения качественного порядка, так как его выполнение является следствием выполнения свойств транзитивности и антирефлексивности.
1. Инверсия качественного порядка остается качественным порядком.
2. Пересечение качественных порядков является отношением качественного порядка.
3. Двойственное отношение обладает свойствами полносвязности и негатранзитивности, поэтому является отношением нестрогого качественного порядка.
4. Из качественного порядка может быть получен нестрогий частичный порядок путем объединения качественного порядка с диагональю.
Слабым порядком называется любое асимметричное негатранзитивное отношение (11).
Другими словами, отношение слабого порядка является частным случаем отношения доминирования, при котором дополнительно требуется негатранзитивность.
Бинарное отношение "быть студентом более старшего курса" на множестве студентов некоторого факультета.
1. Слабый порядок является транзитивным отношением (так как из выполнения свойств асимметричности и негатранзитивности следует выполнение свойства транзитивности).
2. Слабый порядок является двойственным к отношению нестрогого слабого порядка.
3. Если есть хотя бы одна какая-либо связь, то никакой из вариантов не может быть совсем изолирован от других.
4. Слабый порядок можно представить в виде множества частично упорядоченных слоев, каждый из которых содержит только изолированные друг от друга варианты.
5. Из каждого варианта нижних слоев обязательно существует дуга ко всем вариантам вышележащих слоев.
Строгим порядком (строгим предпочтением, сильным порядком, строгим линейным порядком) называется антирефлексивное, транзитивное, слабосвязное бинарное отношение (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. Таким образом, отношение нестрогого порядка можно представить как результат объединения диагонали и строгого порядка, порожденных исходным отношением.