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

– определённая совокупность объектов. Объекты - элементы множества.
Примеры множеств
а) N

/ М., Энергоиздат, 1988.– 480с.

Новиков Ф. А. Дискретная математика

нуля ø =

.

обозначают .
Теорема. Для

не является счётным.
Док-во. (от противного)

1.4 Отношения
 Отношения - один из

Определение. Подмножество R называется n-местным отношением на множестве А. При этом говорят, что элементы a1, a2, ... ,an находятся в отношении R, если (a1, a2, ... , an) .

R.

- прямое произведение множеств.
Для n = 1 - одноместное отношение, для n = 2 - двухместное, для n = 3 – трехместное и т.д.
Одноместные (унарные) отношения – подмн-ва мн-ва А. Они отражают наличие какого-то признака R у элементов мн-ва A.
Пример унарного отношения
Подмн-во четных чисел Nчетн на мн-ве N.
Двухместные (бинарные) отношения используются для определения взаимосвязей пар элементов в множестве А.
Пример бинарного отношения
Отношение строгого неравенства (a > b) на мн-ве N.

4, 5}

1. Одноместное отношение: R - нечетные элементы А.

R= = {(1, 1); (2, 2); (3, 3); (4, 4); (5, 5)}.
3. Трехместное отношение: R - отношение суммы
R = {(a, b, c): a + b = c, a, b, c A}.

R+ = {(1, 1, 2); (1, 2, 3); (1, 3, 4); (1, 4, 5); (2, 1, 3);
(2, 2, 4); (2, 3, 5); (3, 1, 4); (3, 2, 5); (4, 1, 5)}.

Отношения могут быть заданы и на множествах разной природы: R Mn.

M1

M2

...

При этом элементы (a1, a2, ... , an), находящиеся в отношении R, принадлежат соответственно a1

M1, a2

M2, ... , an

Mn).

значений:

в) обратное отношение:


г) композицию (для отношений R1 и

выполняется.
2.Матрицей - бинарному отношению

Пример. Пусть А = {1, 2, 3}. Задать матрицей отношение: