Независимая система функций и базис функционально замкнутого класса

Система функций независима, если ни какая функция из системы не может быть выражена с помощью суперпозиций через остальные функции системы. Система { , } независима, так как T , T , L, L. Для определения независимости функций надо найти два класса из пяти такие (можно по таблице Поста), что одна функция принадлежит первому классу и не принадлежит второму, а вторая функция наоборот принадлежит второму классу и не принадлежит первому. Система { , , } зависима, смотри выше законы Моргана.

Независимая система функций называется базисом функционально замкнутого класса, если всякая функция из этого класса есть суперпозиция функций из этой системы. Системы функций {&, } и { , } – базисы класса всех булевых функций.

Система функций {~, 0} – базис класса L. Это независимая система функций, так как 0 принадлежит классу M, а ~ не принадлежит классу M, 0 не принадлежит классу T , а ~ принадлежит классу T . Каждая линейная функция выражается суперпозициями функций + и , поскольку x = x + 1. Но эти функции в свою очередь выражаются через 0 и ~: x = x ~ 0, x + y = (x ~ y).