щий решатель Задач» (несомненно, это была первая попытка построения «думающей машины»). Затем формализацией логики занимался Лейбниц и многие другие, пока, в конце концов, все не сошлось в двух работах английского математика Джорджа Буля, который жил и работал уже в середине XIX века.
Заметки на полях
Любопытно название второй из этих работ — «Исследование законов мышления», первая же работа называлась поскромнее, но без «мышления» и тут не обошлось — в названии фигурировало слово «рассуждения». Значит, и сам Буль, и все его предшественники в течение более чем двух тысяч лет, и еще сто с лишним лет после него — никто так и не усомнился, что в основе мышления лежит именно та логика, которая называется «аристотелевой». Это была такая, как сейчас модно говорить, парадигма. И лишь в XX веке, после работ Геделя и Тьюринга, и особенно в связи с благополучно провалившимися (как и у Луллия за 700 лет до того) попытками создания «искусственного интеллекта», до ученых наконец начало доходить, что мышление вовсе не имеет логической природы, а логика есть лишь удобный способ сделать свои рассуждения доступными окружающим, т. е. перевести их в вербальную форму.
Рис. 7.1.Клод Элвуд Шеннон (Claude Elwood Shannon, 1916–2001).
Фото Lucent Technologies Inc./Bell Labs
Главное для нашего повествования свойство логики обнаружил в своей магистерской диссертации от 1940 года великий Клод Шеннон (которому, как автору теории информации, мы вообще обязаны самим существованием цифрового века). Оказалось, что абстрактные булевы законы, не интересные, в общем, никому, кроме математиков (да и те сначала сомневались, стоит ли причислять логику к математическим дисциплинам), в точности совпадают с принципами функционирования реально существующих объектов — релейных электрических схем.
Что самое поразительное — все компоненты, необходимые для моделирования законов логики с помощью электрических устройств (реле, выключатели), были известны еще до опубликования Булем своих работ, но в течение еще почти ста лет никто не обращал на это внимание. Шеннон скромно утверждал, что случилось так, что до него просто никто не владел математикой и электротехникой одновременно. Не обратил на это внимание даже Чарльз Бэббидж, сконструировавший еще задолго до работ Буля механическую вычислительную («аналитическую») машину, а ведь был знаком и с самим Булем и с его работами!
Но довольно рассуждений, перейдем к практике.
Основные операции алгебры Буля
Булева алгебра имеет дело с абстрактными логическими переменными (операндами), для которых определены некоторые операции, подчиняющиеся определенным правилам:
• логическое сложение двух операндов (операция объединения, операция «ИЛИ» или «OR», обозначается обычным знаком сложения);
• логическое умножение двух операндов (операция пересечения, операция «И» или «AND», мы будем обозначать ее крестиком, чтобы отличить от обычного умножения)[5];
• отрицание для одного операнда (операция «НЕ» или «NOT», обозначается черточкой над символом операнда).
Остальные операции могут быть выведены из сочетания этих трех основных. Любая конкретная интерпретация булевых операндов — математическая или техническая — должна отвечать этим установленным правилам. Например, оказалось, что логическим операндам отвечают множества (отсюда названия операций «пересечение» и «объединение»). Но нас больше интересуют технические приложения, которые, однако, ничего не меняют в принципе: операция пересечения множеств совершенно адекватна операции «И» с логическими переменными, как и соответствующей манипуляции с выключателями в электрической сети, о чем далее.
В булевой алгебре многое совпадает с обычной (например, правила типа А + В = В + А; или А + (В + С) = (А + В) + С), но для нас важны как раз отличия. Вот они: А + А = А (а не 2А, как было бы в обычной алгебре), а также А х А = А (а не А2). Последнее уравнение в обычной алгебре, впрочем, имело бы решение, причем сразу два: 0 и 1. Таким путем обычно и переходят к интерпретации булевых операндов, как логических переменных, которые могут иметь только два состояния: 1 и 0 или «правда» (True) и «ложь» (False). Тогда мы действительно можем с помощью определенных выше действий записывать некоторые словесные высказывания в виде уравнений и вычислять их значения, что дает иллюзию формального воспроизведения процесса мышления. Но сначала надо определить, как и в обычной алгебре, правила, которым подчиняются операции, т. е. таблицы логического сложения и умножения. Они таковы:
0 + 0 = 0 0 x 0 = 0
0 + 1 = 1 0 x 1 = 0
1 + 0 = 1 1 x 0 = 0
1 + 1 = 1 1 x 1 = 1
Операция отрицания «НЕ», понятно, меняет 1 на 0 и наоборот.
Примеры записи логических выражений обычно приводят для каких-нибудь бытовых высказываний, но мы не будем разбирать все эти любимые научно-популярными авторами схоластические доказательства утверждений вроде «все лебеди черные», а приведем более близкий к практике пример из области школьной математики.
Пусть высказывание состоит в следующем: <а меньше нуля или х больше единицы и у меньше двух». Как записать это высказывание? Введем следующие логические переменные: А = (х < 0); В = (х > 1); С = (у < 2). Как мы видим, все они могут принимать только два значения — «правда» (если условие выполняется) и «ложь» (если не выполняется). Обозначим значение всего выражения через D. Тогда высказывание запишется в виде логического уравнения:
D = (А + В) х С. (7.1)
Возможны другие варианты записи этого выражения:
• D = (A ИЛИ В) И С (по-русски);
• D = (A OR В) AND С (по-английски);
• D = ((x<0) or (x> 1)) and (у< 2) (язык программирования Pascal);
• D = ((x< 0) | (x> 1)) & (у < 2) (язык программирования С).
Рассмотрим подробнее возможные варианты решения уравнения 7.1. Пусть х = 0,5, у = 1. Чему будет равно D в этом случае? Очевидно, что выражение (А + В) примет значение «ложь» (или 0), т. к. x не удовлетворяет ни одному из условий А и В. А переменная С примет значение «правда» (или 1), но результату это уже не поможет, т. к. произведение 0 на 1, согласно таблице логического умножения, равно 0. Таким образом, D в данном случае есть «ложь».
Если же принять значение х = — 0,5, то D примет значение «правда». Интересный оборот примут события, если вместо «OR» между А и В подставить «AND» — легко догадаться, что выражение в скобках тогда не выполнится ни при каком значении х, т. к. условия «х меньше 0» и «х больше 1» взаимоисключающие. Потому результирующее условие D всегда будет принимать значение 0, т. е. «ложь». Но вот если мы изменим выражение следующим образом:
(7.2)
т. е. инвертируем выражение в скобках с помощью операции «НЕ», то получим обратный результат: D всегда будет «правдой» (черточкой над символом или выражением, напомним, изображается инверсия). Интересно, что тот же самый результат мы получим, если запишем выражение следующим образом:
D = (A¯ + B¯) x C. (7.3)
Это свойство выражается в т. н. правилах де Моргана (учителя Буля):
Отметим, что из таблиц логического умножения и сложения вытекает одно Любопытное следствие. Дело в том, что ассоциация значения «ложь» с нулем, & «правды» — с единицей есть действие вполне произвольное, ничто не мешает нам поступить наоборот. В первом случае логика носит название «положительной», во втором — «отрицательной». Так вот, замена положительной логики на отрицательную приводит к тому, что все операции «ИЛИ» заменяются на «И» и наоборот (рассмотрите таблицы внимательно). А вот операция «НЕ» к такой замене индифферентна, т. к. 0 меняется на 1 в любой логике. В дальнейшем, если это специально не оговорено, мы всегда будем Иметь в виду положительную логику.
Далее приведены несколько соотношений, которые вместе с правилами де Моргана помогают создавать и оптимизировать логические схемы. Некоторые из них очевидны, некоторые же — совсем нет.
А х В х С = (А х В) х С = А х (В х С) (ассоциативный закон умножения);
А + В + С = (А + В) + С = А + (В + С) (ассоциативный закон сложения);
А х А = А; А + А = А;
А + А¯ = 1; А х А¯ = 0;
А x 1 = А; А + 1 = 1;
А x 0 = 0; А + 0 = А;
А + А х В = А;
А х (В + С) = А х В + А х С;
А + В х С = (А + В) х (А + В);
1¯ = 0; 0 = 1¯.
Булева алгебра на выключателях и реле
Для того чтобы представить булевы переменные и операции над ними с помощью технических устройств (то, что сделал Клод Шеннон в своей диссертации), надо придумать схемы, которые воспроизводили бы эти операции согласно вышеизложенным правилам. Самый простые варианты таких схем показаны на рис. 7.2.
Рис. 7.2. Схемы реализации логических функций на кнопочных выключателях
Здесь операции «И» и «ИЛИ» выполняются обычными кнопками без фиксации. Каждая из них соответствует одной логической переменной, которая принимает значение «1», если контакты замкнуты, и «О» — если разомкнуты. На выходе значению «О» соответствует погасший светодиод, «I» — горящий. Легко понять, что работать эти схемы будут именно так, как указано в правилах для соответствующих логических операций. Для технических устройств, которые, как мы увидим далее, могут выполнять функции, отличающиеся от базового набора булевых операций, правила соответствия вход