Том 20, номер 2, 2013 г., Стр. 88-101

УДК 519.71
Марченков С. С.
О максимальных и минимальных элементах частично упорядоченных множеств булевых степеней

Аннотация:
Рассмотрен «самый слабый» вариант алгоритмической сводимости – булева сводимость. Исследованы частично упорядоченные множества $\mathcal L_Q$ булевых степеней, отвечающие различным замкнутым классам $Q$ булевых функций. Доказано, что $\mathcal L_Q$ не имеют максимальных элементов для многих замкнутых классов $Q$. Приведены примеры достаточно крупных классов $Q$, для которых $\mathcal L_Q$ содержат континуальное число максимальных элементов. Установлено, что для замкнутых классов $T_{01}$ и $S$M соответствующие множества степеней имеют континуальное число минимальных элементов.
Библиогр. 8.

Ключевые слова: булева сводимость, замкнутый класс булевых функций.

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

Статья поступила 29 мая 2012 г.

Литература

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

[2] Марченков С. С. Булева сводимость // Дискрет. математика. - 2003. - Т. 15, № 3. - С. 40–53.

[3] Марченков С. С. Конечная порождаемость замкнутых классов булевых функций // Дискрет. анализ и исслед. операций. Сер. 1. - 2005. - Т. 12, № 1. - С. 101–118.

[4] Марченков С. С. О строении частично упорядоченных множеств булевых степеней // Дискрет. математика. - 2006. - Т. 18, № 1. - С. 63–75.

[5] Марченков С. С. Полные и неполные булевы степени // Пробл. передачи информ. - 2010. - Т. 46, № 4. - С. 83–90.

[6] Марченков С. С., Матвеев С. А. Булевы степени, определяемые классами линейных функций и конъюнкций // Мат. вопросы кибернетики. Вып. 14. - М.: Физматлит, 2005. - С. 35–48.

[7] Рейна Г. Степени автоматных преобразований // Кибернет. сб. Вып. 14. - М.: Мир, 1977. - С. 95–106.

[8] Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972. - 624 с.