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

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

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

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

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

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. Составляются таб

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать