Текст книги "Код. Тайный язык информатики"

Глава 10. Логика и переключатели

Что есть истина? Аристотель полагал, что она как-то связана с логикой. Сборник его сочинений под названием «Органон» (датируемый IV веком до н. э.) – самое раннее произведение, где подробно освещается эта тема. Для древних греков логика – средство анализа языка c целью нахождения истины, поэтому она считалась формой философии. Основа логики Аристотеля – силлогизм. Самый известный силлогизм (который фактически отсутствует в работах Аристотеля) формулируется так:

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

Сократ – человек;

следовательно, Сократ смертен.

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

Смертность Сократа может показаться достаточно очевидной, однако существует множество разнообразных силлогизмов. Рассмотрим следующие две предпосылки, которые предложил математик XIX века Чарльз Доджсон, известный как Льюис Кэрролл:

Все философы логичны;

нелогичный человек всегда упрям.

В данном случае вывод не очевиден. Он формулируется так: «Некоторые упрямые люди не являются философами». Обратите внимание на неожиданное и привносящее неопределенность слово «некоторые».

На протяжении более двух тысяч лет математики боролись с логикой Аристотеля, пытаясь укротить ее с помощью математических символов и операторов. До XIX века ближе всех к решению этой задачи удалось подойти только Готфриду Вильгельму фон Лейбницу (1646–1716), который занимался логикой в молодости, а затем заинтересовался иными вещами, например одновременно с Исааком Ньютоном разработал дифференциальное исчисление (независимо от него)[15]15
  Лейбниц и Ньютон предложили разный терминологический аппарат и различные формы записи дифференциального исчисления. В итоге победил вариант Лейбница. Прим. науч. ред.


[Закрыть]. Затем на сцену вышел Джордж Буль.

Джордж Буль родился в 1815 году в Англии в социуме, где его шансы на успех были очень малы. Поскольку он был сыном башмачника и бывшей горничной, его перспективы не сильно отличались от перспектив его предков по причине жесткой классовой иерархии британского общества. Однако благодаря своему пытливому уму и отцу, который интересовался наукой, математикой и литературой, молодой Джордж получил образование, как правило являющееся привилегией мальчиков из высших классов общества. Он изучал латынь, греческий язык и математику. Ранние работы Буля по математике позволили ему в 1849 году стать первым профессором математики в Королевском колледже Корка.

Несколько математиков в середине 1800-х годов работали над формальным определением логики (среди них особо выделялся Огастес де Морган). Однако именно Буль совершил настоящий концептуальный прорыв: сначала в короткой книге «Математический анализ логики, или Очерк исчисления дедуктивных умозаключений» (1847), затем в гораздо более объемном и амбициозном произведении «Исследование законов мышления, на которых основаны математические теории логики и вероятностей» (1854), которое кратко также называется «Исследование законов мышления». Буль умер в 1864 году в возрасте 49 лет от пневмонии, которую он подхватил, попав под дождь по дороге на лекцию.

Название книги Буля 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.

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

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

Ж × Ж = Ж.

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

Ж + Ж = Ж.

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

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

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

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

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

Л × Х = Л.

Выражение Л × Х = Х было бы неправильным, поскольку множество всех смертных существ включает кошек, собак и деревья.

Выражение «Сократ – человек» означает, что пересечение множества Сократов (очень небольшого множества) и множества всех людей (гораздо более крупного множества) представляет множество Сократов:

С × Л = С.

Поскольку из первого уравнения известно, что Л равно Л × Х, можем подставить это выражение во второе:

С × (Л × Х) = С.

Согласно ассоциативному закону это равнозначно выражению:

(С × Л) × Х = С.

Однако мы уже знаем, что С × Л равно С, поэтому можем упростить выражение, используя эту подстановку:

С × Х = С.

Теперь мы закончили. Эта формула указывает, что пересечение множества Сократов и множества всех смертных существ есть С, а это значит, что Сократ смертен. Если бы вместо этого оказалось, что С × Х равно 0, мы бы пришли к выводу, что Сократ не был смертным. Если бы мы обнаружили, что С × Х равно Х, то вывод заключался бы в том, что Сократ является единственным смертным существом, а все остальные бессмертны.

Использование булевой алгебры может показаться излишним для доказательства очевидного факта (особенно учитывая то, что Сократ доказал собственную смертность 2400 лет назад), однако ее можно использовать для того, чтобы определить, удовлетворяет ли что-то определенному набору критериев. Возможно, однажды вы зайдете в зоомагазин и скажете продавцу: «Мне нужен стерилизованный кот белого или рыжего окраса, или стерилизованная кошка любого окраса, кроме белого, или я возьму любую из имеющихся у вас черных кошек». И продавец скажет, что вам нужна кошка из множества, описываемого следующим выражением:

