Материал: Дискретная математика теория и практика

Определение 1.22. Множество всех b B, соответствующих элементу

a A, называется образом элемента a в B при соответствии R и обозначается через R(а).

Определение 1.23. Множество всех a A, которым соответствует элемент b B, называется прообразом элемента b в A при соответствии R и обозначается через R-1(b).

Определение 1.24. Если C Dom R, то образом множества C при соот-

ветствии R называется объединение образов всех элементов множества C и обозначается через R(C).

Определение 1.25. Если D Im R, то прообразом множества D при со-

ответствии R называется объединение прообразов всех элементов множества D обозначается через R-1(D).

Пример 1.15. Рассмотрим соответствие S (см. рис. 1.8). Тогда S(a) = 2,

S(b) = {1, 2}, S-1(3) = {c, e}, S-1(4) = {d}. Если C = {a, c, d}, D = {1, 2, 3}, то S(C) = {2, 3, 4} и S-1 (D) = {a, b, c, e}.

Определение 1.26. Соответствие R называется инъективным (инъекци- ей), если прообразом любого элемента из Im R является единственный элемент из Dom R = A.

Определение 1.27. Соответствие R называется функциональным (или однозначным), если образом любого элемента из Dom R является единственный элемент из Im R.

Определение 1.28. Соответствие R между множествами A и B называется взаимно однозначным (биекцией), если оно всюду определено, сюръективно, функционально и инъективно.

Другими словами, соответствие между A и B является взаимно однозначным, если каждому элементу множества A сопоставляется единственный элемент множества B и каждый элемент множества B соответствует единственному элементу множества A.

Пример 1.16. На рис. 1.7 – 1.10 изображены графы соответствий R, S, P и Q. Соответствие S (см. рис. 1.8) не является инъективным, так как, например,

R −1 (3) ≠ 1 . Соответствие P (рис. 1.9) инъективно, так как ( b Im P) R −1 (b) = 1 .

Среди соответствий R, S, P и Q функциональными являются соответствия R (рис. 1.7), P, Q (рис. 1.10), и только Q – взаимно однозначное соответствие между A и B.

Утверждение 1.2. Если между конечными множествами A и B существует взаимно однозначное соответствие, то мощности этих множеств равны.

17

Доказательство. Предположим противное. Пусть A ≠ B . Тогда либо

A > B , либо A < B .

Если A > B , то в множестве A существуют по крайней мере два различ-

ных элемента, которым соответствует один и тот же элемент из множества В, так как соответствие всюду определено. Это означает, что соответствие не является инъективным, что противоречит условию утверждения.

Если A < B , то в множестве B существует по крайней мере два различных

элемента, соответствующих одному и тому же элементу из множества A, так как соответствие сюръективно. Следовательно, соответствие не является функциональным, что также противоречит условию утверждения.

Замечание 1.9. На основании утверждения 1.2 можно выполнить следующие действия:

1)установить равенство мощностей двух множеств, не вычисляя этих мощностей;

2)вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.

1.8.Задачи, связанные с определением мощности конечного множества

Теорема 1.1. Если A – конечное множество, то мощность его булеана P(A) равна 2 A .

Доказательство. Пусть A = n. Будем использовать математическую ин-

дукцию по n.

1. База индукции. Если n = 0, то A = и P(A) = { }. Следовательно,

P( A) = { } = 1 = 20 = 2 A .

2.Индуктивное предположение. Пусть для любого множества A мощности n < k теорема справедлива, то есть P( A) = 2 A = 2n .

3.Индукционный переход. Докажем справедливость теоремы для n = k. Рассмотрим A = {a1, a2, …, ak}, A = k. Положим A1 = {X P(A)| ak X} и

A2 = {Y P(A)| ak Y}. Имеем: P(A) = A1 A2 и A1 ∩ A2 = . Между элементами множеств A1 и A2 можно установить следующее взаимно однозначное соответ-

A2 = P({ a1, a2, …, ak-1}), то, по индукционному предположению, A1 = A2 = 2k −1 и P( A) = A1 + A2 = 2k −1 + 2k −1 = 2 2k −1 = 2k = 2 A . Следовательно, теорема верна для лю-

бых n.

Теорема 1.2. Пусть X1, X2, …, Xn (n ≥ 2) – конечные множества и

18

