«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2013. Vol. 3

Criteria of decomposability of the Post’s clones

Author(s)
Y. V. Akulov
Abstract

Problem of realization of Boolean functions using the formulas of special kind is considered in this paper. Notion of completion of the systems of Boolean functions is introduced. Criteria of decomposability of the completions to the intersection of simpler completions is obtained.

Keywords
paper, contains
UDC
519.95
References

1. Акулов Я.В. О полноте систем функций для классов расширенной суперпозиции / Я. В. Акулов // Вестн. МГУ. Математика. Механика. – 2011. – №1. – С. 36–41.

2. Голунков Ю.В. Полнота систем функций в операторных алгоритмах, реализующих функции k-значной логики / Ю. В. Голунков // Вероятност. методы и кибернетика. – 1980. – Вып. 17. – С. 23–34.

3. Касим-Заде О. М. О метрических свойствах обобщенных инвариантных классов / О. М. Касим-Заде // Математические вопросы кибернетики. – М. : Наука. – 2006. – Вып. 15. – С. 9–34.

4. КузнецовЮ.В. О классах булевых функций, инвариантных относительно отождествления переменных / Ю. В. Кузнецов // Докл. АН СССР. – 1986. – Т. 290, № 4. – С. 780–785.

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

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

7. Марченков С.С. Замкнутые классы булевых функций / С.С. Марченков, А. Б. Угольников. – М. : Изд-во ИПМ АН СССР, 1990.

8. Марченков С.С. Замкнутые классы булевых функций / С.С. Марченков. – М. : Физматлит, 2000.

9. Нгуен Ван Хоа О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами / Нгуен Ван Хоа // Дискрет. математика. – 1993. – Т. 5, №4. – С. 87–108.

10. Соловьев В.Д. Замкнутые классы в k-значной логике с операцией разветвления по предикатам / В. Д. Соловьев // Дискрет. математика. – 1990. – Т. 2, №4. – С. 18–25.

11. Тайманов В. А. О функциональных системах k-значной логики с операциями программного типа / В. А. Тайманов // Докл. АН СССР. – 1983. – T. 268, №6. – С. 1307–1310.

12. Тарасова О. С. Классы k-значной логики, замкнутые относительно расширенной операции суперпозиции / О. С. Тарасова // Вестн. МГУ. Математика. Механика. – 2001. – №6. – С. 54–57.

13. Тарасова О.С. Классы функций трехзначной логики, замкнутые относительно операций суперпозиции и перестановок / О. С. Тарасова // Математические вопросы кибернетики. – М.: Физматлит, 2004. – Вып. 13. – С. 59–112.

14. Угольников А. Б. О замкнутых классах Поста / А. Б. Угольников // Изв. вузов. Математика. – 1988. – №7 (314). — С. 79–88.

15. Угольников А. Б. Классы Поста / А. Б. Угольников. – М. : Изд-во ЦПИ при мех.-мат. фак. МГУ им. М. В. Ломоносова, 2008.

16. Яблонский С.В. Введение в дискретную математику / С. В. Яблонский. – М. : Высш. шк., 2006.

17. Яблонский С.В. О классах функций алгебры логики, допускающих простую схемную реализацию / С. В. Яблонский // Успехи мат. наук. – 1957. – Т. 12, №6 (78) – С. 189–196.

18. Яблонский С.В. Об алгоритмических трудностях синтеза минимальных контактных схем / С. В. Яблонский // Проблемы кибернетики. – 1959. – Вып. 2 – С. 75–121.

19. Яблонский С.В. Функции алгебры логики и классы Поста / С. В. Яблонский, Г. П. Гаврилов, В. Б. Кудрявцев. – М. : Наука, 1966.

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

21. Post E. L. Two-valued iterative systems of mathematical logic / E. L. Post // Annals of Math. Studies. – Princeton-London : Princeton Univ. Press, 1941. – Vol. 5.


Full text (russian)