Многочлены Жегалкина

Система булевых функций {+, &, 1} – полна, более того, она является базисом, называемым базисом Жегалкина; Тогда любую булеву функцию можно представить в виде многочлена от своих переменных и такой многочлен называется многочленом Жегалкина. Многочленом Жегалкина называется многочлен, являющийся сум­мой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени. Многочлен Жегалкина константы равен самой же константе; мно­гочлен Жегалкина булевой функции одной переменной многочлен Жегалкина булевой функции двух переменных многочлен Жегалкина булевой функции трех переменных и т.д. Коэффициенты a1 ,... i , и свободный член ао принимают значения 0 или 1, а число слагаемых в формуле равно 2^n, где n — число переменных. Знак — сумма по модулю два. Теорема (Жегалкина). Каждая булева функция f(x1,…, хn) может быть представлена в виде многочлена Жегалкина и притом единственным образом, с точностью до порядка слагаемых. Первый алгоритм построения многочлена Жегалкина. Выше было указано, что любую функцию, отличную от константы 0, можно представить в виде СДНФ. Если сравним таблицы истинности дизъюнкции и суммы по модулю два, видим, что они отличаются только последней строкой, т. е. на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю два. Кроме того, известно, что . На этом и основан первый алгоритм построения многочлена Жегалкина: 1. Составляем СДНФ. 2. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегалкина. 3. Упрощаем, если можно, полученное выражение, используя тождество 4. В полученной формуле каждое отрицание заменяем на . 5. Раскрываем скобки в полученной формуле, содержащей только функции +, &, 1. 6. Приводим подобные члены, используя тождество . Используя метод неопределенных коэффициентов, получаем Второй алгоритм определения многочлена Жегалкина: 1. Составляем систему линейных уравнений относительно 2^n неиз­вестных коэффициентов, содержащую 2^n уравнений, решением которой являются коэффициенты многочлена Жегалкина. Многочлен Жегалкина называется нелинейным, если он содержит конъюнкции переменных, а если он не содержит конъюнкции перемен­ных, то он называется линейным. Функция f(x1,…, хn) называется линейной, если ее многочлен Же­галкина имеет вид и нелинейной в противном случае. Из определения многочлена Жегалкина следует, что для любой буле­вой функции коэффициенты при переменных x1,…, хn и свободный член вычисляются по формулам: На этом основан алгоритм определения линейности (или нелинейно­сти) булевой функции. 1. По таблицам истинности булевой функции f(x1,…, хn) и выше указанным формулам находим коэффициенты: (а0, а1,...,аn). 2. Выписываем многочлен и про­веряем, задает ли он эту функцию. Для этого строим таблицу истинности многочлена Ф(x1,…, хn) и сравниваем ее с таблицей истинности функ­ции f(x1,…, хn). Если таблицы истинности совпадают, то функция f(x1,…, хn) ли­нейная и Ф(x1,…, хn) — ее многочлен Жегалкина, В противном случае функция нелинейная.

Дата добавления: 2015-07-11