Минимизация булевых функций с помощью карт Карно

Карты Карно используют для получения канонической суммы минтермов (в математике используется термин МДНФ) переключательной функции и отрицания функции. Для этого на карте объединяют группы единиц (нулей для отрицания) размером , чтобы число ячеек в каждой группе было максимальным (тогда будет минимально число элементов в терме-произведении), а количество таких групп было минимальным (соответствует числу термов). При построении групп учитывается возможность наличия пересечений, т.е. когда одна ячейка принадлежит разным группам.

рис. 1.4 Группы на карте Карно для функции четырех переменных.

Для того, чтобы написать выражение по карте Карно, нужно воспользоваться «разметкой» координатных осей карты. Нужно для каждой группы отобрать те переменные на координатных осях, чьи значения не изменяются в пределах группы. Эти переменные и будут входить в соответствующие термы-произведения. Если переменные равны логическому нулю, то они должны входить с отрицанием, если они равны логической 1 – без отрицания.

Для иллюстрации обратимся к рисунку. Мы видим, что квадратная группа расположена в первой и второй строках карты. В этих строках переменная w равна логи­ческому 0. Поэтому терм должен содержать . Поскольку переменная изменяет свое зна­чение от первой строки ко второй, она не должна входить в терм. Рассмотрев два столбца, в которых лежит группа, мы обнаружим, что переменная y имеет постоянное значение, рав­ное логической 1, и, следовательно должна войти в терм, а z изменяет значение и поэтому вой­­ти в терм не должна. Итак, мы установили, что квадратная группа соответствует терму .

Применив аналогичную процедуру к двум остальным группам, мы сможем найти соответствующие им термы-произведения. Группа в первой колонке соответствует терму , поскольку и у, и z в этой колонке равны логическому 0, а обе переменные w и x не сохраняют своих значений для этой колонки. Что же касается самой маленькой группы, то ей соответствует терм . Таким образом, минимальная группа для рассматриваемой карты Карно равна
.

Дата добавления: 2015-05-07