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

Система булевых функций называется полной, если любая булева функция может быть выражена через функции системы с помощью суперпозиций (т.е. составления сложных функций). Например, система из трёх функций { , &, } является полной, так как каждая булева функция имеет свои ДНФ и КНФ.

Суперпозицией f и g называется функция, полученная подстановкой одной из этих функций в другую вместо переменной. Пусть f = x ~ y и g = t & p. Из этих двух функций можно составить четыре суперпозиции: (t & p) ~ y (функция g заменила переменную x), x ~ (t & p) (функция g заменила переменную y), (x ~ y) & p (функция f заменила переменную t) и t & (x ~ y) (функция f заменила переменную p). Процесс замены переменных функциями можно продолжать сколь угодно долго.

Теорема: если система функций F = {F1, …, Fm} полная и любая из функций этой системы может быть выражена с помощью суперпозиций через функции системы функций G = {G1,…, Gt}, то система функций G тоже является полной. Доказательство: берём любую функцию и выражаем её с помощью суперпозиций через функции системы F. Это возможно, так как система F полная. Далее заменяем все функции из системы F функциями из системы G и получаем, что любая функция может быть выражена через функции системы G. Теорема доказана.