Часть 2.

Минимизация с помощью метода Квайна и Мак-Класски

Минимальную форму ищут в форме дизъюнкции простых импликант неизбыточной системы простых импликант. Для этого сначала определяют систему простых импликант исходной функции, а затем удаляют из неё избыточные элементы.

Для построения системы простых импликант используют теоремы Квайна и Мак-Класски или численную процедуру минимизации на гиперкубах. Эти методы основаны на склеивании элементов, являющихся ближайшими соседями.

Вспомогательные характеристики конституэнт единицы, используемые в теоремах Квайна и Мак-Класски:

1. | x_e | = – десятичное представление двоичного набора.

2. index( x_e ) =

3. _lp = abs ( | x_l | – | x_p | ) – разность

Теорема Квайна

Для того чтобы 2 конституэнты единицы склеивались необходимо и достаточно, чтобы:

1. _lp = 2^k , kZ⁺

2. | index (x_l ) - index (x_p )|=1

3. | x_l | > | x_p |  index (x_l ) > index (x_p )

Теорема Мак-Класски

Необходимыми и достаточными условиями склеивания импликант произвольного уровня являются:

1. Равенство последовательностей разностей

2. Возможность склеивания младших конституэнт единицы в склеиваемых импликантах.

0	0	(0 1)(1) (0 2)(2) (0 4)(4) (0 16)(16)	(0 1 2 3)(1 2) (0 2 4 6)(2 4) (0 2 16 18)(2 16) (0 4 16 20)(4 16)	(0 2 4 6 16 18 20 22)(2 4 16)
1	1 2 4 16
		(1 3)(2) (1 9)(8) (1 17)(16) (2 3)(1) (2 6)(4) (2 18)(16) (4 6)(2) (4 20)(16) (16 18)(2) (16 20)(4)
2	3 6 9 17 18 20
			(1 3 9 11)(2 8) (1 3 17 25)(2 16) (1 9 17 25)(8 16) (2 3 18 19)(1 16) (2 6 18 22)(4 16) (4 6 20 22)(2 16) (16 18 20 22)(2 4)
				(1 3 9 11 17 19 25 27)(2 8 16)
		(3 11)(8) (3 19)(16) (6 14)(8) (6 22)(16) (9 11)(2) (9 13)(4) (9 25)(16) (17 19)(2) (17 25)(8) (18 19)(1) (18 22)(4) (20 22)(2) (20 28)(8)
3	11 13 14 19 22 25 28		(3 11 19 27)(8 16) (9 11 25 27)(2 16) (17 19 25 27)(2 8)
		(19 27)(8) (25 27)(2)
4	27
		(27 31)(4)
5	31

Набор не покрывающих друг друга импликант

(6 14)(8) A =

(9 13)(4) B =

(20 28)(8) C =

(27 31)(4) D =

(0 1 2 3)(1 2) E =

(2 3 18 19)(1 16) F =

(0 2 4 6 16 18 20 22)(2 4 16) G =

(1 3 9 11 17 19 25 27)(2 8 16) H =

Построим импликантную матрицу для данного набора импликант.

0

1

2

3

4

6

9

11

13

14

16

17

18

19

20

22

25

27

28

31

A

+

+

B

+

+

C

+

+

D

+

+

E

+

+

+

+

F

+

+

+

+

G

+

+

+

+

+

+

+

+

H

+

+

+

+

+

+

+

+

Тогда конъюнктивная форма импликантной матрицы выглядит следующим образом:

GH(GA)(HA)BA(GC)(HD)CD = ABCDGH

Результат минимизации с помощью метода Квайна и Мак-Класски:

F(x)=     