Пример. Функция в булевом базисе преобразуется к виду:

Пример.

Функция в булевом базисе преобразуется к виду:

.

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

Для оценки формы булевой функции, которая наиболее предпочтительна для практической реализации, обычно вводится индекс (коэффициент) простоты , где - формула, реализующая функцию, характеризующий «сложность» ДНФ (КНФ). Наиболее часто встречаются следующие виды коэффициентов простоты:

а) - число символов (букв) переменных, встречающихся в записи ДНФ (КНФ);

б) - число элементарных конъюнкций (дизъюнкций), входящих в ;

в) - число символов инверсий, встречающихся в записи ДНФ (КНФ).

Сравним две формулы и , реализующие одну функцию. Для них: и , следовательно проще, чем ; и , следовательно, проще, чем ; и , следовательно, проще, чем .

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

Дата добавления: 2014-10-22