Изменения

{{Определение |definition='''Функциональный элемент''' (англ. ''Combinational element'') — устройство, предназначенное для обработки информации в цифровой форме. Функциональный элемент имеет ''входы '' и ''выходы''.Сигналы на входах функционального элемента — аргументы функции, которую реализует функциональный элемент, его выходной сигнал является функцией входныхсигналы на выходах — значение функции от аргументов. }}{{Определение |definition=Если входные и выходные значения сигналы — являются нулями и единицами, элемент называется '''логическим''' (англ. ''logic gate'').При подаче на входы логического элемента любой комбинации двоичных сигналов, на выходах также возникает сигнал — значение [[Определение булевой функции|булевой функции]].}} Отождествление переменных осуществляется при помощи ветвления проводников.[[File:Отождествление.png|thumb|200px|Отождествление переменных]] Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.[[File:Подстановка.png|thumb|200px|Подстановка]]

{| class = "standardwikitable" border = "1"

!-align="center" |И!-align="center" |ИЛИ!-align="center" |НЕ|!Штрих Шеффера|!Стрелка Пирса

{{Определение |definition= '''Схемная сложность'' ' (англ. ''Circuit complexity'') функции <mathtex>f</mathtex> относительно базиса <mathtex>B</mathtex> — это минимальное количество функциональных элементов из набора <mathtex>B</mathtex>,необходимое для реализации функции <mathtex>f</mathtex> в базисе <mathtex>B</mathtex> .Схемную сложность функции <mathtex>f</mathtex> в базисе <mathtex>B</mathtex> обозначают так:<tex>size_B(f)</tex>}} {{Теорема|statement =Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~size_{B_2}(f) \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 = \underset{i=1 \ldots n}{\max} \ size_{B_1}(g_i)</tex> раз больше функциональных элементов, чем соответствующая схема в <tex>B_2</tex>. Параметр <tex>~C</tex> зависит только от выбранных базисов.}} == Глубина схемы =={{Определение |definition= '''Глубина схемы''' для функции <tex>f</tex> относительно базиса <tex>B</tex> (англ. ''Circuit depth'') — это максимальная длина пути от входа до выхода по схеме соответствующей функции <tex>f</tex>, состоящей из элементов набора <tex>B</tex>, где за единицу длины принимается один элемент схемы. Глубину схемы для функции <tex>f</tex> в базисе <tex>B</tex> обозначают <tex>depth_B(f)</tex>}}Примечание: понятие глубины имеет смысл только для схем с ограниченной степенью входа (''bounded fan-in'').  {{Теорема|about=аналогична теореме про схемную сложность|statement =Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~depth_{B_2}(f) \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* [http://en.wikipedia.org/wiki/Logic_gate Wikipedia — Lodic gate]* [http://www.intuit.ru/department/calculate/lancalc/2/ Лекция "Схемы из функциональных элементов" в НОУ "ИНТУИТ"] [[Категория: Дискретная математика и алгоритмы]]