Основные понятия алгебры множеств (стр. 3 из 3)

1.

=A.

Пример 5. Пусть U={a, b, c, d} и P={a, c}. Тогда

={b, d} и ={a, c}=P.

В алгебре множеств это соотношение (двойное дополнение) носит название закон инволюции. В логике этот закон известен под названием закон отрицания отрицания (или закон двойного отрицания): не (не-A) – то же самое, что и A.

2. A Ç

= Æ (множество и его дополнение не имеют общих элементов)

В логике этому закону соответствует закон непротиворечия (утверждение и его полное отрицание логически несовместимы).

3. A È

= U.

В логике этому закону соответствует закон исключенного третьего (совмещение любого утверждения и его полного отрицания не допускает присутствия какого-либо третьего промежуточного варианта).

Следующие соотношения характеризуют более подробно свойства пустого множества и универсума:

4.

= U;

5.

= Æ

6. AÇÆ = Æ;

7. AÈÆ = A;

8. AÇU = A;

9. AÈU = U.

Следующие законы алгебры множеств связывают друг с другом отношения включения и равенства:

10. Из AÍB следует:

10a. AÇB = A;

10b. AÈB = B;

10c.

ÈB = U;

10d. AÇ

= Æ.

Соотношение 10d можно выразить также с помощью операции разности множеств:

10e. Из AÍB следует A\B = Æ.

Следующие законы в логике и алгебре множеств называются законами де Моргана:

11a.

= È ;

11b

= Ç .

И, наконец, приведем два закона, которые определяют основные свойства отношения включения. Их используют в дальнейшем в правилах логического вывода.

12a. Если AÍB и BÍC, то AÍC (закон транзитивности включения);

12b. Если AÍB, то справедливо также и

Í (закон контрапозиции).

В математической литературе приводятся разные способы обоснования этих законов. Многие из них весьма сложны для понимания. Здесь рассмотрим относительно простой способ, который называется комбинаторным.

Пусть нам необходимо вывести некоторые законы для двух множеств X и Y. Рассмотрим диаграмму Эйлера (рисунок 7), на которой изображены эти множества и объемлющий их универсум (U).

Рис. 7

Выделим на диаграмме участки a, b, c и d, которые не имеют внутренних границ, т.е. выполним разбиение нашего универсума на непересекающиеся друг с другом множества. Такое разбиение позволяет нам представить эти множества как элементы, из которых состоят универсум U и множества X и Y. Тогда для них справедливы соотношения:

U = {a, b, c, d}; X = {a, b}; Y = {b, c}.

Примем эти соотношения в качестве исходных данных и докажем для этого общего представления данной системы из двух множеств один из законов де Моргана

= È . Тогда получим:

1) XÇY = {b};

2)

= {a, c, d};

3)

= {c, d};

4)

= {a, d};

5)

È ={a, c, d};

6) сравнивая 2 и 5 заключаем, что

= È , что и требовалось доказать.

Закон транзитивности (12a) интуитивно понятен. Рассмотрим обоснование закона контрапозиции (12b). Поскольку он действителен только в том случае, когда XÍY, то придется немного изменить нашу исходную систему. Для этого примем, что множество, представленное в системе элементом a, равно пустому множеству, и поэтому его можно исключить из универсума. Тогда получим следующие исходные данные:

U = {b, c, d}; X = {b}; Y = {b, c}.

Ясно, что в этой системе соотношение XÍY соблюдается. Приступим к доказательству.

1)

= {c, d};

2)

= {d};

3) сравнивая

и , убедимся, что Í , что и требовалось доказать.

Литература

1. Алгебра и начало анализа – Высшая школа – М. 2003 г.

2. Алгебра – под ред. Бутинець К.К. – К . – 2000 г.