Название книги Буля 1854 года говорит о постановке амбициозной задачи: поскольку мозг разумного человека мыслит, используя логику, то, найдя способ математического представления логики, мы получим математическое описание того, как работает мозг. Разумеется, в наше время такое видение кажется весьма наивным (или просто оно значительно опережает свое время).
Изобретенная Булем алгебра очень похожа на обычную. В обычной алгебре операнды (обычно буквы) обозначают цифры, а операторы (например, «+» и «×») указывают, как эти числа должны объединяться. Как правило, мы используем обычную алгебру для решения таких задач: у Ани есть три яблока. У Бетти в два раза больше яблок, чем у Ани. У Кармен на пять яблок больше, чем у Бетти. У Дейрдре в три раза больше яблок, чем у Кармен. Сколько яблок у Дейрдре?
Чтобы решить эту задачу, сначала преобразуем ее в арифметические выражения, используя четыре буквы, соответствующие количеству яблок, имеющихся у каждой из четырех женщин:
A = 3;
Б = 2 × A;
К = Б + 5;
Д = 3 × К.
Мы можем объединить эти четыре выражения в одно путем подстановки, а затем уже выполнить операции сложения и умножения:
Д = 3 × К;
Д = 3 × (Б + 5);
Д = 3 × ((2 × А) + 5);
Д = 3 × ((2 × 3) + 5);
Д = 33.
Имея дело с обычной алгеброй, мы следуем определенным правилам. Эти правила настолько укоренились в практике, что мы больше не думаем о них как о правилах и даже иногда забываем их названия. Однако любая форма математики подчиняется им.
Первое правило заключается в том, что сложение и умножение являются коммутативными операциями. Это означает, что можно менять операнды местами в обеих частях выражения, не влияя на результат:
A + B = B + A;
A × B = B × A.
Напротив, операции вычитания и деления не являются коммутативными.
Сложение и умножение — ассоциативные операции, то есть:
A + (B + C) = (A + B) + C;
A × (B × C) = (A × B) × C.
Наконец, умножение дистрибутивно по отношению к сложению:
A × (B + C) = (A × B) + (A × C).
Другой характеристикой обычной алгебры является то, что она всегда оперирует числами, например килограммами сыра, количеством уток, расстоянием, которое прошел поезд, или возрастом членов семьи. Гений Буля сделал алгебру более абстрактной, отделив ее от концепции числа. В булевой алгебре (именно такое название получила алгебра Буля) операнды относятся не к числам, а к классам. Класс — это просто набор предметов, который в дальнейшем стал множеством.
Поговорим о кошках. Кошки могут быть мужского и женского пола. Для удобства множество котов будем обозначать буквой M, а множество кошек — Ж. Имейте в виду, что эти два символа не соответствуют количеству кошек. Количество котов и кошек может меняться с течением времени по мере того, как новые особи рождаются, а старые, к сожалению, уходят в мир иной. Эти буквы обозначают классы кошек со специфическими характеристиками. Говоря о котах, мы можем просто сказать «М».
Мы также можем использовать другие буквы для обозначения окраса кошек: буквой Р описать множество рыжих, буквой Ч — множество черных, буквой Б — множество белых, а буквой Д — множество кошек всех «других» цветов, то есть кошек, не входящих в классы Р, Ч или Б.
Наконец (по крайней мере, в нашем примере) кошки могут быть либо стерилизованными, либо нет. Давайте обозначим буквой С множество стерилизованных кошек, а буквой Н — множество нестерилизованных.
В обычной (числовой) алгебре операторы «+» и «×» используются для обозначения операций сложения и умножения. В булевой алгебре применяются те же символы «+» и «×», что может вызвать путаницу. Всем известно, как складывать и умножать числа в обычной алгебре, но как можно складывать и умножать классы?
Дело в том, что в булевой алгебре мы фактически ничего не складываем и не умножаем. Вместо этого символы «+» и «×» означают нечто совершенно иное.
В булевой алгебре символ «+» — это объединение двух классов, которое предполагает объединение всего, относящегося к первому классу, со всем, относящимся ко второму. Например, выражение Ч + Б означает множество всех кошек черного и белого окраса.
Символ «×» — это пересечение двух классов, то есть пересечение множества элементов, принадлежащих как первому, так и второму классу. Например, Ж × Р — класс всех кошек женского пола и рыжего окраса. Как и в обычной алгебре, мы можем написать Ж × Р в виде Ж и Р или просто ЖР (именно так предпочитал писать сам Буль). Вы можете рассматривать эти две буквы в качестве двух прилагательных, описывающих множество «рыжие кошки женского пола».
Чтобы не спутать обычную алгебру с булевой, вместо символов «+» и «×» для обозначения объединения и пересечения классов иногда используются символы 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 является единственным выражением, отличающим его алгебру от обычной. Вот еще одно булево выражение, которое выглядит странно с точки зрения обычной алгебры:
Ж + Ж = Ж.
Объединение множества кошек-самок и множества кошек-самок по-прежнему является множеством кошек-самок.
Булева алгебра предоставляет математический метод для решения силлогизма Аристотеля. Давайте рассмотрим первые две его части:
Все люди смертны;
Сократ — человек.
Буквой Л мы обозначим множество всех людей, буквой Х — множество всех смертных существ, а буквой С — множество Сократов. Что означает выражение «все люди смертны»? Пересечение множества всех людей и множества всех смертных существ — это множество всех людей:
Л × Х = Л.
Выражение Л × Х = Х было бы неправильным, поскольку множество всех смертных существ включает кошек, собак и деревья.
Выражение «Сократ — человек» означает, что пересечение множества Сократов (очень небольшого множества) и множества всех людей (гораздо более крупного множества) представляет множество Сократов:
С × Л = С.
Поскольку из первого уравнения известно, что Л равно Л × Х, можем подставить это выражение во второе:
С × (Л × Х) = С.
Согласно ассоциативному закону это равнозначно выражению:
(С × Л) × Х = С.
Однако мы уже знаем, что С × Л равно С, поэтому можем упростить выражение, используя эту подстановку:
С × Х = С.
Теперь мы закончили. Эта формула указывает, что пересечение множества Сократов и множества всех смертных существ есть С, а это значит, что Сократ смертен. Если бы вместо этого оказалось, что С × Х равно 0, мы бы пришли к выводу, что Сократ не был смертным. Если бы мы обнаружили, что С × Х равно Х, то вывод заключался бы в том, что Сократ является единственным смертным существом, а все остальные бессмертны.