Поліном жегалкіна - це

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

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

Поліном Жегалкина є сумою по модулю два творів неінвертірованних змінних, а також (якщо необхідно) константи 1. Формально поліном Жегалкина можна представити у вигляді

або в більш формалізованому вигляді як:

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

передумови

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

Хоча б одна функція, що не зберігає 0.
Хоча б одна функція, що не зберігає 1.
Хоча б одна нелінійна функція.
Хоча б одна немонотонна функція.
Хоча б одна несамодвойственная функція.

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

Cуществованіе і єдиність подання

По теоремі Жегалкина кожна булева функція єдиний образ представляється у вигляді полінома Жегалкина. Теорема доводиться наступним чином. Зауважимо, що різних булевих функцій від n змінних штук. При цьому кон'юнкція виду існує рівно 2 n. так як з n можливих сомножителей кожен або входить в кон'юнкцію, чи ні. У поліномі у кожній такій кон'юнкції варто 0 або 1, тобто існує різних поліномів Жегалкина від n змінних. Тепер достатньо лише довести, що різні поліноми реалізують різні функції. Припустимо гидке. Тоді прирівнявши два різних полінома і перенісши один з них в іншу частину рівності, отримаємо поліном, тотожне рівний нулю і має ненульові коефіцієнти. Тоді розглянемо доданок з одиничним коефіцієнтом найменшої довжини, тобто з найменшим числом змінних, що входять в нього (будь-який один, якщо таких декілька). Підставивши одиниці на місця цих змінних, і нулі на місця інших, отримаємо, що на цьому наборі тільки одне це доданок приймає одиничне значення, тобто нульова функція на одному з наборів приймає значення 1. Протиріччя. Значить, кожна булева функція реалізується полиномом Жегалкина єдиним чином.

Вивчення функцій у вигляді полінома Жегалкина

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

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

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

При перетвореннях використані співвідношення:

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

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

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

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

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

Логічна функція трьох змінних, представлена у вигляді карти Карно. перетвориться в поліном Жегалкина наступними кроками:

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

Метод трикутника [1]

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

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

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

література

Дивитися що таке "поліном жегалкіна" в інших словниках:

Многочлен Жегалкина - поліном жегалкіна поліном над Z2, тобто поліном з коефіцієнтами виду 0 і 1, де в якості твору береться кон'юнкція, а в якості складання виключає або. Поліном був запропонований в 1927 році І. І. Жегалкина в якості зручного засобу ... Вікіпедія

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

Булеві вирази - В теорії дискретних функціональних систем булевої функцією називають функцію типу. де булево безліч, а n невід'ємне ціле число, яке називають арность або місцевістю функції. Елементи 1 (одиниця) і 0 (нуль) стандартно інтерпретують ... ... Вікіпедія

Лінійна функція - Приклади лінійних функцій. Лінійна функція функція виду (для функцій однієї змінної). Основна властивість лінійних функцій: приріст функції п ... Вікіпедія

Поліном Жегалкина. Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Поліном Жегалкина - многочлен над кільцем, тобто ... Детальніше Купити за 870 руб