Алгебра Жегалкина - это алгебра над множеством двух бинарных булевых функций
(И,) и нульарной функции 1.
Легко проверить следующие соотношения этой алгебре:
pq =
q
p;
p(qpqr) = pq
pr;
pp = 0;
p0 = p.
Справедливы в этой алгебре, конечно, и все соотношения, включающие логические функции. Если в произвольной формуле, включающей только функции базиса Жегалкина, раскрыть скобки, то получим бесскобочную формулу, имеющую вид суммы (по модулю два) произведений, то есть некоторый полином. Он называется полиномом Жегалкина.
Пример:
Преобразуем аналитически функцию f (p, q, г) = р v q
rq(p v r) в полиномом Жегалкина.
Поскольку
q = 1
p, a
p v q = (
p
q) = 1
(1
p)
(1
q) =
p
q
pq, то после подстановки и
раскрытия скобок имеем:
f(p, q, r) = p v q
rq (p v r) =
((1
p)
q
(1
p)q)
(rq(p
r
pr)) =
= (1p
q
q
pq)
(pqr
qr
pqr) = 1
p
pq
qr.
Теорема |
---|
Любая булева функция может быть представлена в виде полинома Жегалкина, причем единственным образом. |
Существование полинома для любой функции гарантируется тем, что функции
{И, , 1} образуют базис.
Далее, легко видеть, что число возможных членов в полиноме с m переменными
равно 2m. Поэтому число различных полиномов Жегалкина от m
переменных равно 2 в степени 2m, то есть числу возможных двоичных
функций от m переменных. Поскольку одна и та же формула не может представлять
различные функции, то тем самым между множествами двоичных функций и полиномов
Жегалкина от m переменных установлено взаимнооднозначное соотношение.
Пример
Построим для функции f (p, q, r) =
p v q
rq (p v r) полиномом
Жегалкина непосредственно из таблицы истинности.
p | q | r | f |
---|---|---|---|
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 0 |
f (p, q, r) = а0
app
aqq
arr
aprpr
aqrqr
apqrpqr.
Всего коэффициентов 8, каждый коэффициент может быть 0 или 1, число возможных вариантов равно 28 = 256 - как раз столько, сколько всех возможных булевых функций от-трех переменных. Для нахождения коэффициентов заданной функции используем таблицу ее значений.
Искомые коэффициенты последовательно найдем из следующей системы уравнений:
f (0,0,0) = 1 = a0; отсюда a0=1;
f (1,0,0) = 0 = a0
ap = 1
ap;
отсюда ap=1;
f (0,1,0) = 1 = a0
aq = 1
aq;
отсюда aq=0;
f (0,0,1) = 1 = a0
ar = 1
ar;
отсюда ar=0;
f(1,1,0) = 1 = a0
ap
aq
apq = 1
1
0
apq;
отсюда apq = 1;
f(1,0,1) = 0 = a0
ap
ar
apr =
1
1
0
apr;
отсюда apr = 1;
f(0,1,1) = 0 = a0
aq
ar
aqr = 1
0
0
aqr;
отсюда aqr = 1;
f(1,1,1) = 0 = a0
ap
aq
ar
apq
apr
aqr
apqr =
1
1
0
0
1
0
1
apqr; отсюда apqr=0;
Найденное представление совпадает с представлением, полученным для этой
функции ранее аналитически: f(p,q,r) =
1p
pq
qr.
Булева функция, полиномом Жегалкина которой имеет вид
a0
axi x i,
называется линейной.