Ноу Інти, лекція, еквівалентність формул і нормальні форми

багаточлени Жегалкина

Багаточлени Жегалкина є ще одним цікавим подклассом формул, що дозволяє однозначно представляти булеві функції.

Визначення 4.4. Багаточленами Жегалкина назваются формули над безліччю функцій FJ =<0, 1, *, +> (Тут * - це інше позначення кон'юнкції).

Таким чином, кожен многочлен Жегалкина (можливо, після розкриття дужок і "приведення" подібних членів) представляє суму (по модулю 2) позитивних (монотонних) елементарних кон'юнкція (тобто елементарних кон'юнкція без заперечень). Оскільки для + і * справедливі закони асоціативності. ми будемо при записі многочлена Жегалкина опускати дужки, вважаючи, що * пов'язує аргументи сильніше, ніж +

Неважко перевірити, що справедливі такі еквівалентності:

З цих еквівалентностей і теореми 4.1 легко отримати першу частину наступного твердження.

Теорема 4.3. Для будь-якої булевої функції існує задає її многочлен Жегалкина. Він единственен з точністю до перестановок доданків і порядку змінних в кон'юнкції.

Доказ Існування такого многочлена випливає з того, що для будь-якої ДНФ або КНФ можна за допомогою зазначених еквівалентностей знайти еквівалентний многочлен Жегалкина. (J1) - (J3) дозволяють замінювати все входження і на + і *. а (J4) - перемножать утворені після такої заміни многочлени.

Для доказу єдиності подання підрахуємо число різних многочленів Жегалкина від змінних. Кожна позитивна елементарна кон'юнкція має вигляд Xi1 *. * Xik. де 1 <= i1 <.

де кожен з коефіцієнтів дорівнює 0 або 1. Отже, число многочленів Жегалкина одно, тобто числу всіх булевих функцій від n змінних. Тому кожна функція задається в точності одним многочленом Жегалкина.

Приклад 4.3. Нехай функція f (X1, X2, X3) задається ДНФ. Знайдемо поліном Жегалкина. який також задає цю функцію.

Спочатку замінюємо на *. а потім, застосовуючи еквівалентність (J1), усуваємо заперечення і отримуємо:

Перемноживши за правилами (J4), отримаємо:

Еквівалентність (J3) дозволяє усунути

Знову, використовуючи (J4), перемножимо перші дві дужки і усунемо повторення змінних в кон'юнкції:

Спростимо цю суму, використовуючи еквівалентності: і. В результаті отримаємо многочлен Жегалкина

еквівалентний вихідної ДНФ

Якщо функція f (X1. Xn) задана таблично, то для побудови реалізує її многочлена Жегалкина можна застосувати метод невизначених коефіцієнтів. Порівняємо i -ому набору значень змінних в таблиці позитивну кон'юнкцію змінних, рівних 1 в цьому наборі. Зокрема, K1 - порожня кон'юнкція. K2 = Xn. K3 = Xn-1. K4 = (Xn * Xn-1). і т.д. Тоді для отримання потрібного многочлена Жегалкина досить визначити всі коефіцієнти, в вираженні

Підставляючи в цю рівність значення змінних з набору, ми отримаємо 2 n лінійних рівнянь щодо 2 n невідомих коефіцієнтів. Вирішивши цю систему, отримаємо необхідний многочлен Жегалкина. Ця система трикутна і легко вирішується "зверху-вниз": кожне визначається за значеннями з рівняння, відповідного набору.

Приклад 4.4. Розглянемо як приклад функцію f (X1. Xn). задану наступною таблицею.