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

В булевой алгебре многое совпадает с обычной (например, правила типа А + В = В + А; или А + (В + С) = (А + В) + С), но для нас важны как раз отличия. Вот они: А + А = А (а не 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 в любой логике. В дальнейшем, если это специально не оговорено, мы всегда будем Иметь в виду положительную логику.

Далее приведены несколько соотношений, которые вместе с правилами де Моргана помогают создавать и оптимизировать логические схемы. Некоторые из них очевидны, некоторые же — совсем нет.

Ах Вх С= ( Ах В) х С= Ах ( Вх С) (ассоциативный закон умножения);