Замкнутые классы. Монотонные функции. Критерий функциональной полноты

Метод установления функциональной полноты системы путем ее сведения к заведомо полной системе , рассмотренный в предыдущей главе, удобен для человека, но не поддается алгоритмизации. Поэтому, в общем случае, для установления полноты системы используют критерий полноты Поста-Яблонского, который будет рассмотрен в данной главе. Критерий основан на анализе свойств функций, образующих , и использует понятие замкнутого класса.

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

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