Юрий Ревич - Занимательная микроэлектроника

• отрицание для одного операнда (операция «НЕ» или «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= ( AOR В) 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» — горящий. Легко понять, что работать эти схемы будут именно так, как указано в правилах для соответствующих логических операций. Для технических устройств, которые, как мы увидим далее, могут выполнять функции, отличающиеся от базового набора булевых операций, правила соответствия входов и выхода называются «таблицами истинности» (или «таблицами состояния») и оформляются в следующем виде: