Функционально полные системы переключательных функций

Система элементарных булевых функций φ ₁, φ ₂,…., φ _m называется функционально полной, или базисо м, если любую функцию алгебры логики можно представить в виде их суперпозиции функций. Имея логические элементы, осуществляющие операции f ₀ – f ₁₅ можно выполнить любую сложную функцию. Однако условие наличия 16 различных типов логических элементов, каждый из которых реализует одну из 16 элементарных операций, является условием, достаточным, но не необходимым. Для синтеза логического устройства любой сложности можно ограничиваться меньшим набором элементарных функций. Последовательно исключая из базиса избыточные функции, можно получить минимальный базис. Под минимальным базисом понимают такой набор функций, исключение из которого любой функций превращает этот набор в неполную систему функций.

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

Функционально полными системами являются базисы:

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

3.6. Минимизация переключательных функций