Назовем систему
<D1, D2, …, Dn> полной, здесь D1, D2, …, Dn – символы логических
операций, если для любой формулы алгебры высказываний существует равносильная
ей формула, построенная с помощью операций D1, D2, …, Dn.
Поскольку для любой формулы алгебры
высказываний существует равносильная ей ДНФ и КНФ, ясно, что <Ø, Ù, Ú > – полная система.
Лемма
9.1 Следующие системы логических
связок являются полными:
<Ø, Ù, Ú, ® >, <Ø, Ù >, <Ø, Ú >, <Ø, ®>.
Лемма
9.2 Следующие системы логических
связок не являются полными:
<Ù, Ú, ® >, <Ø >.