Применение алгебры логики к синтезу и анализу цифровых (релейных) схем

Алгебра логики, созданная в XIX в. известным английским математиком Джорджем Булем, являетсяалгеброй двух чисел. Каждый отдельный аргумент в алгебре логики может принимать только два значения: «истинно», условно обозначаемое 1, и «ложно», условно обозначаемое 0. Алгебра логики занимается исчислением высказываний или предложений, которые могут рассматриваться как истинные или ложные.

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

Так как функции, выполняемые элементами цифрового устрой­ства, можно выразить с помощью логических формул, то такие функции называются логическими, а элементы, реализующие эти логические функции, — логическими элементами.

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

Выход логического элемента ИЛИ имеет ВЫСОКИЙ уровень, если ВЫСОКИЙ уровень присутствует хотя бы на одном из его входов. Этот элемент реализует дизъюнкцию – логическую операцию ИЛИ. На рис. 3.1, показан логический элемент ИЛИ на 2 входа (слева – изображение в иностранной литературе, справа – в отечественной, а также иллюстрация функции ИЛИ с помощью контактов). В общем случае число входов не ограничено, однако в стандартном корпусе микросхемы обычно размещаются четыре 2-входовых элемента, три 3-входовых или два 4-входовых. Для обозначения операции ИЛИ в булевой алгебре и с пользуются символы +.Функция «А ИЛИ В» записывается как А + В(Х₁ +Х₂). Таблица состояний для элемента ИЛИ выглядит следующим образом:

Выход логического элемента И имеет ВЫСОКИЙ уровень только в том случае, если ВЫСОКИЙ уровень присутствует на всех его входах. Этот элемент реализует конъюнкцию – логическую операцию И. Символическое изображение элемента И приведено на рис. 3.2 (слева – изображение в иностранной лите- ратуре, справа – в отечественной, а также иллюстрация функции И с помощью контактов). Выпускаемые промышенностью логические элементы И, так же как и элементы ИЛИ, могут иметь 2, 3, 4, а иногда и большее число входов. Для обозначения операции И в булевой алгебре используются символы . Функция «А И В» записывается как А В , или просто АВ. Таблица состояний для элемента И выглядит следующим образом:

Часто бывает нужно получить дополнение (инверсию) логического сигнала. Эту функцию выполняет инвертор — логический элемент, имеющий толькоодин вход. Символическое изображение инвертора (элемента НЕ) приведено на рис. 3.3 (слева – изображение в иностранной литературе, справа – в отечественной).

Для обозначения операций НЕ в булевой алгебре используется черта над символом, а иногда апостроф; «НЕ А» записывается как или как А'.

Таблица состояний для элемента НЕ выглядит следующим образом:

Логические элементы могут совмещать инвертирование с выполнением функций И и ИЛИ. Как вскоре будет показано, такие элементы имеют более широкое распространение, чем просто И и ИЛИ (рис. 3.4).

Таблицы состояний элементов И-НЕ и ИЛИ-НЕ выглядят следующим образом:

Существенный интерес представляет логическая функция «Исключающее ИЛИ», хотя она и не относится к числу основных (рис. 3.5). На выходе элемента «Исключающего ИЛИ» ВЫСОКИЙ уровень действует на выходе тогда, когда входы имеют различное состояние. Этот элемент может иметь только два входа. Операция «Исключающее ИЛИ» идентична сложению 2-х бит по модулю 2. Таблица состояний:

Этот элемент также может совмещать инвертирование с выполнением основной функции «Исключающее ИЛИ-НЕ», и тогда ВЫСОКИЙ уровень действует на выходе тогда, когда входы имеют одинаковое состояние.

3.4. Основные законы алгебры логики

В алгебре логики существует четыре пары основных законов: два переместительных (коммутативных), два сочетательных (ассоциативных), два распределительных (дистрибутивных) и два закона инверсии.

Эти законы устанавливают равносильность различных выражений, которые можно взаимно заменять подобно тому, как это делается в тождествах обычной алгебры. В качестве символа равносильности применяется символ «=», аналогичный алгебраическому символу равенства.

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

Переместительные законы показывают, что для логической суммы и логического произведения порядок расположения переменных не играет никакой роли.

Переместительный закон записывается следующим образом:

относительно сложения ,

относительно умножения .

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

Сочетательные законы записываются так:

относительно сложения ,

относительно умножения .

Распределительный закон относительно сложения указывает на то, что общий множитель можно выносить за скобки: . Этот закон, так же как переместительные и сочетательные законы, подобен аналогичному закону обычной алгебры.

Распределительный же закон умножения не имеет аналога в обычной алгебре: .

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

Из приведённых выше основных законов алгебры логики и определений конъюнкции и дизъюнкции вытекает ряд следствий. Приводим важнейшие из них:

[блокировка элемента И ],

[деблокировка элемента И ],

[элемент И],

,

[элемент ИЛИ],

,

,

[элемент ИЛИ],

,

,

,

,

,

.

Справедливость приведённых формул может быть легко проверена, например, путём начертания соответствующих правым и левым частям равенств релейно-контактных схем. При этом следует иметь в виду, что для таких схем 0 означает постоянно разомкнутую цепь, а 1 — постоянно замкнутую цепь.

3.5. Синтез однотактных схем и их минимизация

Выше отмечалось, что синтез релейных схем сводится в основном к составлению структурной формулы (аналитического выражения), описывающего логические функции, которые должны выполняться данным устройством. Таким образом, при синтезировании схемы должны быть известны (заданы) некоторые логические функции, комбинируя которые, можно получить логическую функцию всего устройства.

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

Существует, довольно много методов минимизации булевых функций, однако, остановимся на двух из них (алгебраическом и использование карт Карно), получивших наибольшее распространение.

Алгебраический метод рассмотрим на примере. Допустим дана (составлена) таблица срабатывания:

Булева функция составлена по условиям срабатывания:

Таким образом, проведя алгебраические преобразования, с учётом соотношений, полученных в предыдущем параграфе, получена минимальная форма исходной функции. На рис.3.6 приведена схемная реализация полученной функции.