Отношения эквивалентности и порядка.

- Отношением эквивалентности называют бинарное отношение на множестве, если оно рефлексивно, симметрично, транзитивно.

Пример:

Следующие отношения являются отношениями эквивалентности:

“ жить в одном городе ” на множестве людей;

“ находится на одинаковом расстоянии от начала координат ” на множестве точек действительной плоскости R×R.

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

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

Пример:

“ быть не больше ” на множестве натуральных чисел – это отношение нестрогого порядка;

“ быть не старше ” на множестве людей – это отношение нестрогого порядка;

“ быть моложе ”, “ быть прямым потомком ” на множестве людей – отношение строгого порядка.

3.4 Правила построения матриц отношений , R^-1, R⁽²⁾, R⁰, R^*.

1. Матрица дополнения – в матрице исходного отношения R заменяют единицы нулями, а нули – единицами.

2. Матрица обратного отношения R^-1 – для ее построения проставляют в ней единицы, симметричные относительно главной диагонали, соответствующие единицам исходной матрицы.

3. Матрица составного отношения R⁽²⁾.

… a_k1... a_j... a_k2

.

.

а_i 1 1

.

.

.

а_j 1 1

рис. 3.1

Для каждой единицы исходной матрицы отношения R, принадлежащей i-ой строке, например единицы в j-ой компоненте, в i-ой строке вычисляемой матрицы проставить единицы в тех k-ых компонентах, в которых имеются единицы в j-ой строке исходной матрицы (см. рис. 3.1).

4. Матрица транзитивного замыкания R⁰ нетранзитивного отношения R– для ее построения проделывается ряд итераций:

1) в матрицу составного отношения R⁽²⁾ заносят все единицы исходной матрицы, которые отсутствуют в R⁽²⁾.

2) полученную матрицу принимают за исходную и повторяют для нее процедуру (1). Выполняют это до тех пор, пока матрица не перестанет изменяться.

5. Матрица рефлексивного замыкания R^* - для ее построения, построить матрицу транзитивного замыкания, а затем в полученной матрице заменить нули на главной диагонали на единицы.

Пример:

Каковы свойства отношения R, заданного матрицей на рис. 3.2.

рис.3.2

Построить , R^-1, R⁽²⁾, R⁰, R^*.

Решение:

Отношение R = {(a, b),(b, a),(c, b)}

- антирефлексивно, т.к. на главной диагонали только нули.

- несимметрично, т.к. c R b есть, но нет b R c.

- не антисимметрично, т.к. есть симметричная пара (a, b) и (b, a).

- не транзитивно, т.к. есть c R b и b R a, но нет c R a.

						R-1						R(2)						R0						R*
	1	0	1				0	1	0				1	0	0				1	1	0				1	1	0
	0	1	1				1	0	1				0	1	0				1	1	0				1	1	0
	1	0	1				0	0	0				1	0	0				1	1	0				1	1	1

Пример:

На множестве чисел М={1, 2, 3, 4, 5, 6}определено отношение R: “отличаться на 1 ”. Построить матрицы R, , R^-1, R⁽²⁾, R⁰, R^*.