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

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

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

ff₁(xx₁,xx₂,xx₃)=xx₁xx₂xx₃Úxx₁xx₂`xx<sub>3</sub>Úxx<sub>1</sub>`xx₂xx₃Úxx₁`xx<sub>2</sub>`xx₃Ú`xx₁xx₂xx₃.

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

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

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

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

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

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

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

f(x₁,x₂,x₃)=x₁Úx₂x₃.

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

ff₂(xx₁,xx₂,xx₃,xx4,xx5)=xx₁`xx<sub>2</sub>`xx₃`xx4Úxx<sub>1</sub>`xx₂`xx<sub>3</sub>xx4Ú`xx₁xx₂xx₃xx4Ú`xx<sub>2</sub>xx<sub>1</sub>`xx5.

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

Таблица. 7

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

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

ff₂(xx₁,xx₂,xx₃,xx₄,xx₅)=xx₁`xx<sub>2</sub>`xx₃Ú`xx<sub>1</sub>xx<sub>2</sub>xx<sub>3</sub>xx<sub>4</sub>Ú`xx₂xx₁`xx₅.

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

ff₃(xx₁,xx₂,xx₃)=xx₁xx₂`xx<sub>3</sub>Úxx<sub>1</sub>`xx₂xx₃Úxx₁`xx<sub>2</sub>`xx₃Ú`xx<sub>1</sub>xx<sub>2</sub>xx<sub>3</sub>Ú`xx₁xx₂`xx<sub>3</sub>Ú`xx₁`xx₂xx₃.

Табл. 8

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

ff(xx₁,xx₂,xx₃)=`xx<sub>1</sub>xx<sub>3</sub>Úxx<sub>2</sub>`xx₃Úxx₁`xx₂,

ff(xx₁,xx₂,xx₃)=`xx<sub>1</sub>xx<sub>2</sub>Ú`xx₂xx₃Úxx₁`xx₃.