Полнота и замкнутость

Примеры.

 

Определение. Система функций В=из P₂ (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы, т.е. является суперпозицией функций из B.

Примеры.

1) Само множество ;

2);

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

3)– не полна, так как нельзя выразить, например, x.

Теорема. Пусть даны две системы функций из :

, (I)

. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство. Пусть . В силу полноты системы I функцию h можно выразить в виде формулы . По условию теоремы

Поэтому

что и требовалось доказать.

Примеры.

1) – полная. B₀ – базовая система функций.

2) – тоже полная, так как недостающая функция.

3) – тоже полная, так как .

4) и – тоже полные, так как

, ,

 

, ,

.

 

5) функционально полная, так как

, и, следовательно, B₅ сводится к B₁.

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

В алгебре Жегалкина выполняются следующие соотношения:

x Å y = y Å x,

x & (y Å z) = x&y Å x&z,

x Å x = 0, x Å 0=x,

Отрицание и дизъюнкция выражаются через Å и &:

,

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

Теорема Жегалкина. Каждая функция из может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина), причем единственного.

Доказательство. Множество P₂ является функционально полной системой функций. Любая функция из P₂ может быть представлена формулой над , которая после раскрытия скобок и приведения подобных членов дает полином Жегалкина.

Число различных полиномов Жегалкина от n переменных равно числу вариаций вида:

.

Число разных сочетаний равно числу всех подмножеств множества из n элементов, т.е. 2ⁿ. Каждый набор входит с коэффициентом , принимающим одно из 2-х значений {0,1}. Тогда число всевозможных полиномов Жегалкина от n переменных будет равно , т.е. равно числу различных булевых функций от n переменных.

Таким образом, получаем единственность представления функций через полином Жегалкина.