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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Карты Карно)
 
(не показаны 22 промежуточные версии 6 участников)
Строка 1: Строка 1:
Рассмотрим два способа минимизации дизъюнктивных нормальных форм:
+
#REDIRECT [[Сокращённая и минимальная ДНФ #Минимизация ДНФ]]
 +
Рассмотрим два способа [[Сокращенная и минимальная ДНФ|минимизации дизъюнктивных нормальных форм]]:
  
 
== Визуализация гиперкубами ==
 
== Визуализация гиперкубами ==
Строка 5: Строка 6:
 
Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур).
 
Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур).
 
Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать названиям переменных). Затем каждую вершину обрабатываем следующим образом:
 
Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать названиям переменных). Затем каждую вершину обрабатываем следующим образом:
*Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт <math>(\neg X \and Y \and Z)</math>, он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.
+
*Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт <tex>(\neg X \wedge Y \wedge Z)</tex>, он равен единице при 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> мы получим такой гиперкуб: [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]
+
Например, для такой ДНФ: <tex>(X \wedge \neg Y \wedge Z) \vee (X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge \neg Z) \vee ( X \wedge Y \wedge \neg Z)</tex> мы получим такой гиперкуб:<br><br> [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]
  
Далее обработка гиперкуба идёт следующим образом:
+
Далее обработка гиперкуба идёт следующим образом:<br>
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (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>.
+
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <tex>Y</tex>.
*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт <math>(X \and \neg Y \and Z)</math>.
+
*Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <tex>(Y \wedge Z)</tex>.
 +
*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт <tex>(X \wedge \neg Y \wedge Z)</tex>.
  
В итоге нашу изначальную ДНФ можно записать как <math>(Y) \or (X \and \neg Y \and Z)</math>.
+
В итоге нашу изначальную ДНФ можно записать как <tex>(Y) \vee (X \wedge Z)</tex>.
  
 
== Карты Карно ==
 
== Карты Карно ==
Строка 25: Строка 27:
 
  |
 
  |
 
  |
 
  |
  !<math> w </math>
+
  !<tex> w </tex>
  !<math> w </math>
+
  !<tex> w </tex>
  !<math> \neg w</math>
+
  !<tex> \neg w</tex>
  !<math> \neg w</math>
+
  !<tex> \neg w</tex>
 
  |-
 
  |-
 
  |
 
  |
 
  |
 
  |
  !<math>z</math>
+
  !<tex>z</tex>
  !<math> \neg z</math>
+
  !<tex> \neg z</tex>
  !<math> \neg z</math>
+
  !<tex> \neg z</tex>
  !<math>z</math>
+
  !<tex>z</tex>
 
  |-
 
  |-
  !<math>y</math>
+
  !<tex>y</tex>
  !<math>x</math>
+
  !<tex>x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 44: Строка 46:
 
  |
 
  |
 
  |-
 
  |-
  !<math>y</math>
+
  !<tex>y</tex>
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 51: Строка 53:
 
  |
 
  |
 
  |-
 
  |-
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 58: Строка 60:
 
  |
 
  |
 
  |-
 
  |-
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
  !<math>x</math>
+
  !<tex>x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 68: Строка 70:
 
<br>
 
<br>
 
<br>
 
<br>
<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>
+
<tex>(\neg X \wedge Y \wedge Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge \neg W) \vee (\neg X \wedge Y \wedge Z \wedge \neg W) \vee (X \wedge \neg Y \wedge Z \wedge W) \vee (X \wedge \neg Y \wedge \neg Z \wedge W) \vee (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)</tex>
 
<br>
 
<br>
 
<br>
 
<br>
Строка 77: Строка 79:
 
  |
 
  |
 
  |
 
  |
  !<math> w </math>
+
  !<tex> w </tex>
  !<math> w </math>
+
  !<tex> w </tex>
  !<math> \neg w</math>
+
  !<tex> \neg w</tex>
  !<math> \neg w</math>
+
  !<tex> \neg w</tex>
 
  |-
 
  |-
 
  |
 
  |
 
  |
 
  |
  !<math>z</math>
+
  !<tex>z</tex>
  !<math> \neg z</math>
+
  !<tex> \neg z</tex>
  !<math> \neg z</math>
+
  !<tex> \neg z</tex>
  !<math>z</math>
+
  !<tex>z</tex>
 
  |-
 
  |-
  !<math>y</math>
+
  !<tex>y</tex>
  !<math>x</math>
+
  !<tex>x</tex>
  |1
+
  |
  |1
+
  |
 +
|
 +
|
 +
|-
 +
!<tex>y</tex>
 +
!<tex> \neg x</tex>
 +
|
 
  |1
 
  |1
 
  |1
 
  |1
 +
|
 
  |-
 
  |-
  !<math>y</math>
+
  !<tex> \neg y</tex>
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
  |1
+
  |
 
  |1
 
  |1
 
  |1
 
  |1
 
  |1
 
  |1
 
  |-
 
  |-
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
  !<math> \neg x</math>
+
  !<tex>x</tex>
 
  |
 
  |
 
  |
 
  |
 
  |1
 
  |1
|
 
|-
 
!<math> \neg y</math>
 
!<math>x</math>
 
 
  |1
 
  |1
|1
 
|
 
|
 
 
  |}
 
  |}
 
