Математический аппарат инженера

5. Конституенты и представление функции. Для совокупности переменных x₁, x₂, .., x_n выражение x̃₁x̃₂... x̃_n называют конституентой единицы, а выражение x̃₁ ∨ x̃₂ ∨... ∨ x̃_n - конституентой нуля (x̃_i означает либо x_i, либо x̅_i). Данная конституента единицы (нуля) обращается в единицу (нуль) только при одном соответствующем ей наборе значений переменных, который получается, если все переменные принять равными единице (нулю), а их отрицания - нулю (единице). Например, конституенте единицы x₁x̅₂x₃x₄ соответствует набор (1011), а конституенте нуля x̅₁∨x₂∨x₃∨x̅₄- набор (1001).

Так как совершенная дизъюнктивная (конъюнктивная) нормальная форма является дизъюнкцией (конъюнкцией) конституент единицы (нуля), то можно утверждать, что представляемая ею булева функция f(x₁, x₂, ..., x_n) обращается в единицу (нуль) только при наборах значений переменных x₁, x₂, .., x_n, соответствующих этим конституентам. На остальных наборах эта функция обращается в нуль (единицу).

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

Например функции, заданной таблицей

- 516 -

соответствуют совершенные нормальные формы:

y = x̅₁x̅₂x₃ ∨ x̅₁x₂x̅₃ ∨ x₁x̅₂x̅₃ =

= (x₁ ∨ x₂ ∨ x₃) (x₁ ∨ x̅₂ ∨ x̅₃) (x̅₁ ∨ x₂ ∨ x̅₃) (x̅₁ ∨ x̅₂ ∨ x₃)

Полученные выражения можно преобразовать к другому видуна основании свойств булевой алгебры.

6. Алгебра Жегалкина. Другая замечательная алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина по имени предложившего ее советского ученого. Непосредственной проверкой по таблицам соответствия устанавливаются следующие основные свойства этой алгебры:

- коммутативность х + у = у +х; ху = ух;

- ассоциативность х + (у + z) = (х + у) + z; х(уz) = (ху)z;

- дистрибутивность умножения относительно сложения х(у + z ) = ху + хz;

- свойства констант x·1=x; x·0=0; x+0=x

Все эти свойства подобны обычной алгебре, но в отличие от булевой алгебры закон дистрибутивности сложения относительно умножения не имеет силы (xy + z ≠ xz +yz). Справедливы также следующие тождества:

- закон приведения подобных членов при сложении х + х =0;

- закон идемпотентности для умножения хх = х.

Таким образом, в формулах алгебры Жегалкина, как и в булевой алгебре, не могут появляться коэффициенты при переменных и показатели степени. С помощью табл. 6 выводятся также следующие соотношения:

x̅ = 1 + x; x₁ ∨ x₂ = x₁ + x₂ +x₁x₂; x₁ + x₂ = x₁x̅₂∨x̅₁x₂

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

x(x̅ ∨ y)= x[(1+x)+y+(1+x)y] = x(1+x+y+y+xy) =

= x(1+x+xy)= x+xx+xxy=x+x+xy=xy;

1+x+y+xy=(1+x)(1+y)=x̅ y̅.

Через операции алгебры Жегалкина можно выразить все другие булевы функции:

x₁→x₂=x̅₁∨x₂=1+x₁+x₁x₂;

x₁~x₂=(x̅₁∨x₂)(x₁∨x̅₂)=1+x

₁+x₂;

x₁ ← x₂=x₁→x₂=x₁+x₁x₂;

x₁/x₂=¬(x₁x₂)=1+x₁x₂;

x₁ ↓ x₂=¬(x₁∨x₂)=1+x₁+x₂+x₁x₂.

- 517 -

7. Канонические многочлены. Любая булева функция приводится к каноническому многочлену, члены которого не содержит числовых коэффициентов и линейны относительно любой из переменных (переменные входят только в первой степени).

Действительно, если привести данную функцию к совершенной нормальной форме и заменить все дизъюнкции через суммы по модулю 2, а отрицание переменных представить в соответствии с тождеством x̅ = 1 + x, то после раскрытия скобок получим некоторое алгебраическое выражение. Оно приводится к каноническому многочлену на основе соотношений х + х = 0 и хх = х. Такое представление всегда возможно и единственно (с точностью до порядка расположения членов).

Пример.

(1 + х + у) (1 + ху) + (х + ху) у

= 1 + х + у + ху + хху + уху + ху + хуу =

= 1 + х + у + ху + ху + ху + ху + + ху = 1 + х + у + ху.

Проблема разрешимости в алгебре Жегалкина сводится к указанным преобразованиям, в процессе которых делается вывод о выполнимости той или иной формулы.

Пример.

х(х→ у) → у = х (1 + х + ху) → у = ху → у = 1 + ху + хуу =1 + ху + ху = 1

Так как эта формула является тождественной единицей, то она невыполнима.

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

х ∨ у ∨ z = х + у + z + ху + хz + уz + хуz.