Алгебраїчна нормальна форма

Поліном Жегалкіна — довільна формула алгебри Жегалкіна, яка має вигляд суми кон'юнкцій булевих змінних. Поліном був запропонований в 1927 році Жегалкіним Іваном Івановичем, для зручного представлення булевих функцій алгебри логіки. В зарубіжній літературі представлення полінома Жегалкіна зазвичай називається алгебраїчною нормальною формою (АНФ). Якщо у кожний член поліному Жегалкіна кожна змінна входить один раз та поліном не містить однакових членів, то такий поліном Жегалкіна називається канонічним.

Теорема Жегалкіна — стверджує існування і унікальність будь-якої булевої функції у вигляді поліному Жегалкіна. Формально поліном Жегалкіна можна представити у вигляді:

${\displaystyle P(X_{1}...X_{n})=a~\oplus ~a_{1}\wedge X_{1}~\oplus ~a_{2}\wedge X_{2}~\oplus ~...~\oplus ~a_{n}\wedge X_{n}~\oplus ~a_{12}\wedge X_{1}\wedge X_{2}~\oplus ~a_{13}\wedge X_{1}\wedge X_{3}~\oplus ~...~\oplus ~a_{1...n}\wedge X_{1}...\wedge X_{n},}$

${\displaystyle a\ldots a_{1\ldots n}\in \{0,1\}.}$

або в більш формальному

${\displaystyle P=a\oplus \bigoplus _{\begin{array}{c}1\leqslant i_{1}<\ldots <i_{k}\leqslant n\\k\in {\overline {0,n}}\end{array}}a_{i_{1},\ldots ,i_{k}}\wedge x_{i_{1}}\wedge \ldots \wedge x_{i_{k}},\quad a,a_{i_{1},\ldots ,i_{k}}\in \{0,1\}.}$

Приклади поліному Жегалкіна:

${\displaystyle P=B\oplus A\wedge B;}$

${\displaystyle P=X\oplus Y\wedge Z\oplus A\wedge B\wedge X\oplus A\wedge B\wedge D\wedge Y\wedge Z;}$

${\displaystyle P=1\oplus A\oplus A\wedge B\wedge D.}$

Передумови

За теоремою Поста, для того щоб система булевих функцій була повною необхідно й достатньо, щоб в ній існували:

1. Хоча б одна немонотонна функція.
2. Хоча б одна нелінійна функція.
3. Хоча б одна несамодвоїста функція.
4. Хоча б одна функція, що не зберігає нуль.
5. Хоча б одна функція, що не зберігає одиницю.

Цим вимогам відповідає система функцій ${\displaystyle {\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }}$. На її основі і будуються поліноми Жегалкіна.

Існування і єдиність представлення

За теоремою Жегалкіна кожна булева функція єдиним чином представляється у вигляді поліному Жегалкіна. Теорема доводиться таким чином. Помітимо, що кількість різних булевих функцій від n змінних є ${\displaystyle 2^{2^{n}}}$. При цьому, кон'юнкцій вигляду ${\displaystyle x_{i_{1}}\ldots x_{i_{k}}}$ існує рівно 2ⁿ, так як з n можливих елементів кожен або входить в кон'юнкцію, або ні. В поліномі, в кожній такій кон'юнкції стоїть 0 або 1, тобто існує ${\displaystyle 2^{2^{n}}}$ різних поліномів Жегалкіна від n змінних. Тепер потрібно лишень довести, що різні поліноми реалізують різні функції. Використаємо метод доведення від протилежного. Тоді, прирівнявши два різних поліноми і перенісши один із них в іншу частину рівності, отримаємо поліном, тотожно рівний нулю, і який має ненульові коефіцієнти. Тоді розглянемо доданок з одиничними коефіцієнтами з найменшою кількістю змінних (при повторенні змінних, беремо до уваги одну із них). Підставивши одиниці на місця цих змінних, і нулі на місця решти змінних, отримаємо, що на цьому наборі тільки один доданок набуває значення 1, тобто нульова функція на одному з наборів набуває значення 1. Суперечність. Це означає, що кожна булева функція реалізується поліномом Жегалкіна єдиним унікальним чином.

Представлення функції у вигляді полінома Жегалкіна

За допомогою еквівалентних перетворень ДНФ

