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

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

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

Оба типа таких отношений называются отношениями порядка.

Элементы a и b сравнимы по отношению порядка R, если выполняется aRb или bRa.

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

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

Лексико-графический порядок.

Пусть в списке букв конечного алфавита А порядок букв зафиксирован, т. е. всегда один и тот же, как, например, в русском и латинском алфавите. Тогда этот список определяет полное упорядочение букв, которое назовем отношением предшествования и обозначим “ ”: , если предшествует в списке букв).

На основе отношения предшествования букв, строится отношение предшествования слов, определяемое следующим образом:

Пусть даны слова и .

Тогда, тогда и только тогда, когда

1)  , где (  слова возможно непустые,  буквы);

2)  , где  непустое слово.

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

Упражнения

1. Определите свойства отношений и их вид, где М – множество натуральных чисел:

 ”быть меньше”;  ”быть больше или равно”;  ”иметь общий делитель, отличный от 1”;  ”быть делителем”;  ”иметь общий остаток от деления на 3”. Задать эти отношения различными способами, если _.

_{Какие их этих отношений являются отношениями порядка, отношениями эквивалентности?}

2. Определите свойства отношений и их вид, где  множество прямых на плоскости (см. рис 1):

 ”быть параллельной”;

 ”быть перпендикулярной”;

 ”пересекаться” (иметь одну и только одну общую точку)

Задать эти отношения различными способами, если

Рис. 1

3. Определите свойства отношений и их вид, где М – множество элементов структуры, изображённой на рисунке 2:

 ”быть непосредственно связанным с …”;

 ”быть начальником”;

 ”быть непосредственным начальником”;

 ”быть подчинённым”;

 ”быть непосредственно подчинённым”;

 ”быть предком”;

 ”быть потомком”.

Задать эти отношения различными способами.

Рис. 2

4. Определите свойства отношений и их вид, где М – множество натуральных чисел:

 ”быть меньше”;  ”быть больше или равно”;  ”иметь общий делитель, отличный от 1”;  ”быть делителем”;  ”иметь общий остаток от деления на 3”. Задать эти отношения различными способами, если _.

_{Какие их этих отношений являются отношениями порядка, отношениями эквивалентности?}

5. Определите свойства отношений и их вид, где М – множество людей:

 ”любить”;  ”быть моложе”;  ”быть сыном”;

 ”жить в одном городе”;  ”быть соседом (жить за стенкой)”.

6. Определите свойства отношений и их вид, где М – множество точек плоскости:

 ”иметь одинаковое расстояние от начала координат”;  ”лежать на одинаковом расстоянии от оси ОХ”;  ”быть симметричным относительно оси ОУ”.

Сделать рисунок, задать 6 точек, на их примере построить матрицу бинарного отношения. Определить будут ли эти отношения отношениями эквивалентности. Если да, как разбивается плоскость на классы и каков индекс разбиения.