Правила алгебры логики позволяют преобразовать логическую функцию к виду, удобному для реализации в виде логического устройства.
Например, задана функция
(22)
Для реализации функции в данном виде требуется два инвертора НЕ, три трехвходовых элемента 3И, один трехвходовый элемент 3ИЛИ:
Проведем эквивалентные преобразования на основании правил (6), (13), (19)
(23)
Очевидно, что после преобразования функция (22) значительно упростилась (23). Для ее реализации достаточно иметь один двухвходовый элемент 2И, один двухвходовый элемент 2ИЛИ (рис. б). Обе схемы (рис. а, б) позволяют реализовать одну и ту же функцию у.
При рассмотрении законов булевой алгебры использовались только три элементарные функции (НЕ, И, ИЛИ). Всего же существует 4 функции одной переменной и 16 функций двух переменных. Ранее отмечалось, что с помощью элементарных функций можно построить любую сложную логическую функцию.
Определение. Функционально полная система (базис) — совокупность логических элементов, которая позволяет реализовать любую логическую схему произвольной сложности.
Для построения сложной логической функции нет необходимости использовать все элементарные функции. Допустимо ограничить набор элементарных функций, исключая из него те элементы, которые можно выразить через другие. Последовательно исключая из базиса функции, получают минимальный базис.
Определение. Под минимальным базисом понимают такой набор функций, исключение из которого любой функции превращает полную систему в неполную.
Возможны различные базисы, отличающиеся друг от друга числом входящих в них функций и видом этих функций. Выбор того или иного базиса для построения логических устройств обусловлен тем, насколько экономически удобно и просто выполнить элементы, технически реализующие входящие в базис функции, и все логическое устройство в целом.
Через три логические функции инверсии (НЕ), конъюнкции (И), дизъюнкции (ИЛИ) можно выразить любую элементарную функцию и построить любое сложное логическое устройство. Набор из трех функций (НЕ, И, ИЛИ) является базисом. Однако, базис (НЕ, И, ИЛИ) не является минимальным. Из него можно исключить одну из функций И либо ИЛИ. Наборы (НЕ, И), а также (НЕ, ИЛИ) из двух функций служат базисами. Действительно функцию И можно реализовать через функции (НЕ, ИЛИ):
.
Функцию ИЛИ можно реализовать через функции (НЕ, И):
.
Ограничиваясь базисами (НЕ, И); (НЕ, ИЛИ) для выполнения исключенной одной операции требуется проводить дополнительно три операции НЕ, что экономически нецелесообразно. Поэтому на практике часто используют неминимальный базис трех функций (НЕ, И, ИЛИ).
Довольно удобно технически реализуются на микросхемах логические элементы, совмещающие в себе указанные функции. Удобство объясняется тем, что транзистор инвертирует фазу входного сигнала, изменяет ее на 180°. Это элементы И-НЕ (штрих Шеффера) и ИЛИ-НЕ (стрелка Пирса).
Каждый из элементов (И-НЕ), (ИЛИ-НЕ) в отдельности является функционально полным базисом, позволяет синтезировать любое сколь угодно сложное устройство. Рассмотрим реализацию функций НЕ, И, ИЛИ в базисе (ИЛИ-НЕ):
(24)
Для инверсии необходимо подать входной сигнал на оба входа. Для конъюнкции — сначала инвертировать входные сигналы, а затем применить операцию ИЛИ-НЕ. Для дизъюнкции — провести операцию ИЛИ-НЕ, после чего инвертировать полученный результат:
В базисе (И-НЕ) функции НЕ, И, ИЛИ получают следующим образом:
(25)
Легко заметить, что формулы (24), (25) подобны. Их схемное решение показано на рис.
Привлекательность базисов из одной логической функции (И-НЕ) либо (ИЛИ-НЕ) заключается в том, что все логическое устройство построено только на однотипных логических элементах. Получаем логическую схему, которая обладает регулярной структурой. Необходимо только осуществить коммутацию одинаковых логических элементов. Базисы на логических элементах (И-НЕ), (ИЛИ-НЕ) широко используются при проектировании устройств, удобны для реализации в больших интегральных схемах. Уменьшение номенклатуры до одного типа, таким образом, облегчает проектирование устройств. Дополнительные инверторы на входах улучшают нагрузочную способность и служат для формирования сигналов лог. 1 и лог. 0 достаточного уровня.