Функционально полной будет любая система , через функции которой можно выразить дизъюнкцию, конъюнкцию и отрицание. Действительно, для любой логической функции представляющую ее формулу над , можно построить следующим образом: взять булеву формулу для (по теореме 4.2 такая формула обязательно найдется), и все булевы операции в ней заменить формулами над , представляющими эти операции. Аналогично доказывается и более общее утверждение: если все функции функционально полной системы представимы формулами над системой , то также функционально полна. В этом случае говорят, что сводится к .
В гл.2 система была сведена к системе , тем самым была доказана функциональная полнота . Рассмотрим еще ряд примеров доказательства полноты системы логических функций путем ее сведения к заведомо функционально полной системе.
Пример. Доказать функциональную полноту систем и .
Из законов де Моргана и двойного отрицания следует, что в каждой из этих двух систем недостающая до функция выражается через две остальные:
|
|
,
.
Булева формула в системе перейдет в формулу , а в системе – в формулу .
Пример. Системы (штрих Шеффера) и (стрелка Пирса) функционально полны:
; ;
Следовательно, сводится к , а – к (полнота и доказана в предыдущем примере).