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

Алгебра Жегалкина - это алгебра над множеством двух бинарных булевых функций: И и Åи нульарной функции 1. Легко проверить следующие соотношения в этой алгебре:
pÅq = qÅp;
p(qÅr) = pqÅpr;
pÅp = 0;
pÅ0=p.

Справедливы в этой алгебре и все соотношения табл.1.7, включающие эти функции. Если в произвольной формуле, включающей только функции базиса Жегалкина, раскрыть скобки, то получим бесскобочную формулу, имеющую вид суммы (по модулю два) произведений, т.е. некоторый полином. Он называется полиномом Жегалкина.

Пример 1.9. Преобразуем аналитически функцию f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 в полиномом Жегалкина. Поскольку Øp=1Åр, а pÚq = Ø(ØpØq) = 1Å(1Åр)(1Åq) = pÅqÅpq, то после подстановки и раскрытия скобок имеем: f(p,q,r) = ØpÚqÅrq(pÚr) = ((1Åр)ÅqÅ(1Åр)q) Å(rq(pÅrÅpr))= (1ÅpÅqÅqÅpq) Å(pqrÅqrÅ pqr)=1ÅpÅpqÅqr.ÿ

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

Доказательство. Существование полинома для любой функции гарантируется тем, что функции {И, Å, 1} образуют базис. Далее, легко видеть, что число возможных членов в полиноме с m переменными равно 2^m. Поэтому число различных полиномов Жегалкина от m переменных равно 2 в степени 2^m, т.е. числу возможных двоичных функций от m переменных. Поскольку одна и та же формула не может представлять различные функции, то тем самым между множествами двоичных функций и полиномов Жегалкина от m переменных установлено взаимно-однозначное соотношение.ÿ

Пример 1.10. Построим для функции f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 полиномом Жегалкина непосредственно из таблицы истинности (табл.1.6). Эту таблицу повторим здесь:

Таблица 1.6

Будем искать коэффициенты полинома f(p,q,r)=a₀Åa_ppÅa_qqÅa_rrÅa_pqpqÅa_prprÅa_qrqrÅa_pqrpqr. Каждый коэффициент a может быть 0 или 1, возможных вариантов 256 - ровно столько всех возможных булевых функций от 3х переменных. Для нахождения коэффициентов заданной функции используем таблицу ее значений.

Искомые коэффициенты последовательно найдем из следующей системы уравнений:

f(0,0,0) = 1 = a₀; отсюда a₀=1;

f(1,0,0) = 0 = a₀Åa_p=1Åa_p; отсюда a_p=1;

f(0,1,0) = 1 = a₀Åa_q=1Åa_q; отсюда a_q=0;

f(0,0,1) = 1 = a₀Åa_r=1Åa_r; отсюда a_r=0;

f(1,1,0) = 1 = a₀Åa_pÅa_qÅa_pq= 1Å1Å0Åa_pq; отсюда a_pq=1;

f(1,0,1) = 0 = a₀Åa_pÅa_r Åa_pr= 1Å1Å0Åa_pr; отсюда a_pr=0;

f(0,1,1) = 0 = a₀Åa_qÅa_r Åa_qr= 1Å0Å0Åa_qr; отсюда a_qr=1;

f(1,1,1) = 0 = a₀Åa_pÅa_qÅa_rÅa_pqÅa_prÅa_qrÅa_pqr= 1Å1Å0Å0Å1Å0Å1Åa_pqr; отсюда a_pqr=0;

Найденное представление совпадает с представлением, полученным для этой функции ранее аналитически: f(p,q,r)=1ÅpÅpqÅqr.ÿ

Булева функция, полином Жегалкина которой имеет вид a₀ÅSa_xix_i, называется линейной.