Кон'юнктивна нормальна форма - це
Формули не в КНФ:
Але ці 3 формули не в КНФ еквівалентні такими формулами в КНФ:
побудова КНФ
Алгоритм побудови КНФ
1) Позбутися від всіх логічних операцій, що містяться у формулі, замінивши їх основними: кон'юнкція, диз'юнкція, запереченням. Це можна зробити, використовуючи рівносильні формули:
2) Замінити знак заперечення, що відноситься до всього висловом, знаками заперечення, що відносяться до окремих змінним висловлювань на підставі формул:
3) Позбутися від знаків подвійного заперечення.
4) Застосувати, якщо потрібно, до операцій кон'юнкції і диз'юнкції властивості дистрибутивности і формули поглинання.
Приклад побудови КНФ
Наведемо до КНФ формулу
Перетворимо формулу F до формули яка не містить →:
В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:
k -кон'юнктівная нормальна форма
k -кон'юнктівной нормальною формою називають кон'юнктівную нормальну форму, в якій кожна диз'юнкція містить рівно k литералов.
Наприклад, наступна формула записана в 2-КНФ:
Перехід від КНФ до СКНФ
Якщо в простій диз'юнкції не вистачає якоїсь змінної (наприклад, z), то додаємо в неї вираз: (це не змінює самої диз'юнкції), після чого розкриваємо дужки з використанням розподільного закону:
Таким чином, з КНФ отримана СКНФ.
Формальна граматика, що описує КНФ
Наступна формальна граматика описує всі формули, приведені до КНФ:
<КНФ> → <дизъюнкт> <КНФ> → <КНФ> ∧ <дизъюнкт> <дизъюнкт> → <литерал> <дизъюнкт> → (<дизъюнкт> ∨ <литерал>) <литерал> → <терм> <литерал> → ¬<терм>
де <терм> позначає довільну булеву змінну.
Завдання здійсненності формули в КНФ
В теорії обчислювальної складності важливу роль відіграє завдання здійсненності булевих формул в кон'юнктивній нормальній формі. Згідно з теоремою Кука. ця задача NP-повна. і вона зводиться до задачі про здійсненності формул в 3-КНФ, яка зводиться і до якої в свою чергу зводяться інші NP-повні задачі.
Завдання про здійсненності 2-КНФ формул може бути вирішена за лінійний час.
Примітки
література
Дивитися що таке "Кон'юнктивна нормальна форма" в інших словниках:
Кон'юнктивна нормальна форма - пропозіціональная формула, що має вигляд (*) де кожне З ij, i = 1. п; j = 1. mi, є або змінна, або заперечення змінної. К. н. ф. (*) Є тавтологією тоді і тільки тоді, коли для будь-якого iсреді З i1. Cimi. ... ... Математична енциклопедія
K-кон'юнктивна нормальна форма - (k КНФ) в булевої логіки нормальна форма, в якій булева формула має вигляд кон'юнкції декількох диз'юнктів, кожен з яких містить рівно k литералов. Наприклад, наступна формула записана в 2 КНФ ... Вікіпедія
Нормальна форма (значення) - нормальна форма: Нормальна форма в базах даних якість зв'язку в реляційної моделі даних. Нормальна форма в математиці в будь-якому сенсі найпростіший або канонічний вигляд, до якого об'єкт наводиться перетвореннями, ... ... Вікіпедія
Диз'юнктивна нормальна форма - (ДНФ) в булевої логіки нормальна форма, в якій булева формула має вигляд диз'юнкції кон'юнкція літералів. Будь-яка булева формула може бути приведена до ДНФ. [1] Для цього можна використовувати закон подвійного заперечення, закон де Моргана, закон ... ... Вікіпедія
ДОСКОНАЛА НОРМАЛЬНАЯ ФОРМА - досконала діз'юнктівная або досконала кон'юнктивна нормальна форма (див. Булевих функцій нормальні форми) ... Математична енциклопедія
Булева функція - В даній статті або розділі є список джерел або зовнішніх посилань, але джерела окремих тверджень залишаються неясними через відсутність виносок ... Вікіпедія
Булеві вирази - В теорії дискретних функціональних систем булевої функцією називають функцію типу. де булево безліч, а n невід'ємне ціле число, яке називають арность або місцевістю функції. Елементи 1 (одиниця) і 0 (нуль) стандартно інтерпретують ... ... Вікіпедія
- Дискретна математика і математична логіка Частина I. Євгена Філенко. Дана робота включає в себе необхідні довідкові відомості і типові приклади за такими розділами, ряд з яких недостатньо висвітлений в наявній навчальній літературі: 1. Множини і ... Детальніше Купити за 4887 грн (тільки Україна)