Вопрос о полноте системы – один из главных в теории булевых функций.
Во-первых, это интересная научная задача.
А во-вторых, для булевых функций актуальна проблема аппаратной реализации с помощью какой-либо схемы функциональных элементов.
Для решения этой проблемы достаточно иметь набор простейших элементов, которые образуют полную систему.
/p>
Определение
Система булевых функций является полной, если любую булеву функцию можно выразить через функции этой системы с помощью операции суперпозиции.
Для определения полноты системы пользуются критерием Поста:
система является функционально полной тогда и только тогда, когда целиком не принадлежит ни одному из замкнутых классов.
Например, полными системами являются:
,
,
но не являются полными
и
.
Для удобства и наглядности, при определении полноты системы, строят критериальную таблицу с названиями классов в заголовках столбцов и функциями в заголовках строк. Для каждой функции определяется принадлежность к каждому из замкнутых классов.
Если функция принадлежит классу, то ставится знак "+", иначе - знак "-". Пример заполненной таблицы:
Система является полной, если в каждом столбце таблицы есть хотя бы один "-".
В частности, если функция не входит ни в один из замкнутых классов, она сама образует полную систему
(например, функция
– штрих Шеффера).