315
правок
Изменения
→Карты Карно
!<tex>y</tex>
!<tex>x</tex>
|1 |1 |1 |1
|-
!<tex>y</tex>
!<tex> \neg x</tex>
|
|1
|1
|1 |1
|-
!<tex> \neg y</tex>
!<tex> \neg x</tex>
|
|1
|1 |1
|-
!<tex> \neg y</tex>
!<tex>x</tex>
|
|
|1
|1
|}
<br>
*Теперь мы покрываем непересекающимися прямоугольниками (длины сторон которых — степени двойки (1, 2, 4)) с максимальной площадью те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой треугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так):
<br>
{| border="1"
!<tex> y </tex>
!<tex> x </tex>
|style="background:#F4A460"|1 |style="background:#F4A460"|1 |style="background:#F4A460"|1 |style="background:#F4A460"|1
|-
!<tex> y </tex>
!<tex> \neg x</tex>
|
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|style="background:#F4A460"|1 |style="background:#F4A460"|1
|-
!<tex> \neg y</tex>
!<tex> \neg x</tex>
|
|style="background:#F4A460"|1 |style="background:#F4A460"|1
|style="background:#7FFFD4"|1
|-
!<tex> \neg y</tex>
!<tex> x </tex>
|
|
|style="background:#7FFFD4"|1 |style="background:#7FFFD4"|1|}
<br>
*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника: <tex>Y \wedge (X \wedge \neg Y \wedge W) \wedge (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)</tex>
