1.2. Метод минимизирующих карт.

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

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

Прежде, чем продолжить дальнейшее рассмотрение, приведем некоторые определения, которые понадобятся при дальнейшем изложении [1].

Определение. Булева функция , называетсяимпликантой булевой функцией , если на каком-либо наборе переменных,где функцияравна единице, функциятакже равна единице.

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

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

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

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

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

Пример 1.1. Рассмотрим использование карт Карно для минимизации следующих функций:

а)

б)

Этим функциям соответствуют графическое представление (см. рис. 1.1 а, б):

Рис.1.1. Графическое представление функций и в виде карт Карно и склеивание соседних клеток карты

Используя результаты склеивания переменных, которые представлены на рис.1, запишем минимальную дизъюнктивную нормальную форму функций

и

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

- две соседние клетки карты (два 0-куба) образуют один 1-куб.

При этом клетки карты, находящиеся на границах, также являются соседними, а, следовательно, их можно склеивать, образовывая 1-куб (см. рис. 1.1 в). Независимая переменная обозначена символом X;

- четыре соседние клетки карты могут объединяться, образуя 2-куб (рис. 1 в, импликанта X10X), содержащий две переменные;

- восемь клеток куба после склеивания, образуют один 3-куб и т.д.

Пример 1.2. Булева функция задана таблицей истинности (табл. 1.1). Построить карту Карно и определить МДНФ.

Таблица 1.1.

Таблица истинности

Из таблицы истинности собираем СДНФ и создаем карты Карно для четырех переменных (рис.1.2). Поиск МДНФ сводится к определению минимального количества элементарных конъюнкций, которые покрывают все единицы начальной СДНФ.

Используя полученные импликанты (рис. 1.2), запишем МДНФ так

Карты Карно, приведенные на рис. 1.1 и рис 1.2, несколько отличаются, но результат минимизации не зависит от способа построения карт.