Минимизация функций алгебры логики (стр. 3 из 7)

Минимизация логических функций, заданных в базисе

.

Метод неопределенных коэфициентов применим для минимизации функций, заданных в различных базисах. Пусть функция

является ПСНФ, операция имеет особенности, отличающие ее от операции дизъюнкции.

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