Минимизация функций алгебры логики
нности:
|[pic] |[pic] |[pic] |[pic] |[pic] |
|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)
Одним из способов графического представления булевых функций от небольшого
числа переменных являются карты Карно. Их разновидность – карты Вейча,
которые строятся как развертки кубов на плоскости, при этом вершины куба
представляются клетками карты, координаты которых совпадают с координатами
соответствующих вершин куба.
Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на
котором значение функции равно единице, а ноль не ставится, а для КСНФ –
наоборот.
Диаграмма для двух логических переменных (для ДСНФ):
[pic]
Для трех переменных:
[pic]
Карты Карно используются для ручной минимизации функций алгебры логики при
небольшом количестве переменных. Правило минимизации: склеиванию
подвергаются 2,4,8,16,[pic] клеток и клетки, лежащие на границе карты.
При числе переменных 5 и больше отобразить графически функцию в виде единой
плоской карты невозможно. Тогда строят комбинированные карты, состоящие из
совокупности более простых карт. Процедура минимизации заключается тогда в
том, что сначала находится минимальная форма 4-х мерных кубов (карт), а
затем, расширяя понятие соседних клеток, отыскивают min-термы для
совокупности карт. Причем соседними клетками являются клетки, совпадающие
при совмещении карт поворотом вокруг общего ребра.
| |[pic] |[pic] |
|[pic] |[pic] |[pic] |
|[pic] |[pic] |[pic] |
Пример: Минимизировать ФАЛ от двух переменных: [pic]
| |[pic] |[pic] |
|[pic] |1 |1 |
|[pic] |1 | |
[pic]
Минимизировать функцию: [pic]
| |[pic] |[pic] |[pic] |[pic] |
|[pic] |1 |1 |1 | |
|[pic] | |1 | | |
| |[pic] |[pic] |[pic] |[pic] |
[pic]
Минимизация логических функций, заданных в базисе [pic].
Метод неопределенных коэфициентов применим для минимизации функций,
заданных в различных базисах. Пусть функция [pic] является ПСНФ, операция
[pic]имеет особенности, отличающие ее от операции дизъюнкции.
1)[pic]
2)[pic]
3) [pic]
Минимизация при этом усложняется, так как ее основными критериями являются
минимальные ранги каждого терма и их минимальное количество, при этом в
ходе минимизации в базисе [pic] нецелесообразно приравнивать к нулю все
коэффициенты на наборах где [pic], т.к. в наборах, где функция [pic]могут
остаться термы высокого ранга. Поэтому особой разницы между выбором
нулевого или единичного значения функции нет.
Количество коэффициентов, остающихся в нулевых строках должно быть четным,
а в единичных – нечетным. Лучше всего рассматривать единичные строки и
оставлять те коэффициенты минимального ранга, которые чаще всего
повторяются в этих строках. В общем случае для получения минимальной формы
выполняют следующие действия:
1) Подсчитывают, сколько раз в единичных строках встречаются термы первого
ранга и оставляют из них те, которые встречаются максимальное число раз.
2) Находят нулевые строки, в которых встречаются оставленные в первом шаге
термы и их не обнуляют.
3) Рассматривая нулевую строку, в которой остался одни единичные термы и
находят в ней еще единичный терм, встречающийся максимальное число раз в
единичных строках, в которых еще не было оставлено ни одного терма и.т.д.
Метод Квайна-Мак-Класки может быть применим при минимизации этого базиса,
при этом кроме эффективных значений функции, где [pic]включаются некоторые
min-термы, где [pic]. Метод Квайна-Мак-Класки применим для минимизации
базисов стрелки пирса и штриха Шеффера.
Не полностью определенные ФАЛ (1.6)
Определение: не полностью определенные ФАЛ от n переменных называется
функции, заданные на множестве наборов меньше чем [pic].
Если количество неопределенных наборов равно m то путем различных
доопределений можно получить [pic] различных функций.
Пример: доопределить функцию [pic]
Где символ * означает "может быть".
Доопределим *=0
1)[pic]
Доопределим *=1
2) [pic]
Если доопределять *=0 или *=1 то получим минимальный вариант:
3)[pic]
Пример показывает, что доопределение функции существенно влияет на конечный
результат минимизации. При доопределении [pic] можно руководствоваться
правилом: МДНФ не полностью определенных функций получается как дизъюнкция
наиболее коротких по числу букв импликант функции [pic] на всех наборах и
функциях, которые в совокупности покрывают все импликативные СНФ, и [pic]на
всех наборах, где функция не определена.
Пример: найти минимальную форму для [pic]
Составим таблицу истинности:
|[pic] |[pic] |[pic] |[pic] |[pic] |
|0 |0 |0 |0 |1 |
|0 |0 |0 |1 |* |
|0 |0 |1 |0 |* |
|0 |0 |1 |1 |0 |
|0 |1 |0 |0 |* |
|0 |1 |0 |1 |0 |
|0 |1 |1 |0 |1 |
|0 |1 |1 |1 |* |
|1 |0 |0 |0 |* |
|1 |0 |0 |1 |1 |
|1 |0 |1 |0 |0 |
|1 |0 |1 |1 |* |
|1 |1 |0 |0 |0 |
|1 |1 |0 |1 |* |
|1 |1 |1 |0 |1 |
|1 |1 |1 |1 |* |
1) доопрделим *=1 и получим минимальный вид функции[pic]
[pic]
Доопрделим *=0
[pic]
Оптимальное доопрделение функций соответствующее минимальному покрытию
может быть найдено по методу Квайна.
| |[pic] |[pic] |[pic] |[pic] |
|[pic] | | |V | |
|[pic] |V | |V | |
|[pic] | |V | |V |
|[pic] | | |V | |
В результате получится минимальный вид функции вида: [pic]ее таблица
единичных значений тогда будет: [pic]
Временные булевы функции. (1.7)
Определение: Временная булева функция – логическая функция вида [pic],
принимающая значение едини
| | скачать работу |
Минимизация функций алгебры логики |