Алгебра Жегалкина. ПОЛНОТА И ЗАМКНУТОСТЬ

Date: 2015-10-07; view: 640.

Множество булевых функций, рассматриваемое вместе с операциями конъюнкции и сложения (по модулю два), будем называть алгеброй Жегалкина.

– закон коммутативности; – закон ассоциативности; – закон дистрибутивности; ; .

Полиномом Жегалкина называется полином вида

причем в каждом наборе все координаты различны, а суммирование ведется по некоторому множеству таких не совпадающих наборов,
а – константа 0 или 1.

Например, выражение является полиномом Жегалкина.

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

, ,

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

Пример 8 Выразить в виде полинома Жегалкина.

Способ 1 (табличный) Ищем требуемый полином методом неопределенных коэффициентов: .

1) при x = y = 0 имеем: d = 1;

2) при x = 0, y = 1 имеем: a = 0;

3) при x = 1, y = 0 имеем: b = 1;

4) при x = 1, y = 0 имеем: 1 = a + b + c + d = a + 1 + 0 + 1 = a, т.е. а = 1.

Отсюда

Способ 2

Т_{0 -} , для которых .

Т_{1 -} , для которых .

S - .(самодвойственной)( если совпадает со своей двойственной)

L - Булевы функции вида , где и равны 0 или 1

Булева функция называется монотонной, если для любых наборов и таких, что , имеет место неравенство .

Классы булевых функций являются замкнутыми классами.

Теорема 3 (о полноте) Для того, чтобы система булевых функций Д была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T₀, T₁, S, M, L.