logo search
DM_shpory

3. Законы алгебры множеств. Формула включений и исключений.

;

;

;

;

;

;

;

;

;

;

;

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

ïA È Bï = ïAï + ïBï – ïA Ç Bï

4. Декартово произведение множеств. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия. Область значений, образ (Im) соответствия. Всюду определенные и сюръективные соответствия. Образ (im) и прообраз (coim) элемента.

Декартово (прямое) произведение множеств

Упорядоченной парой называется запись вида (a, b), где a — элемент A , а b — элемент B.

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

Декартовым произведением произвольного числа множеств А1, А2, …, An называется множество

А1 ´ А2 ´…´ An = {(а1, а2, ..., ап) : аi Î Аi, i = 1, 2, ...,n}.

Если А1 = А2 =…= An = А, то А ´ А ´…´ A = An

Соответствие, бинарное отношение между двумя множествами A и B — произвольное подмножество R декартова произведения A ´ B.

Если a Î A, b Î B и (a, b) Î R, то пишут также R(a, b) или aRb. Если R = Æ — пустое множество, то соответствие называется пустым, а если R = A ´ B, то соответствие называется полным.

Пусть R Í A ´ B. Областью определения Dom R называется множество элементов a Î A, для каждого из которых найдется хотя бы один элемент b ΠB такой, что aRb. Областью значений, или образом, Im R соответствия R называется множество элементов b Î B, для каждого из которых найдется хотя бы один элемент a Î A такой, что aRb. Соответствие R называется всюду определенным, если Dom R = A, и сюръективным, если Im R = B.

Для каждого a Î A множество элементов b Î B таких, что aRb, называется образом a относительно R и обозначается im R a. Прообразом элемента b Î B относительно R называется множество элементов a Î A таких, что aRb; прообраз обозначается coim R b. Ясно, что Im R = È a Î A im R a, Dom R =  È b Î B coim R b.