Функциональная полнота систем функций алгебры логики

Выше мы видели, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции , xy, xy. В связи с этим возникает вопрос, какими свойствами должна обладать система функций, чтобы через функции этой системы можно было выразить произвольную функцию алгебры логики? Мы собираемся дать достаточно исчерпывающий ответ на этот вопрос и показать, что таким свойством обладают и другие системы функций.

Прежде всего уточним, какими средствами из имеющейся системы функций можно получать новые функции. Новые функции получаются из имеющихся в заданной системе функций с помощью операций замены переменных и суперпозиции. Опишем эти две операции.