Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 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) принадлежат
 
 
(2) принадлежат
 
 
(3) не принадлежат
 
Упражнение 3:
Номер 1
Отрицания свойств из класса :
Ответ:
 
(1) принадлежат
 
 
(2) принадлежат
 
 
(3) не принадлежат
 
Номер 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) существует множество, универсальное для множеств
 
 
(2) не существует множество, универсальное для множеств
 
 
(3) есть класс
 
Номер 2
Свойства класса имеют вид:
Ответ:
 
(1) -разрешимое свойство 
 
(2) -разрешимое свойство 
 
(3) -разрешимое свойство 
Номер 3
Дополнение к универсальному множеству будет:
Ответ:
 
(1) универсальным для
 
 
(2) универсальным для
 
 (3) пустым 
Упражнение 8:
Номер 1
Универсальное множество:
Ответ:
 
(1) принадлежит
 
 
(2) не принадлежит
 
 (3) не существует для всех n
 
Номер 2
Универсальное множество:
Ответ:
 
(1) не принадлежит
 
 
(2) принадлежит
 
 (3) не существует для всех n
 
Номер 3
Класс эквивалентных множеств называют:
Ответ:
 (1) m
- разностью 
 (2) m
- степенью 
 (3) эквивалентностью