Пример. набор из трех функций (И, ИЛИ, НЕ) является базисом

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

Например, задана функция

Для реализации функции в данном виде требуется два инвертора НЕ, три трехвходовых элемента ЗИ, один трехвходовый элемент ЗИЛИ (рис. 1).

Рис. 1

Проведем эквивалентные преобразования с использованием закона поглощения

Очевидно, что после преобразования функция значительно упростилась. Для реализации теперь достаточно иметь один двухвходовый элемент 2И, один двухвходовый элемент 2ИЛИ (рис.3). Обе схемы позволяют реализовать одну и ту же функцию.

Всего же существует 4 функции одной переменной и 16 функций двух переменных. С помощью элементарных функций можно построить любую сложную логическую функцию. При рассмотрении законов булевой алгебры использовались только три элементарные функции (НЕ, И, ИЛИ). Следовательно, в наборе элементарных функций существует избыточность.

Базис

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

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

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

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

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

Базис (И, ИЛИ, НЕ) не является минимальным. Используя закон де Моргана из него можно исключить одну из функций И либо ИЛИ. Действительно функцию И можно реализовать через функции (НЕ, ИЛИ):

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

Функцию ИЛИ тоже можно реализовать через функции (НЕ, И):

Наборы (НЕ, И) и (НЕ, ИЛИ) так же являются базисами.

Обычно логические схемы строятся на основе инвертирующих усилителей на транзисторах. Технически удобно изготавливать логические элементы совмещающие в себе сразу две функции например И-НЕ или ИЛИ-НЕ. Каждый из элементов И-НЕ (штрих Шеффера) и ИЛИ-НЕ (стрелка Пирса) в отдельности является функционально полным базисом и позволяет синтезировать любое сколь угодно сложное логическое устройство.

Рассмотрим, для примера, реализацию функций НЕ, ИЛИ, И в базисе (И-НЕ):

1. Для реализации инверсии НЕ достаточно просто подать входной сигнал на оба входа одновременно.

.

2. Для реализации дизъюнкции ИЛИ с помощью схемы И-НЕ — воспользоваться законом де Моргана, т.е. сначала инвертировать входные сигналы, а потом над результатами выполнить операцию И-НЕ.

3. Для конъюнкции — сначала применить операцию И-НЕ, а затем инвертировать входные сигналы.

Их схемное решение показано на рис. 2.

Рис. 2

Привлекательность базисов из одной логической функции (И-НЕ) либо (ИЛИ-НЕ) заключается в том, что все логическое устройство построено только на однотипных логических элементах. Получаем логическую схему, которая обладает регулярной структурой. Необходимо только осуществить коммутацию одинаковых логических элементов. Базисы на логических элементах (И-НЕ), (ИЛИ-НЕ) широко используются при проектировании больших интегральных микросхем, потому что уменьшают количество типов элементов и технологий для их реализации.

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