Зміст:
- Визначення - Що означає нормальна форма диз'юнктури (DNF)?
- Техопедія пояснює диз'юнктивну нормальну форму (DNF)
Визначення - Що означає нормальна форма диз'юнктури (DNF)?
Диз'юнктивна нормальна форма (DNF) - це нормалізація логічної формули в булевій математиці. Іншими словами, логічна формула вважається в нормальній диз'юнктній формі, якщо це диз'юнкція сполучників з кожною змінною і її заперечення присутнє один раз у кожній сполучнику. Усі диз'юнктивні нормальні форми неоднозначні, оскільки всі диз'юнктивні нормальні форми для одного і того ж пропозиції взаємно еквівалентні.
Диз'юнктивна нормальна форма широко застосовується в таких сферах, як автоматизоване доведення теорем.
Техопедія пояснює диз'юнктивну нормальну форму (DNF)
Логічна формула знаходиться в нормальній диз'юнктній формі лише тоді, коли існує чергування однієї чи декількох сполучників однієї чи декількох літералів. Формула вважається повною диз'юнктивною нормальною формою, якщо всі задіяні змінні представлені лише один раз у кожному пункті. Подібно до кон'юнктивної нормальної форми, пропозиційні оператори в диз'юнктивной нормальній формі однакові: І, АБО і НЕ.
Всі логічні формули можуть бути перетворені в еквівалентну нормальну форму диз'юнкту. Однак у деяких випадках експоненціальний вибух логічної функції можливий через перетворення у диз'юнктивну нормальну форму. Ще одним важливим моментом є те, що будь-яка унікальна булева функція може бути представлена лише однією і унікальною повною диз'юнктивною нормальною формою. За допомогою таких методів, як метод таблиці істинності, дерева істинності або таблиця логічних еквівалентів, може формуватися диз'юнктивна нормальна форма для логічних формул. K-DNF, варіація диз'юнктивної нормальної форми, широко використовується і популярна при вивченні обчислювальної складності.
