 |
|
Минимизация булевых функций
Существует несколько методов упрощения логических выражений, из которых наибольшее распространение получили три: алгебраический, с помощью карт Карно, с помощью таблиц Квайна МакКласки
Задача минимизации Булевых функций
Они используются в качестве форм, по которым строятся логические схемы. При использовании многовходовых логических элементов (И, или, не), логическая схема может быть постоена по ДНФ или КНФ. При этом, минимальной логической схеме соотвествует наименьшее число элементарных конъюнкций(дизъюнкций) в записи функции. Каждой букве, входящей в выражение для функции, соответствует схеме, количество входов равно числу букв в выражении для функции. Нетрудно увидеть, что минимальной можно считать логическую схему, постоенную по КНФ или ДНФ функции, содержащее минимальное число букв. Следует отметить, что минимизация КНФ или ДНФ функции в соответствии с данным критерием не во всех случаях приведет к минимальной логической схеме.
Задача минимизации по критерию числа букв, входящих в ДНФ - каноническая задача минимизации. Существует несколько способов упрощения логических выражений, наиболее распространены - 3(Алгебраический, с помощью карт Карно(Диаграм Вейча), с помощью таблиц Квайна-МакКласки).
Расмотренное упрощение записи функиции основанно скорее на опыте разработчика, чем на систематике логики, поэтому данный метод применяется только в самых простых случаях, проверка происходит по таблице истинности. Составляется таблица по полученной формуле и проверяется первоначальная запись Булевой функции.
Построение минимальных форм Булевых функции сводится к эквивалентному преобразованию Булевых выражений. Наиболее наглядно задача преобразования Булевых выражений с целью их минимизации выполняется с использованием геометр. представления Булевых функций. Представляется как множество с-кубов, пренадлежащих комплексу Kf и таких, чтоб каждая вершина комплекса К0 включена, по-крайней мере,
в один куб комплекса С.(Пример:f=-x1-x2x3 v -x1x2x3, K(f) = {001, 011, 0x1} -> C(f) = {0x1}, минимализируем функцию: -х1х3(-х2 v x2) = -х1х3. При проверке показано, что ошибок не было.)
Образование единичных кубов.
С использованием карт Карно легко выделяется минимальное покрытие функции, по которому строится ДНФ и КНФ функции. Две соседние клетки образуют единичный куб. Имеется ввиду, что клетки, лежащие на границе карты, так же соседние.(Пример: f = -х1-х2-х3 v -x1-x2x3 v -x1x2x3 v x1-x2-x3 v x1x2-x3)
Обводим попарно все клетки, содержащие 1. Первый столбец, где х1 равен 0 и 1, дает единичный куб. Следовательно, минимальное покрытие функции:
x00
C= 0x1
1x0
Общие правила минимизации.
Один из вариантов: факторизация(вынесения общего множетеля). Если значения безразличны, несущественные наборы используются для построения кубов большей размерностей, в результате уменьшается цена покрытия функции.