$S$-классификация функций многозначной логики

Множество функций многозначной логики предлагается классифицировать относительно операций суперпозиции и перехода к двойственным функциям ($S$-классификация). Содержательное описание всех $S$-замкнутых классов, начатое автором в 1979–82 гг., было завершено Нгуен Ван Хоа. При $k\ge5$ множество функций $k$-значной логики имеет только два $S$-предполных класса: класс $I_k$ идемпотентных функций и класс $\operatornameSLP_k$ Слупецкого. В настоящей работе найдены ключевые свойства, определяющие $S$-замкнутые классы, которые формализованы в виде так называемых основных отношений. На языке отношений и с использованием теории Галуа для алгебр Поста доказано, что всякий $S$-замкнутый класс функций, не лежащий в $\operatornameSLP_k$, можно задать с помощью основных отношений. В множестве всех наборов основных отношений определены все независимые наборы, которые соответствуют всем $S$-замкнутым классам, не лежащим в $\operatornameSLP_k$. Получена точная формула числа $S$-замкнутых классов, содержащихся в $I_k$, которая выражается кубическим полиномом от $k$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 95–01–01625.