МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД ГРАФ-СХЕМ

управления, кафедра АПВТ, ХНУРЭ
ДИСКРЕТНАЯ МАТЕМАТИКА
БУЛЕВА АЛГЕБРА

описывающих комбинационные схемы цифровых проектов
Содержание:
Основные положения
Алгоритм

нахождения неопределенных коэффициентов
Пример реализации алгоритма

Тема: Минимизация булевых функций.
Метод граф-схем

1987. С. 194.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко

С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43.

Минимизация
Минимальная ДНФ
Неполностью определенная функция

на теореме разложения функции по переменной xi




xi - компонент функции

есть
- компонент функции есть

Переменная xi существенна, если

или

иметь вид:







Граф-схема автомата для n переменных имеет n ярусов, нумеруемые

снизу вверх: i=1,2,3,...,n
В каждом ряду имеется 2n-i вершин, а вся граф-схема имеет 2n+1-2 ребер

узлы имеют одинаковые аргументы.
Число всех возможных путей от входов

первого ряда к основанию равно 2n (n – число переменных).
Входами для вершин нижнего ряда являются значения функции: f(x)={0,1,X}.

вид:

ряда формируют значения выходов указанных вершин:





Для слов 00, 11, ХХ

переменная несущественна.
Для 01 по теореме разложения имеем:


Для 10 получаем
Входами для узлов второго ряда являются сочетания из множества {0,x4, ,1,a,b,c,d,x}.

ярусе входов x символами {0} получим скобочную форму:



Первый вариант

для Y1 содержит 7 букв, второй – 9. Следовательно, чем больше в графе фиктивных переменных, тем проще конечный вид скобочной формы.
Пути увеличения фиктивности переменных:
1. Оптимальное доопределение значений функций на неопределенных координатах нижнего яруса;
2. Перестановка переменных в ярусах графа.

2 предложим следующую перестановку переменных в ярусах:










В результате получается ГСА,

которая дает функцию

из 6 букв, что свидетельствует о большей минимальности по сравнению с полученными ранее.

карте Карно дает следующий результат, идентичный полученному ранее:

1
Общее число всех возможных вариантов граф-схем равно Q=n!2p, где n

– число переменных, р– количество неопределенных значений функции.
Для рассматриваемого примера Q=4!.26=1536.
Определение. Сходность графа - есть оценка Q, где ki – число сходных узлов в i-м ярусе, где обе выходные функции одинаковы.
Сходность имеет пределы:
При этом S=0, если нет ни одного сходного узла
и если функция тождественно равна 0
или 1.
Если ki=2n-i для i-того яруса, то xi – фиктивная переменная.
На первом рисунке
На втором рисунке

2
Для определения сходных узлов зададим операцию сравнения, где 0, 1,

Х, Y – значения булевых переменных или функций:

3
Процедура минимизации:
1. Вычисляется сходность для каждого яруса с последующей расстановкой

переменных по ярусам.
2. Выполняется доопределение вхоных значений для нижнего яруса.
3. Выполняется запись скобочной формы по ГС.
Алгоритм определения ГС с максимальной сходимостью:
1. Определение xi для 1-го яруса: ;
2. Вычисление xi для 2-го яруса: ;
3. Определение xi для j-го яруса: .
Для подсчета сходности в ярусах используется таблица Венна, где наборы расположены по возрастанию их номеров.

с синтезом вычислительных устройств
Они позволяют в среднем на 20-30% получить

более экономичный проект с позиции аппаратурных затрат
Высокий уровень структуризации представления булевой функции дает возможность минимизировать затраты при обработке схем с большим числом переменных
Метод граф-схем позволяет визуализировать процессы синтеза минимальных форм
Недостатком метода является значительный объем информации при хранении древовидной стуктуры представления булевой функции
Метод может быть использован при синтезе минимальногокубического покрытия