Що нас коштує поліном Жегалкина побудувати...

Думаю, кожен, хто вивчав або вивчає в університеті дискретну математику, знайомий з поняттям многочлена Жегалкина.

Головна особливість цих багаточленів полягає в тому, що будь-яку булеву функцію можна представити поліномом Жегалкина, причому єдиним чином.

Найчастіше для побудови поліномів Жегалкина студентам пропонуються два методи побудови таких поліномів: метод невизначених коефіцієнтів та метод еквівалентних перетворень.

Розрахунки з використанням даних методів часто виявляються громіздкими. По неуважності допустити помилку не становить праці.

Під катом наведено один зручний алгоритм для побудови поліномів Жегалкина, який студенти сприймають «на ура», т. к. вимагає виконання механічних дій» без застосування будь-яких розумових зусиль. Короткий опис методу можна знайти у Вікіпедії, але на мій погляд не зовсім зрозуміло, як швидко проводити обчислення. Мені метод відомий під назвою «метод трикутника Паскаля».

Порядок проведення обчислень простіше показати на прикладі. Далі я буду по кроках показувати, як повинен виглядати розрахунок на папері (або як його зручно проводити).

Метод трикутника Паскаля
Потрібно побудувати поліном Жегалкина для функції f. Для прикладу, в якості функції f візьмемо функцію голосування f(x_1, x_2, x_3)=x_1x_2\vee x_2x_3\vee x_1x_3 = (00010111).

Крок 1. Будуємо таблицю значень функції (рядки в таблиці йдуть у порядку зростання двійкових кодів). Таблицю краще розмістити в лівій частині листа.

Таблиця значень функції

Крок 2. Побудова трикутника.

Для цього беремо вектор значень функції і виписуємо його навпроти першого рядка таблиці:

Виписуємо вектор значень функції

Далі заповнюємо трикутник, складаючи попарно сусідні значення по модулю 2, результат додавання виписуємо нижче.

Будуємо трикутник

Продовжуємо обчислення, поки в рядку не залишиться лише одна цифра.

Завершили побудову трикутника

Крок 3. Побудова полінома Жегалкина.

Нас цікавить ліва сторона трикутника (значення виділено жирним):

Ліва сторона трикутника

Числа на лівій стороні (виділені жирним шрифтом) трикутника є коефіцієнти полінома при монотонних конъюнкциях, відповідних наборів значень змінних.

Тепер випишемо для наочності ці кон'юнкції. Кон'юнкції виписуємо з двійковим наборів у лівій частині таблиці за наступним принципом: якщо навпаки змінної xi коштує 1, то змінна входить в кон'юнкцію; в іншому випадку змінна відсутня в кон'юнкції. Набору (0,0,0) відповідає константа 1.

Формування мономов

Якщо принцип отримання конъюнкций зрозумілий, то стовпець з ними можна (навіть краще) не виписувати, а відразу переходити до побудови полінома.

Для побудови полінома потрібні тільки кон'юнкції з рядків з одиницями на лівій стороні трикутника.

Вибір конъюнкций для полінома

Це і є кон'юнкції, що входять до складу полінома Жегалкина. Залишилося лише виписати сам поліном:
f({{x}_{1}},{{x}_{2}},{{x}_{3}})={{x}_{1}}{{x}_{2}}\oplus {{x}_{2}}{{x}_{3}}\oplus {{x}_{1}}{{x}_{3}}.

Якщо змінних у функції не 3, а 4 або більше, то метод працює без змін, тільки збільшаться розміри таблиць. Тим не менш, на відміну від методу невизначених коефіцієнтів, розрахунки можна без особливих зусиль виконати на аркуші паперу.

Література
На жаль, мені не вдалося знайти і подивитися джерело, зазначений у Вікіпедії:
В. П. Супрун Табличний метод поліноміальних розкладання булевих функцій // Кібернетика. — 1987. — № 1. — С. 116-117.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.