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