Метод минимизации по картам Карно

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

ПримерПример 2. Рассмотрим функцию

ff1(xx1,xx2,xx3)=xx1xx2xx3Úxx1xx2`xx3Úxx1`xx2xx3Úxx1`xx2`xx3Ú`xx1xx2xx3.

Множество переменных разобьем на две группы. Одной группе сопоставим строки таблицы, второй — столбцы, так чтобы каждой клетке соответствовала комбинация переменных из этих групп. Карта Карно для нее имеет вид табл. 5.6.

Таблица 6
x1x2/x3
00    
01   15
11 12 11
10 14 13

 

При составлении карты Карно строки именуются всевозможными комбинациями значений переменных первой группы так, чтобы расстояние

между соседними комбинациями было равно 1.

Табл. 6
x1x2/x3 0 1
00    
01  
11
10

Для нашего случая Для нашего случая 00®01®11®10 ( (при каждом последующем переходе изменяется только подчеркнутый символ). Аналогично именуются столбцы таблицы.

Заполнение карты производится по таблице соответствия исходной функции. В примере конъюнкции x1x2x3 соответствует клетка 11/1, а x1x2`x3 клетка 11/0 и т.д. В данной таблице каждая единица имеет порядковый индекс, который соответствует порядковому номеру данной компоненты в исходной функции (расстановка этих индексов совершенно не обязательна и здесь приведена для лучшего понимания).

Для минимизации необходимо попарно “склеить” рядом стоящие единицы, имеющие хотя бы одну общую компоненту. При этом надо стремиться “склеить” в один набор как можно больше клеток. В данном примере мы можем “склеить” 11,12,13,14 вместе. Это запишется как x1,так как содержимое всех этих клеток зависит только от x1 и не меняется при изменении x2 или x3. На следующем шаге склеим 11 и 15. В результате получим x2x3. Рассуждения аналогичны: при изменении x1 изменения ячеек с 11 и 15 не происходит.

Результирующей минимальной записью исходной функции будет

f(x1,x2,x3)=x1Úx2x3.

ПримерПример 3. Минимизируем функцию пяти переменных:

ff2(xx1,xx2,xx3,xx4,xx5)=xx1`xx2`xx3`xx4Úxx1`xx2`xx3xx4Ú`xx1xx2xx3xx4Ú`xx2xx1`xx5.

Карта Карно для нее приведена в табл.7.


 

Таблица. 7

x4x5\x1x2x3
            14 11,4
              11
    13         12
    13       14 12,4

 

Если в конъюнкции переменная не присутствует, то 1 ставится во все клетки, удовлетворяющие присутствующим переменным. Так, например, первой конъюнкции соответствует две клетки: 100/00 и 100/01.

Минимизация приводит к формуле

ff2(xx1,xx2,xx3,xx4,xx5)=xx1`xx2`xx3Ú`xx1xx2xx3xx4Ú`xx2xx1`xx5.

ПримерПример 4. Рассмотрим функцию

ff3(xx1,xx2,xx3)=xx1xx2`xx3Úxx1`xx2xx3Úxx1`xx2`xx3Ú`xx1xx2xx3Ú`xx1xx2`xx3Ú`xx1`xx2xx3.

Таблица 8
x1x2/x3
 
 

 

Табл. 8

x1x2/x3 0 1
00  
01
11  
10

По карте Карно в табл.5.8 видно, что для данной функции существует две минимальных формы:

ff(xx1,xx2,xx3)=`xx1xx3Úxx2`xx3Úxx1`xx2,

ff(xx1,xx2,xx3)=`xx1xx2Ú`xx2xx3Úxx1`xx3.








Дата добавления: 2015-08-21; просмотров: 711;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.