Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №19, Москва, 2019
Авторы: Михайлец Е.В.
Об одной мере сложности неявных представлений функций многозначной логики
Аннотация:
В работе исследуется сложность неявных представлений функций k-значной логики. Функция f неявно представима над A, если используя символы переменных и функции из A можно записать систему уравнений, единственным решением которой является функция f. Для неявно полных классов (т.е. таких, над которыми неявно представима любая функция) рассматривается ранговая функция — минимальное число уравнений, достаточное для неявного представления любой функции от n переменных над заданным классом. В работе построены примеры неявно полных классов с ранговыми функциями, имеющими экспоненциальный порядок роста. Для всех минимальных неявно полных замкнутых классов функций трехзначной логики исследовано поведение ранговых функций и найден порядок роста, а для отдельных классов — точное выражение. При этом установлено, что порядок роста ранговой функции для всех таких классов либо линейный, либо экспоненциальный. Кроме того, получены достаточные условия неявной полноты в k-значной логике, и для всех классов, удовлетворяющих этому условию получено точное выражение ранговой функции, имеющее линейный порядок роста.
Ключевые слова:
k-значная логика, неявное представление, сложность, порядок роста, неявная полнота
Язык публикации: русский,  страниц: 76 (с. 37-112)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Михайлец Екатерина Викторовна,