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

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

Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru
Структурный метод карт Карно - student2.ru        
Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru   Структурный метод карт Карно - student2.ru    
  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru

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

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

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

  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  
Структурный метод карт Карно - student2.ru         Структурный метод карт Карно - student2.ru
        Структурный метод карт Карно - student2.ru
Структурный метод карт Карно - student2.ru        
        Структурный метод карт Карно - student2.ru
  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  
             

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

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

Структурный метод карт Карно - student2.ru

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

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

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

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

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

1х1;

1х2; 2х2;

1х4; 2х4; 4х4

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

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

  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru
Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  
Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  
  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru

Структурный метод карт Карно - student2.ru

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

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

Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  
  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  
Структурный метод карт Карно - student2.ru                 Структурный метод карт Карно - student2.ru
                Структурный метод карт Карно - student2.ru
Структурный метод карт Карно - student2.ru                
                Структурный метод карт Карно - student2.ru
  Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru  

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

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

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

Метод Блейка

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

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

Структурный метод карт Карно - student2.ru

Здесь и далее Структурный метод карт Карно - student2.ru - проиэвольные логические произведения;

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

Структурный метод карт Карно - student2.ru

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

Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru

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

1) на первом этапе раскрыть скобки, удаляя слагаемые вида Структурный метод карт Карно - student2.ru и заменяя слагаемые Структурный метод карт Карно - student2.ru ;

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

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

Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru Структурный метод карт Карно - student2.ru

Наши рекомендации