logo
Лекции ДМ

Полином Жегалкина.

Познакомимся с определением полинома:

Любую булеву функцию можно представить в виде двоичной суммы различных одночленов (конъюнкций), в которые все переменные входят не выше, чем в первой степени и константы 1 или 0, т.е. булева функция представима в виде:

Причем, такое представление единственное.

Эта сумма называется многочленом Жегалкина.

Существует два способа представления булевой функции в виде полинома: метод неопределенных коэффициентов и метод построения полином по формуле. Опишем каждый метод подробно.

    1. Метод неопределенных коэффициентов.

Перепишем полином в виде :

где Ki – конъюнкции, число которых равно 2n – 1, - вектор коэффициентов, где I {0,1}.

Коэффициент I указывает на присутствие или отсутствие соответствующей конъюнкции в полиноме.

Алгоритм поиска вектора коэффициентов и составления полинома.

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

  1. пользуясь таблицей истинности для двоичного сложения и конъюнкции, вычислить коэффициенты I ;

  2. подставить в полином значения коэффициентов и составить полином.

Представление булевой функции в виде полинома называется разложением функции в многочлен или в полином.

Рассмотрим пример.

Разложить функцию f(x, y, z) = (01101000).

Составим полином

Cоставляя уравнения, нулевые конъюнкции будем исключать:

№1 = 23-3: (001): 0 = 0+ 3;

№2 = 23-2 : (010): 1= 0+2;

№3 = 23-2+23-3: (011): 1= 0+2+3+6;

№4 = 23-1: (100): 0= 0+1;

№5 = 23-1+23-3: (101): 1 = 0+1+3+5;

№6 = 23-1+23-2: (110): 0 = 0+1+2+4;

№7: (111): 0= 0+1+2+3+4+5+6+7;

№8: (000): 0 = 0.

Решая систему , получим вектор коэффициентов: (0,0,1,0,1,1,0,1), тогда функция раскладывается в полином:

P(x,y,z) = 0 + y +xy + xz +xyz.

Проверку можно выполнить, составив таблицу истинности для полинома.

    1. Построение полинома по формуле.

Данный метод основан на применении равносильных преобразований данной булевой функции, представленной в виде формулы, к виду полинома.

Алгоритм построения полинома по формул:

  1. заменить формулу равносильной, содержащей только операции конъюнкцию и отрицание;

  2. снять отрицания, пользуясь равносильностью:

  3. раскрыть скобки:

  4. упростить, используя идемпотентность : х+х =0, равносильность х+0=х.

Рассмотрим примеры.

Задачи для самостоятельного решения.

  1. Построить таблицу истинности для формулы Составить для данной формулы КНФ и ДНФ.

  2. Методом неопределенных коэффициентов разложить функции в полиномы: а) f(x,y,z)= (01001110); б) f(x,y,z) = (11000101); в) f(x,y)= (0101); г) f(x,y)=(1011)

  3. Методом неопределенных коэффициентов и путем равносильных преобразований построить полиномы для формул: а) ху; б) (х|y)z; в) (xy)(yz); г) ((xy)v )|x.

Контрольные вопросы

  1. Привести таблицу истинности для штриха Шеффера. Выразить штрих Шеффера через отрицание и конъюнкцию. Выразить отрицание через штрих Шеффера.

  2. Привести таблицу истинности для стрелки Пирса. Выразить стрелку Пирс через отрицание и дизъюнкцию. Выразить отрицание через стрелку Пирса.

  3. Привести таблицу истинности для двоичного сложения. Выразить двоичное сложение через отрицание и эквиваленцию.

  4. Перечислить свойства двоичного сложения.

  5. Какое представление булевой функции называется полиномом Жегалкина?

  6. Алгоритм построения полинома методом неопределенных коэффициентов.

  7. Алгоритм построения полинома по формуле.

  8. Сколько различных полиномов существует для одной булевой функции?

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4