Федоров В.Н. - Введение в теорию множеств (1023557), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

1) R –рефлексивно, если имеет место aRа для любого (например, отношение "жить в одном городе" – рефлексивно);

2) R – антирефлексивно, если ни для какого не выполняется aRа (например, отношение "быть сыном" – антирефлексивно);

3) R – симметрично, если aRb влечет bRa (например, отношение "работать на одной фирме" – симметрично);

4
) R – антисимметрично, если aRb и bRа влекут а = b, т.е. ни для каких различающихся элементов а и b (а b) не выполняется одновременно aRb и bRа (например, отношение "быть сыном" – антисимметрично); антисимметричное отношение является и антирефлексивным;

Рисунок 3.3

5) R – транзитивно, если aRb и bRc влекут aRc (например, отношения "быть больше", "быть моложе" – транзитивны).

6) Отношение называется нулевым, если оно не выполняется ни для какой пары элементов множества. Пример: имеется множество М = {1, 2, 3, 4, 5}. Пытаемся применить для этого множества отношение “быть равным (=)”. Это отношение не выполняется ни для какой пары элементов, следовательно, оно для данного множества нулевое.

7) Универсальным отношением называется такое, которое выполняется для любой пары элементов множества. Для множества примера предыдущего пункта отношение “быть не равным ( )” является универсальным.

Пример 1. Какими признаками характеризуется матрица отношения R, если R соответственно: рефлексивно, антирефлексивно, симметрично, антисимметрично, транзитивно.

• Пусть R задано на М, .

1) R рефлексивно, если для любого имеет место aRa, т.е. оно выполняется для всех пар (а, а), . В матрице этим парам соответствуют элементы с_ii. Такие элементы составляют главную диагональ матрицы. Следовательно, главная диагональ матрицы рефлексивного отношения содержит только единицы.

2) R антирефлексивно, если ни для какого не выполняется aRа. Из этого следует, что главная диагональ матрицы антирефлексивного отношения должна содержать только нули.

3) R симметрично, если для пары из аRb следует bRa, т.е. для любой пары отношение R выполняется в обе стороны либо не выполняется вообще. Таким образом, если в матрице единица стоит на пересечении i–ой строки и j–ого столбца, т.е. c_ij = 1, то она должна стоять и на пересечении j–ой строки и i–ого столбца, т.е. сji = 1, и наоборот, если c_ji=1, то c_ij = 1. Таким образом, в матрице симметричного отношения c_ji=c_ij, т.е. матрица симметрична относительно главной диагонали.

4) R антисимметрично, если из aRb и bRа следует а = b. Это означает, что в соответствующей матрице ни для каких не выполняется c_ji=c_ij= 1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали.

5) R транзитивно, если для любых а, b, с из aRb и bRс следует aRc. В матрице такого отношения должно выполняться следующее условие:

если в i–ой строке стоит единица, например в j–ой координате (столбце) строки, т.е. с_ij = 1, то всем единицам в j–й строке (пусть этим единицам соответствуют k–е координаты такие, что с_jk = 1) должны соответствовать единицы в i–й строке в тех же k–х координатах, т.е. с_ikj = 1 (и, может быть, еще и в других координатах).

Это условие иллюстрируется на рис. 3.4, где кружком выделена единица c_ij = 1, для которой производится проверка условия, а стрелками показана последовательность проверки данного условия.

В матрице транзитивного отношения это условие должно выполняться для любых таких, что с_ij, = 1. И наоборот, если в матрице R имеется хотя бы одна единица с_ij = 1, для которой данное условие не выполняется, то R не транзитивно.

Пример 2. Пусть бинарное отношение R на М задано в виде графа, состоящего из узлов и стрелок так, что узлам взаимно однозначно соответствуют элементы множества М, а стрелкам, соединяющим пару а и b в направлении от а к b, — наличие отношения aRb. Определить особенности графа в зависимости от характера свойств отношения R.

Р
исунок 3.4

• 1) Отношение рефлексивно, если aRa для любых . Соответствующий граф рефлексивного отношения должен содержать петли у всех вершин (т.е. стрелки, начинающиеся и заканчивающиеся в одной вершине).

