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

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

4) в виде матрицы: пусть A={a1, a2, …, an} и B={b1, b2, …, bm}, r – отношение на A´B. Матричным представлением r называется матрица M=[mij] размера n´m, определенная соотношениями

Бинарное отношение называется отношением эквивалентности, если отвечает условиям:

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

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

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

Если   связан с  , будем писать   и говорить, что   эквивалентен  .

Определение

Пусть   – отношение эквивалентности, тогда подмножество  называется классом эквивалентности.

Теорема

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

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

Имеет интерпретации: «элемент х предпочтительнее у», «х больше у», «х предшествует у», «х включает в себя у».

Множество М с заданным на нем отношением строгого порядка R называют упорядоченным множеством.

Отношение R на множество М называется отношением нестрогого порядка, если оно может быть представлено в виде: , где R1- строгий порядок на М, а Е– диагональное отношение.

Вопрос 18. Понятие соответствия между двумя множествами. Способы задания соответствий. Соответствие обратное данному. Взаимно однозначные соответствия. Равномощные множества.

Р  Х  У

Соответствие между элементами множеств Х и У – это любое подмножество декартова произведения множества Х на множество У.

Пример.

Пусть даны множества Х=1, 2, 3 и У=2, 3, 4, 5. Найдём декартово произведение этих множеств ХУ=(1;2), (1;3), (1;4), (1;5), (2;2), (2;3), (2;4), (2;5), (3;2), (3;3), (3;4), (3;5).

Соответствие Р=(1;2), (1;3), (1;4), (1;5), (2;3), (2;4), (2;5), (3;4), (3;5) или Р: «ху», где хХ, уУ.

Соответствие К= (2;2), (3;3) или К: «х=у».

Соответствие Т=(1;2), (2;4) или Т: «2х=у».

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

• Перечисление пар: В=(1;3), (2;4), (3;5).

• Характеристическое свойство или формула: В: «х+2=у».

• Графический способ: граф

График:

Область определения соответствия – это всё множество первых компонентов пар, связанных данным соответствием. Область определения соответствия – подмножество множества Х. Пример. ООВ=1, 2, 3, где ООВХ.

Область значение соответствия – это всё множество вторых компонентов пар, связанных данным соответствием. Область значения соответствия – подмножество множества У. Пример. ОЗВ=3, 4, 5, где ОЗВУ.