689
правок
Изменения
м
Нет описания правки
Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)</tex>, где константа <tex>~C</tex> зависит только от базисов <tex>~B_1</tex> и <tex>~B_2</tex>.
|proof =
Пусть базис <tex>~B_2</tex> состоит из функций <tex>~g_1, g_2, ..., g_n</tex>. Схемная сложность функции <tex>~g_i</tex> относительно базиса <tex>~B_1</tex> равна <tex>~size_{B_1}(g_i)</tex>(по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса <tex>~B_2</tex> можно собрать с помощью элементов из базиса <tex>~B_1</tex>, затратив на это не более чем <tex>~size_{B_1}(g_i)</tex> элементов. Поэтому в сумме мы затратим не более чем в <tex>~C = \max_{i=1}^n size_{B_1}(g_i)</tex> раз больше функциональных элементов, и <tex>~C</tex> зависит только от выбранных базисов.
}}
==См. также==
[[Реализация булевой функции схемой из функциональных элементов]]
