Том 15. От абака к цифровой революции. Алгоритмы и вычисления - [28]
Логика и Джордж Буль
В 1847 году была опубликована книга «Математический анализ логики» (Mathematical Analysis of Logic) Джорджа Буля, в которой была представлена булева алгебра — попытка применить методы алгебры к логике первого порядка. В настоящее время булева алгебра в общем виде используется при проектировании электрических схем, однако изначально открытия Буля были признаны только узкими специалистами. Лишь в XX веке была понята их важность и возможность применения в информатике.
Большая заслуга в этом принадлежит американскому математику и инженеруКлоду Шеннону (1916–2001), который считается создателем теории информации. Шеннон познакомился с работой Буля на занятиях по философии в Мичиганском университете, и в 1937 году защитил магистерскую диссертацию в Массачусетском технологическом институте (MIT), показав, что булеву алгебру можно использовать для оптимизации электрических цепей. В 1935 году независимо от Шеннона логик Виктор Шестаков (1907–1987) из Московского государственного университета также использовал булеву алгебру в этих же целях.
Булева алгебра оказалась столь полезной в информатике потому, что она описывает идеальный сценарий с точки зрения двоичной логики. В ней используются только нули и единицы, основными операциями являются И, ИЛИ и НЕ, то есть конъюнкция (бинарная операция, обозначаемая
Другие привычные операции, например импликация (операция, схожая с конструкцией «если… то»), выражаются через три основные операции, представленные выше: (х — > у) = ¬х
* * *
ДЖОРДЖ БУЛЬ (1815–1864)
Британский математик и философ Джордж Буль создал алгебру, которая стала основой современной вычислительной техники. Именно поэтому он считается одним из основателей информатики. Его важнейшими математическими трудами являются Treatise on Differential Equations («Трактат о дифференциальных уравнениях»), опубликованный в 1859 году, и его продолжение Treatise on the Calculus of Finite Differences («Трактат о конечных разностях»), вышедший в 1860 году. Свою систему правил для математической записи и упрощения логических и философских задач, аргументы которых могут принимать только два значения (истина или ложь), он изложил в труде «Исследование законов мышления, на которых основываются математические теории логики и вероятностей» (An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities).
* * *
Аксиоматика булевой алгебры строится на основе свойств. Говоря неформальным языком, эти свойства являются необходимыми и достаточными для составления таблиц истинности логических операций.
Число π в XIX веке
В середине XVIII века, точнее в 1761 году, немецкий математик, физик, астроном и философ французского происхождения Иоганн Ламберт (1728–1777) показал, что число π и его квадрат π>2 являются иррациональными числами. Тем самым была доказана невозможность вычислить их «точное» значение. Лишь 120 лет спустя работы по вычислению значения π снова обрели важность. В 1882 году математик Фердинанд Линдеман (1852–1939) доказал, что число π является трансцендентным. Это означало, что задача о квадратуре круга нерешаема с помощью циркуля и линейки.
Некоторые задачи, касающиеся числа π, до сих пор остаются открытыми, в частности задача о нормальности π. Иррациональное число является нормальным, если вероятность появления числовых последовательностей равной длины в его записи одинакова. Например, все цифры от 0 до 9 фигурируют в записи нормального с одинаковой вероятностью, равной 1/10, все последовательности из двух цифр — с вероятностью 1/100 и так далее. Нормальность числа π все еще не доказана, однако считается, что π действительно является нормальным. Были подсчитаны частоты, с которыми в его записи появляются различные цифры. В конце XX века американский математик Дэвид Бэйли проанализировал первые 29360000 знаков π. Рассмотрев последовательности длиной до 6 цифр включительно, он не обнаружил никаких признаков неравномерности. Различия в частотах оказались минимальными и не имели статистической значимости. Приведем в качестве примера частоты, с которыми в записи π появляются цифры от 0 до 9.
* * *
АЛГЕБРАИЧЕСКИЕ И ТРАНСЦЕНДЕНТНЫЕ ЧИСЛА
Число называется алгебраическим, если оно является корнем многочлена одной переменной с целыми коэффициентами. Все целые и рациональные числа, а также некоторые иррациональные, являются алгебраическими. Наиболее известное из алгебраических иррациональных чисел — √2. Это число является корнем многочлена х>2 — 2 = 0. Множество алгебраических чисел является счетным. Трансцендентное же число не является корнем многочлена с целыми коэффициентами. Самыми известными трансцендентными числами являются
