Булевы Функции: Функциональная полнота

В алгебре булевых функций P2=<P2;S>

S – Операцией является подстановка функции в функцию, суперпозиция.

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

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

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

Любую булеву функцию можно представить в нормальной форме используя только операции +,*,not.

{&, v, not}. Конъюнкцию с помощью законов Деморгана можно выразить через остальные элементы системы:

X&Y=not (not(X) v not(Y)) – поэтому система {v, not}.