Побудова таблиці істинності. ДДНФ. ДКНФ. Поліном Жегалкіна.

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

Як користуватися калькулятором

1. Введіть логічну функцію (наприклад, x1 ∨ x2) або її вектор (наприклад, 10110101)
2. Вкажіть дії, які потрібно виконати за допомогою перемикачів
3. Вкажіть, чи потрібно включити перемикач "З рішенням"
4. Натисніть кнопку "Побудувати"

Символи, що використовуються

В якості змінних використовуються літери латинського та російського алфавітів (великі та маленькі), а також цифри, написані після літери (індекс змінної). Таким чином, іменами змінних будуть: a, x, a1, B, X, X1, Y1, A123 і так далі.

Для запису логічних операцій можна використовувати як звичайні символи клавіатури (*, +, !, ^, ->, =), так і традиційні символи логіки, (∧, ∨, ¬, ⊕, →, ≡). Якщо на вашій клавіатурі відсутній потрібний символ операції, то використовуйте клавіатуру калькулятора (якщо вона не видно, натисніть "Показати клавіатуру"), в якій доступні як усі логічні операції, так і набір змінних, що найчастіше використовуються.

Для зміни порядку виконання операцій використовуються круглі дужки. ().

Позначення логічних операцій

• І (AND): & • ∧ *
• АБО (OR): ∨ +
• НЕ (NOT): ¬ !
• Виключне АБО (XOR): ⊕ ^
• Імплікація: -> → =>
• Еквівалентність: = ~ ≡ <=>
• Штрих Шеффера: ↑ |
• Стрілка Пірса: ↓

Що вміє калькулятор

• Будувати таблицю істинності за функцією
• Будувати таблицю істинності за двійковим вектором
• Будувати досконалу кон'юнктивну нормальну форму (ДКНФ)
• Будувати досконалу диз'юнктивну нормальну форму (ДДНФ)
• Будувати поліном Жегалкіна (методами Паскаля, трикутника, невизначених коефіцієнтів)
• Визначати належність функції до кожного з п'яти класів Посту
• Будувати карту Карно
• Мінімізувати ДНФ та КНФ
• Шукати фіктивні змінні

Що таке булева функція

Булева функція f(x1, x2, ... xn) — це будь-яка функція від n змінних x₁, x₂, ... x_n, в якій її аргументи приймають одне з двох значень: або 0, або 1, і сама функція набуває значення 0 або 1. Тобто це правило, за яким довільний набір нулів і одиниць ставиться у відповідність значення 0 або 1. Докладно про булеві функції можна почитати у Вікіпедії.

Що таке таблиця істинності?

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

Досить часто зустрічається варіант таблиці, де число стовпців дорівнює n + число використовуваних логічних операцій. У такій таблиці також перші n стовпців заповнені наборами аргументів, а стовпці, що залишилися, заповнюються значеннями підфункцій, що входять в запис функції, що дозволяє спростити розрахунок кінцевого значення функції за рахунок вже проміжних обчислень.

Логічні операці

