Когда 1+1 равно 1 (часть 1)

2 ноября исполняется 209 лет со дня рождения Джорджа Буля, одного из основателей математической логики, и этот материал — часть большой работы, посвящённой ему и его наследию.

Сегодня я расскажу, какой смысл имеет уравнение 1 + 1 = 1 в булевой арифметике, и как оно стало инструментом для проектирования сложных цифровых схем. Наибольший вклад в это положение дел внесли два человека: Джордж Буль и Клод Шеннон.

Итак, начнём в хронологическом порядке с Джорджа Буля.

В 1833 году молодой преподаватель Института механики Линкольна Джордж Буль испытал озарение, что его долг и судьба заключаются в объяснении логики человеческой мысли. В это время его отец был куратором этого учебного заведения. В викторианской Великобритании и её колониях так назывались образовательные учреждения, которые мы сегодня обозвали бы «вечерними школами». Изначально они были созданы для предоставления образования рабочим мужчинам, чаще всего по техническим предметам. Основной причиной создания институтов механики послужила промышленная революция. Они часто финансировались местными промышленниками на том основании, что в конечном итоге они серьёзно выиграют от наличия более образованных и квалифицированных сотрудников. Институты механики часто включали в свой состав библиотеки для взрослого рабочего класса как альтернативу азартным играм и выпивке в пабах.

Буль работал в разных областях математики, но среди широкой публики он наиболее известен новаторскими работами по символической логике. В двух работах, «Математический анализ логики» и «Исследование законов мышления, на которых основаны математические теории логики и вероятностей», Буль переделал алгебраическую нотацию для нужд логики. Классы вещей были представлены буквами, а символы сложения и умножения использовались для представления операций над этими классами, хотя на практике алгебра Буля опускала символы умножения, как это делается в обычной алгебре. Если x — класс всех кошек, а y — класс всех собак, то (x + y) — класс, состоящий из всех кошек и собак, тогда как xy — класс животных, которые являются и кошками, и собаками — пустой, поскольку котопёс существует только в сериале аниматора Питера Хэннана.

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

На рисунке ниже, показывающем четыре диаграммы Венна, использованы два перекрывающихся круга. Тот что слева представляет класс x, а тот, что справа — класс y. Представьте себе, что каждый круг диаграмм заполнен объектами, принадлежащими соответствующему классу. Класс элементов, принадлежащих обоим классам, называется пересечением двух классов. Элементы, которые не принадлежат ни одному классу, находятся за пределами кругов. Класс элементов, принадлежащих x, y или обоим, называется объединением двух классов (схематически показан в нижнем правом углу). О вопросительном знаке на нижней правой диаграмме я напишу ниже, и он связан с большой ошибкой Буля.

Давайте возьмем классический силлогизм в стиле Аристотеля — «Все люди смертны, Сократ — человек, следовательно, Сократ смертен» — и посмотрим, как Буль мог бы справиться с ним алгебраически, используя свой способ «умножения» классов. Если h — класс людей, а m — класс смертных существ, то hm = h. Чтобы понять, почему, вспомним, что hm обозначает класс всех существ, которые являются как людьми, так и смертными; а поскольку все люди смертны, то выражение «человек и смертен» — это просто словесный способ сказать «человек». Аналогично, каждое существо, которое является и Сократом, и человеком, является Сократом, поэтому sh = s (где s — класс, состоящий из Сократа и никого другого). Теперь мы можем написать доказательство sm = s, то есть «Сократ смертен», которое вообще не использует слов:

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

Конечно, некоторые могут утверждать, что Буль не должен был использовать сложение и умножение для нечисловых целей. В конце концов, одно из основных правил алгебры Буля состояло в том, что каждый класс x должен удовлетворять формуле x × x = x, поскольку, например, «кот, который является котом» — это просто словесный способ сказать «кот». Но формула x × x = x не выполняется для обычной алгебры (если только x не равен 0 или 1 — к этому моменту я вскоре вернусь).

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

Буль увидел, что 0 и 1, два числовых решения x × x = x, должны иметь аналоги в области классов. Он рассуждал, что класс 0, как аналог числа 0, должен обладать свойством, что x × 0 и 0 × x всегда равны 0, независимо от того, что такое класс x. Единственным классом с этим свойством является пустой класс. С другой стороны, класс 1, чтобы быть аналогом числа 1, должен обладать свойством, что x × 1 и 1 × x всегда равны x, и единственным классом с этим свойством является класс, состоящий из всех вещей, которые Буль назвал Вселенной. Пустой класс (можно сказать, Нуль-вселенная) и Вселенная были исходными 0 и 1 теории Буля.

«Погоди, что за чушь. 1 — Истина, а 0 — Ложь в булевой логике!»

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

