35
правок
Изменения
→Глубина схемы
При подаче на входы логического элемента любой комбинации двоичных сигналов, на выходах также возникает сигнал — значение [[Определение булевой функции|булевой функции]].
}}
Отождествление переменных осуществляется при помощи ветвления проводников.[[File:Отождествление.png|thumb|200px|Отождествление переменных]]
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
== Изображение логических элементов на схемах ==
{| class = "standardwikitable" border = "1"
!Тип элемента
!-align="center" |И!-align="center" |ИЛИ!-align="center" |НЕ|!Штрих Шеффера|!Стрелка Пирса
|-
|[[Image:AND_logic_element.png]]
|[[Image:OR_logic_element.png]]
|[[Image:NOR_logic_element.png]]
|-
|[[Image:AND_logic_relement.png]]
[[Image:AND_logic_relement2.png]]
{{Определение
|definition= '''Схемная сложность''' (англ. ''Circuit complexity'') функции <tex>f</tex> относительно базиса <tex>B</tex> (англ. ''Circuit complexity'') — это минимальное количество функциональных элементов из набора <tex>B</tex>, необходимое для реализации функции <tex>f</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 leqslant 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, ...\ldots, g_n</tex>. Каждый функциональный элемент базиса <tex>~B_2</tex> можно собрать с помощью не более чем <tex>~size_{B_1}(g_i)</tex> элементов из базиса <tex>~B_1</tex>. Собрать <tex>f</tex> в базисе <tex>B_1</tex> можно следующим образом: заменить каждый элемент схемы <tex>f</tex> в базисе <tex>B_2</tex> на схему соответствующей функции в базисе <tex>B_1</tex>. Такая сборка использует не более чем в <tex>~C = \max_underset{i=1\ldots n}^n {\max} \ size_{B_1}(g_i)</tex> раз больше функциональных элементов, чем соответствующая схема в <tex>B_2</tex>. Параметр <tex>~C</tex> зависит только от выбранных базисов.
}}
|about=аналогична теореме про схемную сложность
|statement =
Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~depth_{B_2}(f) \leq leqslant C_{(B_1,\;B_2)}depth_{B_1}(f)</tex>, где константа <tex>~C</tex> зависит только от базисов <tex>~B_1</tex> и <tex>~B_2</tex>. Доказательство аналогично доказательству предыдущей теоремы.
}}
== Смотри См. также ==
* [[Простейшие методы синтеза схем из функциональных элементов]]
* [[Сумматор]]
* [[Контактная схема]]
== Источники информации==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5
