Отношения. Множество всех подмножеств множества М называется булеаном и обозначает­ся 2M:

Алгебра подмножеств

Множество всех подмножеств множества М называется булеаном и обозначает­ся 2 ^M:

2 ^м = { А | А М }.

ТЕОРЕМА Для конечного множества М

|2 ^М | = 2^{| М |}.

Свойства операций над множествами

Пусть задан универсум U. Тогда А, В, С U выполняются следующие свойства.

1. идемпотентность:

A A=A A A=A;

2. коммутативность:

A B= B A A B= B A;

3. ассоциативность:

A (B C) = (A B) C, A (B C) = (A B) C;

4. дистрибутивность:

A (B C) = (A B) (A C), A (B C) = (A B) (A C);

5. поглощение:

(A B) A=A (A B) A=A;

6. свойства нуля:

A Æ =A, A Æ = Æ;

7. свойства единицы:

A U=U, A U=A;

8. инволютивность:

= A;

9. законы де Моргана:

10. свойства дополнения:

A =U A = Æ;

11. выражения для разности:

A\B=A .

Упорядоченные пары

Если а и b — объекты, то через (а, b)обозначим упорядоченную пару. Равенство упорядоченных пар определяется следующим образом:

(а, b) = (с, d) Û а = c & b = d.

Вообще говоря, (а, b) ¹ (b, а).

Замечание

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

(а, b) = { а, { а, b }}.

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

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

Пусть A и B — два множества. Прямым (декартовым) произведением двух мно­жеств А и В называется множество упорядоченных пар, в котором первый эле­мент каждой пары принадлежит А, а второй принадлежит В:

А ´ В = {(а, b) | а А & b В }.

Степенью множества А называется его прямое произведение самого на себя. Обо­значение:

Соответственно, А ¹ = А, А ²= А ´ А и вообще Аⁿ = А ´ A ^{n -1}

ТЕОРЕМА | А ´ В | = | А | | В |.

СЛЕДСТВИЕ |А^п| = |А|^п.

Отношения

Пусть А и В — два множества. (Бинарным) отношением (или предикатом) R из множества А в множество В называется подмножество прямого произведения А и В:

R А ´ B.

Для бинарных отношений обычно используется инфиксная форма записи:

аRb = (a, b)

Если А = В, то говорят, что R есть отношение на множестве А.

Пример

Пусть задан универсум U. Тогда (принадлежность) — отношение из множества U в множество 2 ^U,а (включение) и = (равенство) — отношения на 2 ^U. Хорошо известны отношения =, <, <, >, >, , определенные на множестве чисел.

Пусть R есть отношение на A: R А ´ A, a, b А. Введем следующие понятия

Обратное отношение: R ^-1 = {(а, b) | (b, а) R }.

Дополнение отношения: ={(а, b) | (a, b) R }.

Тождественное отношение: I = {(а, а) | а А }.

Универсальное отношение: U = {(а, b) | а А & b А }.

Введем обобщенное понятие отношения: n-местное (n-арное)отношение R -это множество упорядоченных наборов (кортежей):

Множества A_i не обязательно различны.

Свойства отношений

Пусть R Ì А². Тогда отношение R называется

рефлексивным, если " а Î A aRa;

антирефлексивным, если " а Î A Ø аRа;

симметричным, если " а,b Î A aRb bRa;

антисимметричным, если " а,b Î A aRb& bRa a = b;

транзитивным, если " а,b Î A aRb & bRc aRc;

полным, или линейным, если " а,b Î A a ¹ b аRb Ú bRа.

Дата добавления: 2014-12-27