1.10. Полные системы логических связок

 

Назовем систему <D1, D2, …, Dn> полной, здесь D1, D2, …, Dn – символы логических операций, если для любой формулы алгебры высказываний существует равносильная ей формула, построенная с помощью операций D1, D2, …, Dn.

Поскольку для любой формулы алгебры высказываний существует равносильная ей ДНФ и КНФ, ясно, что <Ø, Ù, Ú > – полная система.

Лемма 9.1 Следующие системы логических связок являются полными:

<Ø, Ù, Ú, ® >,  <Ø, Ù >,  <Ø, Ú >,  <Ø, ®>.

Лемма 9.2 Следующие системы логических связок не являются полными:

<Ù, Ú, ® >,  <Ø >.