Том 21, номер 1, 2014 г., Стр. 67–83

УДК 519.716
С. С. Марченков
Позитивно замкнутые классы трёхзначной логики

Аннотация:
Сформулированы теоретические предпосылки и указаны пути построения позитивной классификации множества функций k-значной логики. На этой основе найдены все 194 позитивно замкнутых класса трёхзначной логики. Описание дано как с помощью полугрупп эндоморфизмов, так и посредством указания позитивных базисов. 
Табл. 13, библиогр. 30.

Ключевые слова: оператор позитивного замыкания, функции трёхзначной логики.

Марченков Сергей Серафимович ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 119991 Москва, Россия
е-mail: ssmarchen@yandex.ru

Статья поступила 25 марта 2013 г.

Литература

[1] Боднарчук В. Г., Калужнин Л. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста // Кибернетика. - 1969. - №3. - С. 1–10; - №5. - С. 1–9.

[2] Данильченко А. Ф. О параметрической выразимости функций трёхзначной логики // Алгебра и логика. - 1977. - Т. 16, №4. - С. 397–416.

[3] Данильченко А. Ф. Параметрически замкнутые классы функций трёхзначной логики // Изв. АН МССР. - 1978. - Т. 2. - С. 13–20.

[4] Кузнецов А. В. О средствах для обнаружения невыводимости и невыразимости // Логический вывод. - М.: Наука, 1979. - С. 5–33.

[5] Марченков С. С. Основные отношения S-классификации функций многозначной логики // Дискрет. математика. - 1996. - Т. 8, №1. - C. 99–128.

[6] Марченков С. С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискрет. математика. - 1999. - Т. 11, №4. - С. 110–126.

[7] Марченков С. С. Замкнутые классы булевых функций. - М.: Физматлит, 2000. - 126 с.

[8] Марченков С. С. S-классификация функций трёхзначной логики. - М.: Физматлит, 2001. - 79 с.

[9] Марченков С. С. Дискриминаторные классы трёхзначной логики // Мат. вопросы кибернетики. - 2003. - Вып. 12. - С. 15–26.

[10] Марченков С. С. Операторы замыкания с разветвлением по предикату // Вестн. МГУ. Сер. 1. Математика, механика. - 2003. - №6. - С. 37–39.

[11] Марченков С. С. Критерий позитивной полноты в трЁехзначной логике // Дискрет. анализ и исслед. операций. Сер. 1. - 2006. - Т. 13, №3. - С. 27–39.
Marchenkov S. S. A criterion for positive completeness in ternary logic // J. Appl. Industr. Math. - 2007. - Vol. 1, N 4. - P. 481–488.

[12] Марченков С. С. Дискриминаторные позитивно замкнутые классы трёхзначной логики // Дискрет. анализ и исслед. операций. Сер. 1. - 2007. - Т. 14, №3. - С. 53–6.
Marchenkov S. S. Discriminator positive complete classes in ternary logic // J. Appl. Industr. Math. - 2008. - Vol. 2, N 4. - P. 542–549.

[13] Марченков С. С. О замкнутых классах функций k-значной логики, определяемых одним эндоморфизмом // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, №6. - С. 52–67.

[14] Марченков С. С. Позитивно замкнутые классы трёхзначной логики, порождаемые одноместными функциями // Дискрет. математика. - 2009. - Т. 21, №3. - С. 37–44.

[15] Марченков С. С. Оператор замыкания в многозначной логике, базирующийся на функциональных уравнениях // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, №4. - С. 18–31.
Marchenkov S. S. The closure operator in a multivalued logic basen on functional equations // J. Appl. Industr. Math. - 2011. - Vol. 5, N 3. - P. 383–390.

[16] Марченков С. С. FE-классификация функций многозначной логики // Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика. - 2011. - №2. - С. 32–39.
Marchenkov S. S. FE classification of functions of many-valued logic // Moscow Univer. Comput. Math. Cybern. - 2011. - Vol. 35, N 2. - P. 89–96.

[17] Марченков С. С. О классификациях функций многозначной логики с помощью групп автоморфизмов // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №4. - С. 66–76.

[18] Марченков С. С. Атомы решётки позитивно замкнутых классов трёхзначной логики // Дискрет. математика. - 2012. - Т. 24, №2. - С. 79–81.

[19] Марченков С. С. Оператор позитивного замыкания // Докл. АН. - 2012. - Т. 442, №5. - С. 598–599.
Marchenkov S. S. Operator of positive closure // Dokl. Math. - 2012. - Vol. 85, N 1. - P. 102–103.

[20] Марченков С. С. Задание позитивно замкнутых классов посредством полугрупп эндоморфизмов // Дискрет. математика. - 2012. - Т. 24, №4. - С. 19–26.
Marchenkov S. S. Definition of positive closed classes by endomorphism semigroups // Discrete Math. Appl. - 2013. - Vol. 22, N 5–6. - P. 511–520.

[21] Нгуен Ван Хоа О структуре самодвойственных замкнутых классов трёхзначной логики // Дискрет. математика. - 1992. - Т. 4, №4. - С. 82–95.

[22] Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих базиса // Докл. АН СССР. - 1959. - Т. 127, №1. - С. 44–46.

[23] Barris S. Primitive positive clones which are endomorphism clones // Algebra Univers. - 1987. - Vol. 24. - P. 41–49.

[24] Barris S., Willard R. Finitely many primitive positive clones // Proc. Amer. Math. Soc. - 1987. - Vol. 101, N 3. - P. 427–430.

[25] Danil'čenko A. F. On parametrical expressibility of the functions of k-valued logic // Colloq. Math. Soc. J. Bolyai. - 1981. - Vol. 28. - P. 147–159.

[26] Geiger D. Closed systems of functions and predicates // Pacific J. Math. - 1968. - Vol. 27. - P. 95–100.

[27] Hermann M. On Boolean primitive positive clones // Discrete Math. - 2008. - Vol. 308. - P. 3151–3162.

[28] Snow J. W. Generating primitive positive clones // Algebra Univers. - 2000. - Vol. 44. - P. 169–186.

[29] Szabó L. Concrete representation of related strucrures of universal algebras. I // Acta Sci. Marh. - 1978. - Vol. 40. - P. 175–184.

[30] Szabó L. On the lattice of clones acting bicentrally // Acta Cybern. - 1984. - Vol. 6. - P. 381–388.