Позднее Буль с радостью обнаружил, что идею обоснования логики на дихотомии нуля и единицы выдвинул за полтора столетия до него Г.В. Лейбниц (он представлял конъюнкцию предложений, используя сопоставление связанных символов, хотя, насколько мне известно, он никогда не связывал логическую конъюнкцию с умножением чисел или переменных). Лейбниц также был в восторге, когда в 1689 году узнал, что двоичная арифметика, которую он изобрёл ранее в том же году, идеально вписывается в двоичную мировую систему И Цзин, изобретённую в Китае за несколько тысяч лет до этого.

Говоря об Азии, кажется вероятным, что индийская мысль также оказала влияние на Буля. Известным членом круга общения Буля был Джордж Эверест, который в своё время был генеральным инспектором Великого тригонометрического исследования Индии. Теперь его вспоминают за то, что он невольно дал своё имя вершине, которую он более скромно называл Пиком XV. Сам Эверест ненавидел бы современное название вершины, поскольку считал, что для географических объектов следует использовать местные названия. 

Эверест был исследователем индийской культуры и передал этот интерес другим, включая Буля. Буль впоследствии женился на племяннице Эвереста Мэри, также занимавшейся преподавательской деятельностью в области математики. Позже она писала, что Буль находился под сильным влиянием индийской логики, которой его научил Эверест, и она писала: «Подумайте, каково должно было быть влияние интенсивной индуизации трёх таких людей, как Бэббидж, Де Морган и Джордж Буль, на математическую атмосферу 1830-65 годов». Кстати, очень интересная женщина, но о ней почитайте здесь.

Хотя работа Буля пользовалась уважением среди логиков и математиков, Мэри позже писала, что он был разочарован неспособностью читателей в полной мере оценить, о чём на самом деле был его труд «Исследование законов мышления». Несмотря на то, что одно только название должно было ясно указать на масштаб его амбиций.

«Почти все логики и математики проигнорировали утверждение, что книга была призвана пролить свет на природу человеческого разума; и относились к формуле исключительно как к замечательному новому методу приведения к логическому порядку массы свидетельств о внешних фактах».

До последнего дня своей жизни Буль настаивал на том, что в его арифметике классов попытка сложить 1 и 1 была бессмысленной. Буль исходил из «закона мышления» x × x = x и пришёл к выводу, что в каком-то смысле классы должны вести себя как переменные, которые могут принимать значения только 0 или 1. Но для него единица была классом всего (Вселенная), и он не считал, что имеет смысл складывать классы, если у них изначально были некоторые общие элементы. Для Буля предпосылкой для возможности записать (x + y) было заранее знать, что x и y не пересекаются, т. е. не имеют общих элементов. И в случае, когда x и y оба являются Вселенной, это настолько далеко от истины, насколько это вообще возможно: всё принадлежит как x, так и y, когда x и y оба содержат всё.

Логик Уильям Джевонс, несмотря на всё своё восхищение Булем, считал, что он просто ошибался в этом. Он не видел никакой философской проблемы в объединении двух классов, имеющих общие элементы, и считал, что сложение — идеальный способ представить результирующий больший класс. В частности, Джевонсу было ясно, что, если вы сложите любой класс с самим собой, результатом снова будет тот же самый класс. В символах x + x = x, что в особом случае, когда x — Вселенная, даёт нам 1 + 1 = 1. В своём письме Джевонс предупреждал Буля, что его система с её неоправданно ограниченным понятием сложения может считаться «самым замечательным сочетанием истины и ошибки». Но Буль не смог принять уравнение 1 + 1 = 1, потому что он всё ещё был в плену правил обычной алгебры. Действительно, если бы Буль принял, что 1 + 1 = 1, ему пришлось бы принять 1 + 1 = 1 + 0, но тогда, отбрасывая единицу с обеих сторон уравнения, он бы получил единицу равную нулю, что приравнивает Вселенную к Нуль-Вселенной, тем самым уничтожая всё.

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

Что значит «когда это возможно»? Вот в чём загвоздка. Буль и Джевонс оба видели, что в алгебре классов существует напряжение между двумя принципами алгебры, которые были справедливы для чисел: принципом отмены для сложения и принципом, согласно которому любые две величины могут быть сложены. Какой принцип должен был уступить? Принцип постоянства не говорит нам об этом. Возможно, лучший вариант разрешения такого конфликта — попеременно отбрасывать предположения и сравнивать полученные решения. Джордж Буль оказался не таким гибким.

