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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
*В противном случае мы помещаем в вершину закрашенный белый кружок.
 
*В противном случае мы помещаем в вершину закрашенный белый кружок.
  
−
Например, для такой ДНФ: <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> мы получим такой гиперкуб: [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]
  
 
Далее обработка гиперкуба идёт следующим образом:
 
Далее обработка гиперкуба идёт следующим образом:
−
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <math>Y</math>.
+
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <tex>Y</tex>.
−
*Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <math>(Y \and Z)</math>.
+
*Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <tex>(Y \wedge Z)</tex>.
−
*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт <math>(X \and \neg Y \and Z)</math>.
+
*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 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 \neg Y \wedge Z)</tex>.
  
 
== Карты Карно ==
 
== Карты Карно ==
Строка 25: Строка 25:
 
  |
 
  |
 
  |
 
  |
−
  !<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: Строка 44:
 
  |
 
  |
 
  |-
 
  |-
−
  !<math>y</math>
+
  !<tex>y</tex>
−
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 51: Строка 51:
 
  |
 
  |
 
  |-
 
  |-
−
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
−
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 58: Строка 58:
 
  |
 
  |
 
  |-
 
  |-
−
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
−
  !<math>x</math>
+
  !<tex>x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 68: Строка 68:
 
<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>(X \wedge Y \wedge Z \wedge W) \vee (X \wedge Y \wedge \neg Z \wedge W) \vee (X \wedge Y \wedge \neg Z \wedge \neg W) \vee (X \wedge Y \wedge Z \wedge \neg W) \vee (\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: Строка 77:
 
  |
 
  |
 
  |
 
  |
−
  !<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
 
  |1
 
  |1
Строка 96: Строка 96:
 
  |1
 
  |1
 
  |-
 
  |-
−
  !<math>y</math>
+
  !<tex>y</tex>
−
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |1
 
  |1
 
  |1
 
  |1
Строка 103: Строка 103:
 
  |1
 
  |1
 
  |-
 
  |-
−
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
−
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 110: Строка 110:
 
  |
 
  |
 
  |-
 
  |-
−
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
−
  !<math>x</math>
+
  !<tex>x</tex>
 
  |1
 
  |1
 
  |1
 
  |1
Строка 123: Строка 123:
 
  |
 
  |
 
  |
 
  |
−
  !<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
Строка 142: Строка 142:
 
  |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
Строка 149: Строка 149:
 
  |style="background:#F4A460"|1
 
  |style="background:#F4A460"|1
 
  |-
 
  |-
−
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
−
  !<math> \neg x</math>
+
  !<tex> \neg x</tex>
 
  |
 
  |
 
  |
 
  |
Строка 156: Строка 156:
 
  |
 
  |
 
  |-
 
  |-
−
  !<math> \neg y</math>
+
  !<tex> \neg y</tex>
−
  !<math> x </math>  
+
  !<tex> x </tex>  
 
  |style="background:#D2B48C"|1
 
  |style="background:#D2B48C"|1
 
  |style="background:#D2B48C"|1
 
  |style="background:#D2B48C"|1
Строка 164: Строка 164:
 
  |}
 
  |}
 
<br>
 
<br>
−
*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:&nbsp;<math>Y \and (X \and \neg Y \and W) \and (\neg X \and \neg Y \and \neg Z \and \neg W)</math>
+
*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:&nbsp;<tex>Y \wedge (X \wedge \neg Y \wedge W) \wedge (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)</tex>
  
 
== См. также ==
 
== См. также ==
 
[[Сокращенная и минимальная ДНФ]]
 
[[Сокращенная и минимальная ДНФ]]

Версия 02:54, 12 октября 2010

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

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

Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур). Сначала мы рисуем куб в системе отсчёта 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 \neg Y \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](X \wedge Y \wedge Z \wedge W) \vee (X \wedge Y \wedge \neg Z \wedge W) \vee (X \wedge Y \wedge \neg Z \wedge \neg W) \vee (X \wedge Y \wedge Z \wedge \neg W) \vee (\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] 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


  • Теперь мы покрываем непересекающимися прямоугольниками (длины сторон которых — степени двойки (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] 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 \wedge (X \wedge \neg Y \wedge W) \wedge (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)[/math]

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Минимизация_ДНФ_с_помощью_покрытий_гиперкуба_и_карт_Карно&oldid=3698»