Mathematical Analysis of Logic) Джорджа Буля, в которой была представлена булева алгебра — попытка применить методы алгебры к логике первого порядка. В настоящее время булева алгебра в общем виде используется при проектировании электрических схем, однако изначально открытия Буля были признаны только узкими специалистами. Лишь в XX веке была понята их важность и возможность применения в информатике.
Большая заслуга в этом принадлежит американскому математику и инженеруКлоду Шеннону (1916–2001), который считается создателем теории информации. Шеннон познакомился с работой Буля на занятиях по философии в Мичиганском университете, и в 1937 году защитил магистерскую диссертацию в Массачусетском технологическом институте (MIT), показав, что булеву алгебру можно использовать для оптимизации электрических цепей. В 1935 году независимо от Шеннона логик Виктор Шестаков (1907–1987) из Московского государственного университета также использовал булеву алгебру в этих же целях.
Булева алгебра оказалась столь полезной в информатике потому, что она описывает идеальный сценарий с точки зрения двоичной логики. В ней используются только нули и единицы, основными операциями являются И, ИЛИ и НЕ, то есть конъюнкция (бинарная операция, обозначаемая ), дизъюнкция (бинарная операция, обозначаемая ) и отрицание (унарная операция, обозначаемая ¬). Эти логические операции определяются с помощью следующих таблиц истинности.
Другие привычные операции, например импликация (операция, схожая с конструкцией «если… то»), выражаются через три основные операции, представленные выше: (х — >у) = ¬хy, Кроме того, в виде комбинации этих операций можно представить любую другую логическую функцию. Так называемый закон де Моргана гласит, что существует всего две основные логические операции. Например, это могут быть дизъюнкция и отрицание, с помощью которых также можно выразить операцию конъюнкции.
* * *
ДЖОРДЖ БУЛЬ (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. Множество алгебраических чисел является счетным. Трансцендентное же число не является корнем многочлена с целыми коэффициентами. Самыми известными трансцендентными числами являются π и е.
Глава 4Компьютеры в XX веке
Бурный XX век стал свидетелем всевозможных изменений в политике, общественной жизни и, разумеется, в науке, которые сопровождались невероятной технической революцией. Эта история великих теорий, потрясающих открытий и горьких разочарований сопровождалась прорывом в области вычислений, благодаря чему стало возможным создание нового цифрового мира. Развитие информатики было поистине удивительным, однако в архитектуре вычислительных машин не произошло значительных изменений. В современных компьютерах по-прежнему используется архитектура фон Неймана.
Главными героями в истории информатики и вычислительной техники в XX веке были исключительные личности, которые много лет были никому не известны. Среди них — немецкий инженер Конрад Цузе и его вычислительные машины серии Z. Большинство изобретений Цузе долгое время оставались незамеченными, так как были сделаны незадолго до начала Второй мировой войны, а работа над ними продолжалась в последующие несколько лет. Цузе, сам того не осознавая, следовал идеям Бэббиджа, с работами которого он был совершенно не знаком. Когда Джон фон Нейман позднее описал архитектуру компьютера, он не руководствовался работами Цузе. Несомненно, созданная ими архитектура вычислительных машин была оптимальной: это подтвердили специалисты в области логики. Она содержала устройство управления, память и арифметико-логическое устройство для выполнения вычислений.
Цузе создал две первые машины в период с 1935 по 1939 год, перед самым началом Второй мировой войны. Его первая патентная заявка датирована 11 апреля 1936 года. В 1938 году он подал патентную заявку в США. Она была отклонена, так как Цузе изложил свое открытие недостаточно подробно. Его вычислительные машины назывались Z1 и Z2. Сначала Цузе назвал первую машину VI (от слова Versuchsmodell, что означало «экспериментальная модель»), но затем сменил название, чтобы избежать путаницы с названиями ракет VI и V2 Вернера фон Брауна.
Первая машина Z1 имела размеры 2 х 1,5 метра. Сделанная из стали, она была достаточно ненадежной: поправки требовалось вносить каждые несколько минут. Это был всего лишь двоичный механический калькулятор с ограниченными возможностями программирования, работавший от электричества. Цузе сконструировал Z2, чтобы исправить недостатки первой машины. Для сохранения чисел и представления чисел с фиксированной запятой в ней использовались реле. Позднее, по совету Хельмута Шрайера, Цузе спроектировал машину Z3, в которой использовались электронные лампы. Эта машина работала без сбоев.
Она была представлена в Институте аэродинамических исследований 5 декабря 1941 года. В машине Z3 ввод данных выполнялся с клавиатуры, а управляющая программа записывалась на целлулоидной ленте. В памяти машины можно было сохранять до 64 чисел, представляемых в двоичной системе счисления с плавающей запятой. Для хранения каждого числа использовалось 22 бита: 1 бит для знака, 7 для показателя степени, 14 для мантиссы. Цузе обнаружил, что в представлении числа с плавающей запятой первый бит может быть всегда равным единице — достаточно подобрать соответствующий показатель степени. Эта форма представления чисел используется и сейчас. С ее помощью можно «сэкономить» один бит, который всегда равен единице. Благодаря открытию Цузе машина Z3 могла работать с числами, мантисса которых представлялась 13 битами. Тем не менее эта машина имела одно важное ограничение: в ней не были реализованы условные переходы. Скорость вычислений составляла три-четыре операции сложения в секунду, умножение выполнялось за четыре-пять секунд.
По заказу Института аэродинамических исследований Цузе немедленно приступил к работе над Z4. Окончательный вариант машины был представлен 28 апреля 1945 года. В памяти машины можно было сохранять 1024 32-битных числа. В ней также были реализованы подпрограммы и условные переходы. Кроме того, был реализован механизм чтения двух инструкций, следующих за данной. Таким образом, операции можно было менять местами, если это не влияло на результат, что обеспечивало экономию времени. Эта процедура была реализована в более поздних компьютерах и получила название lookahead («просмотр вперед»).
Перед самым окончанием войны Цузе переехал на ферму в Альпах и начал работу над докторской диссертацией, озаглавленной «Общая теория вычислений». В этой диссертации, завершенной в 1946 году, описывался язык Планкалкюль (от нем.