Одна из причин, по которой он стоял на своём — его понятие сложения. Оно позволяло ему выразить понятие Джевонса о неограниченных объединениях классов окольным путем: если бы классы x и y перекрывались, Буль мог бы записать их объединение как x + (1−x)y. Класс, состоящий из всего, что есть в x, вместе со всем, чего нет в x, но есть в y. Но он не мог применить обычные правила алгебры, чтобы переписать это как x + y − xy. Исходя из его понятий Буль уже в этом моменте, после первых двух членов сказал бы: «Хорош, стопэ!» А жаль, если бы он занялся этим типом уравнения, то мог бы чуть раньше португальца да Сильвы опубликовать принцип включения-исключения и применить его к изучению теории вероятности.

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

Позже в том же году Джевонс опубликовал собственную книгу «Чистая логика» (Pure Logic: Or, The Logic of Quality Apart from Quantity), с замечаниями о системе Буля и о связи логики и математики. В системе Джевонса можно сложить любые два класса. Например, если мы возьмем h и m, как и прежде, то h + m — это класс, состоящий из всех людей и всех смертных существ, что совпадает с классом всех смертных существ. Таким образом, h + m равно m.

Чтобы получить представление о том, как это расширение определения сложения Буля увеличило мощь его системы, есть способ, отличный от того, который я описывал ранее, чтобы доказать силлогизм про Сократа. Поскольку все люди смертны, h + m = m, а поскольку Сократ — человек, s + h = h. Теперь, как сказал бы Лейбниц, давайте посчитаем!

Мы вычислили, что s + m = m. Поскольку это говорит нам, что класс, содержащий Сократа вместе со всеми смертными, есть не что иное, как класс всех смертных, мы можем заключить, что Сократ — смертный.

Это доказательство было доступно Джевонсу, но не Булю, поскольку для Буля суммы, которые встречаются в доказательстве, были бессмысленными. Дополнительная гибкость и мощь системы Джевонса сделали сомнения Буля спорными. Джевонс одержал победу, и никто, кроме историков математики и философии, не имеет в виду логику Буля, когда говорит о «булевой логике».

Булева логика после Буля

По мере того, как последователи Буля упрощали и совершенствовали символическую логику, завещанную им Булем, на первый план вышли три логические операции: конъюнкция, дизъюнкция и отрицание.

Конъюнкция соответствует слову «И», и представлена знаком ∧; если p — это предложение «трава зелёная», а q — это предложение «коровы фиолетовые», то p ∧ q — это составное предложение: «трава зелёная, а коровы фиолетовые». Это предложение ложно, хоть p истинно, потому что q ложно. Вот таблица операций, показывающая, как истинное значение p ∧ q зависит от истинного значения p и истинного значения q:

Дизъюнкция соответствует слову «ИЛИ» и представлена знаком ∨; если p — это предложение «трава зелёная», а q — это предложение «коровы фиолетовые», то p ∨ q — это составное предложение «трава зелёная или коровы фиолетовые». Здесь «ИЛИ» следует понимать в его инклюзивном смысле, иногда называемом «И/ИЛИ», так что p ∨ q истинно всякий раз, когда хотя бы одно из составляющих предложений истинно. Эта таблица операций показывает, как истинное значение p ∨ q зависит от истинного значения p и истинного значения q:

В наши дни, когда вы осуществляете поиск в базе данных со сложным критерием поиска, который объединяет примитивные поисковые термины с использованием логических связок «И», «ИЛИ» и «НЕ», вы выполняете то, что называется булевым поиском.

Американский философ и логик Чарльз Пирс считал реформированную Булеву систему выполнения логики конгениальной и использовал идеи Буля, чтобы расширить пропозициональную логику от изучения свойств отдельных объектов до изучения отношений между объектами, предвосхищая современный подход, который моделирует отношения как булевы матрицы. Например, если наш дискурс состоит из Фарры, Авраама, Сары и Исаака (библейские персонажи), то матрица, показанная ниже слева, кодирует отношение «родил».

Если возвести эту матрицу в квадрат, получим матрицу справа. Двойка соответствует факту, что Фарра, отец Авраама и Сары, был дважды дедушкой Исаака. Новая матрица не является булевой матрицей из-за этой двойки, но, если округлить двойку до единицы, получим булеву матрицу, которая кодирует отношение «родил того, кто родил», то есть «является биологическим прародителем». В качестве альтернативы матричного произведения, можно заменить каждое положительное целое число, которое получается на единицу или, что эквивалентно, заменить повсюду обычную арифметику на арифметику 1 + 1 = 1. Это называется произведением булевых матриц.

В 1886 году Пирс зашёл так далеко, что предположил, что логические операции могут выполняться электрическими коммутационными цепями. Он даже поручил одному из своих студентов, Аллану Маркванду, создать схемы электрических логических машин. Но ни Пирс, ни Маркванд не построили такую машину и не опубликовали свои идеи или наброски, а идея затерялась в пыльных архивах, пока на сцену не вышел Клод Шеннон и не переосмыслил блестящую, но заброшенную идею Пирса. А об этом я напишу в следующей части.

---

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS