Свойства бинарных отношений. Специальные бинарные отношения

Определение 12. Бинарное отношение r на множестве Х называется рефлексивным, если для любого элемента хÎХ выполняется хr х.

Определение13. Бинарное отношение r на множестве X, заданное матрицей смежности, в которой все элементы главной диагонали − единицы, а на остальных местах стоят нули, называется диагональным.

Определение 14. Бинарное отношение r на множестве Х называется симметричным, если для любых х, уÎХ из хr у следует уr х.

Матрица смежности симметричного отношения симметрична относительно главной диагонали: .

Определение 15. Отношение называется антирефлексивным, если ни для одного элемента аÎX не выполняется а а.

Главная диагональ его матрицы смежности содержит только нули.

Определение 16. Бинарное отношение r на множестве Х называется транзитивным, если для любых х, у, zÎХ из хrу и уr z следует хr z.

Пример 6.

Отношения: “равенство”, £, “жить в одном городе” являются транзитивными, а отношение “быть сыном” не транзитивно.

Определение 17. Бинарное отношение, которое одновременно рефлексивно, симметрично и транзитивно отношение на множестве Х называется отношением эквивалентности на множестве Х.

Пример7.

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

2. Отношение подобия на множестве треугольников есть отношение эквивалентности.

3. Отношение «строго меньше» на множестве действительных чисел не рефлексивно, не симметрично и транзитивно на этом множестве.

4. Отношение перпендикулярности прямых не рефлексивно, симметрично, не транзитивно.

Пусть r - отношение эквивалентности на множестве Х.

Определение 18. Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов yÎY, для которых хrу. Класс эквивалентности, порожденный элементом х, обозначается через [x]:

Определение 19. Бинарное отношение r на множестве Х называется антисимметричным, если для любых х, уÎХ из хr у и уr х следует, что х=у.

Определение 20. Бинарное отношение, которое одновременно рефлексивно, антисимметрично и транзитивно называется отношением частичного порядка.

Пример7.

1. Отношение «х £ у» на множестве действительных чисел − отношение частичного порядка.

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

Определение 21.Множество с заданным на нем отношениемчастичного порядка называется частично упорядоченным. Если при этом любые два элемента находятся в отношении, то такое множество называется линейно упорядоченным.

Элементы, находящиеся в отношении частичного порядка называются сравнимыми.

Определение 22. Бинарное отношение называется отношением строгого порядка, если оно одновременно антирефлексивно, антисимметрично и транзитивно.

Пример 8.

Приведем некоторые примеры.

1. Множество действительных чисел линейно упорядочено относительно отношений , .

2. Отношения < и > на множестве действительных чисел являются отношениями строгого порядка.

3. Отношение включения Í на системе подмножеств множества М задает частичный порядок, причем все подмножества множества М линейно упорядочено относительно отношения Í.

4. Отношение включения Ì на системе подмножеств множества М задает строгий порядок.

5. Множества {1, 2}, {1, 2, 3} сравнимы относительно отношения Ì −{1, 2}Ì{1, 2, 3}, a множества {1, 2} и {1, 3, 4} не сравнимы.

6. Отношения подчиненности на предприятии задает строгий частичный порядок. В нем несравнимыми будут сотрудники разных отделов.

7. Пусть порядок букв конечного алфавита А зафиксирован, т. е. всегда один и тот же. Тогда этот порядок определяет линейное упорядочение букв, которое назовем отношением предшествования и обозначим через í. Если предшествует в алфавите, то это записывается следующим образом: í . На основе отношения предшествования букв строится отношение предшествования слов. Это отношение задает линейное упорядочение множества всех конечных слов в алфавите А, которое называется лексикографическим упорядочением слов. Примером такого упорядочения является расположение слов в словаре.

8. Если рассматривать числа в позиционных системах счисления (например десятичной), как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с обычным упорядочением чисел, при этом предполагается, что все сравниваемые числа имеют одинаковое число разрядов (такое дополнение разрядами можно провести искусственно):

20 < 1073;

0020 1073.