Пример. Представить полиномом Жегалкина логическую функцию импликацию ()

Представить полиномом Жегалкина логическую функцию импликацию ().

Вначале запишем СДНФ данной функции, затем выразим операции дизъюнкции и отрицания через конъюнкцию и сумму по модулю 2. получив формулу алгебры Жегалкина, пользуясь методом тождественных преобразований, получим полином Жегалкина:

.

Метод неопределенных коэффициентов, который можно использовать для нахождения полинома Жегалкина заданной функции, рассмотрим на примере.

Пример. Построить полином Жегалкина для функции импликации с использованием метода неопределенных коэффициентов.

Запишем полином для данной функции в виде суммы по модулю 2 всех возможных элементарных конъюнкций для с неопределенными коэффициентами , где коэффициенты принимают значения из множества и определяют присутствие или отсутствие элементарной конъюнкции в полиноме. Найдем последовательно значения коэффициентов, подставляя значения переменных и функции на различных интерпретациях: , , следовательно . Далее проводим вычисления , , следовательно, . Проводим преобразования на следующей интерпретации , , откуда следует . На последней интерпретации: , .

Подставив полученные значения коэффициентов , получим полином Жегалкина для функции

.

Полином Жегалкина, который может быть построен для каждой булевой функции, позволяет определить одно из её важных свойств - линейность.

Дата добавления: 2014-10-22