5.Постановка и методы решения задачи минимизации функции алгебры логики (фал)

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

Под минимизацией логической функции понимается выполнение преобразований с целью получения наиболее простого представления ФАЛ. В инженерной практике используются следующие основные методы минимизации: последовательного перебора, последовательного упрощения аналитического выражения, карт Карно, Квайна, Квайна–Мак-Класки, Л.Т. Мавренкова и т. д

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

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

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

Карта Карно

Карта Карно есть один из вариантов табличной формы представления логических функций. Эти карты составляют исходную информационную основу одноимённого метода минимизации функций. Но, сначала рассмотрим сами карты.

В отличие от таблицы истинности, где в качестве элемента структуры выделяется строка элементом структуры карты является клетка. Число строк и клеток одинаково и равно , где – число независимых переменных логической функции. Каждая клетка карты имеет координаты, соответствующие возможным значениям независимых переменных. В каждой клетке записывается значение функции. На рис.1 приведён пример сопоставления рассматриваемых табличных форм функции двух переменных следующего вида

x1	x2
0	0		0
0	1		1
1	0		1
1	1		0

При преобразовании табличной формы представления функции в аналитическую и обратно удобно вместо значений координат клеток записывать вид переменных (прямой, инверсный), который они имеют в минтермах СДНФ. Сама карта для рассматриваемой функции будет иметь вид, показанный на рисунке.

Правая часть рисунка есть упрощённый вид карты Карно, который обычно используется в практической работе. В этом варианте границы и  и значения  y=0  не ставятся, но подразумеваются.  Карты Карно для числа переменных  имеют точно такой же принцип построения. Как выглядят такие карты можно увидеть на рисунке:

Основное преимущество карт Карно – наглядность. Но, для числа переменных n = 6  и более карта становится структурно сложной и с ней трудно работать. Поэтому, в большинстве случаев карты Карно используются до  n=5 включительно.

На рисунке приведены карты с определённой системой расположения границ переменных. Имеются и другие равноправные возможности.

Функция, представленная картой Карно, может быть преобразована в СДНФ и СКНФ. В случае преобразования в СДНФ каждая «1» будет соответствовать минтерму (логическому слагаемому). Напомним, что минтерм есть логическое произведение независимых переменных, представленных в прямой или инверсной форме (п. 2.3).

Пример 1.

В случае СКВТ, компоновка аналитического вида функции происходит согласно её конструкции (логическое произведение элементарных дизъюнкций). Число элементарных дизъюнкций равно числу пустых клеток (нулей) карты. Этот вопрос решается аналогично случаю компоновки СДНФ, но, в отличие от него, все переменные инвертируются (см. пример 2.5.9).

Рассмотренное существо связи карты Карно с СДНФ и СКНФ используется и при обратном переходе от аналитического вида функции к её табличному представлению. Это хорошо просматривается на примерах.

Пример 2.