Минимизация функций. Карты Карно.

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

Карта Карно представляет собой булево пространство в виде таблицы, в которой отображаются конституенты СДНФ.

Конституента– это набор перемен­ных, соединенных знаком конъюнкции (И).

Если функция при этом наборе пе­ремен­ных равна 1, то в клетку матрицы записывается 1. Черточками над клетками булева пространства помечаются строки и столбцы (по горизонтали и по вертикали), в которых обозначенная переменная примет значение 1.

Например представлена ФАЛ, для которой СДНФ имеет вид:

.

Составим таблицу для этого множества:

Таблица 11

В таблице 11 значение х₁ = 1 распространяется на столбцы 2 и 3, считая справа налево, а значение х₂ = 1 – на столбцы 1 и 2. Аналогично черточка

х₃ =1 относится к нижней строке таблицы (матрицы).

В таблице 11 введены уровни симметрии по столбцам и строкам. Нулевой (0) уровень делит матрицу пополам, единичные уровни (1) делят каждую область строк или столбцов еще раз пополам. Как видно, по строкам только один нулевой (0) уровень симметрии, а по столбцам их 2.

Для минимизации все клетки, содержащие 1, объединяются в замкнутые об­ласти с числом клеток 2, 4, 8… (в зависимости от числа переменных в ФАЛ). Области могут пересекаться, и одни и те же клетки могут входить в разные об­ласти. «Соседними» являются не только клетки, расположенные рядом по горизонтали и вертикали, но и клетки, находящиеся на противоположных гра­ницах карты. При охвате клеток замкнутыми областями следует стремиться к ми­нимальному числу областей.

Действительно, для верхней области, охватывающей две 1 при , видно, что значение x₂ несущественно, т.к. ФАЛ равна 1 как при x₂, так и при , но обе 1 в булевом пространстве при лежат в области x₁. Аналогично для значения x₃ не существенно значение x₁, но обе 1 соответствуют x₂.

Для табл. 11 получим:

.

Одним из вариантов карты Карно является представление кодирования бу­лева пространства кодом Грея, в котором при переходе от клетки к клетке как по вертикали, так и по горизонтали меняется значение только одной переменной.

Такое представление хорошо воспринимается визуально благодаря симмет­рии по осям. В данном случае это оси «0–0» и «1–1». Эта симметрия позволяет легче находить области склеивания конституент, для которых значения какой-либо переменной x_i не влияет на значение ФАЛ. Речь идет о «ручной» минимизации с использованием визуального восприятия, что эффективно при n ≤ 6.

Для столь простого примера нельзя сделать четкий вывод в пользу того или иного способа кодирования булева пространства, но при числе переменных, рав­ном 4, 6 и более, преимущества кода Грея будут очевидны при визуальном методе минимизации ФАЛ.

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

Соседними между собой являются также крайние левые клетки карты с крайними правыми и крайние верхние клетки карты с крайними нижними (как если бы карты были свернуты в цилиндры по вертикали и горизонтали).

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

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

- для каждой клетки, в которой функция имеет значение 1, записывается конъ­юнкция всех входных переменных (прямых или инверсных);

- составляется дизъюнкция этих конъюнкций, которая и представляет собой СДНФ данной функции.

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

1. Все единицы (при записи функции в дизъюнктивной форме) и все нули (при за­писи функции в конъюнктивной форме) должны быть заключены в прямо­угольные контуры. Единичные контуры могут объединять несколько единиц, но не должны содержать внутри себя нулей. Нулевые контуры могут объединять не­сколько нулей, но не должны содержать внутри себя единиц. Одноименные кон­туры могут накла­дываться друг на друга, т.е. одна и та же единица (или нуль) мо­жет входить в не­сколько единичных (нулевых) контуров.

2. Площадь любого контура должна быть симметричной относительно гра­ниц пе­ременных, пересекаемых данным контуром. Другими словами, число кле­ток в контуре должно быть равно 1, 2, 4, 8, 16, 32, ….

3. Во избежание получения лишних контуров, все клетки которых вошли уже в другие контуры, построение следует начинать с тех единиц или нулей, кото­рые мо­гут войти в один-единственный контур.

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

5. Каждой единичной клетке соответствует конъюнкция входных перемен­ных, оп­ределяющих данную клетку. Каждой нулевой клетке соответствует дизъ­юнкция инверсий входных переменных, определяющих данную клетку.

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

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

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

Рассмотрим пример ФАЛ для шести переменных (табл. 12).

Таблица 12

Все области «1», объединенные двойными линиями, представляют один интервал ФАЛ, для кото­рого по горизонтали очевидна независимость от x₁ и x₃, а по вертикали от x₄ и x₆, т.е. весь интервал соответствует . Верхняя область, объединенная сплошным овалом в одну линию по горизонтали, соответствует x₂x₃, а по вертикали , т.е. , а нижняя соответствует , тогда получим:

.

Последняя запись в скобках для х₃ и х₆ как уже говорилось называется функ­цией (обозначим Ζ) суммы по модулю 2 и обозначаются символом . Другое назва­ние функции Ζ – функция неравнозначности, т.к. она принимает значение 1 только при различных значениях переменных.

.

Заметим, что обратная ей функция имеет вид:

.

Эта функция называется функцией тождественности, т.к. она принимает зна­чение 1 только при одинаковых (тождественных «0» и «1») значениях перемен­ных

.

Тогда выражение для y можно записать в виде

.

Существуют функции, значение которых неопределенно на некоторых наборах входных переменных, т.е. некая комбинация, например , не может быть реализована. Практических примеров таких булевых функций много, особенно для реальных технологических процессов. Все такие комбинации переменных также наносятся на карту Карно и отмечаются символом, отличающимся от символа «0» или «1», с целью получения минимальной формы булевых функций Такие булевы функции называются не полностью определенными*.