Cтраница 1
Функция Шеннона вводится - в два этапа. [1]
Аналогично определяется функция Шеннона для полиномиальных нормальных форм. [2]
О поведении функций Шеннона для бесконечных базисов известно меньше. До недавнего времени порядки роста или асимптотики функций Шеннона были установлены лишь для некоторых конкретных базисов. Из этих результатов явствует, что поведение функций Шеннона для бесконечных базисов может быть довольно разнообразным. [3]
Обычным образом введем функцию Шеннона L ( п): пусть L ( /) 1 ( минимум берется по всем схемам S, реализующим заданную функцию /), тогда L ( п) max L ( S) по всем булевым функциям от п аргументов. [4]
Таким образом, асимптотика функции Шеннона сохраняется с точностью до множителя, сколь угодно близкого к единице, и при этом вероятность сбоя е ограничена константой. [5]
Следующая теорема дает верхнюю оценку функции Шеннона диагональных форм. [6]
Теперь задача получения нижней оценки для функции Шеннона сводится к вычислению функции S ( n, & ()) и подбору возможно большей функции k ( n), удовлетворяющей приведенному выше неравенству. [7]
Подробнее этот процесс был проиллюстрирован при получении функции Шеннона. Метод получения верхних оценок почти всегда определяется конкретной задачей и изобретательностью решающего эту задачу. К сожалению, в теории оптимального структурного синтеза не существует сейчас сколько-нибудь общих методов или подходов, которые оказались бы эффективными при решении различных задач синтеза. Наиболее показательна в этом плане многолетняя история установления окончательной оценки числа элементов в схеме, реализующей умножение - разрядных чисел. [8]
Функция L ( n) носит название функции Шеннона. Она играет важнейшую роль в теории синтеза управляющих систем. Величина L ( n), как это следует из определения, равна наименьшей сложности, с которой заведомо можно реализовать любую булеву функцию от п переменных. [9]
Функция L4) ( п) называется функцией Шеннона по имени американского математика Клода Шеннона, который впервые ввел эту функцию для контактных схем, им же были получены первые утверждения об этой функции. [10]
В данной работе предложен новый подход к получению оценок функций Шеннона для произвольных бесконечных базисов, позволяющий при довольно слабых ограничениях оценивать рост функций Шеннона с точностью до полиномиальной эквивалентности. [11]
В дальнейшем оценки высокой степени точности были получены также для функций Шеннона, связанных с реализацией ФАЛ из некоторых специальных классов. Так в [3] были установлены асимптотические оценки высокой степени точности для сложности реализации функций, связанных с автоматными языками, в классах схем из функциональных элементов и ориентированных контактных схем. [12]
Функции L ( n), LA ( п) называются функциями Шеннона. [13]
Отметим также работу [8], где решена близкая по постановке задача о характеризации поведения функций Шеннона для базисов с произвольными весами элементов. [14]
Заметим во избежание недоразумений, что результат об одновременном достижении асимптотики по мощности и асимптотики функции Шеннона [37] не имеет отношения к обсуждаемой проблеме. [15]