02Глава21-22 (561019), страница 6
Текст из файла (страница 6)
Импликанта ACD не поглощает ни один минтерм функциональных наборов, так как образована из тех минтермов функции φ1, которые в φ0 не входят.
Пример. Найти МДНФ и МКНФ не полностью определенной функции
Причем наборы ,
и
являются запрещенными.
Используем метод карт Вейча (рис.11).
Незаполненные клетки карты соответствуют запрещенным наборам.
§8. Абсолютные минимальные представления булевых функций.
До сих пор мы рассматривали проблему минимизации функций, относящихся к классу ДНФ. Однако очень часто МДНФ функции можно упростить введением скобочной записи.
Пример. f(ABCD)=m8+ m9+ m10+ m11+ m14+ m15;
Однако более простая запись получится при вынесении А за скобки:
Поэтому возникла проблема нахождения абсолютных минимальных представлений для булевых функций.
Определение. Выражение Q называется абсолютным минимальным представлением для функции f(x1x2…xn), если в базисе {/\,\/,ˉ} не существует более минимальных представлений, каким бы способом ни получалось это выражение.
Встает вопрос: не является ли абсолютными минимальными выражения, которые могут быть получены их МКНФ путем всевозможных вынесений за скобки и выбором наиболее простого выражения из этих скобочных форм.
В 1951 г. Беркхарт показал, что существуют такие минимальные выражения, которые не могут быть получены при вынесении за скобки в МДНФ или МКНФ.
В работах Абхъянкара дан алгоритм непосредственного нахождения абсолютных минимальных выражений для данной функции. Однако этот алгоритм практически неприменим даже при малом n из-за большого количества необходимых операций.
Так, на последнем этапе получения абсолютного минимального выражения функции n переменных число операций оценивается как
+1≤m≤
.
При n=4 2257≤m≤265536.
Таким образом, нахождение абсолютных минимальных выражений функции с числом переменных больше четырех по имеющемуся алгоритму Абхъянкара становится неприемлимым даже при использовании средств вычислительной техники.
Более практической является минимизация МДНФ путем вынесения за скобки.