Логічна операція — операція над висловлюваннями, що дозволяє складати нові висловлювання шляхом поєднання простіших. Як основні операції зазвичай називають кон'юнкцію (∧ або &), диз'юнкцію (∨ або |), імплікацію (→), заперечення (¬), еквівалентність (=), виключне АБО (⊕). (∧

Таблиця істинності логічних операцій

Як задати логічну функцію

Є безліч способів задати булеву функцію:

• таблиця істинності
• характеристичні множини
• вектор значень
• матриця Грея
• формули

Розглянемо деякі з них:

Щоб задати функцію через вектор значень необхідно записати вектор з 2ⁿ нулів і одиниць, де n - число аргументів, від яких залежить функція. Наприклад, функцію двох аргументів можна задати так: 0001 (операція І), 0111 (операція АБО).

Щоб задати функцію у вигляді формули, необхідно записати математичний вираз, що складається з аргументів функції та логічних операцій. Наприклад, можна задати таку функцію: a∧b ∨ b∧c ∨ a∧c

Способи представлення булевої функції

За допомогою формул можна отримувати величезну кількість різноманітних функцій, причому за допомогою різних формул можна отримати одну й ту саму функцію. Іноді дуже корисно дізнатися, як побудувати ту чи іншу функцію, використовуючи лише невеликий набір заданих операцій або використовуючи якнайменше довільних операцій. Розглянемо основні способи завдання булевих функцій:

• Досконала диз'юнктивна нормальна форма (ДДНФ)
• Досконала кон'юнктивна нормальна форма (ДКНФ)
• Алгебраїчна нормальна форма (АНФ, поліном Жегалкіна)

Досконала диз'юнктивна нормальна форма (ДНФ)

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

Наприклад, ДНФ є функція ¬abc ∨ ¬a¬bc ∨ ac, але вона не є ДДНФ, бо в останній кон'юнкції відсутня змінна b.

Досконала кон'юнктивна нормальна форма (КНФ)

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

Наприклад, КНФ є функція (a ∨ b) ∧ (a ∨ b ∨ c), але не є ДДНФ, так як у першій диз'юнкції відсутня змінна с.

Алгебраїчна нормальна форма (АНФ, поліном Жегалкіна)

Алгебраїчна нормальна форма, поліном Жегалкіна - це форма подання логічної функції у вигляді полінома з коефіцієнтами виду 0 і 1, в якому як добуток використовується операція кон'юнкції, а як додавання - виключне АБО.

Приклади поліномів Жегалкіна: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм побудови ДДНФ для булевої функції

1. Побудувати таблицю істинності для функції
2. Знайти всі набори аргументів, на яких функція приймає значення 1
3. Виписати прості кон'юнкції для кожного з наборів за таким правилом: якщо в наборі змінна набуває значення 0, то вона входить до кон'юнкції з запереченням, інакше без заперечення
4. Об'єднати всі прості кон'юнкції за допомогою диз'юнкції

Алгоритм побудови ДКНФ для булевої функції

1. Побудувати таблицю істинності для функції
2. Знайти всі набори аргументів, на яких функція набуває значення 0
3. Виписати прості диз'юнкції для кожного з наборів за таким правилом: якщо в наборі змінна приймає значення 1, то вона входить у диз'юнкцію з запереченням, інакше без заперечення
4. Об'єднати всі прості диз'юнкції за допомогою кон'юнкції

Алгоритм побудови полінома Жегалкіна бульової функції

Є кілька методів побудови полінома Жегалкіна, розглянемо найбільш зручний та простий з усіх.

1. Побудувати таблицю істинності для функції
2. Додати новий стовпець до таблиці істинності та записати в 1, 3, 5... комірки значення з тих же рядків попереднього стовпця таблиці істинності, а до значень у рядках 2, 4, 6... додати по модулю два значення з відповідно 1, 3, 5... рядків.
3. Додати новий стовпець до таблиці істинності та переписати в новий стовпець значення 1, 2, 5, 6, 9, 10... рядків, а до 3, 4, 7, 8, 11, 12... рядків аналогічно попередньому пункту додати переписані значення.
4. Повторити дії щоразу збільшуючи вдвічі кількість переносимих і складених елементів до тих пір, поки довжина не дорівнюватиме кількості рядків таблиці.
5. Виписати булеві набори, на яких значення останнього стовпця дорівнює одиниці
6. Записати замість одиниць у наборі імена змінних, що відповідають набору (для нульового набору записати одиницю) та об'єднати їх за допомогою операції виключне АБО.

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

Побудуємо досконалі диз'юнктивну та кон'юнктивну нормальні форми, а також поліном Жегалкіна для функції трьох змінних F = ¬ab∨¬bc∨ca

1. Побудуємо таблицю істинності для функції

---

Побудова досконалої диз'юнктивної нормальної форми:

Знайдемо набори, на яких функція набуває істинного значення: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

У відповідність до знайдених наборів поставимо елементарні кон'юнкції по всіх змінних, причому якщо змінна в наборі приймає значення 0, то вона буде записана з запереченням:

K₁: { 0, 0, 1 } — ¬a¬bc
K₂: { 0, 1, 0 } — ¬ab¬c
K₃: { 0, 1, 1 } — ¬abc
K₄: { 1, 0, 1 } — a¬bc
K₅: { 1, 1, 1 } — abc

Об'єднаємо кон'юнкції за допомогою диз'юнкції та отримаємо досконалу диз'юнктивну нормальну форму:

---

Побудова досконалої кон'юнктивної нормальної форми:

Знайдемо набори, на яких функція набуває значення фальш: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

У відповідність до знайдених наборів поставимо елементарні диз'юнкції по всіх змінних, причому якщо змінна в наборі приймає значення 1, то вона буде записана з запереченням:

D₁: { 0, 0, 0 } — a∨b∨c
D₂: { 1, 0, 0 } — ¬a∨b∨c
D₃: { 1, 1, 0 } — ¬a∨¬b∨c

Об'єднаємо диз'юнкції за допомогою кон'юнкції та отримаємо досконалу кон'юнктивну нормальну форму:

---

Побудова полінома Жегалкіна:

Додамо новий стовпець до таблиці істинності і запишемо в 1, 3, 5 і 7 рядки значення з тих же рядків попереднього стовпця таблиці істинності, а значення в рядках 2, 4, 6 і 8 складемо по модулю два зі значеннями відповідно 1, 3, 5 та 7 рядків:

Додамо новий стовпець до таблиці істинності і запишемо в 1 і 2, 5 і 6 рядки значення з тих же рядків попереднього стовпця таблиці істинності, а значення в рядках 3 і 4, 7 і 8 складемо по модулю два зі значеннями відповідно 1 і 2, 5 та 6 рядків:

Додамо новий стовпець до таблиці істинності і запишемо в 1 2, 3 і 4 рядки значення з тих же рядків попереднього стовпця таблиці істинності, а значення в рядках 5, 6, 7 і 8 складемо по модулю два зі значеннями відповідно 1, 2, 3 та 4 рядків:

Остаточно отримаємо таку таблицю:

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

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc

Об'єднуючи отримані кон'юнкції за допомогою операції виключне АБО, отримаємо поліном Жегалкіна: c⊕b⊕bc⊕ab⊕abc