Минимизация логических функций по картам Карно

 

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

При решении задач минимизации логических функций важную роль играют понятия простой импликанты логической функции. Установим эквивалентные им геометрические образы (контуры) на карте Карно.

Вспомним, что импликанта логической функции получается в результате операции склеивания соседних (отличающихся значением только одной переменной) членов СДНФ (конституент единицы).

Рассмотрим карту Карно на четыре переменных (Рисунок 3.7), на которой задана некоторая функция, и контур 2 на ней, состоящий из двух соседних единичных клеток. Клетки имеют коды 0000 и 0100, т.е. соответствуют наборам и Их дизъюнкция приводит к исключению переменной x2:

  x1x2 x3x4    
       
    ~    
    ~    
    ~    
    ~    
    Рисунок 3.7    

Таким образом, двухклеточный контур карты Карно соответствует импликанте, покрывающей две конституенты, соответствующие клеткам, входящим в контур. Двухклеточный контур исключает одну переменную.

Рассмотрим контур 3, состоящий из четырех попарно соседних единичных и условной клеток. Заметим, что условные клетки никаких ограничений на задание функции не вносят, поэтому их можно включать в контуры вместе с единичными, т.е. за их счет доопределять логическую функцию. Контур 3 покрывает четыре набора:

Таким образом, видим, что 4-клеточный контур соответствует импликанте, покрывающей четыре конституенты, и приводит к исключению двух переменных. Нетрудно показать, что 8-клеточный контур, объединяющий единичные и условные клетки карты, приводит к исключению трех переменных.

Очевидно, что одноклеточный контур (контур 1 на рисунке 3.7) покрывает лишь одну конституенту и не приводит к исключению переменных.

Таким образом, можно сделать вывод, что любой, являющейся элементарной конъюнкцией импликанте логической функции, заданной на карте Карно, можно поставить в соответствие правильный контур, в который войдут клетки, соответствующие соседним наборам, допускающим склеивание. Правильные контуры могут включать 1, 2, 4, …, 2n клеток карты Карно, соответствующих единичным или условным наборам логической функции. Соседним клеткам карты Карно поставлены в соответствие соседние наборы, и поэтому на картах Карно легко различаются правильные контуры.

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

Отсюда нетрудно установить признаки контуров карты Карно, соответствующих простой импликанте логической функции.

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

Отличительным признаком максимально возможного правильного контура является то, что он не может быть составной частью другого правильного контура.

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

Типичные конфигурации максимальных правильных контуров представлены на рисунках: 3.8 – двухклеточные, 3.9 – четырехклеточные, 3.10 – восьмиклеточные.

  x1x2 x3x4   x1x2 x3x4  
     
   
~    
     
  ~  
  а   б  
  Рисунок 3.8  
   
  x1x2 x3x4   x1x2 x3x4   x1x2 x3x4  
       
     
     
     
     
  а   б   в  
  Рисунок 3.9  
 
  x1x2 x3x4   x1x2 x3x4   x1x2 x3x4  
       
     
       
       
     
  а   б   в  
  Рисунок 3.10  
                                                             

Особое внимание следует обращать на контуры, которые терпят видимый разрыв, так как объединяемые ими соседние клетки находятся в крайних строках или столбцах карты Карно.

При минимизации с помощью карт Карно логических функций пяти переменных трудности значительно возрастают, так как правильные контуры на этих картах терпят разрывы не только по краям, но и внутри карты и теряется основное достоинство метода – наглядность.

Чтобы по виду максимального правильного контура определить аналитическую форму записи простой импликанты, необходимо определить те переменные логической функции, которые в пределах рассматриваемого контура сохраняют свои значения. Если переменная сохраняет свое значение во всех клетках контура и равна 1, то она входит в выражение простой импликанты.

Если переменная сохраняет свое значение во всех клетках контура и равна нулю, то в выражение простой импликанты входит ее инверсия. Переменные, которые в пределах рассматриваемого контура изменяют свое значение, не включаются в выражение простой импликанты, так как они поглощаются при склеивании соседних наборов, объединяемых в контур.

Например, выражение для простой импликанты, соответствующей максимально правильному контуру, показанному на рисунке 3.9, в, имеет вид так как в пределах этого контура переменные x2 и x4 сохраняют свое значение, равное 0. Простые импликанты для контуров, показанных на рисунке 3.10, б и в, имеют вид:

Рассмотренная методика определения простых импликант и лежит в основе метода минимизации логических функций по картам Карно.

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

Методика минимизации логических функций по картам Карно заключается в следующем:

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

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

3. Для всех максимальных правильных контуров, вошедших в найденную совокупность, выписать соответствующие им простые импликанты и объединить их знаком дизъюнкции.

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

Действительно, так как выбраны максимальные правильные контуры, то импликанты, им соответствующие, являются простыми. Так как покрыты все единичные клетки (т.е. все конституенты единицы), то совокупность импликант является полной, а так как каждый контур содержит хотя бы одну единичную клетку, не вошедшую в другие контуры, то совокупность импликант является приведенной. Таким образом, в результате минимизации получается приведенная система простых импликант. Их дизъюнкция и является одной из тупиковых ДНФ.

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

Рассмотрим пример. Провести минимизацию с помощью карты Карно логической функции, заданной в символической форме

Построим карту Карно на четыре переменных и отметим на ней все рабочие, запрещенные и условные клетки (Рисунок 3.11). образуем максимальные правильные контуры, охватывающие все единичные и необходимые условные клетки, обращая внимания на то, чтобы контур содержал хотя бы одну единичную клетку, не входящую в другие контуры.

На рисунке 3.11, а, б показаны два возможных варианта образования контуров.

Находим соответствующие выделенным контурам простые импликанты и запишем две тупиковые ДНФ данной функции:

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

 

  x1x2 x3x4   x1x2 x3x4  
     
~   ~  
     
~   ~  
~   ~  
  а   б  
  Рисунок 3.11  

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

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

                          c                  
                        d                    
                    ~                  
                    b ~                  
                  a ~                  
                                     
Рисунок 3.12

Проведем минимизацию логической функции

при условии, что наборы и являются условными. Действуя установленным образом, находим на карте Карно (Рисунок 3.12) максимальные правильные контуры и получаем тупиковую ДНФ:

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

Так, для функции, заданной картой Карно на рисунке 3.11, сокращенная ДНФ имеет вид: