Определение простых импликант

 

Каждый отдельный контур объединения соответствует минтерму, который иначе называют простой импликантой. Для определения и записи простой импликанты, прямо по карте Карно, проводится анализ переменных по тем строчкам и столбцам карты, которые пересекают контур объединенных 1 (вершин куба). Начинают анализ с первой переменной Х₁.

Если переменная Х₁ в любой строчке(столбце), проходящей через контур, не изменяет значения своей координаты (т.е. во всех строчках контура ее значение либо 0, либо 1), то в минтерм объединения записывается ее значение (либо 0, либо1).

Если переменная Х₁ в строчках (столбцах), проходящих через контур, изменяет значение своей координаты (т.е. в одной строчке контура ее значение 0, а в другой 1, либо наоборот), то в минтерм объединения записывается, так называемая, неопределенная переменная Х на том месте, где должно записываться значение переменной Х₁ (рисунок 9.1д,е,ж). Аналогичный анализ проводится последовательно для всех переменных, в результате чего получаем минтерм объединения. На рисунке 9.1д,е,ж они расположены на выносках.

Это первый этап записи минимальной логической функции прямо с карты Карно. На втором этапе меняем значения переменных на соответствующие им переменные по правилу: если значение переменной 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 переменных.