Логические основы цифровой техники

Минимизацию функции методом Квайна можно проводить так­ же с использованием СКНФ. Тогда операция склеивания будет иметь вид: (Х| V *2 ) л (д:, V S j ) = х, л д:, V Х2 л л:, V X| л V ^2 л *2 = = х, V д:, л (д^2 ^ *2) ^ О = л:, V л:, л 1 = х,, (28) а операция поглощения: х, л (л:, VX j ) = х, л х, V х, л ^2 = х, л ( 1 V * 2 ) = X| . (29) Минимизация функций методом Квайна - Мак-Класки Мак-Класки предложил алгоритм, который упрощает миними­ зацию по Квайну, а также позволяет полностью автоматизировать процесс минимизации. Выполняется алгоритм в несколько этапов. Рассмотрим пример. Пусть задана некоторая логическая функция: J* = J, л ^2 л X j л д:, V J, л ^2 л *3 л д-4 V л, л Зс, л J j л V VX, л ^2 л д:, л J4 V д:, л л дГз л д-^ V дс, л ^2 л Зс, л д:^. Вначале эта функция записывается в виде совокупности слага­ емых в двоичной форме: J' = 0 0 0 1 v 0 1 0 1 v l 0 0 1 v l 0 1 0 v l 0 1 1 v l l 0 1 . (30) Все слагаемые выражения (30) разбиваются на группы по чис­ лу единиц и записываются в таблицу (табл. 6). Тогда 1-ю группу бу­ дет представлять только одно слагаемое-(0001); вторую-три: (0101; 1001; 1010); итретью-два слагаемых (1011; 1101). Таблица б Номер группы Слагаемые 1-й этап 2-й этап 3-й этап 0 - - - 1 0001 0*01 *001 *•01 0101 *101 10*1 1*01 101* 2 1001 1010 10*1 101^ 3 1011 1101 17