Структурный метод карт Карно

Метод карт Карно применяется для минимизации функций при количестве переменных n =2, 3, 4, 5 или 6. Результатом работы метода является минимальная совершенной дизъюнктивной нормальной формы (МДНФ). Исходной формой для метода служит СДНФ, хотя область применения метода может быть расширена на СКНФ, а также на произвольные ДНФ или КНФ.

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

 

Пример карты для функции трех переменных приведен на рис. 1, для функция четырех переменных - на рис. 2.

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

 

 

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

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

Обобщая понятие смежности, будем называть смежными также 4 набора, различающихся всевозможными значениями только в i -той и в j- той позициях при неизменных остальных; 8 наборов, различающихся всевозможными значениями только в 3-х позициях и т.д.

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

Карта Карно рассматривается "наложенной" на поверхность тора ("баранки"). Для этого плоскость карты должна быть мысленно свернута в трубку, концы которой соединены между собой. На карте, наложенной на тор, смежным наборам соответствут соседние ячейки.

Алгоритм Карно включает в себя следующие действия:

1. выписать СДНФ минимизируемой функции;.
2. проставить 1 в клетках, соответствующих слагаемым СДНФ;
3. на карте, наложеннной на тор, клетки, помеченные I, покрыть наименьшим количеством прямоугольников, имеющих наибольшую площадь; причем длины сторон прямоугольников должны составлять клеток. Например, для карты от 4-х переменных допустимыми являются прямоугольники

1х1;

1х2; 2х2;

1х4; 2х4; 4х4

1. по каждому из покрывающих прямоугольников, выписать логическое произведение, включив в него переменные ики их отрицания, общие для всех клеток прямоугольника (переменные, входящие в клетки прямоугольника с отрицанием и без отрицания, отбрасываются);
2. образованные логические произведение соединяются в логическую сумму.

Пример 6. Построим МДНФ функции из примера 1

Очевидно, чем меньше общее количество покрывающих прямоугольников, тем меньше МДНФ содержит операций дизъюнкции, а также, чем больше площадь покрывающих прямоугольников, тем меньше МДНФ содержит операций конъюнкции. Последнее указывает на целесообразность допущения «разумных нахлёстов» при осуществлении покрытия отмеченных ячеек прямоугольниками.

Метод карт Карно может быть использован и в случае пяти пере­менных. При этом минимизация функции осуществляется на двух зеркально симметричных картах от 4-переменных , в одной из которых ячейки, относящиеся к переменной , а в другой – к (см.рис.3). Перед «наложением» карты на тор ее складывают, при этом правильнее говорить, что покрытие отмеченных ячеек осуществляется не плоскими прямоугольниками, а объемными.

 

 

Рис 3. Карта Карно для функции 5 переменных

 

Аналогично метод карт Карно может быть использован и в случае шести пере­менных. При этом минимизация функции осуществляется на четырех картах от 4-переменных , в которых ячейки, относящиеся к соответственно к сочетаниям переменных , , и . Перед «наложением» карты на тор ее складывают дважды.

Для аналитический минимизации используется метод Блейка. Исходной для начала работы метода формой являтся произвольная ДНФ или КНФ. Применимость метода не ограничивается определенным количеством переменных.

Метод Блейка

Метод Блейка аналитической минимизации функции, исходя из произвольной ДНФ. Минимизация осуществляется в 2 этапа

1) на первом этапа применяется) закон обобщенного склеивания (до тех пор пока это возможно)

Здесь и далее - проиэвольные логические произведения;

2) на втором этапе применяется закон обобщенного поглощения (до тех пор пока это возможно)

Пример 7. Построить МДНФ для функции, заданной в виде произвольной ДНФ:

Метод Блейка аналитической минимизации функции, исходя из произвольной КНФ

1) на первом этапе раскрыть скобки, удаляя слагаемые вида и заменяя слагаемые ;

2) на втором этапе применяется закон обобщенного поглощения

Пример 8. Построить МДНФ для функции, заданной в виде произвольной КНФ