Минимизация функций алгебры логики (84391)

Посмотреть архив целиком

Минимизация ФАЛ

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

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

Существуют два направления минимизации:

1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.

2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу).

При этом следует учесть, что ни один из способов минимизации не универсален!

Существуют различные методы минимизации:

1. Метод непосредственных преобразований логических функций. (1.1)

При применении данного метода:

а) Записываются ДСНФ логических функций

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

По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу.

Определение: Min-термы, образованные при склеивании называются импликантами.

Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным.

Определение: Несклеивающиеся импликанты называются прослойками.

Определение: Формула, состоящая из простых импликант – тупиковая.

Пример:

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

0


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

Пример:

Мы получили минимальную СНФ.

Метод неопределенных коэффициентов. (1.2)

Суть метода состоит в преобразовании ДСНФ в МДНФ.

На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

Алгоритм определения коэффициентов:

1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.

2. Напротив каждого выражения поставить соответствующее значение функции.

3. Выбрать строку, в которой значение функции и приравнять все к нулю.

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

5. Проанализировать оставшиеся коэффициенты в единичных строках.

6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.

7. Записать исходный вид функции.

Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.


Пример:


0

0

0

0

00

00

00

000

1

1

0

0

1

00

01

01

001

0

2

0

1

0

01

00

10

010

1

3

0

1

1

01

01

11

011

0

4

1

0

0

10

10

00

100

1

5

1

0

1

10

11

01

101

0

6

1

1

0

11

10

10

110

0

7

1

1

1

11

11

11

111

1


Итак, получим

Метод Квайна (1.3)

Суть метода сводится к тому, чтобы преобразовать ДСНФ в МДНФ. Задачи минимизации по методу Квайна состоит в попарном сравнении импликант, входящих в ДСНФ с целью выявления возможности склеивания по какой-то пременной так:

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

Определение: Непомеченные термы называются первичными импликантами.

Полученное логическое выражение не всегда оказывается минимальным, поэтому исследуется возможность дальнейшего упрощения.

Для этого:

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

2. Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.

3. Задача упрощения сводится к нахождению такого минимального количества импликант, которые покрывают все столбцы.

Алгоритм метода Квайна (шаги):

1. Нахождение первичных импликант.

Исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз. Непомеченные импликанты переходят в функции на этом шаге.

2. Расстановка меток избыточности.

Составляем таблицу, в которой строки – первичные импликанты, столбцы – исходные термы. Если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку.

3. Нахождение существенных импликант.

Если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным.

4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются.

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

5. Выбор минимального покрытия.

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

6. Далее результат записывается в виде функции.

Пример:

Шаг 1.

Термы 4го ранга

Термы 3го ранга

Термы 2го ранга

* 1

* 3

* 4

* 1

* 2

* 2

* 3

* 4

* 1

* 2

* 2


* 1


Шаг 2.