RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2002, том 9, выпуск 4, страницы 57–74 (Mi da186)

Об инвариантных классах функций, бесповторно выразимых формулами

Д. Ю. Черухин

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет

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

УДК: 519.714

Статья поступила: 06.05.2002



Реферативные базы данных:


© МИАН, 2024