Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Объединение и вычитание множеств считают равноправными операциями.

Пример. В выражении CАВ надо сначала выполнить вычитание (из А вычесть В), а затем полученное множество объединить с множеством С.

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

1. A, AA=A. AA=A (идемпотентность).

2. Пересечение и объединение множеств коммутативно (перестановочно):

A ,B AB = BA; A ,B AB = BA.

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

Эти свойства вытекают из определения. Действительно, пусть xAB, тогда xA и xB, следовательно, xBA. Отсюда (AB)(BA). Аналогично доказывается обратное утверждение (BA)(AB). Отсюда AB = BA.

Пусть xAB, тогда либо xA, либо xB, но тогда xBA и (AB)  (BA). Аналогично (BA)  (AB). Следовательно, AB = BA.

3. Пересечение и объединение множеств ассоциативно: для любых множеств A, B и C имеем (AB)C=A(BC); (AB)C=A(BC).

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

Пусть x(AB)C, отсюда x(AB) и xC, или xA, xB, xC. Отсюда x(BC) и xA, следовательно, xA(BC) и верно (AB)CA(BC). Наоборот, если xA(BC), следует, что xA, xC, xB, откуда x(AB)C и верно A(BC)(AB)C. Отсюда A(BC) = (AB)C. Аналогично доказывается равенство множеств A(BC) = (AB)C.

4. Для любых множеств A, B справедливо: если AB, то AB = A; AB = B.

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

Пусть xAB, то есть xA и xB, отсюда xA. Пусть теперь xA. Из условия AB следует, что xB, отсюда xAB. Следовательно, AB = A.

Пусть xA B, тогда xA или xB. Но AB, и, следовательно, xB, ABB. Если xB, то по определению xAB и верно включение BAB. Отсюда AB = B.

5. Для любых множеств A, B и C справедливы равенства (свойство дистрибутивности):

a) A(BC) = (AB) (AC);

б) A(BC) = (AB) (AC).

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

а) Пусть xA(BC). Тогда xA и x(BC) → xA, xB или xC → xAB или xAC → x (AB)(AC) → A(BC) (AB)(AC). Пусть x (AB)(AC). Тогда x(AB) или x(AС)→(xA, xB) или (xA, xC) → xA и xB или xC→xA(BC) и отсюда (AB)(AC) A(BC). Окончательно имеем A(BC) = (AB)(AC).

б) Пусть xA (BC). Тогда xA или x (BC) → xA или (xB и xC) → (xA или xB) и (xA или xC) → x (AB) (AC) → A (BC) (AB) (AC). Обратно, пусть x (AB) (AC). Тогда x (AB) и x (AC) → (xA или xB) и (xA или xC) → или xA или (xB и xC) → xA (BC), то есть (AB) (AC)A (BC). Следовательно, A (BC) = (AB) (AC).

6. ; (законы де Моргана).

7. Свойства универсального и пустого множества: A справедливо

AU=U;

Рекомендуем скачать другие рефераты по теме: ответы на сканворды в одноклассниках, реферат на тему технология.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата