Материал: Алгебра_кортежей

одновременно множеству B.

Пример 1.4. Пусть A = {a, b, c, d} и B = {a, c, f}. Тогда A \ B = {b, d}.

Для разности множеств справедливо следующее соотношение:

A \ B = A B.

Если в примере 1.4 задать универсум, например, U={a, b, c, d, e, f}, то нетрудно убедиться в справедливости этого равенства:

B= {b, d, e}; тогда A \ B = A B = {b, d}.

Вто же время операцию дополнения можно выразить с помощью

операции разности: A = U \ A. На рис. 1.2 соответствующие операции над множествами изображены с помощью диаграмм Эйлера. Серым цветом показаны результаты операций.

Рис. 1.2. Операции алгебры множеств

Здесь хотелось бы обратить внимание на одно важное обстоятельство. Для множеств A и B, у которых нет общих элементов, справедливы следующие соотношения:

A B = ; A B; B A.

Их можно наглядно отобразить с помощью такой диаграммы (рис. 1.3).

Рис. 1.3. Множества, не имеющие общих элементов

Законы алгебры множеств есть, по сути, теоремы, которые выводятся из основных определений и аксиом. Часто приводятся 26 или 28 законов алгебры множеств. Ниже мы приведем без доказательства лишь некоторые из них, необходимые для ясного понимания дальнейшего. Пусть A, B, C – некоторые произвольные множества в универсуме U. Тогда законами алгебры множеств являются следующие соотношения между ними.

20

1. A = A.

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

P= {a, c} = P.

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

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

иего полное отрицание логически несовместимы).

3.A A = U.

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

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

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

10. Если A B , то справедливы следующие соотношения:

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

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

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

11a. A B = A B; 11b. A B = A B.

Законы дистрибутивности декларируют правила раскрытия скобок в некоторых выражениях алгебры множеств:

21

12.A (B C) = (A B) (A C);

13.A (B C) = (A B) (A C).

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

14a. Если A B и B C, то A C (закон транзитивности включения). 14b. Если A B, то справедливо также и B A (закон контрапозиции). В математической литературе приводятся разные способы обоснования

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

комбинаторным.

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

Рис. 1.4. Пересекающиеся множества

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

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

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

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

1)X Y = {b};

2)X Y = {a, c, d};

3)X = {c, d};

4)Y = {a, d};

22

5)X Y = {a, c, d};

6)сравнивая 2 и 5, заключаем, что X Y = X Y , что и требовалось доказать.

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

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

Докажем для этого случая справедливость закона де Моргана.

1)X Y = ;

2)X Y = {a, c, d};

3)X = {c, d};

4)Y = {a, d};

5)X Y = {a, c, d};

6)сравнивая 2 и 5, заключаем, что X Y = X Y , что и требовалось доказать.

Закон транзитивности (14a) интуитивно понятен. Рассмотрим обоснование закона контрапозиции (14b). Схема на рис. 1.4 не подходит, так как между множествами X и Y нет соотношения включения. Однако, если убрать из универсума элемент a, найдем то, что нужно: X Y. Данный результат можно выразить в виде следующих равенств: U = {b, c, d}; X = {b};Y = {b, c}.

Приступим к доказательству. Для этого вычислим

1)X = {c, d};

2)Y = {d};

3)сравнивая X и Y , получим Y X , что и требовалось доказать. Рассмотрим несколько важных для анализа рассуждений законов, которые

всовокупности не встречаются в литературе по алгебре множеств. Объединим их общим названием законы сохранения. Эти законы можно интерпретировать как обобщение в алгебре множеств свойства монотонности.

Понятие монотонности в настоящее время связывают с системами логического вывода. В классическом варианте математической логики

23

монотонность является неотъемлемым свойством логического вывода. Это свойство может не соблюдаться в некоторых вариантах неклассической логики (например, в логике умолчаний и в немонотонной логике [Тейз, 1990]). Свойство монотонности заключается в следующем: если из некоторого множества посылок выводится предложение B, то при добавлении во множество любой посылки (например, A) предложение B также должно выводиться.

В алгебре множеств этому свойству логического вывода соответствует следующий закон:

Если G B, то (G A) B, где A – любое множество.

Доказательство этого закона таково. Из определения пересечения следует, что (G A) G. Тогда по закону транзитивности из (G A) G и G B следует (G A) B, что и требовалось доказать.

Рассмотрим законы сохранения.

1)Закон сохранения равенства: если X = Y, то для любого множества Z

справедливы следующие равенства:

X Z = Y Z и X Z = Y Z.

2)Законы сохранения для нестрогого включения: если X Y, то для любого множества Z справедливы следующие соотношения:

(i) X Z Y Z; (ii) X Z Y Z.

Первый закон сохранения кажется очевидным (возможно, поэтому его и не рассматривают в литературе по алгебре множеств и булевой алгебре). Докажем закон сохранения нестрогого включения.

(X Z)\(Y Z)=(X Z) Y Z =X Z (Y Z )=(X Z Y ) (Y Z Z ).

Множество X Z Y равно , так как по условию X Y, в силу чего

X Y = , а множество X Z Z равно , так как Z Z = . Следовательно, (X Z)\(Y Z) = и соответственно X Z Y Z.

Теперь перейдем к доказательству соотношения (ii), что равносильно доказательству (X Z)\(Y Z) = .

24