lec05
.pdfАлгоритм минимизации ДНФ методом Квайна.
Таким образом
DС = π1 π2 π3 π4 π5
DC = 1 2 4 1 2 3 2 3 4 1 3 4 2 4
Находим Dφ.
Находим какие из вершин носителя покрываются единственным πi.
21
Ядровой является та конъюнкция, для которой найдётся единственный в |
|
|
|||||||||||||||||||
своем столбце +, и Kj соответствует ядровому импликанту πi. |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
K1 K2 K3 K4 K5 K6 K7 K8 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Dc(π)\Nf(K) 0 0 0 1 1 0 1 1 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
D |
φ |
= π |
1 |
π |
3 |
π |
5 |
= |
|
π1= 1 2 4 |
+ + |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
π2= 1 2 3 |
|
+ + |
|
|
|
|
|
|||||
= |
|
|
|
|
|
|
|
||||||||||||||
|
1 |
|
2 |
4 |
2 |
|
3 |
4 |
|
2 |
4 |
π3= 2 3 4 |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
π4= 1 3 4 |
|
|
+ |
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
π5= 2 4 |
|
|
|
+ + |
|
+ + |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
|
Далее выясним, покрывает ли ядро весь носитель. Ядро,
соответствующее π1 π3 π5 покрывают все Ki кроме K3. K3
покрывается дополнительно любым из интервалов для π2 или для π4.
K1 K2 K3 K4 K5 K6 K7 K8 |
|||||||
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
Dc(π)\Nf(K) 0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
π1= 1 2 4 |
+ + |
|
|
π2= 1 2 3 |
+ + |
|
|
π3= 2 3 4 |
+ |
|
+ |
π4= 1 3 4 |
+ |
+ |
|
π5= 2 4 |
|
+ + |
+ + |
D1 = Dφ π2 = Dφ 1 2 3 D2 = Dφ π4 = Dφ 1 3 4
rang Dmin = rang Dφ + rang π2 = rang Dφ + rang π4 = 8+3 = 11