Логический элемент Булева операция

x₁x₂

`x₁

Входы одних логических элементов можно подсоединить к выходам других элементов и получить логическую сеть. Логическая сеть реализует некоторую булеву функцию. В случае контактных цепей выражение для функции с наименьшим числом вхождений переменных дает реализацию цепи с наименьшим количеством контактов. Простота логической сети может определяться как числом логических элементов, так и числом входов логических элементов. Кроме того, логические элементы характеризуются запаздыванием, поэтому быстродействие сети пропорционально числу ступеней сети (т.е. максимальному числу логических элементов, через которые проходит входной сигнал без учета инверторов). Представление функции в ДНФ дает двухступенчатую быстродействующую реализацию. Поэтому, для упрощения логической сети можно использовать минимизацию булевой функции методом Квайна, но при этом ввести понятие «стоимости» простой импликанты. В задаче минимизации числа логических элементов стоимость простой импликанты, содержащей две и более переменные, принимается равной 1, а стоимость простой импликанты из одной переменной – 0 (т.к. для ее реализации не требуется логический элемент «и»). В задаче минимизации общего числа входов логических элементов стоимость простой импликанты складывает из входов логического элемента «и», реализующего импликанту, и входов логического элемента «или». При построении минимальной ДНФ по множеству простых импликант, среди простых импликант выбирается множество с суммарной минимальной стоимостью простых импликант.