lec05
.pdf
Минимизация ДНФ в B4 картой Карно.
Для Вn две вершины принадлежат одному ребру, когда их координатные векторы отличаются в одной позиции.
4 вершины - двумерная грань - отличие в двух позициях. 8 вершин – трехмерная грань – отличие в трех позициях.
Виды покрытий в В4 для карты Карно.
Rang конъюнкта |
n-r |
масштаб покрытия |
Вершин |
|
|
|
|
4 |
0 |
20 – вершина (1х1) |
1 |
3 |
1 |
21 – ребро (2х1; 1х2) |
2 |
2 |
2 |
22 – квадрат* (2х2; 4x1; 1x4) |
4 |
1 |
3 |
23 – грань* (4х2; 2х4) |
8 |
(* - в геометрии гиперкуба В4).
11
Минимизация ДНФ в B4 картой Карно.
Перестановки строк/столбцов сделаны для того, чтобы соседние вершины стояли последовательно.
12
|
|
|
|
|
Минимизация ДНФ в B4 картой Карно. |
|
|
|
|||||||||
Ищем сокращенную ДНФ, максимальные интервалы и |
1 |
|
|
|
|
|
|||||||||||
сумму конъюнкций. |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
||||||||
Какие вообще интервалы ? |
|
x1x2\x3x4 |
00 01 11 10 |
|
|||||||||||||
Запишем из них максимальные: |
|
|
|||||||||||||||
|
|
00 |
1 |
0 |
1 |
1 |
|
||||||||||
|
|
|
|
0000 |
|
|
|
|
|
3 |
|
|
|||||
I |
|
= |
↔ K |
= |
|
|
|
01 |
0 |
1 |
1 |
0 |
|
||||
1 |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
||||||||||
|
|
|
0010 |
1 |
|
1 |
2 |
4 |
|
|
11 |
0 |
1 |
1 |
0 |
||
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|||||
I |
2 |
= |
0011 |
↔ K |
= |
1 2 x3 |
|
|
10 |
0 |
0 |
0 |
1 |
|
|||
|
|
0010 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0011 |
↔ K3 = 1 3 4 |
|
|
|
|
4 |
|
|
|
||||
I3 |
= |
|
Запишем СокрДНФ: |
|
|
|
|||||||||||
|
|
|
|
0111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
I4 |
= |
0101 |
0111 |
|
↔ K4 = 2 4 |
Dc = K1 K2 K3 K4 K5 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
1101 |
1111 |
|
|
|
|
Dc = 1 2 4 1 2 x3 1 |
3 4 2 4 2 3 4 |
||||||
|
|
|
|
1010 |
|
|
|
|
|
||||||||
I5 |
= |
↔ K5 = |
2 3 4 |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
0010 |
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Минимизация ДНФ в B4 картой Карно. |
|
|
|
||||
Выпишем ядровую ДНФ (вершины |
|
1 |
|
|
|
|
|
покрыты только этим интервалом): |
|
x1x2\x3x4 |
00 01 11 10 |
|
|||
I* = I1 I4 I5 |
|
|
|||||
3 |
00 |
1 |
0 |
1 |
1 |
|
|
|
01 |
0 |
1 |
1 |
0 |
2 |
|
|
|
||||||
Dφ = 1 2 4 2 4 2 3 4 |
|
11 |
0 |
1 |
1 |
0 |
|
|
|
||||||
!!! Dφ не тождественна исходной БФ. |
|
10 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
5 |
|
Какой вершины нет ? Каким интервалом покроем ? |
|
|
|
|
|
||
|
|
|
|
4 |
|
|
|
Имеем I2 (или I3) подтверждающий это. |
|
|
|
|
|
|
|
Найдем Dmin, такую, что |
|
|
|
|
|
|
|
Dφ Dmin DС
Дополняем Dφ конъюнкциями из DС для получения Dmin. Dmin не единственна. К ядру I* можно добавить I2 (или I3), получив покрытия Nf для Dmin
14
|
Минимизация ДНФ в B4 картой Карно. |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
N |
= I* I = I |
|
I I |
|
I |
|
|
x1x2\x3x4 00 01 11 10 |
|
||||
1 |
5 |
2 |
|
00 |
1 |
0 |
1 |
1 |
|
||||
f |
2 |
4 |
|
3 |
|
|
|
|
|
|
|||
|
D1 = Dφ 1 2 3 |
|
|
01 |
0 |
1 |
1 |
0 |
2 |
||||
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
11 |
0 |
1 |
1 |
0 |
|
N |
= I* I = I |
1 |
I I |
5 |
I |
3 |
|
10 |
0 |
0 |
0 |
1 |
|
f |
3 |
4 |
|
|
|
|
|
|
|
|
|||
|
D2 = Dφ 1 3 4 |
|
|
|
|
|
|
4 |
|
|
5 |
||
При этом rang Dmin = rang Dφ + rang K2 = rang Dφ + rang K3 = 8+3 = 11 |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
Часть 2.
Метод Квайна-Мак-Класки.
Задана булева функция (x1,x2, … xi, … xn). Используем тождества:
1) (тождество склейки)
kx k = k |
(5.1) |
Доказательство. |
|
kx k = k(x ) = k 1 = k |
|
2) (тождество сложения с 1) |
|
k1k2 k1 = k1 |
(5.2) |
Доказательство. |
|
k1k2 k1 = k1k2 (k1 1) = k1 (k2 1) = k1 1 = k1
17
Алгоритм минимизации ДНФ методом Квайна.
1)Выписывается СДФН.
2)Каждый конъюнкт из СДНФ записывается в виде: вместо xi на i-ом месте пишется 1, а вместо – 0.
Пример 5.4. Запись: 1 2 3 4 = 1011
3. Все конъюнкты разбиваются на классы и упорядочиваются по числу входящих в них единиц и выписываются в столбец в порядке возрастания классов. Операция склейки применяется всюду, где это возможно. При этом в силу (5.1) склеиваться могут только конъюнкции, принадлежащие соседним классам. При каждой склейке пропадает одна переменная, вместо которой в конъюнкции пишется черта.
Пример 5.5. Запись 1 2 3 4 1 2 3 4 = 1 2 4.
1011 склейка 1001 = 10-1.
Конъюнкция участвовавшая в склейке, считается . К конъюнкциям, полученным после склейки, снова применяется операция склейки, где это возможно, пока все возможные склейки не будут выполнены.
!!! Символ склейки также можно склеивать.
18
Минимизация ДНФ в B4 методом Квайна.
Пример 5.6.
Нахождение Dmin методом Квайна.
(x1,x2,x3,x4), n = 4.
БФ задана ТИ.
СДНФ = 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4.
x1 |
x2 |
x3 |
x4 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
19
0000 |
00−0 |
π1 |
|
π1 = |
1 2 4 |
|||
|
|
|
|
|||||
0010 |
001− |
π2 |
|
π2 = |
1 2 3 |
|||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||
|
−010 |
π3 |
|
π3 = |
2 3 4 |
|||
1010 |
|
|
|
|
|
|
1 3 4 |
|
0011 |
0−11 |
π4 |
|
π4 = |
||||
|
|
|
|
|
|
|||
0101 |
01−1 |
−1−1 |
|
π |
|
|
|
|
|
−101 |
−1−1 } |
π5 |
5 |
= 2 |
4 |
||
|
|
|||||||
|
|
|
|
|
||||
|
|
|
|
|
|
|
||
0111 |
|
|
|
|
|
|
|
|
1101 |
−111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
11−1 |
|
|
|
|
|
|
|
1111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20