Ekzamen-Дисмат

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

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

- общий вид

{i1,...ik}N={1,...n}

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

Доказательство.

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

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

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

3)x=x|+|^(2)1 – избавились от отрицания

4)Получили формулу над множеством функций {0,1,&,|+|^2}

5)Преобразуем полученное выражение к виду полинома Жегалкина.

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

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

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

Содержание