Алгебро-логические методы в информатике и искусственный интеллект
Мощность решетки замкнутых классов полиномов в $k$-значной логике при составных $k$
С. Н. Селезнева Московский государственный университет им. М. В. Ломоносова, Москва, Российская Федерация
Аннотация:
Рассматриваются замкнутые относительно суперпозиции классы в
$k$-значной логике. Э. Пост установил, что решетка по включению всех замкнутых классов в двузначной логике является счетной. Кроме того, любой замкнутый класс в двузначной логике имеет конечный базис. Ю. И. Янов и А. А. Мучник показали континуальность решетки всех замкнутых классов в
$k$-значной логике при каждом
$k \geqslant 3$. Кроме того, в
$k$-значной логике при
$k \geqslant 3$ найдутся замкнутые классы без базиса и замкнутые классы со счетным базисом. В силу континуальности решетки всех замкнутых классов при
$k \geqslant 3$ изучаются ее подрешетки. В частности, рассматривается замкнутый класс всех функций
$k$-значной логики, представимых полиномами по модулю
$k$. Этот замкнутый класс содержит все функции
$k$-значной логики, если и только если
$k$ является простым числом. Если
$k$ является составным числом, то этот замкнутый класс не является даже предполным. В работах А. Н. Черепова, А. Б. Ремизова, А. А. Крохина, К. Л. Сафина, Е. В. Суханова, Д. Г. Мещанинова и др. изучалось строение надрешеток и подрешеток замкнутого класса всех полиномиальных функций при составных
$k$. В настоящем исследовании при каждом составном числе
$k$ устанавливается континуальность подрешетки замкнутого класса всех полиномиальных функций
$k$-значной логики.
Ключевые слова:
функция
$k$-значной логики, кольцо вычетов по модулю
$k$, полином, замкнутый класс, решетка замкнутых классов.
УДК:
519.716.5,
512.56,
512.714
MSC: 06D25,
08A40,
13M10 Поступила в редакцию: 20.03.2025
Исправленный вариант: 14.04.2025
Принята в печать: 21.04.2025
DOI:
10.26516/1997-7670.2026.55.123