35
правок
Изменения
Нет описания правки
== Логические элементы ==
'''Функциональный элемент''' (англ. ''Combinational element'') — устройство, предназначенное для обработки информации в цифровой форме. Функциональный элемент имеет ''входы'' и ''выходы''.
Сигналы на входах функционального элемента — аргументы функции, которую реализует функциональный элемент, сигналы на выходах — значение функции от аргументов.
Если входные и выходные сигналы — являются нулями и единицами, элемент называется '''логическим''' (англ. ''logic gate'').
При подаче на входы логического элемента любой комбинации двоичных сигналов, на выходах также возникает сигнал — значение [[Определение булевой функции|булевой функции]].
|Стрелка Пирса
|-
|[[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]]
[[Image:NAND_logic_relement2.png]]
|[[Image:NOR_logic_relement.png]]
[[Image:NOR_logic_relement2.png]]
|}
{{Определение
|definition= '''Схемная сложность''' функции <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>
}}
{{Определение
|definition= '''Глубина схемы''' для функции <tex>f</tex> относительно базиса <tex>B</tex> — это максимальная длина пути от входа до выхода по схеме соответствующей функции <tex>f</tex>, состоящей из элементов набора <tex>B</tex>, где за единицу длины принимается один элемент схемы.
Глубину схемы для функции <tex>f</tex> в базисе <tex>B</tex> обозначают <tex>depth_B(f)</tex>
}}
}}
Доказательство аналогично доказательству предыдущей теоремы.
== Смотри также ==
* [[Простейшие методы синтеза схем из функциональных элементов]]
* [[Сумматор]]
* [[Каскадный сумматор]]
* [[Контактная схема]]
== Источники ==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5* [http://en.wikipedia.org/wiki/Logic_gate Статья Logic Gate на английской википедииWikipedia — Lodic gate]* [http://www.intuit.ru/department/calculate/lancalc/2/ Лекция "Схемы из функциональных элементов" в Интернет Университете Информационных ТехнологийНОУ "ИНТУИТ"]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
