Этап. Нахождение существенных импликант. 2 страница

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

       
       
           
         
         

 

Разделим карту двумя осями, симметрично которым и будем располагать аргументы (см. карту).

 

 

Каждая клетка карты соответствует членам СДНФ функции, содержащим 3 знака.

       
       
 
   
         

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

Так можно склеить клетки 1 и 5, 1 и 2 и т.д., а также 2, 3, 6, 7; 1, 5, 4, 8 и т.д.

Если представить карту свернутой по вертикали в цилиндр, то крайние клетки окажутся рядом, их тоже можно склеить.

Рассмотрим несколько примеров

 

                       
                 
        1 1              
                  1    
                             

 

                             
               
          1    
                   
                             

 

                         
                 
  1 1                
                   
                             

нельзя склеить

Приведем примеры карт Карно для числа аргументов

x5

x4 x4

x3 x3

                         
                         
                       
x2         x2                
x1 x1

x 7

x6 x6

x5 x5

x4 x4

                                                   
                                               
                                                 
                                                 
                                               
                                               
x2                 x2                                
x3                 x3                                

x1 x1

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

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

Чтобы упростить отыскание нужной клетки в карте Карно, целесообразно дополнительно пронумеровать строки и столбцы.

 

                  0 1x3
  x3     0x4
  0 x4     0x5
      x4   x3     x4 x3     x5  
0 0             0 0                
0 1           0 1                  
1 1           1 1                
1 0 x2           1 0 x2                

x1x2 x1 x1x2 x1

Обработка карт.

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

  *     *  
       
*

*

x5