Минимизация ФАЛ
Таким образом, можно понизить ранг термов. Процедура производится до тех пор, пока не остается ни одного терма, допускающего склейки с другим. Причем склеивающиеся термы помечаются *.
Определение: Непомеченные термы называются первичными импликантами.
Полученное логическое выражение не всегда оказывается минимальным, поэтому исследуется возможность дальнейшего упрощения.
Для этого:
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.
V | V | |||||||
V | V | |||||||
V | V | |||||||
V | V | |||||||
V | V | |||||||
V | V | V | V |
Шаг 4 пропускаем.
Шаг 5.
Выбираем те min-термы, при записи которых, МДНФ функции минимальна.
Шаг 6.
Недостаток метода Квайна — необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант.
Идея модификации метода Квайна — метод Квайна-Мак-Класки. (1.4)
1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.