ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2009, ТОМ 15, ВЫПУСК 4, СТР. 189-208
А. П. Соколов
Аннотация
Посмотреть как HTML
Посмотреть как рисунок
В работе рассматриваются пороговые функции алгебры логики. Вводится определение сигнатуры пороговой функции. Доказано, что если пороговая функция существенно зависит от всех своих переменных, то её сигнатура определяется однозначным образом. Доказана теорема, характеризующая разбиение множества пороговых функций по классам сигнатур. Отмечается особая важность класса монотонных пороговых функций. Исследуется сложность преобразования одной пороговой функции, заданной некоторой целочисленной линейной формой, в другую. Показано, что в худшем случае данная задача имеет экспоненциальную сложность. Рассматривается строение множеств линейных форм, задающих одну пороговую функцию. Доказана теорема о бесконечной порождённости данных множеств относительно операции сложения линейных форм.
Полнотекстовая версия статьи в формате PDF (380 Kb)
| Главная страница | Содержание журнала | Новости | Поиск |
URL страницы: http://mech.math.msu.su/~fpm/rus/k09/k094/k09407h.htm
Изменения вносились 21 апреля 2010 г.