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

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

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

Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур). Сначала мы рисуем куб в системе отсчёта 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].
• И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт [math](X \and \neg Y \and Z)[/math].

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

Карты Карно

Этот способ работает при количестве переменных не более 4.

Мы рисуем следующую таблицу n*n, где n — количество переменных:

		[math] w [/math]	[math] w [/math]	[math] \neg w[/math]	[math] \neg w[/math]
		[math]z[/math]	[math] \neg z[/math]	[math] \neg z[/math]	[math]z[/math]
[math]y[/math]	[math]x[/math]
[math]y[/math]	[math] \neg x[/math]
[math] \neg y[/math]	[math] \neg x[/math]
[math] \neg y[/math]	[math]x[/math]

Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы. Например, ДНФ

[math](X \and Y \and Z \and W) \or (X \and Y \and \neg Z \and W) \or (X \and Y \and \neg Z \and \neg W) \or (X \and Y \and Z \and \neg W) \or (\neg X \and Y \and Z \and W) \or (\neg X \and Y \and \neg Z \and W) \or (\neg X \and Y \and \neg Z \and \neg W) \or (\neg X \and Y \and Z \and \neg W) \or (X \and \neg Y \and Z \and W) \or (X \and \neg Y \and \neg Z \and W) \or (\neg X \and \neg Y \and \neg Z \and \neg W)[/math]

будет выглядеть на картах Карно так:

		[math] w [/math]	[math] w [/math]	[math] \neg w[/math]	[math] \neg w[/math]
		[math]z[/math]	[math] \neg z[/math]	[math] \neg z[/math]	[math]z[/math]
[math]y[/math]	[math]x[/math]	1	1	1	1
[math]y[/math]	[math] \neg x[/math]	1	1	1	1
[math] \neg y[/math]	[math] \neg x[/math]			1
[math] \neg y[/math]	[math]x[/math]	1	1

• Теперь мы покрываем непересекающиеся прямоугольниками с максимальной площадью те ячейки карт Карно, которые содержат в себе единицу до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так:)

		[math] w [/math]	[math] w [/math]	[math] \neg w[/math]	[math] \neg w[/math]
		[math] z [/math]	[math] \neg z[/math]	[math] \neg z[/math]	[math] z [/math]
[math] y [/math]	[math] x [/math]	1	1	1	1
[math] y [/math]	[math] \neg x[/math]	1	1	1	1
[math] \neg y[/math]	[math] \neg x[/math]			1
[math] \neg y[/math]	[math] x [/math]	1	1

• После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника: [math]Y \and (X \and \neg Y \and W) \and (X \and \neg Y \and \neg Z \and \neg W)[/math]

См. также

Сокращенная и минимальная ДНФ