RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Иркутского государственного университета. Серия «Математика» // Архив

Известия Иркутского государственного университета. Серия Математика, 2026, том 55, страницы 123–133 (Mi iigum649)

Алгебро-логические методы в информатике и искусственный интеллект

Мощность решетки замкнутых классов полиномов в $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



© МИАН, 2026