«Математика» 2013 3

Критерий универсальной разложимости замкнутых классов булевых функций

Авторы: Я. В. Акулов
Аннотация:

В работе рассматривается задача о реализации булевых функций формулами специального вида. Вводится понятие пополнения систем булевых функций. Получен критерий разложимости пополнений в пересечение более простых пополнений.
Ключевые слова: булева функция; формула; суперпозиция
УДК: 519.95
Литература: 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.