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

Алгебра Жегалкина - это алгебра над множеством двух бинарных булевых функций: И и Åи нульарной функции 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 переменными равно 2m. Поэтому число различных полиномов Жегалкина от m переменных равно 2 в степени 2m, т.е. числу возможных двоичных функций от m переменных. Поскольку одна и та же формула не может представлять различные функции, то тем самым между множествами двоичных функций и полиномов Жегалкина от m переменных установлено взаимно-однозначное соотношение.ÿ

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

Таблица 1.6

p q r f

Будем искать коэффициенты полинома f(p,q,r)=a0ÅappÅaqqÅarrÅapqpqÅaprprÅaqrqrÅapqrpqr. Каждый коэффициент a может быть 0 или 1, возможных вариантов 256 - ровно столько всех возможных булевых функций от 3х переменных. Для нахождения коэффициентов заданной функции используем таблицу ее значений.

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

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=0;

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)=1ÅpÅpqÅqr.ÿ

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

 






Дата добавления: 2016-07-27; просмотров: 2314; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.02 сек.