Минимизация ФАЛ - (реферат)
p>Выбираем те min-термы, при записи которых, МДНФ функции минимальна. Шаг 6.Недостаток метода Квайна –необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант.
Идея модификации метода Квайна – метод Квайна-Мак-Класки. (1. 4) 1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором. 2. Вся совокупность номеров наборов разбивается на группы в зависимости от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа и. т. д. ).
3. Сравниваются две группы, отличающиеся на одну единицу.
4. В результате сравнения в номере набора, имеющего большее число единиц на позиции, где обнаружится разница на одну единицу ставится прочерк. 5. В процессе преобразования возникают новые сочетания (n-группы). 6. Процесс преобразования длится до тех пор, пока возможна операция склеивания. 7. Элементы преобразованных групп являются первичными импликантами, которые вместе с номерами исходных наборов образуют таблицы разметок. 8. В остальном эти методы совпадают с единственным уточнением –если в результате таблицы разметок ни одна из строк не покрывает единицу столбца, то надо выбрать номер столбца набора из предыдущей группы преобразований.
Определение: n-группа –это такой набор аргументов функции, что число всех аргументов равных единице равно n, причем значении функции равно 1.
Пример:
Составим таблицу истинности:
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
1
Запишем n-группы:
0-Группа: 0000
1-Группа: 0001, 0010, 0100, 1000
2-Группа: 0011, 0101, 0110, 1001
3-Группа: 0111, 1011
4-Группа: 1111
Теперь сравним группы с номерами n и n+1:
0-Группа: 000-, 00-0, 0-00, -000
1-Группа: 00-1, 0-01, -001, 001-, 0-10, 010-, 01-0, 100
2-Группа: 0-11, -011, 01-1, 011-, 10-1
3-Группа: -111, 1-11
Еще раз сравним (при этом прочерки должны быть на одинаковых позициях): 0-Группа: 00--, 0-0-, -00
1-Группа: 0--1, -0-1, 0-1-, 01—
2-Группа: --11
И еще раз сравним:
0-Группа: 0--
Запишем таблицу исходных min-термов, где функция равна 1:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1011
1111
V
V
V
V
V
V
V
V
0--
Выделим минимальное число групп, покрывающих
Для проверки составим таблицу истинности
1000
1001
1011
1111
-00
V
V
-0-1
V
V
-111
V
V
Метод минимизирующих карт (для ДСНФ и КСНФ). (1. 5)
Одним из способов графического представления булевых функций от небольшого числа переменных являются карты Карно. Их разновидность–карты Вейча, которые строятся как развертки кубов на плоскости, при этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба.
Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на котором значение функции равно единице, а ноль не ставится, а для КСНФ– наоборот.
Диаграмма для двух логических переменных (для ДСНФ):
Для трех переменных:
Карты Карно используются для ручной минимизации функций алгебры логики при небольшом количестве переменных. Правило минимизации: склеиванию подвергаются 2, 4, 8, 16, клеток и клетки, лежащие на границе карты.
При числе переменных 5 и больше отобразить графически функцию в виде единой плоской карты невозможно. Тогда строят комбинированные карты, состоящие из совокупности более простых карт. Процедура минимизации заключается тогда в том, что сначала находится минимальная форма 4-х мерных кубов (карт), а затем, расширяя понятие соседних клеток, отыскивают min-термы для совокупности карт. Причем соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.
Пример: Минимизировать ФАЛ от двух переменных:
1
1
1
Минимизировать функцию:
1
1
1
1
Минимизация логических функций, заданных в базисе .
Метод неопределенных коэфициентов применим для минимизации функций, заданных в различных базисах. Пусть функция является ПСНФ, операция имеет особенности, отличающие ее от операции дизъюнкции. 1)
2)
3)
Минимизация при этом усложняется, так как ее основными критериями являются минимальные ранги каждого терма и их минимальное количество, при этом в ходе минимизации в базисе нецелесообразно приравнивать к нулю все коэффициенты на наборах где , т. к. в наборах, где функция могут остаться термы высокого ранга. Поэтому особой разницы между выбором нулевого или единичного значения функции нет.
Количество коэффициентов, остающихся в нулевых строках должно быть четным, а в единичных–нечетным. Лучше всего рассматривать единичные строки и оставлять те коэффициенты минимального ранга, которые чаще всего повторяются в этих строках. В общем случае для получения минимальной формы выполняют следующие действия: 1) Подсчитывают, сколько раз в единичных строках встречаются термы первого ранга и оставляют из них те, которые встречаются максимальное число раз. 2) Находят нулевые строки, в которых встречаются оставленные в первом шаге термы и их не обнуляют.
3) Рассматривая нулевую строку, в которой остался одни единичные термы и находят в ней еще единичный терм, встречающийся максимальное число раз в единичных строках, в которых еще не было оставлено ни одного терма и. т. д. Метод Квайна-Мак-Класки может быть применим при минимизации этого базиса, при этом кроме эффективных значений функции, гдевключаются некоторые min-термы, где . Метод Квайна-Мак-Класки применим для минимизации базисов стрелки пирса и штриха Шеффера.
Не полностью определенные ФАЛ (1. 6)
Определение: не полностью определенные ФАЛ от n переменных называется функции, заданные на множестве наборов меньше чем.
Если количество неопределенных наборов равно m то путем различных доопределений можно получить различных функций.
Пример: доопределить функцию
Где символ * означает "может быть".
Доопределим *=0
1)
Доопределим *=1
2)
