Занимательная электроника

Рис. 14.1. Клод Элвуд Шеннон (Claude Elwood Shannon), 1916–2001

_{Фото Lucent Technologies Inc /Bell Labs}

Основные операции алгебры Буля

Булева алгебра имеет дело с абстрактными логическими переменными. Эти переменные можно интерпретировать по-разному, но интерпретацию мы пока отложим.

Вне зависимости от интерпретации, для логических переменных определены некоторые операции, подчиняющиеся определенным правилам. Базовые операции такие:

□ операция логического сложения двух операндов — операция объединения, операция «ИЛИ» («OR»), обозначается обычным знаком сложения;

□ операция логического умножения двух операндов — операция пересечения, операция «И» («AND»), мы будем обозначать ее крестиком, чтобы отличить от обычного умножения;

□ операция отрицания для одного операнда — операция «НЕ» («NOT»), обозначается черточкой над символом операнда.

В математике операция логического сложения (дизъюнкция) обозначается еще знаком v, а умножения (конъюнкция) — ^. Кроме того, операция умножения часто обозначается знаком &, и это обозначение нам встретится, когда мы перейдем к микросхемам. Остальные операции могут быть записаны как сочетания этих трех основных.

Любая конкретная интерпретация булевых операндов — математическая или техническая — должна отвечать правилам булевой алгебры. Например, оказалось, что этим правилам отвечают множества (отсюда другие названия тех же операций: «пересечение» и «объединение»). Программисты имеют дело с логическими переменными 0 и 1, которые также есть одно из представлений булевых операндов.

Следует отчетливо понимать, что вне зависимости от интерпретации (включая и напряжения в релейных цепях по Шеннону), любые булевы объекты ведут себя одинаково: так, операция пересечения множеств совершенно адекватна операции «И» с логическими переменными или соответствующей манипуляции с выключателями в электрической сети.

В булевой алгебре многое совпадает с обычной — например, справедливы правила типа А + В = В + А или А + (В + С) = (А + В) + С), но для нас важны как раз отличия.

Вот они: А + А = А (а не 2А, как было бы в обычной алгебре), а также А х А = А (а не А²). Последнее уравнение в обычной алгебре, впрочем, имело бы решение, причем сразу два: 0 и 1. Таким путем обычно и переходят к интерпретации булевых операндов, как логических переменных, которые могут иметь только два состояния: 1 и 0 или «правда» (true) и «ложь» (false). В этом представлении мы действительно можем попробовать с помощью определенных ранее операций записывать некоторые высказывания в виде уравнений и вычислять их значения, что дает иллюзию формального воспроизведения процесса мышления. Но сначала надо определить, как и в обычной алгебре, правила, которым подчиняются операции, — т. е. таблицу логического сложения и таблицу логического умножения. Они таковы:

Операция отрицания «НЕ» меняет 1 на 0 и наоборот.

Примеры записи логических выражений обычно приводят для каких-нибудь бытовых высказываний, но мы поступим нетрадиционно: приведем пример из области математики. Пусть высказывание состоит в следующем:«x меньше нуля или х больше 1 и у меньше 2». Как записать это высказывание? Введем следующие логические переменные: А = (х < 0); В = (х > 1); С = (у < 2). Как мы видим, все они могут принимать только два значения: «правда» (если условие выполняется) и «ложь» (если не выполняется). Обозначим значение всего выражения через D. Тогда высказывание записывается так:

D = (A + B) x C (1)

Можно записать и так:

D = (A ИЛИ B) И C

Или так:

D = (A OR B) AND C

Или, наконец, так:

D = ((х < 0) OR (х > 1)) AND (у < 2)

Последняя запись хорошо знакома всем, кто изучал язык программирования Pascal. На языке С та же запись выглядит непонятнее:

D =((x < 0)||(x > 1))&&(y < 2)

* * *