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