Представление переключательной функции в виде полинома Жегалкина.

f(x₁,..., x_n) = а_о Å a₁x₁ Å a₂x₂ Å …Å a_nx_n Å a_n+1x₁ x₂Å … Å a_Nx_1…x_n ,

(3.1)

где a₀, a₁x₁, … a_N— константы, равные нулю или единице;

Å — операция сложения по модулю два.

При записи конкретной переключательной функции в виде многочлена коэффициенты a₀, a₁x₁, … a_N выпа­дают, так как члены, при которых коэффициенты рав­ны нулю, можно опустить, а коэффициенты, равные еди­нице, не писать.

Для доказательства теоремы Жегалкина предположим, что задана произвольная переключатель­ная функция п аргументов f(x₁,..., x_n), равная еди­нице на некотором числе наборов с номерами m₁, … m_p.

Покажем, что переключательная функция f(x₁,..., x_n) равна сумме конституент единицы, ко­торые равны единице на тех же наборах, что и данная функция:

f(x₁,..., x_n) = K_m1 Å K_m2 Å... Å K_mp. (3.2)

Действительно, на каждом из наборов с номерами m₁, … m_p равна единице только одна конституента, стоящая в правой части выражения (3.2), а осталь­ные равны нулю. Следовательно, на этих наборах и только на них правая часть выражения (3.2) принимает значение, равное единице.

Для того чтобы перейти от выражения (3.2) к виду (3.1), достаточно представить конституенты едини­цы в виде произведений и, используя соотношение , заменить все переменные с отрицаниями (так как отрицания в выражение (3.1) не входят). Пусть на­пример, конституента единицы записана в виде

.

Тогда получим

K_i= (1 Å x₁)x₂(1Åx₃)x₄x₅.

Раскрывая скобки и приводя подобные члены в соответствии со свойствами операции сложения по модулю два, получаем запись заданной функ­ции в форме (3.1), что и доказывает теорему.

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

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

x, если п нечетно,

x Å x Å... Å x =

0, если п четно.

Пример 3.3. Представить в виде полинома Жегалкина функцию f₅₈(x₁,x₂,x₃) (см. табл. 1.1).

Функция f₅₈(x₁,x₂,x₃) равна единице на втором, третьем, четвертом и шестом наборах, и может быть записана в виде суммы соответствующих конституент единицы:

f₅₈(x₁,x₂,x₃) =K₂Å K₃Å K₄Å K₆ = .

Используя соотношение , получаем

f₅₈(x₁,x₂,x₃)=(1Å x₁)x₂(1Å x₃)Å (1Å x₁)x₂x₃Å x₁(1Å x₂)(1Å x₃)Å x₁x₂(1Å x₃).

Приводя подобные члены, окончательно находим

f₅₈(x₁,x₂,x₃)= x₁Å x₂Å x₁x₂Å x₁x₃.