17) Понятие полной системы. Примеры полных систем (с доказательством)

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

Система {или , &, не} является полной.

До-во:

Если любая функция f отлична от тождественного 0, то для нее всегда можно построить СДНФ, ч.т.д.

Лема:

Если система А – полная и любая функция может быть выражена формулой над системой В, то В тоже полная.

{или , не}

Не(X&Y)=не X или не Y=двойное не(X&Y)=не(не X или не Y)=X&Y=не(не X или не Y) т.е. эта система полная.

{&, не}

Не(X или Y)=(не X)& (не Y)= двойное не(X или Y)= не(не X & не Y)=X или Y=не(не X & не Y) т.е. эта система полная.