Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 8

Основы теории вычислимых функций - тест 8

Упражнение 1:

Номер 1

Множество  перечислимо тогда и только тогда, когда:

Ответ:

(1)

- разрешимое

(2) X - проекция Y

(3) X совпадает с N

Номер 2

Свойство A(x),  перечислимо тогда и только тогда, когда:

Ответ:

(1)

-разрешимое

(2)

-разрешимое

(3)

-неразрешимо

Номер 3

Если B(x,y) - некоторое разрешимое свойство, то свойства вида  определяют свойства:

Ответ:

(1) отрицания которых перечислимы

(2) отрицания которых не перечислимы

(3) дополнения которых перечислимы

Упражнение 2:

Номер 1

Свойство A принадлежит классу , если для некоторого разрешимого свойства В:

Ответ:

(1)

(2)

(3)

Номер 2

Свойство A принадлежит классу , если для некоторого разрешимого свойства В:

Ответ:

(1)

(2)

(3)

Номер 3

Отрицания свойств из класса :

Ответ:

(1) принадлежат math

(2) принадлежат math

(3) не принадлежат math

Упражнение 3:

Номер 1

 Отрицания свойств из класса :

Ответ:

(1) принадлежат math

(2) принадлежат math

(3) не принадлежат math

Номер 2

Каждая операция проектирования:

Ответ:

(1) уменьшает размерность на 1

(2) увеличивает размерность на 1

(3) не изменяет размерность

Номер 3

Если , то:

Ответ:

(1)

(2)

(3)

Упражнение 4:

Номер 1

Если , то:

Ответ:

(1)

(2)

(3)

Номер 2

Если , то:

Ответ:

(1)

(2)

(3)

Номер 3

Если , то:

Ответ:

(1)

(2)

(3)

Упражнение 5:

Номер 1

Класс  является:

Ответ:

(1) наследственным вниз

(2) наследственным вверх

(3) наследственным и вниз, и вверх

Номер 2

Класс  является:

Ответ:

(1) наследственным вниз

(2) наследственным вверх

(3) наследственным и вниз, и вверх

Номер 3

Если , то:

Ответ:

(1)

(2)

(3) X и Y - совпадают

Упражнение 6:

Номер 1

Если , то:

Ответ:

(1)

(2)

(3) X и Y - совпадают

Номер 2

Если , то:

Ответ:

(1)

(2)

(3) X - пусто

Номер 3

Классы  и :

Ответ:

(1) совпадают при одинаковых n

(2) различаются при различных n

(3) совпадают для простых n

Упражнение 7:

Номер 1

Для любого n в классе :

Ответ:

(1) существует множество, универсальное для множеств math

(2) не существует множество, универсальное для множеств math

(3) есть класс math

Номер 2

Свойства класса  имеют вид:

Ответ:

(1)

-разрешимое свойство

(2)

-разрешимое свойство

(3)

-разрешимое свойство

Номер 3

Дополнение к универсальному множеству  будет:

Ответ:

(1) универсальным для math

(2) универсальным для math

(3) пустым

Упражнение 8:

Номер 1

Универсальное  множество:

Ответ:

(1) принадлежит math

(2) не принадлежит math

(3) не существует для всех n

Номер 2

Универсальное  множество:

Ответ:

(1) не принадлежит math

(2) принадлежит math

(3) не существует для всех n

Номер 3

Класс эквивалентных множеств называют:

Ответ:

(1) m - разностью

(2) m - степенью

(3) эквивалентностью

Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 8