Статья в сборнике "Математические вопросы кибернетики" №5, Москва, 1994
Авторы:Семенов А.А.
Сложность приближенной реализации булевых функций схемами из функциональных элементов
Аннотация:
В данной статье рассматривается проблема приближённой реализации булевых функций. Приближенная реализация булевых функций схемами из функциональных элементов понимается в смысле хэмминговых систем окрестностей (функции считаются близкими, если расстояние Хэмминга между ними мало). Изучены случаи сильной, средней и слабой определённости реализуемой булевой функции, соответствующие малой, средней и большой мощности окрестностей функций. Для каждого из этих случаев при различных дополнительных условиях получен единый результат: асимптотическая эквивалентность функции Шеннона и функции специального вида, зависящей от количества переменных реализуемой булевой функции, мощности хэмминговой системы окрестностей и приведённого веса конечного полного базиса.
Ключевые слова:
приближенная реализация булевых функций, схемы из функциональных элементов, хэмминговы системы окрестностей, функция Шеннона
