Лекция № 2.. Основные вопросы, рассматриваемые на лекции:

Тема: БИНАРНЫЕ ОТНОШЕНИЯ

Основные вопросы, рассматриваемые на лекции:

1. Декартово произведение множеств.

2. Бинарные отношения.

3. Обратное отношение. Композиция отношений.

4. Отношение эквивалентности и фактор-множество.

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

Краткое содержание лекционного материала

1. Декартово произведение множеств. Упорядоченная пара – это объект, в котором указаны первый и второй элементы (соответственно, и ).

Декартовым произведением двух множеств и называется множество всех упорядоченных пар с первым элементом из множества и со вторым элементом из множества :

.

Если , то декартово произведение представляется на координатной плоскости: пара изображается точкой с координатами и .

2. Бинарные отношения. Любое подмножество декартова произведения называется (бинарным) отношением на множестве M.

Пусть и . Тогда пишут .

Приведем основные свойства отношения P, заданного на множестве M:

рефлексивность: для всех x Î M выполняется xPx .

антирефлексивность: для всех x Î M неверно, что xPx .

симметричность: для всех x, y Î M из xPy следует, что yPx .

асимметричность: для всех x, y Î M из xPy следует неверно, что yPx .

антисимметричность: для всех x, y Î M из xPy и yPx следует, что x = y .

транзитивность: для всех x, y, z Î M из xPy и yPz следует, что xPz .

связность: для всех x, y Î M верно, что xPy, или yPz или x = y.

3. Обратное отношение. Композиция отношений. Над отношениями, заданными на множестве M, можно производить те же операции, что над множествами: объединение , пересечение , дополнение .

Отношение называется диагональю множества M.

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

Отношение называется композицией отношений и .

С помощью операций над отношениями можно охарактеризовать свойства отношений: отношение P на множестве M

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

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

симметрично тогда и только тогда, когда .

асимметрично тогда и только тогда, когда .

антисимметрично тогда и только тогда, когда .

транзитивно тогда и только тогда, когда .

связно тогда и только тогда, когда .

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

Пусть ~ есть эквивалентность на множестве M, а x Î M. Тогда множество [ x ]={ y | y ~ x } называется классом эквивалентности, порожденным элементом x.

Фактор-множество множества относительно эквивалентности ~ – это семейство всех классов эквивалентности: M /~={[ x ]| x Î M }.

Семейство множеств M_i, i Î I, называется разбиением M на классы, если:

1) для всех i Î I множество M_i непустое подмножество M: M_i ¹Æ, M_i Í M .

2) множества M_i попарно не пересекаются: M_i Ç M_j =Æ, где i ¹ j .

3) объединение всех M_i, i Î I, совпадает с множеством M.

Теорема 1. Пусть на множестве M задана эквивалентность ~. Тогда семейство всех классов эквивалентности [ x ], x Î M, есть разбиение M на классы.

Теорема 2. Пусть дано разбиение M на классы. Тогда отношение P на M, такое, что xPy Û x и y принадлежат одному классу есть эквивалентность.

Пример. Разбиение множества всех учеников школы на классы определяет эквивалентность ученики x и y учатся в одном классе.

5. Отношения порядка. Асимметричное и транзитивное отношение называется порядком. Если порядок является также рефлексивным (антирефлексивным), то называется нестрогим (строгим) порядком. Связный порядок называется линейным. Примеры строгих порядков: &lt ., &gt . на множестве R, Ì, É на множестве 2 ^M, где M – некоторое множество. Примеры нестрогих порядков: £, ³ на множестве R, Í, Ê на множестве 2 ^M. Порядки &lt ., &gt ., £, ³ являются линейными, а порядки Ì, É,Í, Ê – нелинейными. Отношение «x делится на y» является нелинейным нестрогим порядком на множестве N, но не на множестве Z. Лексикографический порядок (Расположение слов по алфавиту) является линейным строгим порядком на множество слов некоторого алфавита.