Функционально
полными называют наборы логических элементов, пользуясь которыми можно
реализовать любую двоичную функцию. Функционально полный набор может
состоять и из одного элемента. Функция, реализуемая таким элементом,
называется шефферовой. К универсальным, шефферовым относятся логические
элементы, реализующие функции ИЛИ-НЕ и И-НЕ
Существуют наборы логических функций, с помощью которых
можно выразить любые другие логические функции. Такие наборы называются
функционально полными наборами или базисами. Наиболее известный и
изученный базис - набор И, ИЛИ, НЕ (конъюнкция, дизъюнкция, отрицание).
Множество всех логических функций, на котором определены эти три
операции, называется булевой алгеброй. Операции и формулы булевой
алгебры также часто называют булевыми
Наборы {ИЛИ, НЕ} и {И, НЕ} также являются функционально
полными. Отсюда следует, что базисом может служить одиночная функция
стрелка Пирса или штрих Шеффера.
С лекции Федосеева: система булевых функций (W) называется
функционально полной, если для любой функции может быть построена
равная ей функция путём суперпозиции из W от аргументов x1…xn.