Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

f3(x)=[pic]&(1,3,4,5)

_ _ _ _ _ _ y=(x1(x2(x3) (x1(x2(x3) (x1(x2(x3) (x1(x2(x3) (*)

Преобразование произвольной аналитической формы Булевой функции в нормальную

В Булевой алгебре в виде теоремы доказывается следующее утверждение: существует единый конструктивный подход, позволяющий преобразовать аналитическое выражение Булевой алгебры в произвольной форме к нормальной форме.
Пример:

_ _ _ _

_ _ y=f4(x)=(x1x2(x2x3)(x1|x4)=(x1x2(x2x3)(x1x4)=(x1x2(x2x3)(x1(x4)=

_ _ _ _ _ _ _
_ _ _
=x1x2(x1x2x4(x1x2x3(x2x3x4=x1x2(x1x2x3(x2x3x4=x1(x2(x2x3)(x2x3x4=

_ _ _ _
=x1(x2(x3) (x2x3x4=x1x2(x1x3(x2x3x4
(КДНФ)

Замечания:

1) В общем случае любая Булева функция может иметь несколько КДНФ, отличающихся либо количеством термов, либо количеством букв в этих термах.

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

3) По сравнению со схемой, построенной по ДНФ, схема, построенная по скобочной форме (*), является более предпочтительной т.к. при одном и том же числе логических элементов (И, ИЛИ) содержат меньшее число входов (9 вместо 10).

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

4) Сущность конструктивного подхода при получении ДНФ состоит в следуюшем: а) преобразование операций не-Булевого базиса к операциям
Булевого базиса (см. последние строки таблицы) б) снятие отрицаний над выражениями с применением законов двойственности в) раскрытие скобок с применением дистрибутивного закона г) упрощения выражения с применением закона поглощения

Приведение произвольных нормальных форм Булевой функции к каноническим

Для приведения произвольной ДНФ к КНФ необходимо использовать правило дизъюнктивного развертывания применительно к каждому из неполных конъюнктивных термов.

_ _
P=P(xi(xi)=Pxi(Pxi, где P-неполный конъюнктивный терм (ранг этого терма меньше n), а xi - недостающий в терме аргумент.
Пример:

_ _ _ _ _ _

_ _ _ _ y=x1(x2x3(ДНФ)=x1(x2(x2)(x3(x3) (x2x3(x1(x1)=x1x2x3( x1x2x3(

_ _ _ _ _ _ _ _ _

(x1x2x3(x1x2x3( x1x2x3( x1x2x3 (КДНФ)

Замечание:

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

y=[pic] (0,1,2,3,5)=f3
Преобразование КНФ к ККНФ реализуется путем применения правила конъюнктивного развертывания к каждому неполному дизъюнктивному терму.

_ _

Рекомендуем скачать другие рефераты по теме: реферат на тему менеджмент, класс.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата