Задать вопрос юристу

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

Полиномом Жегалкина (полиномом по модулю 2) от переменных называется выражение вида

где .

Наибольший из рангов элементарных конъюнкций входящих в полином, называется степенью этого полинома. Степень полинома 0 принимается равной . Число слагаемых в формуле полинома называется длиной полинома.

Теорема. Каждая функция из представляется в виде полинома Жегалкина и это представление единственно.

Доказательство. Существование полинома для каждой булевой функции, отличной от константы 0, следует из того, что ее СДНФ применением равенств

сводится к полиному.

Для доказательства единственности подсчитаем число полиномов Жегалкина от переменных , т.е. число выражений вида

.

Число слагаемых в указанной сумме равно количеству подмножеств из чисел , т.е. . Каждому полиному в соответствие можно поставить вектор длины , компонентами которого являются числа , равные 0 или 1. Следовательно, искомое число полиномов равно , т.е. числу всех булевых функций от переменных .

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

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

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

Запишем его в виде

Вектор длины назовем вектором коэффициентов полинома . Найдем его компоненты. Для этого заметим, что если переменным придать значения из -ой строки таблицы, то значение будет равно сумме с компонентами вектора , соответствующими ненулевым конъюнкциям (). В итоге получим систему из уравнений с неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома .

2. Метод, основанный на преобразовании формул над множеством связок . Строят некоторую формулу над множеством связок , реализующую данную функцию . Затем заменяют всюду подформулы вида на , раскрывают скобки, пользуясь дистрибутивным законом , и применяют эквивалентности .

Пример. Построить полином Жегалкина функции .

Решение. 1. (Метод неопределенных коэффициентов). Запишем искомый полином в виде

Табл. 1.11

0 0 1
0 1 1
1 0 0
1 1 1

Тогда

Получаем систему уравнений

Из системы уравнений находим .

Следовательно,

2. (Метод преобразования формул). Имеем

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

1. Представить в виде СДНФ следующие функции:

а) ; б) ;

в) ;

г) .

2. Представить в виде СКНФ следующие функции:

а) ; б) ;

в) ;

г) .

3. Подсчитать число функций , у которых СДНФ удовлетворяет следующему условию:

а) содержит не более двух элементарных конъюнкций;

б) отсутствуют элементарные конъюнкции, у которых число букв с отрицаниями равно числу букв без отрицаний;

в) каждая элементарная конъюнкция содержит хотя бы две буквы с отрицаниями ();

г) отсутствуют элементарные конъюнкции, содержащие нечетное число букв с отрицаниями;

д) в каждой элементарной конъюнкции число букв с отрицаниями не больше числа букв без отрицаний.

4. Подсчитать число функций , у которых СКНФ является одновременно и ДНФ (необязательно совершенной).

5. Найти длину СДНФ функции :

а)

б)

6. С помощью эквивалентных преобразований построить какую-нибудь ДНФ функции :

а) ;

б) ;

в) ;

г) .

7. С помощью эквивалентных преобразований построить какую-нибудь КНФ функции :

а) ;

б) ;

в) .

8. Применяя преобразования вида и , построить из заданной ДНФ функции ее СДНФ:

а) ;

б) .

9. Применяя преобразования вида и , построить из заданной КНФ функции ее СКНФ:

а) ;

б) .

10. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:

а) ;

б) ;

в) ;

г)

11. Используя метод, основанный на преобразовании формул над множеством связок , найти полиномы Жегалкина для следующих функций:

а) ; б) ;

в) ;

г) .

12. Найти число:

а) полиномов Жегалкина степени над множеством переменных

б) полиномов Жегалкина степени над множеством , обращающихся в 1 на наборе

в) полиномов Жегалкина длины над множеством ,

г) полиномов Жегалкина длины над множеством , удовлетворяющих условию: в полиноме не могут содержаться одновременно (в качестве слагаемых) конъюнкции одинакового ранга

13. Выяснить, на скольких наборах из обращается в единицу полином :

а) ;

б) .

14. Найти функцию , у которой длина полинома Жегалкина в раз превосходит длину ее СДНФ (). Ответы

1. а) ; б) ; в) ;

г) .

2. а) ; б) ; в) г) .

3. а) ; б) если четное, то ; если нечетное, то ; в) ; г) ; д) если нечетное, то , если четное, то . 4. .

5. а) ; б) . 6. а) ;

б) ; в) ; г) .

7. а) ; б) .

8. а) ;

б) ; в) .

9. а) . 10. а) ;

б) ; в) ;

г) .

11. б) ;

в) .

12. а) 1 при ; , где при ; б) ; в) ; г) .

13. а) ; б) . 14. .

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме Полином Жегалкина:

  1. Разложение булевых функций в канонический полином Жегалкина
  2. 4.4. ПОЛИНОМ
  3. Арифметическое разложение булевых функций
  4. 2.2.3.4. Теорема Поста о функциональной полноте
  5. 2.2.3.2. Линейные функции
  6. СОДЕРЖАНИЕ
  7. Логический отбор видов аппроксимирующей функции.
  8. 4.7. ПОКАЗАТЕЛЬНАЯ ФУНКЦИЯ
  9. Полиномиальное разложение булевых функций
  10. 4.3. Блок текущего контроля
  11. 4.2. Построение интерполяционных многочленов
  12. §1.5. Полнота, замкнутость. Теорема Поста о полноте
  13. §1.7. Схемы из функциональных элементов
  14. Граничные условия для 4-3-4-траекторий
  15. 1.2.2. Интерполяционные многочлены
  16. Борьба с аберрациями, индуцированными ЛАСИК
  17. 2.1. Разностные множества и последовательности с двухуровневой ПАКФ