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

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

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

Теорема.

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

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

Лемма 1.

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

Лемма 2.

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

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

Например, – функционально полна в слабом смысле. Эта система функций алгебры Жегалкина. Для того, чтоб с ее помощью можно было записать все полиномы Жегалкина, необходимо добавить константу 1. Это означает, что– функционально полна (в сильном смысле).

Теорема 1 о функциональной полноте.

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

Лемма 3.

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

Теорема 2 о функциональной полноте (теорема Поста).

Для того чтобы система функций была функционально полна (в сильном смысле), необходимо и достаточно, чтобы она содержала

хотя бы одну немонотонную,

хотя бы одну нелинейную,

хотя бы одну несамодвойственную,

хотя бы одну не сохраняющую 0,

хотя бы одну не сохраняющую 1 функцию.