Способы минимизации логических функций. Сущность минимизации по методу Вейче-Карно.

СДНФ выражение может быть преобразовано (не всегда) к виду, имеющему меньшее число переменных и операций по сравнению с исходным. Такое преобразование называется минимизацией.

Рассмотрим пример. Имеется три двоичных датчика xi. Необходимо реализовать ЛФ Yмажор принимающую значение 1, когда равны 1 значения двух и более датчиков. Такая функция называется мажоритарной. Ее таблица истинности имеет вид:

По формуле (1.12): Yмажор = ~x2∙x1∙x0 + x2∙~x1∙x0 + x2∙x1∙~x0 + x2∙x1∙x0. (3,5,6,7 - строчки таблицы ). Полученному выражению соответствует схема на рис.6.

Схема содержит 4 трехвходовых элемента "И" и 1 четырехвходовый элемент "ИЛИ". Нахождение минимальной формы ЛФ производится методом алгебраических преобразований, с помощью таблиц Карно или машинными методами для больших проектов.

Таблица Карно.

Таблица Карно (ТК) это видоизмененная запись таблицы истинности. Для функции мажоритарности из последнего примера (ТК) выглядит следующим образом:

Правила построения ТК следующие: 1)Количество клеток ТК равно количеству строк таблицы истинности. 2)Слева и сверху располагаются значения аргументов. Порядок размещения аргументов таков, что в двух соседних по горизонтали и вертикали клетках отличается значение только одного аргумента (поэтому соседними считаются и клетки, находящиеся на противоположных краях таблицы). 3)В клетки заносятся соответствующие значения ЛФ. 4)Единичные клетки объединяются в прямоугольники (импликанты) по 2^i клеток. 5)Для каждого прямоугольника записывается произведение тех аргументов, которые в соседних клетках не изменяют своего значения. 6)Переменные входят в произведение в прямом виде, если их значение в соседних клетках равно 1, в противном случае в инверсном. 7)Полученные произведения складываются по ИЛИ в искомую ЛФ.

В примере имеется 3 прямоугольника - A,B,C, причем Ya = x2∙x0 (x1 в соседних клетках меняет свое значение, поэтому в конъюнкцию не входит). Yb = x1∙x0 и Yс = x2∙x1.

Yмажор = Ya + Yb + Yc = x2∙x0 + x1∙x0 + x2∙x1. (13)

Соответствующая схема (рис.7.) проще, чем на рис.6.