Алгебра Жегалкина

Полные системы операций и функций.

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

Так как всякая формула может быть представлена приведенной формулой, то система å₀ = {Ù, Ú, } - полна. Полной будет и любая система å, через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание.

Если все операции полной системы å^* представимы формулами над системой å, то å полна, в этом случае говорят, что å сводится к å^*.

Алгебра над множеством логических функций с двумя операциями Ù и Å называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:

, ,

, ,

а также ассоциативность, коммутативность, идемпотентность конъюнкции и свойства констант.

Задание. Доказать полноту системы å₅ = {Ù, Å}.

Решение. Сведем систему å₅ к полной системе å₀.

.

Доказательство неполноты системы операций необходимо проводить в терминах булевых функций.

Дата добавления: 2015-06-04