Том 9, серия 1, номер 4 , 2002 г., Стр. 57-74

УДК 519.714
Д. Ю. Черухин
Об инвариантных классах функций, бесповторно выразимых формулами

Аннотация:
Показано, что мощность множества инвариантных классов функций 2-значной логики, бесповторно выразимых формулами в фиксированном полном конечном базисе, счетна; доказана возможность описания этих классов с помощью запрещённых подфункций и контекстно-свободных грамматик. Для каждого $k>2$ приведён пример конечного базиса в $k$-значной логике, для которого мощность множества таких классов равна континууму.
Библиогр. 3.

Черухин Д. Ю. ¹
1. MГУ, мех.-мат. факультет,
Воробьевы горы, 119992 Москва, Россия

Статья поступила 6 мая 2002 г.