3.2 Булеан

Определение 8 Множество вcех подмножеств множества M называется булеаном и

обозначается 2M

Задание 4 Записать множество 2

A

, если A = {0, 1, 2}.

Ответ: 2

A = {?, {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2}}.

Теорема 1 Для конечного множества M: |2M| = 2

|M|

.

Доказательство: (по индукции)

1. База: Пусть M = ?. Тогда 2M = {?}, |2M| = 1 = 2

0

- верно.

2. Индуктивное предположение:Предположим ?M : |M| < k верно |2M| = 2

|M|

.

3. Индуктивный переход: Рассмотрим множество M мощности k: M = {a1, . . . , ak}.

Рассмотрим 2 семейства множеств:

M1 = {A ? 2

M

|ak ? A}, M2 = {A ? 2

M

|ak 6? A}

Они задают разбиение множества 2M, т.к. 2M = M1 ? M2 и M1 ? M2 = ?.

По индуктивному предположению |M1| = 2

k?1

, |M2| = 2

k?1

.

|2

M

| = |M1| + |M2| = 2

k?1

+ 2

k?1

= 2

k

3.3 Множество действительных чисел

Действительное (вещественное) число определяется как бесконечная десятичная дробь, то

есть выражение вида ±a0, a1a2 . . . an . . .

Теорема 2 (Кантора)

Множество всех действительных чисел отрезка [0, 1] не является счетным.8 Кустицкая Т.А. Дискретная математика

Доказательство: (от противного)

Предположим, что множество счетно. Тогда существует его нумерация. Расположим все

числа, изображенные изображенные бесконечными десятичными дробями в порядке этой

нумерации:

1 0, a11 a12 a13 . . .

2 0, a21 a22 a23 . . .

3 0, a31 a32 a33 . . .

. . . . . . , . . . . . . . . . . . .

Рассмотрим бесконечную десятичную дробь

0, b1 b2 b3 . . .

такую, что b1 =6 a11, b2 =6 a22, . . . .

Эта дробь не может войти в указанную последовательность, т.к. от каждого числа с

номером i она отличается i-й цифрой.

Значит все действительные числа из [0,1] не могут быть пронумерованы и это множество

является несчетным.

Про множества, равномощные множеству вещественных чисел отрезка [0,1] говорят, что

они имеют мощность континуума (или являются континуальными), и мощность таких

множеств обозначается символом c (|R| = c).

3.4 Прямое произведение множеств

Определение 9 Прямым (Декартовым)произведением множеств A и B называет-

ся множество упорядоченных пар, первая компонента которых принадлежит A, а вторая

- B.

A * B = {(a, b)|a ? A, b ? B}

Аналогично определяется прямое произведение n множеств:

A1 * A2 * · · · * An = {(a1, a2, . . . , an)|a1 ? A1, a2 ? A2, . . . , a3 ? A3}

Декартова степень

A

n

= A * A * . . . A

Пример 11 1. R2

2. A - множество незамужних женщин, B - множество холостых мужчин, A * B -

множество возможных супружеских пар

Задание 5 Найти геометрическую интерпретацию следующих множеств:

[a, b] * [c, d], где [a, b] и [c, d] - отрезки действительной прямой,

[a, b] * {2}.Кустицкая Т.А. Дискретная математика 9

4 Формула включений и исключений

Пусть M - некоторое множество, являющееся подмножеством универсального множества

U.

Определение 10 Характеристической функцией множества M называется функ-

ция hM : U ? {0; 1}, такая что

hM(x) =

(

1, x ? M,

0, x 6? M.

Свойства характеристических функций:

1. hA?B(x) = hA(x)hB(x);

2. h

A

(x) = 1 ? hA(x);

3. |A| =

P

x?U

hA(x).

Теорема 3 Пусть M1, M2, . . . , Mn - конечные множества. Тогда справедлива формула

включений и исключений:

|M1 ? M2 ? · · · ? Mn| = (|M1| + |M2| + · · · + |Mn|) ? (|M1 ? M2| + · · · + |Mn?1 ? Mn|)+

+(|M1 ? M2 ? M3| + · · · + |Mn?2 ? Mn?1 ? Mn|) + · · · + (?1)

n?1

(|M1 ? M2 ? · · · ? Mn|)

В частности,

при n = 2: |M1 ? M2| = |M1| + |M2| ? |M1 ? M2|,

при n = 3: |M1?M2?M3| = |M1|+|M2|+|M3|?|M1?M2|?|M2?M3|?|M1?M3|+|M1?M2?M3|

Доказательство:

По закону двойного отрицания и закону де Моргана

M1 ? M2 ? · · · ? Mn = M1 ? M2 ? · · · ? Mn = M1 ? M2 ? · · · ? Mn.

Следовательно,

|M1 ? M2 ? · · · ? Mn| = |M1 ? M2 ? · · · ? Mn|

?x ? U справедливо:

h

M1?M2?···?Mn

(x) = 1 ? hM1?M2?···?Mn

= 1 ? hM1

(x)hM2

(x) . . . hMn

(x) =

= 1 ? (1 ? hM1

(x))(1 ? hM2

(x)) . . . (1 ? hMn

(x))

По свойству характеристических функций:

|M1 ? M2 ? · · · ? Mn| =

X

x?U

h

M1?M2?···?Mn

(x) =

X

x?U

(1?(1?hM1

(x))(1?hM2

(x)) . . . (1?hMn

(x))) =

=

X

x?U

(hM1

(x) + hM2

(x) + · · · + hMn

(x) ? hM1

(x)hM2

(x) ? · · · ? hMn?1

(x)hMn

(x) + · · · +

+(?1)

n?1

hM1

(x)hM2

(x) . . . hMn

(x))

Просуммировав по x ? U соответствие со свойствами 1) и 3) характеристических функций

получим формулу включений-исключений.

Задание 6 Найти количество натуральных чисел от 1 до 100,не делящихся ни на одно

из чисел 5, 11, 13

Ответ: 62.10 Кустицкая Т.А. Дискретная математика