Изменения

#REDIRECT [[Сокращённая и минимальная ДНФ #Минимизация ДНФ]]Рассмотрим два способа [[Сокращенная и минимальная ДНФ|минимизации дизъюнктивных нормальных форм]]:

*Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт <mathtex>(\neg X \and wedge Y \and wedge Z)</mathtex>, он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.

Например, для такой ДНФ: <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> мы получим такой гиперкуб: <br><br> [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]

Далее обработка гиперкуба идёт следующим образом:<br>Пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (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)</tex>.*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт <tex>(X \wedge \neg Y \wedge Z)</mathtex>.

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

!<tex> w</tex> !<tex> w</tex> !не <tex> \neg w</tex> !не <tex> \neg w</tex>

!<tex>z</tex> !не <tex> \neg z</tex> !не <tex> \neg z</tex> !<tex>z</tex>

!<tex>y</tex> !<tex>x</tex>

!<tex>y</tex> !не <tex> \neg x</tex>

!не <tex> \neg y</tex> !не <tex> \neg x</tex>

!не <tex> \neg y</tex> !<tex>x</tex>

<mathtex>(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 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>

!<tex> w</tex> !<tex> w</tex> !не <tex> \neg w</tex> !не <tex> \neg w</tex>

!<tex>z</tex> !не <tex> \neg z</tex> !не <tex> \neg z</tex> !<tex>z</tex>

!<tex>y</tex> !<tex>x</tex> |1 |1 | | |- !<tex>y</tex> !<tex> \neg x</tex> |

!<tex> \neg y</tex> !не <tex> \neg x</tex> |1

!не <tex> \neg y</tex> !не <tex>x</tex>

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

!<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> |style="background:#F4A460"|1 |style="background:#F4A460"|1 |style="background:#F4A460"|1 |style="background:#F4A460"|1

!<mathtex> y </mathtex> !<mathtex> \neg x</mathtex> |style="background:#F4A460"|1 |style="background:#F4A460"|1

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

!<mathtex> \neg y</mathtex> !<mathtex> x </mathtex> |style="background:#D2B48C"|1 |style="background:#D2B48C"|1

|style="background:#7FFFD4"|1 |style="background:#7FFFD4"|1|}

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