Изменения

Например, для такой ДНФ: <mathtex>(X \and wedge \neg Y \and wedge Z) \or vee (X \and wedge Y \and wedge Z) \or vee (\neg X \and wedge Y \and wedge Z) \or vee (\neg X \and wedge Y \and wedge \neg Z) \or vee ( X \and wedge Y \and wedge \neg Z)</mathtex> мы получим такой гиперкуб: [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]

*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <mathtex>Y</mathtex>.*Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <mathtex>(Y \and wedge Z)</mathtex>.*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт <mathtex>(X \and wedge \neg Y \and wedge Z)</mathtex>.

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

!<mathtex> w </mathtex> !<mathtex> w </mathtex> !<mathtex> \neg w</mathtex> !<mathtex> \neg w</mathtex>

!<mathtex>z</mathtex> !<mathtex> \neg z</mathtex> !<mathtex> \neg z</mathtex> !<mathtex>z</mathtex>

!<mathtex>y</mathtex> !<mathtex>x</mathtex>

!<mathtex>y</mathtex> !<mathtex> \neg x</mathtex>

!<mathtex> \neg y</mathtex> !<mathtex> \neg x</mathtex>

!<mathtex> \neg y</mathtex> !<mathtex>x</mathtex>

<mathtex>(X \and wedge Y \and wedge Z \and wedge W) \or vee (X \and wedge Y \and wedge \neg Z \and wedge W) \or vee (X \and wedge Y \and wedge \neg Z \and wedge \neg W) \or vee (X \and wedge Y \and wedge Z \and wedge \neg W) \or vee (\neg X \and wedge Y \and wedge Z \and wedge W) \or vee (\neg X \and wedge Y \and wedge \neg Z \and wedge W) \or vee (\neg X \and wedge Y \and wedge \neg Z \and wedge \neg W) \or vee (\neg X \and wedge Y \and wedge Z \and wedge \neg W) \or vee (X \and wedge \neg Y \and wedge Z \and wedge W) \or vee (X \and wedge \neg Y \and wedge \neg Z \and wedge W) \or vee (\neg X \and wedge \neg Y \and wedge \neg Z \and wedge \neg W)</mathtex>

!<mathtex> w </mathtex> !<mathtex> w </mathtex> !<mathtex> \neg w</mathtex> !<mathtex> \neg w</mathtex>

!<mathtex>z</mathtex> !<mathtex> \neg z</mathtex> !<mathtex> \neg z</mathtex> !<mathtex>z</mathtex>

!<mathtex>y</mathtex> !<mathtex>x</mathtex>

!<mathtex>y</mathtex> !<mathtex> \neg x</mathtex>

!<mathtex> \neg y</mathtex> !<mathtex> \neg x</mathtex>

!<mathtex> \neg y</mathtex> !<mathtex>x</mathtex>

!<mathtex> w </mathtex> !<mathtex> w </mathtex> !<mathtex> \neg w</mathtex> !<mathtex> \neg w</mathtex>

!<mathtex> z </mathtex> !<mathtex> \neg z</mathtex> !<mathtex> \neg z</mathtex> !<mathtex> z </mathtex>

!<mathtex> y </mathtex> !<mathtex> x </mathtex>

!<mathtex> y </mathtex> !<mathtex> \neg x</mathtex>

!<mathtex> \neg y</mathtex> !<mathtex> \neg x</mathtex>

!<mathtex> \neg y</mathtex> !<mathtex> x </mathtex>

*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:&nbsp;<mathtex>Y \and wedge (X \and wedge \neg Y \and wedge W) \and wedge (\neg X \and wedge \neg Y \and wedge \neg Z \and wedge \neg W)</mathtex>