dm_tema_1

Свойства прямого произведения:

1)A (B [ C ) = (A B) [ (A C)

2)A (B \ C ) = (A B) \ (A C)

3)(A [ B) C = (A C ) [ (B C )

4)(A \ B) C = (A C ) \ (B C )

5)(A \ B) (C \ D) = (A C) \ (B D)

6)A (B n C) = (A B) n (A C )

7)(A n B) C = (A C ) n (B C)

8)A B = (A B) [ (A B) [ (A B)

Докажем свойство 1

(x; y) 2 A (B [ C ) , x 2 A è y 2 B [ C ,

x 2 A è (y 2 B èëè y 2 C ) , (x 2 A è y 2 B) èëè (x 2 A è y 2 C ) ,

(x; y) 2 A B èëè (x; y) 2 A C , (x; y) 2 (A B) [ (A C)

1.3 Мощность конечного множества

Определение

Количество элементов конечного множества называется мощностью множества и обозначается jAj.

Мощность конечного множества A с характеристической функцией fA(x) равна

X

jAj = fA(x):

x2U

Для разбиения конечного множества

Теорема

Для любых конечных множеств A è B справедливо равенство jA [ Bj = jAj + jBj jA \ Bj:

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

Следующая теорема получила название формулы включения-исключения.

Теорема

Пусть A1; : : : ; An есть подмножества некоторого конечного множества A. Тогда

1 i<j<k n

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

Докажем на основе принципа математической индукции. Базис индукции. При n = 2 получим

jA1 [ A2j = jA1j + jA2j jA1 \ A2j:

Шаг индукции. Пусть теорема справедлива для (n 1)-го подмножества. Тогда

<j<k

Теорема

Пусть A1; : : : ; An есть подмножества некоторого конечного множества A. Тогда

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

Теорема

Пусть множества Ai , i = 1; : : : ; n конечны. Тогда мощность прямого произведения

jA1 A2 Anj = jA1jjA2j jAnj:

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

При построении прямого произведения первый элемент выбираем jA1j способами, второй независимо от первого jA2j способами и т.д. Всего получим jA1jjA2j jAnj различных элементов прямого

произведения.

Как следствие получим jAnj = jAjn.

1.4 Отношения

Определение

Отношение R на множествах Ai , i = 1; : : : ; n есть подмножество прямого произведения этих множеств

R A1 A2 : : : An:

Определение Бинарным отношением называется отношение на двух множествах

R A B:

Определение Бинарным отношением на множестве называется отношение

R A A = A2:

Принадлежность пары (x; y) бинарному отношению R записывается в виде (x; y) 2 R èëè xRy.

Бинарные отношения на конечных множествах можно задавать в виде списка элементов, в виде матрицы, в виде графа.

Пусть A = fx1; x2; : : : ; xng, B = fy1; y2; : : : ; ymg. Матрица бинарного отношения R A B состоит из элементов

1; (xi ; yj ) 2 R

mij = 2 :

0; (xi ; yj ) = R

Матрицу бинарного отношения R будем обозначать MR .