(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.

Верно? И вы ответите: «Да! Точно!»

Проверяя, правильно ли продавец вас понял, можно отказаться от понятий объединения и пересечения, вместо них использовать слова ИЛИ и И. Я пишу эти слова заглавными буквами, потому что они не только соответствуют понятиям в обычном языке, но и могут представлять собой операции в булевой алгебре. Когда вы формируете объединение двух множеств, вы фактически берете элементы из первого ИЛИ второго множества. А когда вы формируете пересечение, то берете только те элементы, которые одновременно принадлежат первому И второму множествам. Кроме того, вы можете использовать слово НЕ везде, где встречается символ 1, за которым следует знак «минус». Таким образом:

• символ «+» (ранее обозначавший объединение) теперь означает ИЛИ;

• символ «×» (ранее обозначавший пересечение) теперь означает И;

• выражение «1 –» (ранее обозначавшее множество всех элементов, за исключением чего-то) теперь означает НЕ.

Именно поэтому приведенное выше выражение также может быть записано:

(М И С И (Б ИЛИ Р)) ИЛИ (Ж И С И (НЕ Б)) ИЛИ Ч.

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

(М И С И (Б ИЛИ Р))

ИЛИ

(Ж И С И (НЕ Б))

ИЛИ

Ч

С помощью этой формулы продавец может выполнить то, что называется проверкой условия. Незаметно мы перешли к несколько иной форме булевой алгебры, в которой буквы не обозначают множества. Вместо этого буквы теперь могут соответствовать числам. Однако буквам может быть присвоено только значение 0 или 1. Число 1 означает «да», «истина», данная конкретная кошка удовлетворяет этим критериям, число 0 – «нет», «ложь», данная кошка не удовлетворяет этим критериям.

Сначала продавец приносит нестерилизованного рыжего кота. Вот выражение, описывающее множество приемлемых кошек:

(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.

Вот как оно выглядит после подстановки значений 0 и 1:

(1 × 0 × (0 + 1)) + (0 × 0 × (1–0)) + 0.

Обратите внимание: единственными символами, которым было присвоено значение 1, являются М и Р, поскольку речь идет о рыжем коте.

Теперь нужно упростить данное выражение. Если оно упрощается до 1, то кошка удовлетворяет вашим критериям; если оно упрощается до 0, то кошка критериям не удовлетворяет. Имейте в виду, что в процессе упрощения выражения мы на самом деле ничего не складываем и не умножаем, хотя обычно можем сделать вид, что выполняем эти операции. Большинство тех же правил применяются тогда, когда символ «+» означает ИЛИ, а символ «×» – И. Иногда в современных текстах для обозначения И и ИЛИ используются символы «∧» и «∨» вместо «×» и «+». Однако именно здесь символы «+» и «×», вероятно, имеют наибольший смысл.

Когда символ «×» означает И, возможны результаты:

0 × 0 = 0;

0 × 1 = 0;

1 × 0 = 0;

1 × 1 = 1.

Другими словами, результат равен 1 только в том случае, если левый И правый операнды равны 1. Эта операция соответствует обычному умножению и называется конъюнкцией, и ее можно описать с помощью небольшой таблицы, аналогичной таблицам сложения и умножения, приведенным в главе 8.

Когда символ «+» означает ИЛИ, возможны следующие результаты.

0 + 0 = 0;

0 + 1 = 1;

1 + 0 = 1;

1 + 1 = 1.

Результат равен 1, если левый ИЛИ правый операнд равен 1. Исход этой операции похож на результаты обычного сложения, за исключением того, что в данном случае 1 + 1 равно 1. Результаты операции ИЛИ, которая называется дизъюнкцией, можно представить в виде другой таблицы.

Мы готовы использовать эти таблицы для вычисления:

(1 × 0 × 1) + (0 × 0 × 1) + 0 = 0 + 0 + 0 = 0.

Результат 0 – «нет», «ложь», этот котенок не подходит.

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

(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.

Снова подставим в него значения 0 и 1:

(0 × 1 × (1 + 0)) + (1 × 1 × (1–1)) + 0.

И упростим его:

(0 × 1 × 1) + (1 × 1 × 0) + 0 = 0 + 0 + 0 = 0.

Еще один несчастный котенок отвергнут.

Затем продавец приносит стерилизованную серую кошку. (Серый соответствует критерию «другой окрас», то есть не белый, не черный и не рыжий.) Вот соответствующее выражение:

(0 × 1 × (0 + 0)) + (1 × 1 × (1–0)) + 0.

Теперь упростим его:

(0 × 1 × 0) + (1 × 1 × 1) + 0 = 0 + 1 + 0 = 1.

Результат вычисления, равный 1, означает «да», «истина», котенок нашел свой дом. (Кроме того, он оказался самым милым!)

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

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

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

Если вы оставляете левый переключатель разомкнутым, а замыкаете правый, также ничего не произойдет. Лампочка загорается, когда и левый, и правый переключатели оказываются замкнутыми.

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

Эта схема решает небольшую логическую задачу. Фактически лампочка отвечает на вопрос: «Замкнуты ли оба переключателя?» Мы можем суммировать результаты работы этой схемы в следующей таблице.

В предыдущей главе мы говорили о том, как с помощью двоичных цифр, или битов, можно представить любую информацию, начиная от чисел и заканчивая направлением большого пальца Роджера Эберта. Мы могли сказать, что ноль бит означает, что палец направлен вниз, а один бит – что палец направлен вверх. Переключатель может находиться в двух положениях, поэтому для его описания достаточно одного бита. Можно сказать, что 0 – это «переключатель разомкнут», а 1 – «переключатель замкнут». Лампочка также имеет два состояния, следовательно, для их описания достаточно одного бита. Можно сказать, что 0 – «лампочка не горит», а 1 – «лампочка горит». Теперь мы просто переписываем приведенную выше таблицу.

Обратите внимание: если мы поменяем местами левый и правый переключатели, результаты останутся прежними. Нам не обязательно различать переключатели. Именно поэтому таблицу можно переписать так, чтобы она напоминала приведенные И/ИЛИ.

Действительно, это соответствует таблице с результатами выполнения булевой операции И.

Эта простая схема фактически выполняет операцию И в булевой алгебре.

Теперь попробуйте соединить два переключателя иначе.

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

Или нижний переключатель.

Можно также замкнуть оба переключателя.

Лампочка загорается, если замкнуть верхний или нижний переключатель. Ключевым словом в данном случае является союз «или».

Опять же, данная схема решает логическую задачу. Лампочка отвечает на вопрос: «Замкнут ли хотя бы один переключатель?» В следующей таблице показаны результаты работы этой схемы.

Теперь снова используем 0 для обозначения разомкнутого переключателя или негорящей лампочки и 1 – для обозначения замкнутого переключателя или горящей лампочки, в результате чего получим следующую таблицу.

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

Вероятно, вы уже догадались, что эта таблица соответствует результатам булевой операции ИЛИ.

Значит, два соединенных параллельно переключателя выполняют операцию, эквивалентную булевой операции ИЛИ.

Явившись в зоомагазин, вы сказали продавцу: «Мне нужен стерилизованный кот белого или рыжего окраса; или стерилизованная кошка любого окраса, кроме белого; или я возьму любую из имеющихся у вас черных кошек», – и продавец составил такое выражение:

(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.

Теперь, когда вы знаете, что два соединенных последовательно переключателя выполняют логическую операцию И (обозначаемую символом «×»), а два переключателя, соединенных параллельно, – логическую операцию ИЛИ (обозначаемую символом «+»), вы можете соединить восемь переключателей.

Все переключатели в этой схеме обозначены буквами, соответствующими буквам в булевом выражении. (Б¯ означает НЕ Б и является альтернативным способом записи выражения 1 − Б). Действительно, если вы просмотрите электрическую схему слева направо и сверху вниз, то столкнетесь с буквами в том же порядке, в каком они представлены в выражении. Каждый символ «×» соответствует месту схемы, где два переключателя (или две группы переключателей) соединены последовательно, каждый символ «+» – месту схемы, в котором два переключателя (или две группы переключателей) соединены параллельно.

Как вы помните, продавец сначала принес нестерилизованного рыжего кота. Замкните соответствующие переключатели.

Несмотря на то что переключатели М, Р и НЕ Б замкнуты, лампочка не загорается. Затем продавец принес стерилизованную белую кошку.

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

Так можно замкнуть все нужные переключатели, зажечь лампочку и показать, что котенок удовлетворяет всем вашим критериям.

Джордж Буль никогда не собирал такую схему. Ему никогда не доводилось видеть логическое выражение, реализованное с помощью переключателей, проводов и лампочек. Разумеется, одним из препятствий было то, что лампа накаливания была изобретена только спустя 15 лет после смерти Буля. Однако Сэмюэл Морзе продемонстрировал свой телеграф в 1844 году – за десять лет до публикации книги Буля «Исследование законов мышления», и ему ничего не стоило заменить лампочки в приведенной выше схеме клопфером.

Никому в XIX веке не удалось уловить связь между булевыми операциями И и ИЛИ и последовательным и параллельным соединением простых переключателей – ни математику, ни электрику, ни оператору телеграфа[16]16
  То, что мы привыкли называть булевой алгеброй, булевыми (или булевскими) переменными – всего лишь побочный эффект прорыва, который совершил Буль. В тот момент, когда на сцене появился Буль, логика и математика развивались в значительной степени автономно на протяжении более двух тысяч лет! Буль при помощи своей алгебры показал, как можно соединить эти две дисциплины, и тем самым создал новую – математическую – логику. Прим. науч. ред.


[Закрыть]. Это не пришло в голову даже отцу-основателю компьютерной революции – Чарльзу Бэббиджу (1792–1871), который переписывался с Булем и был знаком с его работой, а большую часть жизни потратил на разработку разностной, а затем аналитической машины, которая спустя столетие будет считаться предшественником современных компьютеров. Сейчас мы знаем, что Бэббиджу помогло осознание того, что вместо шестеренок и рычагов для выполнения вычислений лучше использовать телеграфные реле.

Да, телеграфные реле.