Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
ОПРЕДЕЛЕНИЕ. Сложностью ДНФ D называется число вхождений в D функций & и
Сложностью ДНФ D называется число вхождений в D функций & и 
. Для обозначения сложности ДНФ используется выражение L(D).
Например, следующая формула является ДНФ:
.
Сложность этой ДНФ равна 8.
Одна и та же булевская функция может представляться различными ДНФ.
Например, две ДНФ:
U = 
и
W = 
представляют одну и ту же б.ф.
Если некоторая функция задана в виде ДНФ, то структура этой ДНФ непосредственно преобразуется в структуру с.ф.э., вычисляющей данную функцию. Сложность такой схемы равна числу вхождений & и в ДНФ.
Схема, построенная по формуле W из приведенного примера, будет сложнее схемы, построенной по U. Поэтому для построения простых схем, получаемых на основе ДНФ, естественно искать такую ДНФ, которая имеет наименьшую сложность среди всех ДНФ, представляющих одну и ту же б.ф.
| <== предыдущая страница | | | следующая страница ==> |
| МИНИМАЛЬНЫЕ ДНФ | | | ОПРЕДЕЛЕНИЕ. ДНФ D, представляющая функцию f, называется минимальной ДНФ для этой функции, если L(D) = min(L(D*)) |
Дата добавления: 2014-11-15; просмотров: 238; Нарушение авторских прав
Мы поможем в написании ваших работ!