Доскона́лою диз'юнкти́вною норма́льною фо́рмою (ДДНФ) булевої функції називається диз'юнкція тих конституент одиниці, які перетворюються в одиницю на тих самих наборах змінних, що й задана функція. ДДНФ повинна задовольняти наступним умовам: в ній немає однакових доданків; жоден із доданків не містить двох однакових співмножників; жоден із доданків не містить змінну разом із її запереченням; в кожному окремому доданку є як співмножник або змінна xi, або її заперечення для будь-якого i = 1, 2, …, n. Для будь-якої функції булевої алгебри існує своя ДДНФ, причому тільки одна.
Приклад знаходження ДДНФ Для того, щоб отримати ДДНФ функції, потрібно скласти її таблицю істинності. Наприклад, візьмемо одну з таблиць істинності з статті Метод Куайна, в якій знаходження ДДНФ зустрічається декілька разів:
0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1
В комірках результату відмічаються лишень ті комбінації, які приводять логічний вираз до одиниці. Далі розглядається значення змінних при яких функція дорівнює 1. Якщо значення змінної дорівнює 0, то вона записується з інверсією. Якщо значення змінної дорівнює 1, то вона записується без інверсії. Перший стовпець містить 1 в заданому полі. Відмічаються значення всіх чотирьох змінних це: = 0 = 0 = 0 = 0 Нульові значення — тут всі змінні представлені нулями — записуються в кінцевому виразі інверсією цієї змінної. Перший член ДДНФ даної функції має такий вигляд: Змінні другого члена: = 0 = 0 = 0 = 1
в цьому випадку буде представлений без інверсії:
Таким чином аналізуються всі комірки . ДДНФ цієї функції буде диз'юнкцією всіх отриманих членів (елементарних кон'юнкцій).
Досконала ДНФ цієї функції:
Див. також Нормальна форма формули у логіці предикатів ДНФ КНФ Досконала кон'юнктивна нормальна форма
Посилання
Примітки