Буль: законы мысли

Уточнение

Исходная версия относит обе книги к Корку. Точнее так: «The Mathematical Analysis of Logic» (1847) написана в Линкольне, где Буль тогда содержал собственную школу; профессором в новооткрытом Куинс-колледже Корка он стал только в 1849 году. «An Investigation of the Laws of Thought» (1854) — уже корковская.

Человек

Джордж Буль (1815–1864) — сын сапожника из Линкольна. Формального образования почти не получил: школу оставил в шестнадцать, чтобы содержать семью, работал учителем, к двадцати годам открыл собственную школу.

Математику освоил по книгам — сам, ночами: Лакруа, ЛапласПьер-Симон Лапласфранцузский математик, астроном и физик · 1749–1827Свёл небесную механику в пять томов, а теорию вероятностей — в один, и на полтора столетия задал образ мира, в котором будущее вычисляется из настоящего., ЛагранжЖозеф Луи Лагранжфранцузский математик и механик итальянского происхождения · 1736–1813Написал механику без единого чертежа, довёл до конца всё, что начали Эйлер и Ферма, и первым понял, что решаемость уравнения зависит от перестановок его корней.. Первые статьи начал печатать в «Cambridge Mathematical Journal» в 1841 году; в 1844-м получил золотую медаль Королевского общества за работу об операторных методах в дифференциальных уравнениях — при том, что не имел ни степени, ни должности.

В 1849 году, по рекомендациям математиков, получил кафедру в Куинс-колледже Корка. Умер в 1864-м, в сорок девять лет: пришёл на лекцию, промокнув под дождём, читал в мокрой одежде, слёг с воспалением лёгких; жена, увлечённая гомеопатией, по преданию, обливала его холодной водой, следуя принципу «подобное лечится подобным».

Из его пяти дочерей одна, Этель Лилиан Войнич, написала роман «Овод»; другая, Алисия Стотт, стала математиком и ввела термин «политоп».

Идея

Двадцать два века логика считалась завершённой наукой. Аристотелева силлогистика излагалась почти без изменений; Кант в предисловии к «Критике чистого разума» (1787) писал, что логика со времён АристотеляАристотельгреческий философ · 384–322 до н. э.Не был математиком, но задал математике две вещи, которыми она пользуется до сих пор: определение науки как вывода из недоказуемых начал и открытие, что правильность рассуждения зависит только от его формы. не смогла сделать ни шагу вперёд и, по всей видимости, представляется законченной.

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

Пусть $x$ — класс объектов (или, в позднейшей трактовке, истинностное значение высказывания). Определим:

• $xy$ — пересечение классов («и»);
• $x+y$ — объединение (у Буля — только для непересекающихся классов; Джевонс позже снял ограничение);
• $1-x$ — дополнение («не»);
• $1$ — универсум, $0$ — пустой класс.

Закон, которого нет в обычной алгебре

$$\boxed{\;x^{2}=x\;}$$

Смысл. Пересечение класса с самим собой есть он же: «умные и умные» = «умные». В обычной алгебре это уравнение имеет ровно два решения:

$$x^{2}-x=0 \iff x(x-1)=0 \iff x=0 \text{ или } x=1.$$

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

Соотношение $x^2=x$ называется идемпотентностью, и это первый пример алгебраической структуры, задаваемой тождеством, не выполняющимся у чисел. Ещё один шаг в ту же сторону, что и некоммутативность ГамильтонаУильям Роуэн Гамильтонирландский математик, физик и астроном · 1805–1865Пятнадцать лет искал, как умножать тройки чисел, и однажды на мосту в Дублине понял, что надо взять четвёрки и отказаться от коммутативности..

Как это работает

Закон исключённого третьего:

$$x(1-x)=0.$$

«Ничто не может быть одновременно $x$ и не-$x$». Буль подчёркивает, что этот закон, который Аристотель считал первоосновой мышления, у него выводится из $x^2=x$ обычным преобразованием.

Законы де Моргана (сформулированы Огастесом де Морганом, современником и другом Буля, в 1847 году — в тот же год):

