Схемотехника / Учебники и методички / 0350_Minimizatsiya_FAL_s_pomoschyu_kart_Karno__Studentam
.pdf
ПРАВИЛА СОСЕДСТВА КЛЕТОК ДЛЯ n = 5, 6
Для n = 5, n = 6 карты Карно состоят из двух и четырёх карт Карно с n = 4, имеющих общие границы, которые выделены толстыми линиями.
Для любой клетки соседними являются 4 соседние клетки в карте Карно (n = 4) и клетки, расположенные в соседних картах Карно (имеющих общие границы) (для n = 4) симметрично выделенной клетке относительно границ соседних карт Карно
11
МИНИМИЗАЦИЯ ФАЛ С ПОМОЩЬЮ К.К.
Минимизация ФАЛ, заданной таблицей истинности:
Номер |
x2 |
x1 |
x0 |
y |
набора |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
2 |
0 |
1 |
0 |
0 |
3 |
0 |
1 |
1 |
1 |
4 |
1 |
0 |
0 |
1 |
5 |
1 |
0 |
1 |
1 |
6 |
1 |
1 |
0 |
1 |
7 |
1 |
1 |
1 |
0 |
|
|
|
|
|
Эталонная К.К.: |
РабочаяК.К.: |
||||||||||||||
|
|
|
x1 |
|
|
|
y |
|
x1 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x2 |
6 |
7 |
5 |
4 |
x2 |
1 |
0 |
1 |
1 |
||||||
2 |
3 |
1 |
0 |
0 |
1 |
1 |
0 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
x0 |
|
|
|
|
|
|
x0 |
|
||
12
МИНИМИЗАЦИЯ ФАЛ С ПОМОЩЬЮ К.К.
1)На К.К. выделить прямоугольные контуры (покрытия) из «1» с числом клеток 2k;
2)нельзя покрывать клетки, содержащие «0»;
3)покрытия могут пересекаться;
4)покрытия должны иметь max площадь;
5)количество покрытий должно быть min;
6)существуют разные эквивалентные наборы покрытий;
7)должны быть покрыты все «1» клетки;
8)ФАЛ = сумме импликант, выбранных
покрытиями.
13
МИНИМИЗАЦИЯ ФАЛ С ПОМОЩЬЮ К.К.
y |
|
x1 |
|
|
|
|
|
|
|
|
|
y |
|
x1 |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x2 |
|
1 |
0 |
1 |
|
1 |
|
|
|
|
x2 |
|
|
1 |
0 |
|
1 |
1 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
0 |
1 |
1 |
|
0 |
|
|
|
|
0 |
1 |
|
1 |
0 |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
x0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0 |
|
|
|
||||
|
|
|
∙ |
|
|
|
|
|
∙ |
|
|
|
|
|
∙ |
∙ |
|
|
|
|
|
|
∙ |
|
|
|
∙ |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
14
ПРИМЕРЫ
y1 x1
0 0 0 0
x3
0 1 0 1
x2
1 1 1 1
1 0 1 0
x0
15
ПРИМЕРЫ
y1 x1
0 0 0 0
x3
0 1 0 1
x2
1 1 1 1
1 0 1 0
x0
16
ПРИМЕРЫ
y2 x1
0 0 1 1
x3
0 0 1 1
x2
0 1 1 0
0 1 1 0
x0
17
ПРИМЕРЫ
y2 |
|
x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
0 |
1 |
1 |
|
x3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x3 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
0 |
0 |
1 |
1 |
x2 |
|
|
x1 |
|
|
|
|
|
1 |
y2 |
||||||||
|
|
|
|
||||||||||||||||||||
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
& |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
0 |
1 |
1 |
0 |
|
|
|
x0 |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер набора 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
y2
18
НЕПОЛНОСТЬЮОПРЕДЕЛЁННАЯ ФАЛ
y3 |
|
x1 |
|
|
|
|
||
x3 |
|
|
1 |
x |
||||
|
|
|||||||
|
|
|
|
x |
|
x2 |
||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
||||
|
|
|
|
|
||||
|
|
|
|
|
|
|
||
|
|
x |
1 |
x |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0 |
|
|
|
19
НЕПОЛНОСТЬЮОПРЕДЕЛЁННАЯ ФАЛ
y3 |
|
x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
x3 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
x |
|
|
|
|
|
x3 |
|
|
|
|
|
& |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
|
x0 |
|
|
|
|
|
1 |
y3 |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
x |
|
|
|
|
1 |
|
|
x |
|
|
|
|
|
|
|
|
x1 |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер набора 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
y3
20