Чарльз Петцольд - Код. Тайный язык информатики

В булевой алгебре символ «+» — это объединение двух классов, которое предполагает объединение всего, относящегося к первому классу, со всем, относящимся ко второму. Например, выражение Ч + Б означает множество всех кошек черного и белого окраса.

Символ «×» — это пересечение двух классов, то есть пересечение множества элементов, принадлежащих как первому, так и второму классу. Например, Ж × Р — класс всех кошек женского пола и рыжего окраса. Как и в обычной алгебре, мы можем написать Ж × Р в виде Ж и Р или просто ЖР (именно так предпочитал писать сам Буль). Вы можете рассматривать эти две буквы в качестве двух прилагательных, описывающих множество «рыжие кошки женского пола».

Чтобы не спутать обычную алгебру с булевой, вместо символов «+» и «×» для обозначения объединения и пересечения классов иногда используются символы U и ∩.

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

Коммутативные, ассоциативные и дистрибутивные правила остаются справедливыми в булевой алгебре. Более того, здесь оператор «+» является дистрибутивным по отношению к оператору «×», чего нельзя сказать об обычной алгебре:

Б + (Ч × Ж) = (Б + Ч) × (Б + Ж).

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

Булевой алгебре необходимы еще два символа. Они смахивают на числа, но ими не являются, поскольку иногда с ними обращаются не так, как с числами. Символ 1 означает множество всех вещей, о которых мы говорим. В данном примере 1 — это множество всех кошек:

М + Ж = 1.

Значит, множество всех кошек содержит самцов и самок. Точно так же оно включает всех кошек рыжего, черного, белого и других окрасов:

Р + Ч + Б + Д = 1.

Кроме того, множество всех кошек можно получить и так:

С + Н = 1.

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

1 − М.

Как видите, это множество всех кошек, кроме самцов. Множество всех кошек, исключающее всех самцов, соответствует множеству кошек женского пола:

1 − М = Ж.

Другой необходимый символ — 0, а в булевой алгебре 0 означает пустое множество, которое ничего не содержит. Пустое множество — результат пересечения двух взаимоисключающих множеств, например множество кошек-гермафродитов:

Ж × М = 0.

Обратите внимание: символы 1 и 0 иногда работают одинаково в булевой и в обычной алгебре. Например, пересечение множества всех кошек и кошек женского пола соответствует множеству кошек-самок:

1 × Ж = Ж.

Пересечение пустого множества и множества кошек-самок представляет пустое множество:

0 × Ж = 0.

Объединение пустого множества и множества всех кошек-самок — это множество кошек-самок:

0 + Ж = Ж.

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

1 + Ж = 1.

Это не имеет смысла в обычной алгебре.

Поскольку Ж — множество всех кошек-самок, а 1 − Ж — множество всех кошек, которые не являются самками, объединение этих двух множеств соответствует 1:

Ж + (1 − Ж) = Ж + М = 1.

Пересечение двух множеств соответствует 0:

Ж × (1 − Ж) = 0.

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

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

Ж × Ж = Ж.

Пересечение множества кошек-самок и множества кошек-самок по-прежнему множество кошек-самок. Это выражение имеет смысл в булевой алгебре. Однако оно неверное, если бы буква Ж означала число. Буль считал, что выражение X2 = X является единственным выражением, отличающим его алгебру от обычной. Вот еще одно булево выражение, которое выглядит странно с точки зрения обычной алгебры:

Ж + Ж = Ж.

Объединение множества кошек-самок и множества кошек-самок по-прежнему является множеством кошек-самок.

Булева алгебра предоставляет математический метод для решения силлогизма Аристотеля. Давайте рассмотрим первые две его части:

Все люди смертны;

Сократ — человек.

Буквой Л мы обозначим множество всех людей, буквой Х — множество всех смертных существ, а буквой С — множество Сократов. Что означает выражение «все люди смертны»? Пересечение множества всех людей и множества всех смертных существ — это множество всех людей: