Элементы теории отношений

Отношения устанавливают связь между объектами по какому-то правилу или закону.

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

Например, ; X = {1,2,3} – множество объектов

= {<1,2>,<1,3>,<2,3>,<1,1>,<2,2>,<3,3>}

Любое бинарное отношение – подмножество декартова произведения некоторых двух множеств. Первый элемент каждой пары бинарного отношения называется первой координатой, второй элемент - второй координатой.

Множество всех первых координат отношения – область определения. Обозначается D₀. В нашем примере = { 1,2,3}

Множество всех вторых координат отношения – область значения. Обозначается D_з. D_з = {1,2,3}

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

(1) = {1,2,3};

(2) = {2,3};

(3) = {3}.

Способы задания отношений:

1. Аналитические (3 штуки).

2. Матричный.

3. Графический.

1. Аналитические:

• перечислением:

= {<1,1>,<1,2>,<2,3>};

• с помощью определяющего свойства: X, = {<x_i,x_j> | P(x_i,x_j)};

• с помощью фактор-множества: это матрица , где первая строка - все первые координаты отношения, а вторая - сечение отношения по этим координатам.

Пример: = {<1,1>,<1,2>,<2,3>}

1 2

{1,2} {3} - фактор – множество

2. Матричный способ.

Строки матрицы – первые координаты, столбцы – вторые координаты. На пересечении строки i и столбца j ставится 1, если пара <x_i,x_j>Î

= {<1,2>,<1,3>,<2,3>}

2 3

1 1 1

2 1

3. Графический способ.

Первые и вторые координаты - точки на плоскости. Строится ориентированная связь i j, если пара <x_i,x_j>Î

Операции над отношениями:

Так как все отношения есть множества, то все операции над множествами справедливы и для отношений.

₁È ₂; ₁∩ ₂; ₁\ ₂; ₁÷ ₂; где = (D_o D_з)\

Дополнительно определены две специальные операции:

1) обращения (симметризации): - меняем местами первые и вторые координаты;

2) композиции: ₃= ₁∙ ₂

Пусть X,Y,Z – три множества.

₁ X Y

₂ Y Z

Отношение ₃= ₁∙ ₂ называется композицией ₁ и ₂ и состоит из пар <x,z>, для которых <x,y> , <y,z> .

Пример: ₁ = {<x₁,y₁>,<x₁,y₂>,<x₂,y₂>,<x₃,y₂>}

₂ = {<y₁,z₁>,<y₁,z₂>,<y₂,z₁>}

₃ = {<x₁,z₁>,<x₂,z₁>,<x₃,z₁>,<x₁,z₂>}

Свойства отношений:

1. Рефлексивность;

2. Симметричность;

3. Транзитивность.

Рефлексивность:

Отношение на множестве X называется рефлексивным, если " x_i Î X справедливо < x_i, x_i > Î .

Пример: X = {1, 2, 3}

= {<1,1>,<2,2>,<3,3>,<1,2>,<1,3>} – рефлексивно.

Отношение антирефлексивно на множестве X, если " x_i Î X справедливо

<x_i, x_i> Ï .

Пример: X = {1, 2, 3}

= {<1,2>,<1,3>,<2,1>}

Отношение на множестве X называется нерефлексивным, если для некоторых элементов x_i Î X рефлексивность выполняется, а для некоторых – нет.

Пример: = {<1,1>,<2,3>,<1,2>}

Симметричность:

Отношение называется симметричным, если " <x_i, x_j> Î пара <x_j, x_i> Î тоже.

Пример: = {<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}

Отношение антисимметрично, если " <x_i, x_j> Î пара <x_j, x_i> Ï .

Пример: = {<1,1>,<1,2>,<2,3>} – несмотря на <1,1>!

Отношение несимметрично, если для некоторых пар симметричность выполняется, а для некоторых – нет.

Транзитивность:

Отношение транзитивно, если для всякой пары <x_i, x_j> Î и пары <x_j, x_z> Î пара <x_i, x_z> Î тоже, либо для пары <x_i, x_j> отношения пары <x_j, ?> нет вообще.

Пример: = {<1,2>,<2,3>,<1,3>} – транзитивно.

Специальные типы бинарных отношений:

1. Отношение эквивалентности (рефлексивно, симметрично, транзитивно);

2. Отношение порядка (рефлексивно, антисимметрично, транзитивно);

(≤) X = {1,2,3}

= {<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>}

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

(<) X = {1,2,3}

= {<1,2>,<1,3>,<2,3>}

Важнейший признак отношения эквивалентности – оно разбивает элементы множества, на котором берется отношение, на взаимнонепересекающиеся классы, которые называются классами эквивалентности.

Пример:

X = {2,3,4,8,9,27}, – иметь общие знаменатели ≠ 1

= {<2,2>,<3,3>,<4,4>,<8,8>,<9,9>,<27,27>,<2,4>,<4,2>,<2,8>,<8,2>,<4,8>,

<8,4>,<3,9>,<9,3>,<3,27>,<27,3>,<9,27>,<27,9>}

A₁={2,4,8}; A₂={3,9,27};

Дата добавления: 2014-11-08; просмотров: 285; Нарушение авторских прав

Мы поможем в написании ваших работ!