ШЕННОНА ФУНКЦИЯ

— функция , равная такому наименьшему числу, что любую функцию алгебры логики от переменных можно реализовать схемой контактной, содержащей не более чем контактов. Впервые ввел ее амер. математик К. Шеннон (р. 1916) (отсюда и название Впоследствии подобную ф-цию изучали для схем из произвольных элементов и для отдельных классов таких схем (напр., параллельно-последовательных схем). В настоящее время термин Ш. ф. относится к семейству всех таких ф-ций, но каждый раз при этом указывают, какой класс схем рассматривается. Изучалось асимптотическое поведение Ш. ф. для класса всех ф-ций алгебры логики, а также для многих важных классов замкнутых функций алгебры логики. М. И. Кратко.