Суперпозиции функций. Полные системы логических функций

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

можно переименовать любую переменную, входящую в функцию из K;

вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию.

Суперпозицию еще иначе называют сложной функцией.

Пример 7. 1. Если дана одна функция х | y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x| (x|y), x| (y|z) и т. д.

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

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

Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).

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

Из (3.3) следует, что система является функционально полной. Очевидно, что любая система , через функции которой можно выразить конъюнкцию, дизъюнкцию и отрицание, будет полной. Действительно, для любой функции f можно взять булеву формулу (по(3.3.- , (3.3.)

) или (3.24.)), и все булевы операции в них заменить формулами над , представляющими эти операции. Несложно также доказать утверждение.

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