X1 = m1, X 2 = m2, …, X n = mn. Тогда мощность множества X1× X2× …× Xn равна произведению мощностей X1, X2, …, Xn: X 1 × X 2 ×...× X n = m1 m2 ... mn .

Доказательство. Воспользуемся методом математической индукции

по n.

1.База индукции. Очевидно, что для n = 1 теорема верна.

2.Индуктивное предположение. Пусть теорема справедлива для n = k.

3.Индукционный переход. Докажем справедливость теоремы для

n = k +1. Возьмем произвольный кортеж (x1, x2, …, xk) X1× X2 × …× Xk и припишем справа элемент xk+1 Xk+1. Так как X k +1 = mk+1, то это можно сделать mk+1 разными способами. В результате получим mk+1 различных кортежей из

X1× X2 × …× Xk+1. По индуктивному предположению,

X 1 × X 2 × ... × X k = m1 m2 ... mk . Следовательно, из всех m1 … mk кортежей из

X1× X2× …× Xk приписыванием справа элемента из Xk+1 можно получить

m1 … mk mk+1 кортежей из X1× X2 × …× Xk+1, причем все они различны, и никаких других кортежей в X1× X2 × …× Xk+1 не содержится. Поэтому теорема верна

для n = k+1, следовательно, верна для любых n.

Доказательство. Доказательство проведем методом математической индукции по n.

1.База индукции. Для n = 2 формула (2) совпадает с (1).

2.Индуктивное предположение. Пусть формула (2) верна для случая n – 1 множеств, где n ≥ 3.

3.Индукционный переход. Докажем справедливость формулы (2) для n множеств. Для этого разобьем множества X1, X2, …, Xn на две группы:

X1, X2, …, Xn-1 и Xn. Тогда согласно формуле (1) получаем

19

Из (3), учитывая (4) и (5), получаем формулу (2).

Формула (2) называется формулой включений и исключений. Ее частный случай при n = 3 имеет вид:

Подставляя (2) в (8), получаем формулу (7). Пример 1.17. Студенты третьего курса, изучающие информационные

технологии в университете, могут изучать и дополнительные дисциплины по выбору. В этом году 30 из них выбрали дисциплину «Информационные технологии моделирования интерьера», 35 предпочли дисциплину «Информационные технологии в рекламе», а 20 решили изучать дисциплину «Информационные технологии моделирования ландшафта». Кроме того, 15 студентов изъявили желание посещать «Информационные технологии моделирования интерьера» и «Информационные технологии в рекламе», 7 – «Информационные технологии в рекламе» и «Информационные технологии моделирования ландшафта», 10 – «Информационные технологии моделирования интерьера» и «Информационные технологии моделирования ландшафта», 3 – все три дисциплины. Сколько студентов выбрали по крайней мере одну дополнительную дисциплину? Сколько из них предпочли только дисциплину «Информационные технологии в рекламе»?

Решение. Пусть A – множество студентов, выбравших дисциплину «Информационные технологии моделирования интерьера», B –

20

B \ [( A ∩ B) (B ∩ C] = B − ( A ∩ B) (B ∩ C) = B − [A ∩ B + B ∩ C − A ∩ B ∩ C ] =

= 35 – (15 + 7 – 3) = 16.

Таким образом, 56 студентов выбрали по крайней мере одну дополнительную дисциплину и 16 – только дисциплину «Информационные технологии в рекламе».

Задачи и упражнения к главе 1

1.Какие из следующих высказываний истинны и какие ложны? Дайте обоснование ответа:

а) π R ;

б) cos π Q ; 3

в) 0,1010010001... Q ;

г) Ø Ø; д) Ø {Ø};

е) a {{a, b}} ;

ж) {a, b} {{a, b}};

з) {a, b} {{a, b};{a, c}; a; b} .

2.Равны ли множества:

а) {1, 3, 5} и {1, 3, 5, 1} ; б) {11, 13} и {{11, 13}}; в) {a, b, c} и {a, b, a, c} ;

г) {a, b, c}и {{a}, {b}, {c}} ; д) {{a, b}, c} и {a, {b, c}} ; е) {x R 22 ≤ x ≤ 3} и Ø.

3.Вставьте между множествами символ или так, чтобы получилось истинное высказывание:

а) {1} и {1,{1, 2}}; б) {1, 2}и {1, 2, {1}, {2}};

21