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

Определение

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

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

Например, полными системами являются: , , но не являются полными и .

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

Система является полной, если в каждом столбце таблицы есть хотя бы один "-".
В частности, если функция не входит ни в один из замкнутых классов, она сама образует полную систему (например, функция – штрих Шеффера).