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

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

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

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

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

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

Карта Карно

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

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

x1	x2

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

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

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

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

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

Пример 1.

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

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

Пример 2.

Пример 3.

Пример 4.

Пример 5.

Приведённый пример позволяет отметить следующее:

1. полученное объединение единиц есть графическая форма представления результата склеивания минтермов,

2. объединение, так же как и исходные минтермы, имеет координаты в виде последовательности независимых переменных ,

3. аналитический результат склеивания (минимизированная функция рассматриваемого примера) получается путём логического перемножения координат полученного объединения единиц .

Несмотря на свою простоту, пример 5 в основном отражает существо рассматриваемого метода минимизации логических функций.

Склеиваются только соседние минтермы, а объединяются только соответствующие им единицы, которые всегда оказываются рядом стоящими. Последнее отражает основную особенность карты Карно. Поэтому, объединять можно:

a) две рядом стоящие единицы,

b) две рядом стоящие пары единицы, образующие «четвёрку» единиц,

c) две «четвёрки», объединяющие восемь единиц.

Конфигурация объединений строго регламентирована. Возможные её варианты представлены на рисунке.

Существуют так же модификации разрешённых конфигураций объединений единиц:

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

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

Пересечение объединений может быть однократным, двух, трёх, и четырёхкратным. Возможные варианты пересечения показаны на рисунке.

Критерий выбора варианта объединения единиц на карте Карно из множества возможностей формулируется следующим образом. Для достижения минимальной тупиковой формы функции необходимо обеспечить:

1. минимум числа объединений единиц,

2. максимум единиц составляющих каждое объединение.

Первый пункт критерия носит безусловный характер. Второй пункт должен соблюдаться только при выполнении первого. Формулировку критерия сопровождают два следствия:

a) каждая единица на карте Карно должна принадлежать какому-либо объединению, даже если объединение содержит только одну единицу,

b) объединение должно содержать хотя бы одну «свою» единицу, не принадлежащую ни к какому другому объединению.

Эти следствия так же важно помнить при формировании вариантов объединений единиц.

Пример 6.

В процедуре минимизации функций обычно не расписывают действия как это сделано в примере. Можно сразу же составлять минтермы, не включая в них координаты заключённые в скобки.

Пример 7.

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

Пример 8.

Вопросы для самопроверки

1. Осуществите минимизацию функций, используя метод карт Карно:

;

;

;

2. Используя метод карт Карно, минимизируйте функции от пяти аргументов:

Не нашли, что искали? Воспользуйтесь поиском по сайту: