- будь-які два доданків розрізняються як мінімум в двох позиціях,
- жоден з Кон'юнктів не міститься в іншому.
Наприклад: міститься в.
Функцію можна записати за допомогою скороченою ДНФ не єдиним способом.
Запишемо функцію (медіана) у вигляді досконалої ДНФ. . Відомо, що цей вислів рівносильне наступному:. Винесемо в кожної дужки загальний Кон'юнктів (наприклад, в першій. Так як, то такий Кон'юнктів не впливає на значення виразу, і його можна опустити. Отримаємо в результаті формулу.
[Ред] Мінімальна ДНФ
Мінімальна ДНФ (англ. Minimal disjunctive normal form) - така скорочена ДНФ, в якій міститься мінімальна кількість входжень змінних.
Кожна мінімальна ДНФ є скороченою, але не кожна скорочена - мінімальна. Наприклад, запис є мінімальною ДНФ для медіани (вона ж скорочена, як видно в прикладі вище); а запис - не мінімальний, але скорочена ДНФ.
[Ред] Мінімізація ДНФ
Розглянемо кілька способів мінімізації діз'юнктівних нормальних форм:
[Ред] Візуалізація гіперкуби
Цей спосіб працює при кількості змінних не більше трьох (в іншому необхідно вводити четвертого чи наступні за ним вимірювання для подання фігур). Спочатку ми малюємо куб в системі відліку (назви координатних осей співпадають з назвами змінних). Потім кожну вершину обробляємо наступним чином:
Якщо у нас Кон'юнктів, змінні в якому дорівнюють відповідним координатам вершини, то в цю вершину ми поміщаємо зафарбований чорним гурток.
Вершині з координатами відповідає Кон'юнктів, він дорівнює одиниці при та)
В іншому випадку ми поміщаємо в вершину зафарбований білий кружок.
Для такої ДНФ: ми отримаємо наступний гиперкуб (див. Малюнок)
Далі обробка гиперкуба йде наступним чином:
поки у нас є незафарбовані вершини, ми вибираємо грань, або вершину, або ребро, на яких найбільше зафарбованих чорним вершин і ще не оброблених вершин.
Якщо в даному гиперкубе є грань, все вершини на якій зафарбовані чорним, то ми можемо записати її в якості Кон'юнктів, де буде тільки змінна з незмінних відповідної їй координатою.
Грань, на якій лежать зафарбовані вершини і ми можемо записати як Кон'юнктів.
Тепер ми дивимося, чи залишилися на ребрах куба зафарбовані і не відмічені нами в ДНФ вершини. Якщо - так, то ребра з такими вершинами ми можемо записати як Кон'юнктів, де будуть тільки змінні з незмінюються відповідним їм координатами
Ребро, що з'єднує зафарбовані вершини і ми можемо записати як Кон'юнктів.
І якщо після такої обробки у нас залишилися вільні вершини, ми просто переписуємо координати кожної такої вершини в окремий Кон'юнктів, рівний.
Вершину ми б переписали як Кон'юнктів.
У підсумку нашу споконвічну ДНФ можна записати як.
[Ред] Карти Карно
Побудуємо наступну таблицю, де - число змінних:
Тепер покриваємо прямокутниками (довжини сторін яких - ступеня двійки ()) ті осередки карт Карно, які містять в собі одиницю (на кожному ходу ми вибираємо такий прямокутник, щоб він покривав найбільшу кількість ще не покритих клітин) до тих пір, поки не покриємо всі такі осередки.
Для карт Карно на прикладі це виглядало б так:
Обидві елементарні кон'юнкції на даному етапі є елементами скороченою ДНФ.
В результаті виконання алгоритму ми отримуємо наступну скорочену ДНФ:
Перехід від скороченою форми до мінімальної:
- Одиниці ДНФ, що покриваються елементами або позначаються "+". Пари і, що потрапляють в ядро позначаються "*".
- Одиниці функції, які покриваються тільки якимось одним Кон'юнктів з системи елементів скороченою ДНФ, позначаються ">".
- Одиниці функції, що покриваються ядром, але не покриваються тільки якимось одним Кон'юнктів з системи елементів скороченою ДНФ позначаються ">>".