Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно

Известны два способа минимизации дизъюнктивных нормальных форм:

Визуализация гиперкубами

Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур). Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать названиям переменных). Затем каждую вершину обрабатываем следующим образом:

• Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт [math](\neg X \and Y \and Z)[/math], он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.
• В противном случае мы помещаем в вершину закрашенный белый кружок.

Например, для такой ДНФ: [math](X \and \neg Y \and Z) \or (X \and Y \and Z) \or (\neg X \and Y \and Z) \or (\neg X \and Y \and \neg Z) \or ( X \and Y \and \neg Z)[/math] мы получим такой гиперкуб:

Далее обработка гиперкуба идёт следующим образом:

• Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт [math]Y[/math].
• Если в данном гиперкубе есть ребро, все вершины на котором закрашены чёрным, то мы можем записать его в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт [math](Y \and Z)[/math].

В итоге нашу изначальную ДНФ можно записать как [math](Y) \or (X \and \neg Y \and Z)[/math].