Курсовая работа: Элементы теории множеств

Обычно все рассматриваемые в ходе какого-либо рассуждения множества являются подмножествами некоторого множества U, которое называют универсальным. Например, для числовых множеств универсальным является R, для точечных множеств на плоскости - множество точек всей плоскости и т.д.

Приоритеты операций.

Под приоритетом операции понимается порядок ее выполнения. Первой выполняется та операция, приоритет которой выше.

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

Приоритет операции пересечения множеств выше приоритета операции вычитания.

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

Пример. В выражении 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 справедливо