logo search
флеров

2. Суперпозиция функций алгебры логики.

Пусть имеется функция f(x1, x2, ... , xn) и функции

,

тогда функцию будем называть суперпозицией функции f(x1, x2, ... , xn) и функций .

Другими словами: пусть F = { fj } - набор функций алгебры логики, не обязательно конечный. Функция f называется суперпозицией функций из множества F или функцией над F, если она получена из функции путем замены одной или нескольких ее переменных функциями из множества F.

Пример.

Пусть задано множество функций

F = {f1(x1), f2 (x1 ,x2 ,x3 ), f3(x1 ,x2 )}.

Тогда суперпозициями функций из F будут, например, функции:

(x, x) = f( f(x), f(x));

2(x, x) = f (x , f(x1 ), f3(x1 ,x2 )).

Cовершенная ДНФ - суперпозиция функций из множества

.

Определение.

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

Мы уже имеем некоторый набор полных систем:

;

, так как ;

, так как ;

{x+y, xy, 1}.

Как же определить условия, при которых система полна. С понятием полноты тесно связано понятие замкнутого класса.

      1.