<br>
 
<br>
*Теперь мы покрываем непересекающимися прямоугольниками (длины сторон которых — степени двойки (1, 2, 4)) с максимальной площадью те ячейки карт Карно, которые содержат в себе единицу до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так):
+
*Теперь мы покрываем прямоугольниками (длины сторон которых — степени двойки (1, 2, 4)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так):
 
<br>
 
<br>
 
{| border="1"
 
{| border="1"
 
  |
 
  |
 
  |
 
  |
  !<math> w </math>  
+
  !<tex> w </tex>  
  !<math> w </math>  
+
  !<tex> w </tex>  
  !<math> \neg w</math>
+
  !<tex> \neg w</tex>
  !<math> \neg w</math>
+
  !<tex> \neg w</tex>
 
  |-
 
  |-
 
  |
 
  |
 
  |
 
  |
  !<math> z </math>  
+
  !<tex> z </tex>  
  !<math> \neg z</math>
+
  !<tex> \neg z</tex>
  !<math> \neg z</math>
+
  !<tex> \neg z</tex>
  !<math> z </math>  
+
  !<tex> z </tex>  
 
  |-
 
  |-
  !<math> y </math>  
+
  !<tex> y </tex>  
  !<math> x </math>  
+
  !<tex> x </tex>  
  |style="background:#F4A460"|1
+
  |
  |style="background:#F4A460"|1
+
  |
  |style="background:#F4A460"|1
+
  |
  |style="background:#F4A460"|1
+
  |
 
  |-
 
  |-
  !<math> y </math>  
+
  !<tex> y </tex>  
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
  |style="background:#F4A460"|1
+
  |
|style="background:#F4A460"|1
 
 
  |style="background:#F4A460"|1
 
  |style="background:#F4A460"|1
 
  |style="background:#F4A460"|1
 
  |style="background:#F4A460"|1
 +
|
 
  |-
 
  |-
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
|
 
 
  |
 
  |
 +
|style="background:#F4A460"|1
 +
|style="background:#B4D19A"|1
 
  |style="background:#7FFFD4"|1
 
  |style="background:#7FFFD4"|1
|
 
 
  |-
 
  |-
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
  !<math> x </math>  
+
  !<tex> x </tex>  
|style="background:#D2B48C"|1
 
|style="background:#D2B48C"|1
 
 
  |
 
  |
 
  |
 
  |
  |}
+
  |style="background:#7FFFD4"|1
 +
|style="background:#7FFFD4"|1
 +
|}
 
<br>
 
<br>
*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:&nbsp;<math>Y \and (X \and \neg Y \and W) \and (X \and \neg Y \and \neg Z \and \neg W)</math>
+
*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:&nbsp;<tex>(\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)</tex>
  
 
== См. также ==
 
== См. также ==
 
[[Сокращенная и минимальная ДНФ]]
 
[[Сокращенная и минимальная ДНФ]]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Булевы функции ]]

Текущая версия на 00:09, 1 февраля 2019

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

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

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

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

Например, для такой ДНФ: [math](X \wedge \neg Y \wedge Z) \vee (X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge \neg Z) \vee ( X \wedge Y \wedge \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 \wedge Z)[/math].
  • И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт [math](X \wedge \neg Y \wedge Z)[/math].

В итоге нашу изначальную ДНФ можно записать как [math](Y) \vee (X \wedge 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](\neg X \wedge Y \wedge Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge \neg W) \vee (\neg X \wedge Y \wedge Z \wedge \neg W) \vee (X \wedge \neg Y \wedge Z \wedge W) \vee (X \wedge \neg Y \wedge \neg Z \wedge W) \vee (\neg X \wedge \neg Y \wedge \neg Z \wedge \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]
[math]y[/math] [math] \neg x[/math] 1 1
[math] \neg y[/math] [math] \neg x[/math] 1 1 1
[math] \neg y[/math] [math]x[/math] 1 1


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


[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] 1 1
[math] \neg y[/math] [math] \neg x[/math] 1 1 1
[math] \neg y[/math] [math] x [/math] 1 1


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

См. также

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