4. Практикум к решению задач Основные обозначения

{ х₁, х₂, х₃ } – множество из трех элементов х₁, х₂, х₃, заданное перечислением;

х  А – х является элементом множества А;

y  B – y не является элементом множества B;

В  А, В  А – множество В есть подмножество множества А;

А  В – объединение множеств A и B;

A  B – пересечение множеств A и B;

А \ В – разность множеств А и В;

А ÷ В – симметрическая разность множеств А и В;

А = В – равенство множеств А и В;

А = – дополнение множества А;

U – универсальное множество;

– пустое множество;

 – квантор общности, х читается: "для всех х";

 – квантор существования, х читается: "существует х";

→ – "если …, то …";

↔ – "тогда и только тогда, когда";

– "есть по определению";

/ – "таких, что";

{ х / х … } – множество, заданное с помощью характеристического свойства, читается: "множество элементов х, таких, что …".

4.1. Операции над множествами

Объединением множеств А и В называется множество

А  В { х / х  А  х  В }.

Пересечением множеств А и В называется множество

А  В { х / х  А  х В }.

Разностью множеств а и в называется множество

А \ В { х / х  А  х В }.

Симметрической разностью множеств а и в называется множество

А ÷ В = ( А \ В )  ( В \ А).

Множество В есть подмножество множества А тогда и только тогда, когда

В  А   х  В → х  А.

Если В А и В А, то используется обозначение В  А:

В  А  (  х  В → х  А )  (  у  А / у  В ).

Два множества А и В равны тогда и только тогда, когда

А = В  (  х  А → х  В )  (  у  В → у  А ),

т.е. существуют оба включения

А = В ↔ А  В  В  А.

Универсальным множеством U называется множество, состоящее из всех элементов.

Дополнением множества А называется множество

А = U \ А { х / х  А }.

Пустым множеством называется множество, не имеющее ни одного элемента.

Основные законы алгебры множеств

- Закон коммутативности

А  В = В  А ; А  В = В  А.

- Закон ассоциативности

(А  В)  С = А  (В С) ; (А  В)  С = А  (В  С ).

- Закон дистрибутивности

А  (В  С) = (А  В)  (А  С) ; А  (В  С) = (А  В) (А  С))

- Закон де Моргана

А  В = А  В ; А  В = А  В.

- Закон идемпотентности

А  А = А ; А  А = А.

- Закон инвалюции

Задачи и упражнения

1. Доказать закон дистрибутивности: А(ВС)=(АВ)(АС).

Решение

В задаче требуется доказать равенство множеств X=A(BC) и У=(АВ)(АС).

В соответствием с выражением (7) два множества Х и У равны тогда и только тогда, когда выполняются два условия:

Х=У(хХхУ)(уУуХ).

Пусть хА(ВС). Тогда по определению пересечения множеств (2) хА хВС. Используя выражение (1) можно утверждать, что хА  (хВ  хС). Выражение хВ  хС означает, что могут иметь место следующие три случая:

хÎВхС или хВ  хÎС, или хВ  хС.

Если хА  хВ  хС, то хАВ, если хА  хВ  хС, то хАС, если хА  хВ  хС, то хАВС, т.е. имеем

хАВ  хАС  хАВС.

На основании (14) можно записать

хАВ  хАС  х(АВ)(АС).

По определению объединения

х(АВ)х(АС)х(АВ) (АС).