Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник






Зображення булевої функції многочленом Жегалкіна

Зобразимо будь-яку функцію формулою над базисом .

Означення. Одночленом будемо називати будь-який вираз вигляду , де . Сума за модулем 2 різних одночленів називається многочленом Жегалкіна.

Простіше кажучи, многочлен Жегалкіна – це вираз вигляду

, ,

де – стала 1 або 0 (звичайно 0 не пишуть) і при – попарно різні елементарні кон’юнкції, які не містять заперечень.

Приклад многочлена Жегалкіна; .

Запишемо загальне означення.

Означення. Многочленом Жегалкіна називається формула вигляду

,

де множина перебігає всі можливі підмножини множини , , а додавання відбувається за модулем 2.

Приклад. Загальний вигляд многочлена Жегалкіна від двох змінних:

.

Загальний вигляд многочлена Жегалкіна від трьох змінних:

.

Теорема (Жегалкіна). Будь-яка булева функція, відмінна від константи 0, може бути єдиним чином представлена у вигляді многочлена Жегалкіна:

=,

де множина перебігає всі можливі підмножини множини , , а додавання відбувається за модулем 2.

(Тут єдиність розуміють з точністю до порядку доданків у сумі і порядку множників у кон’юнкціях.)

Доведення. Існування. Нехай – булева функція. Зобразимо її у вигляді формули через кон’юнкцию і додавання за модулем 2, використовуюси числа 0 і 1. Це можна зробити, оскільки система є повною (приклад 7). В силу дистрибутивності кон’юнкції відносно додавання за модулем 2: , в формулі можна розкрити всі дужки і привести подібні. В результаті отримаємо многочлен від змінних, який складається з членів вигляду , які з’єднані знаком , тобто многочлен Жегалкіна.

Єдиність. Доведемо єдиність представлення. Підрахуємо число різних многочленів Жегалкіна від змінних, тобто число варіацій виду . Число наборів дорівнює числу різних підмножин множини з елементів , сюди входить і порожня множина (при ). Число підмножин скінченної множини дорівнює , а оскільки кожен набір входить з коефіцієнтом , який набуває два значення: 0 або 1, то число всіх можливих многочленів дорівнює , тобто числу всіх булевих функцій від змінних. Звідси випливає єдиність зображення функцій многочленом Жегалкіна. □

 

Існують наступні методи зображення булевої функції многочленом Жегалкіна:

1. Метод заміни. Цей спосіб зручний, коли функція задана формулою. Булеву функцію зображаємо формулою у ДДНФ над системою і робимо заміну , .

Приклад. Зобразити многочленом Жегалкіна функцію, задану формулою

.

Розв’язання.

.

Зауваження. При зведенні подібних треба пам’ятати, що парне число однакових доданків в сумі за модулем 2 дає 0.

2. Метод невизначених коефіцієнтів. Цей спосіб зручний, коли функція задана таблицею. Визначаємо коефіцієнти у загальному вигляді многочлену Жегалкіна, використовуючи значення функції на всіх наборах. Підставляємо в обидві частини різні значення змінних, отримаємо систему лінійних рівнянь (одне рівняння для кожного рядка таблиці). Розв’язавши систему, підставляємо знайдені коефіцієнти в многочлен.

Приклад. Зобразити многочленом Жегалкіна функцію , задану таблицею

Розв’язання. Запишемо функцію у вигляді многочлена Жегалкіна від двох змінних у загальному вигляді:

=.

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

Отже, =.

3. Метод трикутника Паскаля. Цей спосіб зручний, коли функція задана вектором своїх значень. Коефіцієнти многочлена Жегалкіна можна отримати за допомогою трикутника Паскаля, побудованого за вектором значень функції, по одиницях його лівої сторони.

Приклад. Зобразити многочленом Жегалкіна функцію , задану таблицею, за допомогою трикутника Паскаля.

Одночлени трикутник Паскаля
0 1 1 1
1 0 0
1 0
1

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

Остаточно маємо =.

 


Читайте також:

  1. Адвокатура в Україні: основні завдання і функції
  2. Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції
  3. Але відмінні від значення функції в точці або значення не існує, то точка називається точкою усувного розриву функції .
  4. Аналіз коефіцієнтів цільової функції
  5. АРХІВНІ ДОВІДНИКИ В СИСТЕМІ НДА: ФУНКЦІЇ ТА СТРУКТУРА
  6. Асимптоти графіка функції
  7. Базальні ядра, їх функції, симптоми ураження
  8. Базові функції, логічні функції
  9. Банки як провідні суб’єкти фінансового посередництва. Функції банків.
  10. Банківська система та її основні функції
  11. Банківська система та її структура. Функції Центрального банку.
  12. Банківська система: сутність, принципи побудови та функції. особливості побудови банківської системи в Україн




Переглядів: 2618

<== попередня сторінка | наступна сторінка ==>
Повні системи булевих функцій | Замикання і замкнені класи булевих функцій

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.029 сек.