Функциональная полнота систем

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

Например, . Эта система функционально полна, так как любая функция имеет булеву формулу.

Теорема.

Произвольная система будет функционально полной, если она сводится к функционально полной системе .

Это означает, что через функции системы можно выразить все функции системы .

Лемма 1.

Если функция – немонотонна, то подстановкой n-1 константы из нее можно получить отрицание.