Программирование на JAVA

Реклама :




2. 4. Например, стоимость большей схе­мы на этом рисунке равна 21: 5 вентилей плюс 16 входных значений. Инверсия входных значений при подсчете игнорируется. Стоимость более простого выра­жения равна 9: 3 вентиля плюс 6 входных значений.

Теперь можно определить и критерий минимизации.

Сумма произведений считается минимальной, если не существует эквивалентного ей выражения меньшей стоимости.

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

Стратегия упрощения заданного выражения заключается в следующем. Преж­де всего, термы-произведения разбиваются на пары, отличающиеся единой пере­менной, которая в одном терме дополняется (

), а во втором используется как есть (х). Затем в каждой паре общее произведение двух переменных выносится за скобки, а в скобках остается терм х +
, всегда равный 1. Вот что мы получим, применив эту процедуру к первому выражению для функции f1:


    

    

    

Это выражение минимально. Соответствующая ему логическая схема приве­дена на уже упоминаемом нами рис. 2. 4.


<< назад вперед >>