Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.

Система ф-ции {0,1,&,}-полная система ф-ции. Для того, чтобы это показать, мы рассмотрим:

Определение.Многочлен от переменных х1,...xn(n≥1) над множеством функций {0,1,&,}, являющийся многочленом первой степени относительно каждой переменной называют полиномом Жегалкина.

Люой полином Жегалкина от n-переменных однозначно задаёт некоторую булеву ф-цию f(x1,…,xn). Все булевы ф-ции полностью определяются полиномом Жегалкина.

n=1 a0 a1x1

na0a1x1 a2x2 a12x1x2

a0 ai i2,…,ik xi1xi2…xik…- общий вид в n-ой степени

{i1,i2,…,ik}⊆N={0,1,…,n}

{i1,...ik}{1,...n}

Теорема(первая теорема Жегалкина). Любую булеву функцию можно представить в виде полинома Жегалкина.

Следствие с теоремы: Система {0,1,&,}-полная система ф-ции.

1.Представим булеву функцию в виде СДНФ. Возможны 2 случая:

а.Если f≡0, то соответствующий полином Жегалкина принимает вид a0=0;

б.f≢0, f≡1, полином Жегалкина: а0=1

2.Используя закон де Моргана, выразим V в виде формулы, тождественной над множеством функции {}

3.x=x1 – избавились от отрицания путём использования тождества

4.Получили формулу над множеством функций {0,1,&,. И путём преобразования, преобразуем полученное выражение к виду полинома Жегалкина.

Даный способ построения полинома Жегалкина называется алгебраическим.

Теорема(Вторая теорема Жегалкина). Представление ф-ции в виде полинома Жегалкина единственно.

Любой полином Жегалкина от n переменных однозначно определяется набором своих коэфициэнтов (длина набор- 2^n). Всего полиномов Жегалкина 2^(2^n) и совпадает с общим числом булевых ф-ций от n-переменных, следовательно, существует взаимнооднозначное соответствие между полиномами Жегалкина и булевыми функциями.