Классификация бинарных отношений

План лекции №14 Классификация бинарных отношений

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).

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

Нестрогим порядком называется антисимметричное нестрогое упорядочение.

3 Элементарные конструкции - лекция, которая пользуется популярностью у тех, кто читал эту лекцию.

Свойства отношений нестрогого линейного порядка

1. Симметричная часть нестрогого порядка является диагональю.
2. Асимметричная часть R^ас нестрогого порядка транзитивна и слабосвязна, поэтому является отношением строгого порядка.
3. Двойственное отношение обладает свойствами асимметричности, негатранзитивности и слабосвязности поэтому является отношением строгого порядка. Кроме того оно совпадает с R^ас.
4. Таким образом, отношение нестрогого порядка можно представить как результат объединения диагонали и строгого порядка, порожденных исходным отношением.

Двойственность отношений строгого и нестрогого порядка

Обзор свойств различных видов отношений