Материал: Ответы на экзаменационные вопросы по дискретной математике

Свойства бинарных отношений на множестве

Рефлексивность. Если каждый элемент множества находится в отношении с самим собой: — то бинарное отношение называется рефлексивным. Если же ни один элемент множества не находится в отношении с самим собой: — то бинарное отношение называется антирефлексивным. Иначе нерефлексивным.

Пример. Отношение сравнимости рефлексивно при любом и на любом множестве целых чисел. Отношение строгого неравенства () антирефлексивно.

Симметричность. Если вместе с каждой парой в отношении входит симметричная пара : — то бинарное отношение называется симметричным. Если же ни одна пара не входит в отношение вместе с симметричной парой : — то бинарное отношение называется асимметричным (полная противоположность симметричному). Если ни одна пара, состоящая из разных элементов, не входит в отношение вместе с симметричной ей: — то бинарное отношение называется антисимметричным. Иначе несимметричным.

Бинарное отношение асимметрично тогда и только тогда, когда оно антисимметрично и при этом антирефлексивно.

Пример. Отношение сравнимости симметрично при любом натуральном модуле и на любом множестве целых чисел. Отношение строгого неравенства () асимметрично на множестве вещественных чисел. Отношение нестрогого неравенства () на множестве вещественных чисел антисимметрично.

Транзитивность. Если для любых трёх элементов , таких, что и входят в отношение , то в входит пара : .

1. Явное перечисление пар, определяющих бинарное отношение.

Пример. .

2. Задание процедуры проверки.

Пример. .

3. Задание матрицей смежности.

Диагональ матрицы смежности рефлексивного отношения состоит из единиц, антирефлексивного — из нулей.

Матрица смежности симметричного отношения симметрична относительно диагонали ().

Можно доказать, что для того, чтобы отношение было транзитивным, необходимо и достаточно, чтобы его матрица смежности удовлетворяла неравенству .

Пример. . Пусть : если , то , иначе .

В данном случае приведена матрица смежности отношения сравнимости по модулю 3 на множестве .

Как можно понять, отношение рефлексивно, симметрично и транзитивно.

4. Задание графом.

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

Граф рефлексивного отношения имеет петли в каждой вершине.

Граф симметричного отношения вместе с ребром, соединяющим с , содержит ребро, соединяющее с .

Граф транзитивного отношения обладает следующим свойством: если из вершины , двигаясь вдоль рёбер, можно попасть в вершину , то в графе должно быть ребро, непосредственно соединяющее с .

Пример. Отношение сравнимости транзитивно при любом и на любом множестве целых чисел. Отношение строгого неравенства () транзитивно на любом подмножестве вещественных чисел. Отношение на множестве вещественных чисел не является транзитивным: !

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

Пример. Граф для отношения сравнимости по модулю 3 на множестве состоит из трёх компонент связности: , и .

Рисунок 16

Петли изображены в виде небольших окружностей.

Ориентированные рёбра заменены неориентированными рёбрами, так как отношение симметрично.

5. Задание списком смежностей.

Для каждого элемента множества перечисляются те элементы, которые находятся с ним в данном отношении.

Пример. Список смежности для отношения сравнимости по модулю 3 (см. пред.):

Функция

Функция (отображение) — бинарное отношение , обладающее следующим свойством: если и , то . Это означает, что если определен первый элемент упорядоченной пары, то второй элемент определяется единственным образом. Это свойство функции называют однозначностью. Обозначают функцию или , что означает, что функция задана на множестве со значениями во множестве и осуществляет отображение множества во множество (или устанавливает соответствие между множествами и ). Если , то элемент из множества называют аргументом функции, или прообразом элемента , а элемент — значением функции, или образом элемента . В силу условия однозначности у всякого прообраза имеется единственный образ.

Аргументы функции — элементы произвольной природы, в частности, они могут быть упорядоченными последовательностями . В этом случае функцию называют функцией переменных или .

Область определения функции — множество её прообразов: . Если область определения совпадает с (), то функция называется тотальной, в противном случае — частично определенной.

Область значений функции — множество её образов: . Если область значений совпадает с множеством (), то функция называется сюръективной.

Инъективное отображение. Пусть . Функция инъективна, если (или, иначе, из и следует, что ). То есть если у каждого образа () есть не более одного прообраза ().

Сюръективное отображение. Пусть . Функция сюръективна, если . То есть если у каждого образа () есть хотя бы один прообраз (). Говорят, что такая функция отображает множество на множество .