Минимизация функций алгебры логики методом карт Карно

Карты Карно наиболее целесообразно использовать для минимиза­ции ФАЛ от двух до шести переменных. При минимизации ФАЛ данным методом рассматриваемая функция от n-переменных должна быть задана картой Карно соответствующей размерности, содержащей полей. Каждому полю карты ставится в соответствие строго определённый набор аргументов. При составлении карты Карно необходимо следить, чтобы наборы соседних полей (клеток) карты различались значением только одного аргумента. В каждом поле записывается значение, принимаемое функцией на соответствующем наборе аргументов.

При выполнении минимизации осуществляется накрытие с помощью правильных конфигураций полей карты, содержащих единицы или нули. Правильными конфигурациями ранга i на карте Карно для ФАЛ от n -переменных являются все прямоугольники (вертикальные, горизонтальные и квадратные), имеющие площадь 2^n–i (i = 1, 2,..., n). Следовательно, правильными конфигурациями на карте Карно для ФАЛ от двух переменных являются все прямоугольники, имеющие площадь 2^2–i (рис. 10.1), от трёх переменных – прямоугольники, имеющие площадь 2^3–i (рис. 10.2), от четырёх переменных – прямоугольники, имеющие площадь 2^4–i (рис. 10.3). Рангом накрытия называется сумма рангов всех правильных конфигураций, образующих накрытие.

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

Принцип минимизации ФАЛ заключается в объединении соседних полей карты в пределах каждой правильной конфигурации. При нахождении минимальной формы ФАЛ выписываются переменные, не изме­няющие своего значения для всех полей правильной конфигурации.

Рисунок 10.1 Использование карт Карно при минимизации ФАЛ от двух переменных

Рисунок 10.2 Использование карт Карно при минимизации ФАЛ от трёх переменных

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

Как видно из рис. 10.1–10.3, при объединении двух полей исключается одна переменная, при объединении четырех полей – две переменные, при объединении восьми полей – три переменные.

В поля карты, соответствующие наборам аргументов, при которых значение функции нас не интересует, вместо нулей или единиц проставляется символ «×» (рис. 10.3). Поля, отмеченные символом «×», включаются в конфигурации накрытия, если это способствует получению более простого выражения для записи функции.

Рисунок 10.3 Использование карт Карно при минимизации ФАЛ от четырёх переменных

Карты Карно наиболее целесообразно использовать для минимизации ФАЛ от двух до шести переменных. При минимизации ФАЛ от пяти переменных она может быть представлена в виде двухслойного параллелепипеда, образованного двумя картами по 16 полей (рис. 10.4). Для удобства записи значений, принимаемых функцией на каждом наборе аргументов, вместо параллелепипеда используют две располагаемые рядом карты Карно (рис. 10.4). Одной из карт ставится соответствие прямое, а другой – инверсное значение пятой переменной. Отличительной особенностью минимизации ФАЛ от пяти переменных является возможность объединения в одну конфигурацию соседних полей, расположенных на различных картах. Поэтому в данном случае образуемые конфигурации могут рассматриваться как некоторые выделяемые области параллелепипеда, характеризуемые не только площадью, но и определённым объёмом. Чем больше объём образуемой конфигурации, тем меньшее количество переменных выписывается из неё при минимизации функции.

При минимизации ФАЛ шести переменных она может быть представлена в виде куба, образованного четырьмя картами по 16 полей.

Для удобства записи значений, принимаемых функцией на каждом наборе аргументов, вместо куба рассматриваются четыре располагаемые рядом карты Карно по 16 полей (рис. 10.5).

Рисунок 10.4 Использование карт Карно при минимизации ФАЛ от пяти переменных

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

Рисунок 10.5 Использование карт Карно при минимизации ФАЛ от пяти переменных