Линейные функции и алгебра Жегалкина.

Алгебра Буля – частный случай булевых алгебр и кроме него существует бесконечное число булевых алгебр.Одна из них – алгебра Жегалкина.

Это к-значная алгебра вида: А = < М, Å, & >

Она подчиняется следующим законам:

х Å у = у Å х

х (у Å z) = xy Åxz

х Å х =Æ Любую булеву функцию можно представить с помощью алгебры Жегалкина.

Например:

Операция отрицания: = х Å 1

Операция сложения: х + у = = (х Å 1)(у Å 1) Å 1 = ху Å х Å у Å 1 Å Å 1 = ху Å х Å у

следовательно, исходя из теоремы Шинона, через операции сложения по mod 2 (Å) и конъюнкции (&) может быть выражена любая функция.

f(х₁,х₂,х₃) = х_{1 2}х₃ + ₁х₃ = x_{2 1}х₃ & ₁х₃ = (х₁х₃(х₂ Å 1) Å 1) & (х₃(х₁ Å 1)) Å 1 =(х₁х₂х₃ Å х₁х₃ Å 1)(х₁х₃ Å х₃ Å 1) Å 1 = х₁х₂х₃ Å х₁х₂х₃ Å х₁х₂х₃ Å х₁х₃ Å х₁х₃ Å х₁х₃ Å х₁х₃ Å х₃ Å 1 Å 1 = х₁х₂х₃ Å х₃

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

Функция линейная, если она представлена полиномом Жегалкина вида:

f(х₁,х₂,….х_n) = a_i x_i + j

- сумма по модулю 2

a_i - произв. коэффициент

j - свободный коэффициент

Класс линейных функций так же замкнут.

Пример: f(х₁,х₂,х₃) = х₁ Å х₃ a₁ = 1, a₂ = 0, a₃ = 1, j = 0

С помощью линейного полинома Жегалкина можно представить функцию отрицания: f(1,x₂.1) = g(x₂) = ₂

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

а слагаемые: x_j1,x_j2,…,x_jk

Предположим, что х_j1 и х _j2 принимают произвольные значения функции,

а x_j3 = x_j4 = …= x_jk = 1; a x_jk+1 = x_jk+2 = … = x_jk+n = 0

Тогда функция от аргументов имеет вид:

f (x₁,…,x_n) = x_j1x_j2 Å ax_j1 Å bx_j2 Å j

где a, b, j - произ. коэффициенты

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

Покажем, что при любых a, b, j для функции f_i (x_j1,x_j2) может быть получена конъюнкция (используем функцию отрицания q(x) = ).

Для этого составим таблицу, где для удобства обозначим: x_j1 = x; x_j2 = y

f(x,y) = xy Å ax Å by Å j

fi	a b j	& Å	& —	xy
f0	0 0 0	xy	xy	f0(xy) = xy
f1	0 0 1	xy Å 1	xy	g(f1(xy)) = xy
f2	0 1 0	xy Å y	y	f2(g(x),y) = xy
f3	0 1 1	xy Å y Å 1	y	G(f3(g(x),y)) = xy
f4	1 0 0	xy Å x	x	f4(x,g(y)) = xy
f5	1 0 1	xy Å x Å 1	x	G(f5(x,g(y))) = xy
f6	1 1 0	xy Å x Å y		g(f6(g(x),g(y))) = xy
f7	1 1 1	xy Å x Å y Å 1		f7(g(x),g(y)) = xy

Таким образом с помощью суперпозиции нелинейных функции и функции отрицания можно получать функцию коньюнкции.

Пример: f(x₁,x₂,x₃) = x_{1 2} + ₁x₃ + x₂

Преобразуем функцию в мин.форму, представив с помощью операции сложения по

mod 2 и конъюнкции

f(х₁,х₂,х₃) = x_{1 2} & ₁x₃ & ₂ = ((х₁(х₂ Å 1)) Å 1)) & ((х₃(х₁ Å 1) Å 1) & (х2 Å Å1) Å 1 = (х₁х₂ Å х₁ Å 1)(х₁х₃ Å х₃ Å 1)(х₂ Å 1) Å 1 = (х₁х₂х₃ Å х₁х₂ Å х₁х₃ Å Åх₁ Å х₃ Å 1)(х₂ Å 1) = х₁х₂х₃ Å х₁х₂ Å х₂х₃ Å х₂ Å х₁х₃ Å х₁ Å х₃ Å 1

Выберем в качестве мин. слагаемого х₁х₂ Þ х₃ = 0

f(x₁,x₂, Æ) = x₁x₂ Å x₁ Å x₂ Å 1 = _{1 2}

x₁x₂ = f(q(x₁),q(x₂),Æ)