Порівняно з ДНФ в поліномі Жегалкіна відсутні операції АБО(диз'юнкція). Таким чином, поліном Жегалкіна можна отримати з ДНФ, виразивши операції АБО і НЕ через операції додавання за модулем два та константу 1. Для цього потрібно застосувати такі відношення:

${\displaystyle A\vee B=A\oplus B\oplus AB;}$

${\displaystyle {\overline {A}}=A\oplus 1.}$

${\displaystyle A\oplus A=0;}$

${\displaystyle (A\oplus B)C=AC\oplus BC.}$

Нижче наведений приклад перетворення ДНФ в поліном Жегалкіна:

${\displaystyle X\wedge {Y}\vee {\overline {X}}\wedge {\overline {Y}}=X\wedge {Y}\oplus {\overline {X}}\wedge {\overline {Y}}\oplus X\wedge {Y}{\overline {X}}\wedge {\overline {Y}}=X\wedge {Y}\oplus {\overline {X}}\wedge {\overline {Y}}=X\wedge {Y}\oplus (X\oplus 1)(Y\oplus 1)=}$

${\displaystyle =X\wedge {Y}\oplus X\wedge {Y}\oplus X\oplus Y\oplus 1=X\oplus Y\oplus 1.}$

За допомогою еквівалентних перетворень ДДНФ

ДДНФ володіє властивістю, що при будь-яких значеннях вхідних змінних, в одиниці перетворюється не більше одного члена виразу. Для таких виразів операція диз'юнкції еквівалентна операції додавання за модулем два.

При перетворенні ДДНФ в поліном Жегалкіна, достатньо просто замінити всі диз'юнкції на операцію додавання за модулем два та позбутись від інверсій за допомогою еквівалентного перетворення

${\displaystyle {\overline {A}}=A\oplus 1.}$

За допомогою Карти Карно

Перетворення карти Карно в поліном Жегалкіна

Булева функція від трьох змінних ${\displaystyle P(A,B,C)}$, представлена у вигляді карти Карно, перетворюється в поліном Жегалкіна таким чином:

• Розглядаємо всі комірки карти Карно в порядку зростання кількості одиниць в їхніх кодах. Для функції з трьома змінними послідовність комірок буде 000–100 — 010–001 — 110–101 — 011–111. Кожній комірці карти Карно відповідає член полінома Жегалкіна, в залежності від позиції коду, в якому стоять одиниці. Наприклад, комірці 111 відповідє член ABC, комірці 101 — член AC, комірці 010 — член B, комірці 000 — член 1.
• Якщо в комірці знаходиться 0, переходимо до наступної комірки.
• Якщо в комірці знаходиться 1, добавляємо в поліном Жегалкіна відповідний член, інвертуємо в карті Карно всі комірки, де цей член дорівнює 1 і переходимо до наступної комірки. Наприклад, дана комірка з кодом, і в цій комірці є одиниця, то в поліном Жегалкіна добавляється член АВ і всі комірки карти Карно, де A=1 і B=1, інвертуються. Якщо комірка 000 дорівнює одиниці, тоді в поліном Жегалкіна добавляється член 1 та інвертується вся карта Карно.
• Процес перетворення можна вважати закінченним, коли після чергової інверсії всі комірки карти Карно стають нульовими.

Метод трикутника

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

Метод трикутника дозволяє перетворити таблицю істинності в поліном Жегалкіна шляхом побудови допоміжної трикутної таблиці згідно з такими правилами:

• Будується повна таблиця істинності, в якій рядки йдуть в порядку зростання двійкових кодів від 000…00 до 111…11.
• Будується допоміжна трикутна таблиця, в якій перший стовпець збігається зі стовпцем значень функції в таблиці істинності.
• В кожному наступному стовпці комірка отримується шляхом додавання за модулем 2 двох комірок попереднього стовпця, який стоїть в тому самому рядку та рядком нижче.
• Стовпці допоміжної таблиці нумеруються двійковими кодами в тому ж самому порядку, що й рядки таблиці істинності.
• Кожному двійковому коду ставиться у відповідність один із членів полінома Жегалкіна в залежності від позиції кодів, в яких стоять одиниці. Наприклад, комірці 111 відповідає член ABC, комірці 101 — член AC, комірці 010 — член B, комірці 000 — член 1 і т. д.
• Якщо у верхньому рядку будь-якого стовпця стоїть одиниця, тоді відповідний член є в поліномі Жегалкіна.

Подібні роботи

В цей же рік створення поліному Жегалкіна (1927) американський математик Ерік Белл опублікував складну арифметизацію алгебри логіки, яка основана на Дедекіндовій теорії ідеалів та загальній арифметиці залишкових класів (як протиставлення до арифметики додавання за модулем 2). Набагато легший арифметичний зміст поліному Жегалкіна вперше був помічений на Заході (хоча на той час, спілкування між західними та радянськими математиками було сильно обмеженим) американським математиком Маршалом Стоуном у 1936 році, коли, дописуючи свою успішну теорему «Stone Duality», він помітив, що ймовірна втрата аналогії між булевою алгеброю та кільцями може, по суті, бути сформульована як точна рівносильність, яка є вірною як і для скінченних, так і для нескінченних алгебр, що змусило його істотно реорганізувати свою роботу.

Див. також

• Приклад обчислення поліному Жегалкіна [Архівовано 12 серпня 2020 у Wayback Machine.]

Література

• Яблонський С. В. Вступ в дискретну математику. — М.: Наука. — 1986
• Марченков С. С. Замкнуті класи булевих функцій. — М.: Фізматліт. — 2000