Глава 1. Основы теории переключательных функций

1.1. Аксиомы, основные теоремы и тождества алгебры логики

Основы алгебры логики были заложены в середине XIX века трудами английского математика Дж. Буля [1, 2], по имени которого она называется также булевой алгеброй. Ясное понимание принципов, лежащих в ее основе, исключительно важно для овладения формальными методами проектирования цифровых систем. Начало использованию алгебры логики для синтеза; переключательных (релейных) схем было положено в 1938 г. работами американского ученого К. Шеннона [3,4].

Аксиомы алгебры логики. В алгебре логики рассматриваются переменные, которые могут принимать только два значения — 0 и 1. В дальнейшем переменные будем обозначать латинскими буквами x, y, z, ... . В алгебре логики определены отношение эквивалентности и три операции [5]: дизъюнкция (операция ИЛИ), обозначаемая знаком V, конъюнкция (операция И), обозначаемая знаком или точкой, которую можно опускать (например, и отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или над элементами 0 и 1 (например, ). Отношение эквивалентности удовлетворяет следующим свойствам:

Из отношения эквивалентности следует принцип подстановки: если то в любой формуле, содержащей х, вместо х

можно подставить у, и в результате будет получена эквивалентная формула.

Алгебра логики определяется следующей системой аксиом:

Аксиома (1.1) является утверждением того, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (1.2) - (1.4) определяют операции дизъюнкции и конъюнкции, а аксиома (1.5) — операцию отрицания. Если в аксиомах (1.2) -(1.5), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы пары получится другая. Это свойство называется принципом двойственности.

Теоремы и тождества алгебры логики. С помощью аксиом алгебры логики можно доказать целый ряд теорем и тождеств. Одним из эффективных методов доказательства теорем является метод перебора всех значений переменных: если теорема истинна, то с учетом (1.2) - (1.5) уравнение, формулирующее утверждение теоремы, должно быть истинно при подстановке любых значений переменных в обе его части. Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1. Так, методом перебора легко убедиться в справедливости следующих теорем:

идемпотентные законы

коммутативные законы

ассоциативные законы

дистрибутивные законы

законы отрицания

законы двойственности (теоремы де Моргана)

закон двойного отрицания

законы поглощения (абсорбция)

операции склеивания

операции обобщенного склеивания

Теоремы (1.6) - (1.13) и (1.15) - (1.18) записаны парами, причем каждая из теорем пары двойственна другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, т.е. путем взаимной замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если

они имеются. Теорема (1.14) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции).

Все теоремы могут быть доказаны аналитически или методом перебора. В табл. 1.1 приведено доказательство одного из тождеств (1.13) методом перебора.

Таблица 1.1. (см. скан) Пример использования метода перебора

Если в логическое выражение входят операции дизъюнкции и конъюнкции, то следует соблюдать порядок выполнения операций: сначала выполняется операция конъюнкции, а затем — операция дизъюнкции. Этим устанавливается иерархия операций: конъюнкция — старшая операция, дизъюнкция — младшая. В сложных логических выражениях для задания порядка выполнения операций используются скобки. Для упрощения записи выражений принято опускать те скобки, которые являются только подтверждением иерархии операций, например:

Но скобки нельзя опустить в выражении поскольку

Некоторые тебремы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в соотношениях (1.6), (1.10) - (1.12) и (1.15) - (1.18) правая часть проще левой, поэтому, произведя в логических выражениях соответствующие преобразования, можно добиться существенного их упрощения. С этой целью особенно часто используются тождества (1.15)-(1.18).

Операции дизъюнкции, конъюнкции и отрицания легко реализовать довольно простыми контактными (релейными) цепями и электронными схемами с односторонней проводимостью, имеющими конечное число входов и один выход и называемыми логическими элементами (ЛЭ).

Операция сумма по модулю два. Кроме основных операций алгебры логики (дизъюнкция, конъюнкция, отрицание), определяемых аксиомами (1.2) - (1.5), целесообразно оперировать более сложными операциями, такими как ИЛИ-НЕ, И-НЕ

(1.13) и сумма по модулю два. Эти операции, естественно, определяются через основные операции алгебры логики.

Операция сумма по модулю два (исключающее ИЛИ, логическая неравнозначность) обозначается символом и определяется соотношением

Легко убедиться, что Это выражение также можно использовать для определения операции сумма по модулю два. Очевидно, что На основании аксиом алгебры логики (1.2) - (1.5) можно показать, что

Из данных соотношений следует, что значение совпадает со значением младшего разряда суммы двух двоичных чисел, где — значения младших разрядов этих чисел. Соответственно этому значение разряда суммы двух двоичных чисел будет определяться значением где значения разрядов двоичных чисел, а перенос в разряд из предыдущего -го разряда.

Операция сумма по модулю два коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции, т.е.

Для операции сумма по модулю два справедливы также тождества

где для всех (формула справедлива только для одной переменной, повторенной раз).

Для упрощения выражений, содержащих операцию 0, полезны тождества

Операция сумма по модулю два играет особо важную роль в теории переключательных функций.

У начинающих изучать алгебру логики часто возникают затруднения с порядком выполнения операций в выражениях, в которых используется операция сумма по модулю два. В этом случае до преобразования логического выражения рекомендуется проставить скобки, задающие в явном виде порядок их выполнения, руководствуясь правилами:

что следует из определения (1.19) операции сумма по модулю два и иерархии операций конъюнкции и дизъюнкции. После приобретения практических навыков некоторые скобки можно будет опускать, чтобы излишне не усложнять аналитические выражения.

Алгебра логики тесно связана с теорией множеств [5]. Вместо операций дизъюнкции, конъюнкции и отрицания в теории множеств используются операции объединения, пересечения и дополнения. Элементам 0 и 1 соответствуют пустое множество и множество, состоящее из всех его элементов.