- •Индивидуальное задание
- •1. Формальная постановка задачи минимизации булевской функции
- •2. Минимизация функции с помощью процедуры Квайна - Мак-Клаcски
- •Набор не покрывающих друг друга импликант
- •3. Минимизация функции с численной процедуры минимизации на гиперкубах
- •Построение таблицы элементов функции.
- •Формирование списков элементов функции висящих на опорных вершинах
- •Упорядочивание списков элементов функции по убыванию размерности (для каждой опорной вершины)
- •Формирование списков основных элементов функции для каждой опорной вершины
- •Определение избыточных основных элементов функции
- •Получение неизбыточной оболочки заданной функции (получение минимальной формы)
- •Построение прямоугольной таблицы истинности для полученной формулы
-
Формирование списков элементов функции висящих на опорных вершинах
-
Опорная вершина
Список элементов функции
0
j1, j2, j12, j3, j23, j4, j14, j24, j124, j34, j234
17
j5, j25, j45, j245, j2, j3, j4, j24
22
j5
-
Упорядочивание списков элементов функции по убыванию размерности (для каждой опорной вершины)
-
Опорная вершина
Список элементов функции
0
j124, j234, j12, j14, j23, j24, j34, j1, j2, j3, j4
17
j245, j24, j25, j45, j2, j3, j4, j5
22
j5
-
Формирование списков основных элементов функции для каждой опорной вершины
Рассмотрим вершину 0:
-
Элемент функции
Вершины
j124
0, 1, 2, 3, 8, 9, 10, 11
j234
0, 2, 4, 6, 8, 10, 12, 14
j12
0, 1, 2, 3j14
0, 1, 8, 9j23
0, 2, 4, 6j24
0, 2, 8, 10j34
0, 4, 8, 12j1
0, 1j2
0, 2j3
0, 4j4
0, 8
Рассмотрим следующую опорную вершину – 17:
-
Элемент функции
Вершины
j245
17, 19, 25, 27, 1, 3, 9, 11
j24
17,19, 25, 27j25
17,19, 1, 3j45
17,25, 1, 9j2
17,19j3
17, 21
j4
17,25j5
17,1
Рассмотрим следующую опорную вершину – 22:
-
Элемент функции
Вершины
j5
22, 6
-
Определение избыточных основных элементов функции
Импликантная матрица для основных элементов
-
0
1
2
3
4
6
8
9
10
11
12
14
17
19
21
22
25
27
A
0
+
+
+
+
-
-
+
+
+
+
-
-
-
-
-
-
-
-
B
+
-
+
-
+
+
+
-
+
-
+
+
-
-
-
-
-
-
C
17
-
+
-
+
-
-
-
+
-
+
-
-
+
+
-
-
+
+
D
-
-
-
-
-
-
-
-
-
-
-
-
+
-
+
-
-
-
E
22
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
+
-
-