315
правок
Изменения
Нет описания правки
В итоге нашу изначальную ДНФ можно записать как <math>(Y) \or (X \and \neg Y \and Z)</math>.
== Карты Карно ==
Этот способ работает при количестве переменных не более 4.
Мы рисуем следующую таблицу n*n, где n — количество переменных:
{| border="1"
|
|
!w
!w
!не w
!не w
|-
|
|
!z
!не z
!не z
!z
|-
!y
!x
|
|
|
|
|-
!y
!не x
|
|
|
|
|-
!не y
!не x
|
|
|
|
|-
!не y
!x
|
|
|
|
|}
Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы. Например, ДНФ
<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>
<br>
<br>
будет выглядеть на картах Карно так:
<br>
<br>
{| border="1"
|
|
!w
!w
!не w
!не w
|-
|
|
!z
!не z
!не z
!z
|-
!y
!x
|1
|1
|1
|1
|-
!y
!не x
|1
|1
|1
|1
|-
!не y
!не x
|
|
|1
|
|-
!не y
!x
|1
|1
|
|
|}
<br>
*Теперь мы покрываем непересекающиеся прямоугольниками с максимальной площадью те ячейки карт Карно, которые содержат в себе единицу до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так:)
<br>
{| border="1"
|
|
!w
!w
!не w
!не w
|-
|
|
!z
!не z
!не z
!z
|-
!y
!x
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|-
!y
!не x
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|-
!не y
!не x
|
|
|style="background:#7FFFD4"|1
|
|-
!не y
!x
|style="background:#D2B48C"|1
|style="background:#D2B48C"|1
|
|
|}
<br>
*После этого записываем каждый
