Простейшие методы синтеза

1. Метод синтеза, основанный на моделировании СДНФ.

2. Модификация предыдущего метода, заключающаяся в совместной реализации конъюнкций.

Метод синтеза, основанный на моделировании СДНФ, наглядно описали при доказательстве теоремы 1 (рис. 2).

Далее опишем следующий метод, заключающийся в совместной реализации конъюнкций (лемма).

Обозначим через L (F/G) минимальную сложность схемы (в базисе Б), которую надо присоединить к схеме, реализующей функцию G, чтобы полученная схема реализовала функцию F. Очевидно, что

L (F) L (G)+ L (F/G). (2)

В нашем случае Б = (, &, -).

Пусть Q_n (x₁,…,x_n) = {x₁^s1&…&x_n^sn} – система всех 2ⁿ конъюнкций от переменных x₁,…,x_n.

Лемма. L(Q_n) ~ 2ⁿ (сложность реализаций всех конъюнкций от n переменных).

Доказательство. Конъюнкцию x₁^s1&…&x_n^sn можно разбить на 2 части:

x₁^s1&…&x_m^sm и x_m+1^sm+1&…&x_n^sn.

Очевидно, что каждая конъюнкция x₁^s1&…&x_n^sn из Q (x ,…,x ) является конъюнкцией двух конъюнкций: x₁^s1&…&x_m^sm из Q (x ,…,x ) и x_m+1^sm+1&…&x_n^sn из Q_n-m (x_m+1,…,x_n).

Поэтому (согласно рис. 4)

L(Q / Q , Q )£2 . (3)

Рис. 4

Из (1) следует, что

L(Q )£(2m-1)*2 £m*2 ,

L(Q )£[2(n-m)-1]*2 £(n-m)*2 .

Поэтому, учитывая (2) и (3), имеем L(Q )£ L(Q )+ L(Q )+ L(Q / Q , Q )£ m*2 +(n-m)*2 +2 .

Положим теперь m = [ ]. Тогда m*2 £ *2 ,

~

(n-m)* 2 £( +1)*2 . Значит, L(Q ) < 2ⁿ.

С другой стороны, очевидно, что при n ³ 2 L(Q )³2 , так как каждая конъюнкция реализуется на выходе некоторого элемента.

Таким образом, L(Q )~2ⁿ. Лемма доказана.

~

~

Замечание. Используя лемму, можно усовершенствовать предыдущий метод синтеза, заменив в схеме на рисунке 2 верхнюю часть схемы, реализующую конъюнкции раздельно, схемой, реализующей их совместно. При этом для любой функции f(x₁, …, x_n), f , имеем: L(f) L(Q ) + 2 , так как L(Q )~2 , то L(f) < 2*2 . Значит, L(n) < 2*2 .