2.2.3. Полные системы булевых функций

Определение. Система булевых функций f1,f2, …, fn называется полной, если любая булева функция может быть выражена через функции f1,f2, …, fn с помощью суперпозиций.

Пример 42.

Исходя из определения полной системы булевых функций, следует, что система {Ù, U, O} является полной, так как любая булева функция может быть представима в виде СДНФ и/либо СКНФ.

Дадим определение суперпозиции функций.

Определение. - конечная система булевых функций. Функция f называется суперпозицией ранга 1 (или элементарной суперпозицией) функций f1, f2, …, fm, если f может быть получена одним из следующих способов: переименованием некоторой переменной xj какой-нибудь функции fi, т. е. f=fi(x1, …, xj-1, y, xj+1, …, xk1), где y может совпасть с любой переменной; подстановкой некоторой функции fl (1£ l m) вместо какой-либо переменной xj любой из функций fiÎK0, т. е. f=fi(x1, …, xj-1, fl(x1, x2, …, xk1), xj+1, ..., xki).

Определение. Суперпозиции ранга 1 образуют класс функций К1. Класс функций, получающихся из функций класса Кr-1 суперпозиций ранга r-1 с помощью элементарных суперпозиций, называется классом функций Kr суперпозиций ранга r. Суперпозициями функций из К0 называются функции, входящие в какой-либо из классов Kr.

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

Пример 43.

1. Четыре булевы функции одной переменной (f1 = 00, f2 = 11, f3 = 01, f4 = 10) образуют замкнутый класс.

2. Булевы функции f1 = x и образуют замкнутый класс.

Теорема. Класс T0={f | f(0, 0, …, 0)=0} функций, сохраняющих константу ноль на нулевом наборе, замкнут относительно суперпозиций.

Теорема. Класс T1={ f | f(1, 1, …, 1)=1} функций, сохраняющих константу один на единичном наборе замкнут относительно суперпозиций.