$$\overline{x\wedge y}=\bar x\vee\bar y, \qquad \overline{x\vee y}=\bar x\wedge\bar y.$$

Силлогизм. «Все люди смертны; Сократ — человек; значит, Сократ смертен». Обозначим: $l$ — люди, $s$ — смертные, $c$ — Сократ. Первая посылка: $l(1-s)=0$, то есть $l=ls$. Вторая: $c=cl$. Подставляем: $c = c(ls) = (cl)s = cs$, то есть $c(1-s)=0$ — Сократ смертен. $\blacksquare$

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

Что дало это направление

Алгебра логики → математическая логика. Джевонс, Пирс, Шрёдер развивают исчисление; ФрегеГотлоб Фрегенемецкий логик, математик и философ · 1848–1925В книжке на 88 страниц построил язык, на котором математика записывает свои утверждения по сей день, — и получил при жизни столько внимания, сколько получают неудачники. («Begriffsschrift», 1879) добавляет кванторы; дальше — ПеаноДжузеппе Пеаноитальянский математик и логик · 1858–1932Аксиоматизировал натуральный ряд, векторное пространство и математическую запись — и построил кривую, которая проходит через каждую точку квадрата., РасселБертран Расселанглийский логик, философ и общественный деятель · 1872–1970Тремя строчками разрушил дело чужой жизни, десять лет чинил сломанное, а потом ушёл из математики в философию и политику — и получил Нобелевскую премию по литературе. и Уайтхед, ГильбертДавид Гильбертнемецкий математик · 1862–1943Человек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти., ГёдельКурт Гёдельавстрийский и американский логик · 1906–1978Доказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет.. Отдельная линия карты.

Булева алгебра как структура. Абстрактно: множество с операциями $\wedge,\vee,\neg$ и константами $0,1$, подчинёнными аксиомам (дистрибутивность в обе стороны, законы поглощения, дополнения). Примеры: множество всех подмножеств данного множества; алгебра высказываний; открыто-замкнутые множества топологического пространства.

Теорема Стоуна о представлении (1936): всякая булева алгебра изоморфна алгебре открыто-замкнутых подмножеств некоторого компактного вполне несвязного пространства. Красивый мост между алгеброй, топологией и логикой.

Булево кольцо. Кольцо, в котором $x^2=x$ для всех $x$. Упражнение, доступное школьнику: докажите, что всякое булево кольцо коммутативно и что $2x=0$ для всех $x$.

Подсказка: раскройте $(x+y)^2=x+y$, получите $xy+yx=0$; затем возьмите $y=x$.

Отложенный финал: ШеннонКлод Шеннонамериканский математик и инженер · 1916–2001В магистерской работе связал булеву алгебру с электрическими схемами, а через одиннадцать лет измерил информацию в битах — и создал предмет, которого до него не было.

В 1937 году двадцатиоднолетний Клод Шеннон защищает в Массачусетском технологическом институте магистерскую диссертацию «A Symbolic Analysis of Relay and Switching Circuits» (опубликована в 1938-м).

Наблюдение простое до неприличия. Реле имеет два состояния: замкнуто или разомкнуто. Последовательное соединение контактов проводит ток, только если замкнуты оба; параллельное — если замкнут хотя бы один.

$$\text{последовательно} \;=\; \wedge, \qquad \text{параллельно}\;=\;\vee, \qquad \text{размыкающий контакт}\;=\;\neg.$$

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

Практическое следствие огромно: до Шеннона схемы проектировали интуитивно, методом проб; после — алгебраически, с гарантией минимальности. Отсюда прямая дорога к логическим вентилям, сумматорам, процессорам.

Диссертацию Шеннона называют самой значимой магистерской работой XX века, и это, вероятно, не преувеличение.

Итог: «Законы мысли», написанные в Корке в 1854 году как трактат по философии, оказались технической документацией к цифровой технике. Буль был убеждён, что исследует устройство человеческого разума; на деле он описал устройство будущих компьютеров. Точка принадлежит одновременно линии алгебры, линии логики и предыстории информатики.

Следующая точка: Лондон — группа отрывается от уравнений.