Это первый этап записи минимальной логической функции прямо с карты Карно. На втором этапе меняем значения переменных на соответствующие им переменные по правилу: если значение переменной 0 – то пишем , если 1 – то пишем Х_і. На месте неопределенной переменной Х не пишем ничего, т. е. это место опускаем. Тепер соединив все минтермы знаком дизъюнкции, получим минимальную дизъюнктивную нормальную форму логической функции (МДНФ).

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

Покрытие с минимальной ценой формируется, если каждая существенная вершина будет покрыта кубом с наибольшим числом независимых переменных, а для покрытия всех существенных вершин будет использовано наименьшее число кубов.

Наилучшим считается такое покрытие, где минимум контуров объединения. Если вариантов много, то выбирается тот, который дает максимальную суммарную площадь контуров (прямоугольников). Качество минимизации оценивается по коэффициенту покрытия

k = m / s,

где m - количество прямоугольников, s - их площадь. Покрытие лучше, чем меньше k.

В качестве примера использования карт Карно для определения минимальных ДНФ и КНФ рассмотрим функцию, представленную на рисунке 6.5.

Данной ДНФ (рисунок 6.5 а) соответствует минимальная форма вида:

f= +x₁ x₄+x₂x_3.

Нулевые значения этой функции представлены на рисунке 6.5б. Отмеченные на карте клетки определяют функцию , обратную f.

При минимизации функции , получаем

= x₂+x₁+ x_3.

Используя правило де Моргана, преобразуем в КНФ:

f==(x₁++x₃)(+x₃+x₄)(x₂+). При пяти и более переменных строят комбинированную карту, состоящую из совокупности простых, например четырехмерных. Тогда сначала находят минимальные формы внутри четырехмерных карт, а затем, расширяя понятие соседних клеток, отыскивают минимальные термы для совокупности карт. На рисунке 6.6 показаны карты для 5 и 6 переменных.

6.5 Не полностью определенные логические функции в картах Карно

Не полностью определенные логические функции это функции, значение которых на некоторых наборах переменных несущественно (безразлично). Другими словами, это те функции, наборы переменных которых не используются при построении ЦА. Обычно их обозначают символом *. Например, при рассмотрении двоично-десятичных кодов используют десять функций от 0 до 9, а остальные шесть являются не затребованными и могут иметь различные значения, т.е. они не определены.

При минимизации не полностью определенной функции ее можно доопределить самостоятельно на свое усмотрение, для этого вершины отмеченные символом * изменяют, присваивая им значения 1 или 0, повышая, таким образом, эффективность минимизации.

Р
ис. 6.7 - Не полностью определенные ЛФ в картах Карно

Очень часто это упрощает процесс минимизации, так как добавление, например, единиц до существующих определенных наборов, позволяет включать в контур покрытия большее число единиц, снижая при этом число переменных в МДНФ. Доопределение функции при минимизации нулями также упрощает минимальную КНФ функции. Если функция имеет m неопределенных наборов переменных, то может быть 2^m вариантов решения задачи ее доопределения. Желательно остановиться на варианте, который дает наибольший эффект при минимизации.

Задание.

1. Представить ЛФ в виде СДНФ.

2. Мимнимизировать ЛФ методом Квайна-Мак-Класски.

3. Мимнимизировать ЛФ с помощью карт Карно.

4. Построить схему для ЛФ в минимальной форме.

Индивидуальные задания: