Кожна формула має кінцеве число входжень змінних. Під входженням змінної розуміється місце, яке змінна займає у формулі. Завдання полягає в тому, щоб для даної булевої функції f знайти ДНФ, що представляє цю функцію і має найменше число входжень змінних.
Якщо х - логічна змінна, а σ∈, то вираз
¬x якщо σ = 0
називається літерою. Кон'юнктів називається кон'юнкція літер. Наприклад, формули XY¬Z і XYX¬X є Кон'юнктів. Елементарним твором називається Кон'юнктів, в який будь-яка змінна входить не більше одного разу (або сама, або її заперечення).
Формула f1 називається импликантой формули f, якщо f1 - елементарне твір і f1f = f1, т. Е. Для відповідних формулах функцій справедливо нерівність f1≤f. Импликанта f1 формули f називається простий, якщо після відкидання будь-якої літери з f1 не виходить формула, яка є импликантой формули f.
Приклад. Знайдемо всі імпліканти і прості імпліканти для формули f = X → Y. Всього є 8 елементарних творів зі змінними X і Y. Нижче, для наочності, наведено їх таблиці істинності.
У тупикову ДНФ вибирається мінімальне число простих импликант, диз'юнкція яких зберігає всі констітуенти одиниці, т. Е. Кожен стовпець матриці Квайна містить зірочку, що стоїть на перетині з рядком, що відповідає одній з обраних импликант. Як мінімальної ДНФ вибирається тупикова, яка має найменше число входжень змінних.
У попередньому прикладі по матриці Квайна знаходимо, що мінімальна ДНФ заданої функції є ¬X¬YvXZ.
Зауваження. Для побудови мінімальної КНФ функції f, досить побудувати мінімальну ДНФ для функції f, а потім використовувати f = ¬ (¬f) і закони де Моргана.