Замкнутость

Полином Жегалкина

Т.к. формула, построенная в системе 6) состоит из констант 0, 1 и функций x ₁, x ₂ и x ₁Å x ₂, то после раскрытия скобок выражение формулы переходит в полином по модулю 2 (полином Жегалкина).

Теорема. Каждая функция из P ₂ может быть выражена при помощи полинома по модулю 2. Т.е. в виде ƒ(x ₁, x ₂,…, x _n) = x _i1 ∙ x _i2 ∙∙∙ x _in Å с, где в каждом наборе (i₁, i₂,…,i_n) все i _k (k =1,…,n) различны и суммирование ведется по несовпадающему набору значений. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка следования слагаемых.

Полином Жегалкина называется нелинейным, если он содержит произведения переменных, и линейным – если он их не содержат.

Для получения полинома Жегалкина булевой функции используются аксиомы булевой алгебры и равенства, выражающие операции отрицания, Ù, Ú через операции Å, ⊙.

x ̅ = x Å 1, x Ù y = xy, x Ú y = x Å y Å xy

Можно доказать тождества:

1) x Å y = y Å x; x ∙ y = y ∙ x

2) (x Å y) Å z = x Å (y Å z); (x ∙ y) ∙ z = x ∙ (y ∙ z)

3) x Å x = 0; x ∙ x = x

4) x (y Å z) = x y Å x z

5) 0 Å x = x

6) 0 ∙ x = 0

7) 1 ∙ x = x

8) x Å x ̅ = 1

9) x ∙ x ̅ = 0

Пример. Определить полином Жегалкина для функции

ƒ (x, y, z) = x̅ y̅ z Ú x̅yz Ú x y̅ z̅.

Используя выше приведенные формулы, получим: ƒ (x, y, z) = (x̅ y̅ z Å x̅yz Å x̅ y̅z x̅yz) Ú x y̅ z̅ = (x̅ y̅ z Å x̅yz) Ú x y̅ z̅ = x̅ y̅z Å x̅yz Å x y̅ z̅) Å (x̅ y̅ z Å x̅yz) x y̅ z̅ = x̅ y̅ z Å x̅yz Å x y̅ z̅ Å x̅ y̅z x y̅ z̅ Å x̅yz x y̅ z̅ = x̅ y̅ z Å x̅yz Å x y̅ z̅ = x̅z (y Å y̅) Å x y̅ z̅ = x̅ z̅ ∙ 1 Å x y̅ z̅ = x̅ z̅ Å x y̅ z̅ = (x Å 1) z Å x (y Å 1) (z Å 1) = xz Å z Å (xy Å x) (z Å 1) = xz Å z Å xyz Å xz Å xy Å x = x Å z Å xy Å xyz - полином Жегалкина

Заметим, что если в эквивалентности j Ú ψ = j Å ψ Å jψ формулы j и ψ являются различными конституентами единицы, то их произведения jψ = 0. Тогда j Ú ψ = j Å ψ. Следовательно, для получения полинома Жегалкина из совершенной ДНФ можно сразу заменить Ú на Å.

Пусть A – некоторое подмножество функций из P ₂. Замыканием A называется множество тех булевых функций, которые представимы в виде формул через функции множества A. Замыкание множества A обозначается [ A ]. Заметим, что замыкание инвариантно относительно операций введения и удаления фиктивных переменных.

Примеры: 1) A = P ₂, т. к. [ A ] = P ₂;

2) A = {1, x ₁ Å x₂ }. Замыканием этого множества будет класс L всех линейных функций, имеющих вид ƒ(x ₁, x ₂,…, x _n) = c ₀ Å c ₁ x ₁ Å c ₂ x ₂ Å…Å c _n x _n, где c _i = 0_i1, причем (i =0,…, n)

Свойства замыкания:

1) [ A ] = A

2) [[ A ]] = [ A ]

3) если A ₁ Ì A ₂, то [ A ₁] Ì [ A ₂]

4) [ A ₁ È A ₂] É [ A ₁] È [ A ₂]

Класс (множество) A называется (функционально) замкнутым, если [ A ] = A.

Примеры.

1) P ₂ – замкнутый класс.

2) L – замкнут, т.к. линейное выражение, составленное из линейных выражений, в свою очередь, является линейным выражением.

В терминах замыкания и замкнутого класса можно определить полноту (эквивалентную исходному определению), а именно: A – полная система, если [ A ] = P ₂.

Дата добавления: 2014-01-11