Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
Рассмотрим два способа минимизации дизъюнктивных нормальных форм:
Визуализация гиперкубами
Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур). Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать названиям переменных). Затем каждую вершину обрабатываем следующим образом:
- Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт , он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.
- В противном случае мы помещаем в вершину закрашенный белый кружок.
Например, для такой ДНФ: мы получим такой гиперкуб: 
Далее обработка гиперкуба идёт следующим образом:
- Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт .
- Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт .
- И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт .
В итоге нашу изначальную ДНФ можно записать как .
Карты Карно
Этот способ работает при количестве переменных не более 4.
Мы рисуем следующую таблицу n*n, где n — количество переменных:
Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы. Например, ДНФ
будет выглядеть на картах Карно так:
| 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | ||
| 1 | |||||
| 1 | 1 |
- Теперь мы покрываем непересекающиеся прямоугольниками с максимальной площадью те ячейки карт Карно, которые содержат в себе единицу до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так:)
| 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | ||
| 1 | |||||
| 1 | 1 |
- После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:
