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

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

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

f (7)= fДНФ = gÚ (g& (g&(g&( x1, x2), g& (x3, x4)), g&( x5x6)), g&(x1, x7)) ;

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

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

fДНФ = x1x2x3x4 x5x6 Ú x1x7= x1 (x2x3x4 x5x6 Ú x7) = Fскоб =

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

Lб(fскоб, G1 ) = 7, LF(fскоб, G1 ) = 6, Dep F( fскоб, G1 ) = 5.

fДНФ

Ú

&

&

&

&

&

&

x1

x2

x3

x4

x5

x6

x7

Рис. 7.8. Реализация ДНФ схемой без ветвления