Досконала поліноміальна нормальна форма
Нехай функція представлена в СДНФ. де. різні. За співвідношенням (4.22). Однак кон'юнкція двох різних констітуєнт одиниці і дорівнює 0, так як. принаймні для одного. і тоді і, отже,. Т.ч. . З цієї формули випливає, що в СДНФ можна замінити операцію диз'юнкції операцією сума по модулю 2. Така форма називається досконалою поліноміальною нормальною формою (СПНФ).
Приклад. Отримати СПНФ функції.
Для отримання СПНФ представимо функцію в СДНФ:
Тоді в СПНФ функція запишеться в наступному вигляді:
Якщо в довільній формулою алгебри Жегалкина розкрити дужки за правилом (4.18) і зробити всі можливі спрощення по співвідношенням (4.19) і (4.20), то вийде формула, що має вигляд суми творів, тобто, полінома по модулю 2. Така формула називається поліномом Жегалкина . Поліном Жегалкина має вигляд
Приклад. Отримати поліном Жегалкина функції.
1. У СПНФ функція представляється в такий спосіб (див. Попередній приклад). Позбудемося заперечень, використовуючи співвідношення (4.21):
.
Розкривши дужки і застосувавши формули (4.19) і (4.20), отримаємо
2. Використовуючи формули (4.22) і (4.21), отримуємо
Розкривши дужки, і застосувавши формули (4.19) і (4.20), отримаємо
Для отримання полінома з довільної формули спочатку, звичайно, будують еквівалентну формулу над безліччю зв'язок. а потім, отримують з неї поліном.
Приклад. Отримати поліном Жегалкина функції.
Використовуючи визначення елементарних функцій (в табл. 4.6), отримаємо СКНФ імплікації:. Далі отримаємо поліном:.
Якщо поліном Жегалкина функції має вигляд
,
то функція називається лінійної.
Приклад 4.5. Визначити, чи є функція лінійної:
Таким чином, в поліномі функції відсутні кон'юнкції змінних, отже, функція лінійна. У попередньому прикладі, в поліномі функції була присутня кон'юнкція змінних і. тобто - нелінійна функція.
Теорема 4.3. Для будь-якої логічної функції існує поліном Жегалкина, і до того ж єдиний.
Доказ: Існування полінома вже доведено. Для доказу єдиності, покажемо, що між множинами всіх функцій від змінних і безліччю всіх поліномів Жегалкина від змінних існує взаємно однозначна відповідність. Число різних членів (тобто кон'юнкція змінних) поліномів від змінних дорівнює числу всіх підмножин з елементів, тобто (порожньому подмножеству відповідає член 1). Число різних поліномів, які можна утворити з цих кон'юнкція, дорівнює числу всіх підмножин множини кон'юнкція, тобто (порожньому подмножеству кон'юнкція відповідає поліном 0). Таким чином, число всіх поліномів Жегалкина від змінних дорівнює числу всіх функцій від змінних. Так як різних функцій відповідають різні поліноми (одна і та ж формула не може представляти дві різні функції), то, тим самим, між множинами функцій і поліномів від змінних встановлено взаємне однозначне відповідність, що і доводить єдиність полінома для кожної функції. Теорема доведена.
На підставі теореми 4.3 можна перевіряти еквівалентність формул. Для цього, кожну формулу перетворять в поліном Жегалкина і виробляють порівняння отриманих поліномів.