Метод минимизации по картам Карно
Данный метод минимизации применим для функций с числом переменных не более 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; просмотров: 667;