Съдържание:
- Определение - Какво означава дизъюнктивна нормална форма (DNF)?
- Техопедия обяснява дизъюнктивна нормална форма (DNF)
Определение - Какво означава дизъюнктивна нормална форма (DNF)?
Дисюнктивна нормална форма (DNF) е нормализирането на логическа формула в булева математика. С други думи, логична формула се казва, че е в дизюнктивна нормална форма, ако това е дизъюнкция на съединенията с всяка променлива и нейното отрицание присъства веднъж във всяка връзка. Всички дизюнктивни нормални форми са нееднозначни, тъй като всички дизюнктивни нормални форми за едно и също предложение са взаимно еквивалентни.
Дисюнктивната нормална форма се използва широко в области като автоматизирано доказване на теореми.
Техопедия обяснява дизъюнктивна нормална форма (DNF)
Логическата формула е в дизюнктивна нормална форма, ако и само ако има редуване на един или повече съединения на един или повече буквали. Формулата се счита за пълна дизюнктивна нормална форма, ако всички включени променливи са представени само веднъж във всяка клауза. Подобно на конюнктивната нормална форма, предложените оператори в дизюнктивна нормална форма са еднакви: И, ИЛИ и НЕ.
Всички логически формули могат да бъдат преобразувани в еквивалентна дизюнктивна нормална форма. В някои случаи обаче е възможна експоненциална експлозия на логическата функция поради преобразуване в дизюнктивна нормална форма. Друг забележим момент е, че всяка уникална булева функция може да бъде представена само с една и уникална пълна дизъюнктивна нормална форма. С помощта на техники като метода на таблицата за истинност, дървета на истината или таблица с логически еквивалентности може да се генерира дизъюнктивна нормална форма за логически формули. K-DNF, вариант на дизюнктивна нормална форма, е широко използван и популярен при изследването на изчислителната сложност.
