Языки и исчисления

<<- Назад к вопросам

Биекция $f:X \to X$ - автоморфизм интерпретации, если все функции и предикаты интерпретации:

(Отметьте один правильный вариант ответа.)

Варианты ответа

автономны

устойчивы(Верный ответ)

совпадают

Похожие вопросы

Естественные интерпретации сигнатуры $S = \left\langle { = , < , + ,0,1} \right\rangle$ на носителе R:

n - местный предикат P - устойчив относительно автоморфизма $f:X \to X$ , если:

Контрпример к секвенции $A \mapsto B$ будет контрпримером к формуле ( $\wedge A$ - конъюнкция, $\vee A$ - дизъюнкция формул из А)

Верно утверждение для любой булевой функции

от

аргументов:

Если

- минимальная глубина схемы, вычисляющая функцию

, то:

Теория Т - $\sum\nolimits_1 {}$ аксиоматизируема, если существуют $\sum\nolimits_1 {}$ -формулы, из которых:

Если существуют подстановки $A(y_1 /x_1 \ldots y{}_k/x_k ), \ldots ,A(w_1 /x_1 \ldots w_k /x_k )$ для которых общезначима дизъюнкция, то формула $\exists x_1 \ldots \exists x_k A$ (А - бескванторна):

Сложность большинства булевой

-местной функций при наибольшем размере

их схем:

Вычитание двух

-разрядных двоичных чисел по модулю 2^n

выполнима схема:

Сложность любой булевой

-местной функций при наибольшем размере

их схем:

Языки и исчисления

Биекция - автоморфизм интерпретации, если все функции и предикаты интерпретации:

Биекция $f:X \to X$ - автоморфизм интерпретации, если все функции и предикаты интерпретации: