«Математика» 2012 1

О сложности надструктуры классов монотонных k-значных функций специального вида

Авторы: В. Б. Ларионов, В. С. Федорова
Аннотация:

В статье доказано, что класс монотонных функций многозначной логики, сохраняющих частично упорядоченное множество с одним минимальным элементом и двумя максимальными или частично упорядоченное множество с одним максимальным элементом и двумя минимальными, либо является предпредполным, либо обладает бесконечной надструктурой, состоящей из не предикатно-описуемых классов.
Ключевые слова: многозначная логика; монотонная функция; надструктура; предикат; не предикатно-описуемый класс
УДК: 519.7
Литература: 1. Теория Галуа для алгебр Поста / В. Г. Боднарчук, В. А. Калужнин, В. Н. Котов, Б. А. Ромов // Кибернетика. – 1969. – № 3. – С. 1–10; № 5. – С. 1–9.
2. Ларионов В. Б. Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций : дис. . . . канд. физ.-мат. наук / В. Б. Ларионов. – М., 2009. – 157 с.
3. Ларионов В. Б. О монотонных замкнутых классах функций многозначной логики с бесконечной надструктурой / В. Б. Ларионов // Материалы VII молодежной научной школы по дискретной математике и ее приложениям, 18–23 мая 2009 г. – М. : ИПМ им. М. В. Келдыша РАН, 2009. – С. 7–12.
4. Ларионов В. Б. О положении некоторых классов монотонных k-значных функций в решетке замкнутых классов / В. Б. Ларионов // Дискрет. математика. – 2009. – Т. 21, № 5. – С. 111–116.
5. Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках / В. В. Мартынюк // Проблемы кибернетики, вып. 3. – М. : Наука, 1960. – С. 49–61.
6. Марченков С. С. Замкнутые классы булевых функций / С. С. Марченков. – М. : Физматлит, 2000. – 128 с.
7. Яблонский С. В. О строении верхней окрестности для предикатно-описуемых классов в Pk / С. В. Яблонский // Докл. АН СССР. – 1974. – Т. 218, № 2. – С. 304–307.
8. Яблонский С. В. Предполные классы в многозначных логиках / С. В. Яблонский, Г. П. Гаврилов, А. А. Набебин. – М. : Изд. дом МЭИ, 1997. – 144 с.
9. Янов Ю. И. О существовании k-значных замкнутых классов, не имеющих конечного базиса / Ю. И. Янов, А. А. Мучник // ДАН СССР. – 1959. – Т. 127, № 1. – С. 44–46.
10. Rosenberg I. G. La structure des fonctions de plusiers variables sur un ensemble fini / I. G. Rosenberg // Comptes Rendus Acad. Sci. Paris. – 1965. – Vol. 260. – P. 3817–3819.