В работе исследуется сложность неявных представлений функций k-значной логики. Функция f неявно представима над A, если используя символы переменных и функции из A можно записать систему уравнений, единственным решением которой является функция f. Для неявно полных классов (т.е. таких, над которыми неявно представима любая функция) рассматривается ранговая функция — минимальное число уравнений, достаточное для неявного представления любой функции от n переменных над заданным классом. В работе построены примеры неявно полных классов с ранговыми функциями, имеющими экспоненциальный порядок роста. Для всех минимальных неявно полных замкнутых классов функций трехзначной логики исследовано поведение ранговых функций и найден порядок роста, а для отдельных классов — точное выражение. При этом установлено, что порядок роста ранговой функции для всех таких классов либо линейный, либо экспоненциальный. Кроме того, получены достаточные условия неявной полноты в k-значной логике, и для всех классов, удовлетворяющих этому условию получено точное выражение ранговой функции, имеющее линейный порядок роста.

k-значная логика, неявное представление, сложность, порядок роста, неявная полнота

Математические вопросы и теория численных методов