Оригинальные методы реализации булевых функций в классах формул и схем из функциональных элементов в разных базисах (стр. 3 )

Fскоб

&

&

Ú

x1

x2

x3

x4

Рис. 7.3. Схема без ветвления (реализация скобочной формулы)

Пример 7.3. Булева функция f (5) задается ДНФ FДНФ = x1x2x3x4 Ú x1x2x3x5. Представить ее в базисе G1 (соответствующих ФЭ), минимизируя оценки показателей сложности, в классе формул (схем с ветвлением и без). Исходные данные: r = (4, 4), n = 5, n0 =3, n1 =1, n2 =1.

2.1. В классе ДНФ получаем:

f (5)= FДНФ = gÚ (g& (g&( x1, x2), g& (x3, x4)), g& (g&(x1, x2), g&( x3, x5))) ;

LБ(FДНФ, G1 )=8, LF(FДНФ, G1 )= 7, Dep F(FДНФ, G1 )= 3.

2.2. В классе скобочных формул получаем:

FДНФ = x1x2x3x4 Ú x1x2x3x5 = x1x2x3(x4Úx5) = Fскоб =

= g& (g& (g&( x1, x2), x3), gÚ ( x4, x5)) ;

Lб(Fскоб, G1 ) = 5, LF(Fскоб, G1 ) = 4, Dep F( Fскоб, G1 ) = 3.

2.3. В классе схем без ветвления (на основе ДНФ) получаем значения показателей сложности (см. рис. 7.4): LS(FДНФ, G1 )=5, Dep S(FДНФ, G1 )=3.

2.4. В классе схем с (максимально полным) ветвлением (на основе ДНФ) получаем значения показателей сложности (см. рис. 7.5):

LS(FДНФ, G1 )=5, Dep S(FДНФ, G1 )=4.

2.5. В классе схем с (частичным) ветвлением (на основе ДНФ) получаем значения показателей сложности (см. рис. 7.6):

LS(FДНФ, G1 )=6, Dep S(FДНФ, G1 )=3.

2.6. В классе схем без ветвления (на основе скобочной формулы) получаем значения показателей сложности (см. рис. 7.7):

LS(Fскоб, G1 ) = 4, Dep S( Fскоб, G1 ) = 3.

FДНФ

Ú

&

&

&

&

&

&

x2

x1

x4

x3

x2

x1

x5

x3

Рис. 7.4. Схема без ветвления (реализация ДНФ)