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

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

Нетрудно убедиться, что оба "слагаемых" полученного объединения тождественно равны пустому множеству, из чего следует X Z Y Z.

Интересно отметить, что для строгого включения законы сохранения не выполняются. Имеются исключения, которые можно выявить с помощью теорем 1.1 и 1.2.

Теорема 1.1. Если X Y, то для произвольного множества Z строгое включение (X Z) (Y Z) выполняется, если и только если (Y \ X) Z .

Доказательство. Строгое включение (X Z) (Y Z) выполняется, если и только если (Y Z)\(X Z) . Преобразуем разность (Y Z)\(X Z):

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

Вторая компонента объединения множеств (Y Z Z ), безусловно, равна

. Что касается первой компоненты (Y Z X ), то после преобразования она оказывается равной условию теоремы. Конец доказательства.

Теорема 1.2. Если X Y, то для произвольного множества Z строгое включение (X Z) (Y Z) выполняется, если и только если (Y \ X) Z .

Доказательство. Строгое включение (X Z) (Y Z) выполняется, если

преобразования она оказывается равной условию теоремы. Конец доказательства.

Нетрудно убедиться, что все законы алгебры множеств соответствуют приведенным ранее свойствам булевой алгебры и аксиомам (A1) – (A5). Более краткая система аксиом алгебры множеств приводится в известной книге Р. Куранта и Г. Роббинса [Курант, 1947]. В этой аксиоматической системе для обозначения операции дополнения используется апостроф ('), который размещается после соответствующего символа или выражения. Исходных аксиом всего три:

1)A B = B A;

2)(A B) C = A (B C);

25

3) (A' B')' (A' B)' = A.

Тогда операция и соотношение A B определяются так: A B обозначает множество (A' B')';

A B соответствует равенству A B = B.

Указанных соотношений оказывается достаточно, чтобы вывести все остальные законы алгебры множеств.

Аналогичная математическая система, но уже для аксиоматического построения булевой алгебры, приведена в [Мендельсон, 1984]. В этой аксиоматической системе также вначале вводятся только две операции (пересечение и дополнение) и три аксиомы:

(i)X Y = Y X;

(ii)X (Y Z) = (X Y) Z;

(iii)X Y' = Z Z' тогда и только тогда, когда X Y = X.

Но этих аксиом явно недостаточно для отображения всех свойств булевой алгебры, тем более что в них используются только две операции из трех. Поэтому дополнительно вводятся следующие обозначения:

Выражение (X' Y')' обозначается как X Y – нетрудно видеть в этом "обозначении", с помощью которого вводится третья операция, закон де Моргана.

Выражение Z Z' для любого Z обозначается как 0, а выражение Z Z' для любого Z – как 1. В этом "обозначении" неявно вводятся законы непротиворечия и исключенного третьего, и заодно – значения истинности.

Запись X Y = X предлагается обозначать как X Y. Здесь неявно вводится отношение нестрогого включения, которое в литературе по булевой алгебре часто обозначается символом " ".

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

1)В алгебре множеств имеется отношение принадлежности, которое отсутствует практически во всех остальных булевых алгебрах. Отношение принадлежности неявно присутствует лишь в исчислении предикатов в качестве переменных и констант.

2)В алгебре множеств определено отношение строгого включения, не

являющееся отношением частичного порядка.

26

1.2. Алгебра логики

Со времен Аристотеля формальная логика существовала только в вербальной форме. Дж. Буль описал формальную логику в виде алгебры, то есть в виде системы обозначений и правил, применимых к всевозможным объектам, от множеств (см. предыдущий подраздел) до предложений. Пользуясь этой системой, он смог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) и манипулировать ими подобно тому, как в математике манипулируют числами. В настоящем разделе рассматривается алгебра логики, которая изучает операции над высказываниями, и показывается взаимосвязь между ее законами и законами алгебры множеств.

Пусть задана система, содержащая некоторые объекты, которые мы назовем атомами, причем каждый атом может иметь только одно из двух значений, допустим, 0 и 1. Из атомов можно составлять выражения, используя скобки и операции. К основным операциям относятся:

– отрицание;

– конъюнкция, в логике интерпретируется как "и";– дизъюнкция, в логике интерпретируется как "или";

– импликация, в логике интерпретируется как "влечет" или "если …,

то".

Из операций и атомов можно составлять выражения. Правила составления правильных выражений следующие:

(i)любой атом является правильным выражением;

(ii)если A и B – правильные выражения, то ( A), (A B), (A B), (A B)

–также правильные выражения;

(iii)другие сочетания атомов, операций и скобок правильными выражениями не являются.

Таким образом, в силу определения правильны следующие выражения: A,

B, ( B), ( (A B)), ( ((A B) (A ( B)))) и т.д. Иногда некоторые скобки можно опускать, если при этом однозначно восстанавливается последовательность операций. Например, последнее правильное выражение можно записать как ((A B) (A B)).

Каждое правильное выражение также может принимать значения из множества {0, 1}. Тогда значения выражений определяются значениями

27

входящих в них атомов и последовательностью операций. Для приведенных выше операций эти значения определяются с помощью следующих таблиц:

Определение логических связок "и", "или", "если ..., то" с помощью этих таблиц устраняет некоторые неоднозначности, которые встречаются при использовании связок в естественных рассуждениях. Кроме того, такие определения позволяют установить тесную связь логических операций (или связок) с операциями алгебры множеств. Пусть заданы элемент t и некоторые множества X и Y, и атомы A и B обозначают соответственно высказывания t X

выражение t ( X Y).

Что касается таблицы для отрицания, то ее можно интерпретировать как соответствие дополнению множеств, но при некоторых допущениях. Дело в том, что отрицанием высказывания t X традиционно считается высказывание t X. Но это высказывание не во всех случаях эквивалентно высказыванию t X , поскольку для t X не исключен случай, когда элемент t не принадлежит даже универсуму рассматриваемой системы множеств. Таким образом, при ложном высказывании t X возможны два случая:

1)высказывание t X истинно,

2)высказывание t X ложно – это означает, что элемент t не является элементом принятого для данной системы универсума.

Чтобы сохранить однозначность отрицания, необходимо рассматривать только такие системы, в которых второй вариант отрицания невозможен, т.е.

28

справедливо t X = t X или, равносильно, t в любом случае принадлежит универсуму.

При переходе к формальным логическим системам атомы интерпретируются как высказывания, правильные выражения называются "правильно построенными формулами" или ппф, а вместо множества {0, 1} возможных значений атомов и формул используется соответственно множество значений {ложно, истинно}. Установлено, что при такой замене, а также при выборе соответствующих аксиом получается исчисление высказываний. Заметим, что в формальной логике термин "операция" употреблять не принято, вместо него употребляется термин "логическая связка".

На основе табличного определения операций можно также с помощью таблиц определять значения формул. В качестве примера рассмотрим, как "вычисляются" значения формулы ((A B) (A B)). Для этого так же, как и в приведенных выше таблицах, необходимо перечислить все возможные сочетания значений атомов, входящих в формулу, и затем последовательно выписывать, соблюдая последовательность операций, значения входящих в исходное выражение подформул (табл. 1.5). Такие таблицы называются истинностными таблицами.

эквивалентности между ними. В качестве примера сравним табличным способом две формулы A B и B A, равенство которых соответствует закону контрапозиции в логике и в алгебре множеств (табл. 1.6):

29