dm_tema_1

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

Отношение эквивалентности обозначают x y.

Пример

На множестве целых чисел рассмотрим бинарное отношение сравнения по модулю натурального числа. Два целых числа x; y

сравнимы по модулю натурального числа p

x y ( mod p);

если совпадают остатки от деления этих чисел на p.

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

Другой пример отношение подобия фигур в геометрии, которое также является отношением эквивалентности.

Определение

Пусть x 2 A. Множество [x] = fy 2 Aj x yg называется классом эквивалентности.

Теорема

Классы эквивалентности образуют разбиение множества A.

Доказательство.

[

8x 2 A : x x ) x 2 [x] ) [x] = A;

x2A

8z 2 A : z 2 [x] \ [y] ) x z; z y ) x y ) [x] = [y]:

Теорема

Любое разбиение множества A порождает отношение эквивалентности на этом множестве.

Доказательство.

Пусть

[

A = Ai ; Ai \ Aj = ;; i 6= j:

i2I

Определим отношение

x y , x; y 2 Ai :

Выполняются все три свойства: рефлексивность, симметричность, транзитивность.

Определение

Åñëè R отношение эквивалентности на множестве A, то множество

классов эквивалентности называется фактормножеством и обозначается AjR.

Фактормножество является подмножеством булеана AjR 2A.

Определение

Отношение Rp называется замыканием отношения R относительно свойства p, åñëè:

1)Rp обладает свойством p;

2)R Rp;

3)Rp является подмножеством любого другого отношения, обладающего свойством p.

Теорема

Справедливы представления замыканий 1) Рефлексивное замыкание

Rr = R [ E

2) Симметричное замыкание

Rs = R [ R 1

3) Транзитивное замыкание

1

[

Rt = Ri

i=1

Доказательство. Докажем 3.

8x; y; z : xRt y; yRt z ) 9m; k : xRmy; yRk z ) xRm+k z ) xRt z:

Следовательно, Rt транзитивное отношение. Условие R Rt также выполняется, поскольку R = R1 Rt .

Пусть R0 транзитивно и R R0. Тогда

8x; y : xRt y ) 9m : xRmy )

9z1; z2; : : : ; zm 1 : xRz1; z1Rz2; : : : ; zm 1Ry )

xR0z1; z1R0z2; : : : ; zm 1R0y ) xR0y ) Rt R0:

Теорема

Пусть R A2 бинарное отношение на конечном множестве с n элементами. Транзитивное замыкание R равно

Справедливо включение Rn Rt . Покажем, что Rt Rn. Для этого достаточно показать, что Rm Rn ïðè m > n. Пусть xRmy, m > n.

Существует последовательность элементов

z = (z1; z2; : : : ; zm 1)

таких, что

xRz1; z1Rz2; : : : ; zm 1Ry:

В этой последовательности обязательно найдутся два одинаковых элемента zi = zj , j > i. Следовательно,

xRz1; : : : ; zi Rzj+1; : : : ; zm 1Ry:

Продолжая сокращать последовательность элементов z, придем к последовательности, длина которой k n 1 и, таким образом, xRk y.

Следовательно,

xRmy ) xRny ) Rm Rn:

Пусть R бинарное отношение на конечных множествах A è B. Матрица MR отношения R состоит из n = jAj строк и m = jBj столбцов.

Элементы MR принимают два значения: 0; 1. Такого рода матрицы называются логическими или булевыми.

Для булевых матриц определяются операции суммы и произведения с уч¼том булевых операций сложения и умножения

Для матриц бинарных отношений справедливы равенства:

1)MR1[R2 = MR1 + MR2

2)MR1 R2 = MR1 MR2

3)MRk = (MR )k

4)MR 1 = (MR )T

5)MRr = MR + ME

6)MRs = MR + (MR )T

7)MRt = Pni=1(MR )i