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

ГЛАВА 1. УПРОЩЕНИЕ И МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

Задача минимизации булевых функций

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

Очевидно, что сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок. К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно (диаграммы Вейча), метод Квайна - Мак-Класки и др. Эти методы наиболее пригодны для обычной технической практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В достаточно редких случаях, когда число переменных больше шести, обычно используют метод Квайна - Мак-Класки.

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

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

Как было отмечено выше, одним из способов представления ФАЛ от небольшого числа переменных (обычно не больше 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, несколько отличаются, но результат минимизации не зависит от способа построения карт.

Дата добавления: 2015-07-08