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