2) Отношение R антирефлексивно, если ни для каких не выполняется aRa. Граф антирефлексивного отношения не должен содержать ни одной петли.

3) Отношение R симметрично, если из aRb следует bRа. В графе симметричного отношения для каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая эти узлы в обратном направлении.

4) Отношение R антисимметрично, если из aRb и bRa следует а = b. В графе антисимметричного отношения не существует двух различных узлов, связанных парой (разнонаправленных) стрелок.

5) Отношение R транзитивно, если из aRb и bRc следует aRc. В графе транзитивного отношения для любых двух стрелок таких, что одна направлена от а к b, а другая – от b к с, существует стрелка, соединяющая а и с в направлении от а к с.

3.3. Эквивалентность и порядок

Эквивалентность и порядок – это основные виды отношений.

Отношением эквивалентности (или просто эквивалентностью) называют бинарное отношение на множестве, если оно

• рефлексивно,

• симметрично,

• транзитивно.

Например, отношение "жить в одном городе" на множестве людей – эквивалентность.

Отношение эквивалентности обозначается или a ~ b.

Для отдельных частных случаев используют такие знаки эквивалентности

= – равенство,

|| – параллельность,

– логическая эквивалентность.

Отношение эквивалентности имеет важную особенность: эквивалентность R разбивает множество М, на котором оно задано, на непересекающиеся подмножества так, что элементы одного и того же подмножества находятся в отношении R, а между элементами из разных подмножеств отношение R отсутствует. В таком случае говорят, что отношение R задает разбиение на множестве М, или систему классов эквивалентности по отношению R. Мощность этой системы называется индексом разбиения (обозначим его I). В то же время любое разбиение множества М на классы определяет некоторое отношение эквивалентности, а именно отношение "входить в один и тот же класс данного разбиения".

Для классов эквивалентности справедливо

Для любых двух классов эквивалентности

Если для всех

Отношением нестрогого порядка (или нестрогим порядком) называют бинарное отношение на множестве, если оно рефлексивно, антисимметрично, транзитивно, и отношением строго порядка (строгим порядком), если оно антирефлексивно, антисимметрично, транзитивно. Оба эти отношения называются отношениями порядка. Например, отношения "быть не старше" на множестве людей, "быть не больше" на множестве натуральных чисел – нестрогий порядок. Отношения "быть моложе", "быть прямым потомком" на множестве людей – строгий порядок.

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

Множество М, на котором задано отношение порядка, может быть:

а) полностью упорядоченным множеством, если любые два элемента из М сравнимы по отношению порядка. В таком случае говорят, что отношение R задает полный порядок на множестве М. Например, отношение "быть не старше" задает полный порядок на множестве людей;

б) частично упорядоченным множеством – в противном случае. При этом говорят, что отношение R задает на множестве М частичный порядок. Например, отношение "быть начальником" задает на множестве сотрудников организации частичный порядок, так как, например, для пары сотрудников одного отдела данное отношение не выполняется: они не сравнимы по данному отношению.

Пример 1. Проиллюстрировать диаграммами Эйлера–Венна следующие разбиения множества U:

а) {А, };

б)

в)

Указанные разбиения изображены на рис. 3.5.

Р
исунок 3.5

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

Так как отношения на М задаются подмножествами (или , если М₁ = М₂ = М), то для них определимы те же операции, что и над множествами (см. п. 1.2):

1. Объединение :

или .

2. Пересечение :

и .

3. Разность R₁ \ R₂:

R₁ \ R₂ = и .

4. Дополнение :

=U\R, где U = M₁ х М₂ (или U = M²).

Кроме того, определяют другие операции над отношениями, в том числе:

5. Обратное отношение R^–1:

R^–1 = .

aR^–1b тогда и только тогда, когда bRa:

Например, если R – "быть моложе", то R^–1 – "быть старше", если R — "быть сыном", то R^–1 – "быть отцом (или матерью)".

6. Составное отношение (композиция) R₁○R₂ (применяют и такое обозначение R₁R₂)

Характеристики

Список файлов книги