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

Пример. .

Прямое (декартово) произведение () — множество всех упорядоченных пар, где первый элемент принадлежит множеству , а второй множеству : .

Прямое произведение множеств () — множество всевозможных упорядоченных наборов из элементов , где . То есть Каждый такой набор элементов называется кортежем. Произведение множества самого на себя называется квадратом множества и обозначается . Аналогично -ая степень : .

Пример. .

Пример. .

Операция дистрибутивна (), но не коммутативна () и не ассоциативна ().

Диаграммы Эйлера — Венна. На диаграммах Эйлера — Венна множество изображается прямоугольником, а множества — областями внутри прямоугольника. На следующем рисунке проиллюстрированы введённые определения операций над множествами.

Рисунок 13

Алгебра множеств — это пример булевой алгебры, поэтому все указанные далее (см. следующую таблицу) свойства операций следуют из свойств дизъюнкции, конъюнкции и отрицания.

Таблица 2

Бинарное отношение

Упорядоченная пара — совокупность, состоящая из двух элементов и , расположенных в определенном порядке. Две пары и равны только тогда, когда . В частности, и равны, если .

Упорядоченная совокупность — совокупность, состоящая из элементов, расположенных в определенном порядке.

Бинарное (двуместное) отношение из множества в множество — любое подмножество прямого произведения . Если , то подмножество множества называется бинарным отношением на множестве . Если пара принадлежит : , то говорят, что элемент находится в отношении с элементом , и записывают . Элементы и — координаты (или компоненты) отношения .

Пример. Множество есть множество вещественных чисел (множество точек вещественной прямой), — множество точек координатной плоскости. Отношение строгого неравенства определяется множеством пар . Если на плоскости выбрана декартова система координат, то отношение есть множество точек, у которых абсцисса () меньше ординаты (), то есть множество точек, лежащих выше биссектрисы 1-го и 3-го координатных углов.

Пример. Введём отношение сравнимости : сравнимо с по модулю (mod. ) тогда и только тогда, когда и имеют одинаковые остатки от деления на (что записывается как ). Рассмотрим отношение сравнимости для случая (то есть ) на множестве :

Область определения бинарного отношения — множество :

Область значений бинарного отношения — множество :

Пример. .

Для бинарных отношений обычным образом определены операции объединения, пересечения и др.

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

Пример. Графики и представлены на следующем рисунке.

Рисунок 14

Так как бинарные отношения — это множества, их можно объединять и пересекать.

Графики и представлены на следующем рисунке.

Рисунок 15

Обратное отношение для : . Причём .

Композиция отношений ( и ):

*

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

* — некоторые математики композицию обозначают иначе ( и меняются местами):

К общему соглашению насчёт обозначения композиции математики не пришли, поэтому на деле важно заранее обозначить композицию так, как будете её использовать в дальнейшем.

Пример.