Изменение размера оптимальной схемы при переходе к другому базису — различия между версиями
Sementry (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 14 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | {{ | + | {{Определение |
+ | |definition = | ||
+ | '''Схемная сложность''' функции <tex>~f</tex> относительно базиса <tex>~B</tex> - это минимальное количество функциональных элементов из набора <tex>~B</tex>, необходимое для реализации функции <tex>~f</tex> в базисе <tex>~B</tex>. | ||
+ | }} | ||
+ | Схемная сложность обычно обозначается как <tex>~size_B(f)</tex>. | ||
− | = | + | {{Теорема |
− | + | |statement = | |
− | Схемная сложность функции < | + | Для любых базисов <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> зависит только от выбранных базисов. | ||
+ | }} | ||
− | == | + | ==См. также== |
− | + | [[Реализация булевой функции схемой из функциональных элементов]] | |
− | |||
− |
Текущая версия на 19:41, 4 сентября 2022
Определение: |
Схемная сложность функции | относительно базиса - это минимальное количество функциональных элементов из набора , необходимое для реализации функции в базисе .
Схемная сложность обычно обозначается как
.Теорема: |
Для любых базисов , и функции верно неравенство , где константа зависит только от базисов и . |
Доказательство: |
Пусть базис | состоит из функций . Схемная сложность функции относительно базиса равна (по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса можно собрать с помощью элементов из базиса , затратив на это не более чем элементов. Поэтому в сумме мы затратим не более чем в раз больше функциональных элементов, и зависит только от выбранных базисов.
См. также
Реализация булевой функции схемой из функциональных элементов