Часть 4.

Минимизация на гиперкубе

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

Основные определения

Элемент гиперкуба – множество 2^k вершин гиперкуба таких, что (n-k) координат у них совпадают.

• Для k=0 элемент гиперкуба – вершина.

• Для k=1 элемент гиперкуба – ребро.

• Для k=2 элемент гиперкуба – грань.

• Для k3 элемент гиперкуба – подкуб размерности k.

Основной элемент гиперкуба – такой элемент гиперкуба, который не является подмножеством никакого другого элемента гиперкуба: не_j [ _i  _j ]

Элемент функции – элемент гиперкуба, такой, что все его вершины принадлежат множеству истинности функции.

Основной элемент функции определяется по аналогии с основным элементом гиперкуба.

Совокупность простых (основных) элементов функции называется приведенной оболочкой функции.

Приведенная оболочка функции является минимальной ДНФ этой функции.

Импликанта называется простой, если любая её собственная часть импликантой не является.

Импликантой для данной функции является функция, множество истинности которой включено в множество истинности исходной функции.

Система простых импликант некоторой булевской функции, не содержащая избыточных простых импликант, называется приведенной системой простых импликант или неизбыточной.

	0	9	14	28	31
0	*
1	J1	J4
2	J2
3	J12	J24
4	J3
6	J23		J4
9		*
11		J2
13		J3
14			*
16	J5
17	J15	J45
18	J25
19	J125	J245
20	J35			J4
22	J235
25		J5
27		J25			J3
28				*
31					*

Первой в списке вершиной является вершина 0.

Вершина 0

Определение «ближайших соседей» для этой вершины

J_j = J^* + (-1)^Xj * 2^j-1

J^* - текущая основная вершина; J_j – ближайший сосед по j-той координате

J1 = J^*+(-1)⁰*2⁰ = 0 + 1 = 1

J2 = J^*+(-1)⁰*2¹ = 0 + 2 = 2

J3 = J^*+(-1)⁰*2² = 0 + 4 = 4

J5 = J^*+(-1)⁰*2⁴ = 0 + 16 = 16

Элементы функции размерности 2:

J12 = J1 + J2 - J^* = 1 + 2 – 0 = 3

J15 = J1 + J5 - J^* = 1 + 16 – 0 = 17

J23 = J2 + J3 - J* = 2 + 4 – 0 = 6

J25 = J2 + J5 - J^* = 2 + 16 – 0 = 18

J35 = J3 + J5 - J^* = 4 + 16 – 0 = 20

Элементы функции размерности 3:

J125 = J1 + J2 + J5 – 2J^* = 1 + 2 + 16 – 0 = 17

J235 = J2 + J3 + J5 – 2J^* = 2 + 4 + 16 – 0 = 22

Второй непокрытой вершиной является вершина под номером 9.

Вершина 9

Определение «ближайших соседей» для этой вершины

J2 = 11

J3 = 13

J4 = 1

J5 = 25

Элементы функции размерности 2:

J24 = J2 + J4 – J* = 11 + 1 – 9 = 3

J45 = J4 + J5 – J* = 1 + 25 – 9 = 17

J25 = J2 + J5 – J* = 11 + 25 – 9 = 26

Элементы функции размерности 3:

J235 = J2 + J3 + J5 – 2J* = 11 + 13 + 25 – 18 = 31

J245 = J2 + J4 + J5 – 2J* = 11 + 1 + 25 – 18 = 19

Следующая непокрытая вершина - 14

Вершина 14

Определение «ближайших соседей» для этой вершины

J4 = 6

Следующая непокрытая вершина – 28

Вершина 28

Определение «ближайших соседей» для этой вершины

J4 = 20

Следующая непокрытая вершина – 31

Вершина 31

Определение «ближайших соседей» для этой вершины

J3 = 27

Теперь определим основные элементы функции, которые соответствуют элементам гиперкуба

Вершина 31

J3 – A =

Вершина 28

J4 – B =

Вершина 14

J4 – C =

Вершина 9

J3 – D =

J245 – E =

Вершина 0

J125 – F =

J235 – G =

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

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

+

+

+

+

+

+

+

+

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

Результат минимизации на гиперкубе

_F(x) = 