Список выпусков > Серия «Математика». 2026. Том 55
Мощность решетки замкнутых классов
полиномов в 𝑘-значной логике при составных 𝑘
Автор(ы)
С. Н. Селезнева
Московский государственный университет им. М. В. Ломоносова, Москва, Российская Федерация
Аннотация
Рассматриваются замкнутые относительно суперпозиции классы в
𝑘-значной логике. Э. Пост установил, что решетка по включению всех замкнутых
классов в двузначной логике является счетной. Кроме того, любой замкнутый класс
в двузначной логике имеет конечный базис. Ю. И. Янов и А. А. Мучник показали
континуальность решетки всех замкнутых классов в 𝑘-значной логике при каждом
𝑘 > 3. Кроме того, в 𝑘-значной логике при 𝑘 > 3 найдутся замкнутые классы без базиса и замкнутые классы со счетным базисом. В силу континуальности решетки всех
замкнутых классов при 𝑘 > 3 изучаются ее подрешетки. В частности, рассматривается замкнутый класс всех функций 𝑘-значной логики, представимых полиномами
по модулю 𝑘. Этот замкнутый класс содержит все функции 𝑘-значной логики, если
и только если 𝑘 является простым числом. Если 𝑘 является составным числом, то
этот замкнутый класс не является даже предполным. В работах А. Н. Черепова,
А. Б. Ремизова, А. А. Крохина, К. Л. Сафина, Е. В. Суханова, Д. Г. Мещанинова
и др. изучалось строение надрешеток и подрешеток замкнутого класса всех полиномиальных функций при составных 𝑘. В настоящем исследовании при каждом
составном числе 𝑘 устанавливается континуальность подрешетки замкнутого класса
всех полиномиальных функций 𝑘-значной логики.
Об авторах
Селезнева Светлана
Николаевна, д-р физ.-мат. наук,
проф., Московский государственный
университет им. М. В. Ломоносова,
Москва, 119991, Российская
Федерация, selezn@cs.msu.ru
Ссылка для цитирования
Селезнева С. Н. Мощность решетки замкнутых классов полиномов в 𝑘-значной логике при составных 𝑘 // Известия Иркутского государственного университета. Серия Математика. 2026. Т. 55. C. 123–133.
https://doi.org/10.26516/1997-7670.2026.55.123
Ключевые слова
функция 𝑘-значной логики, кольцо вычетов по модулю 𝑘, полином, замкнутый класс, решетка замкнутых классов
УДК
519.716.5, 512.56, 512.714
MSC
06D25, 08A40, 13M10
DOI
https://doi.org/10.26516/1997-7670.2026.55.123
Литература
- Айзенберг Н. Н., Семйон И. В. Некоторые критерии представимости функций 𝑘-значной логики полиномами по модулю 𝑘 // Многоустойчивые элементы и их применение. М. : Сов. радио, 1971. С. 84–88.
- Айзенберг Н. Н., Семйон И. В., Циткин А. И. Мощность класса функций 𝑘-значной логики от 𝑛 переменных, представимых полиномами по модулю 𝑘 // Многоустойчивые элементы и их применение. М. : Сов. радио, 1971. С. 79–83.
- Крохин А. А., Сафин К. Л., Суханов Е. В. О строении решетки замкнутых классов полиномов // Дискретная математика. 1997. Т. 9, вып. 2. С. 24–39. https://doi.org/10.4213/dm469
- Марченков С. С. Функциональные системы с операцией суперпозиции. М. : Физматлит, 2004. 104 с.
- Мещанинов Д. Г. Замкнутыe классы полиномов по модулю 𝑝2 // Дискретная математика. 2017. Т. 29, вып. 3. С. 54–69. https://doi.org/10.4213/dm1452
- Мещанинов Д. Г. Метод построения полиномов для функций 𝑘-значной логики // Дискретная математика. 1995. Т. 7, вып. 3. С. 48–60.
- Ремизов А. Б. О надструктуре замкнутого класса полиномов по модулю 𝑘 // Дискретная математика. 1989. Т. 1, вып. 1. С. 3–15.
- Селезнева С. Н. О числе полиномиальных функций 𝑘-значной логики по составному модулю 𝑘 // Дискретная математика. 2016. Т. 28, вып. 2. С. 81–91. https://doi.org/10.4213/dm1371
- Черепов А. Н. Описание структуры замкнутых классов в 𝑃𝑘, содержащих класс полиномов // Проблемы кибернетики. Вып. 40. М. : Наука, 1983. С. 5–18.
- Яблонский С. В. Функциональные построения в 𝑘-значной логике // Труды Математического института им. В.А. Стеклова АН СССР. 1958. Т. 51. С. 5–142.
- Янов Ю. И., Мучник А. А. О существовании 𝑘-значных замкнутых классов, не имеющих конечного базиса // Доклады Академии наук СССР. 1959. Т. 127, вып. 1. С. 44–46.
- Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. Vol. 43, N 4. P. 163–185.