Главная / Алгоритмы и дискретные структуры /
Языки и исчисления / Тест 13
Языки и исчисления - тест 13
Упражнение 1:
Номер 1
Множество истинных бескванторных формул сигнатуры с равенством и константами для всех элементов интерпретации - это:
Ответ:
 (1) диаграмма 
 (2) область определения 
 (3) интерпретация 
Номер 2
Истинность бескванторных формул из D(A)
от присутствия дополнительных элементов:
Ответ:
 (1) зависит 
 (2) не зависит 
 (3) изменяет А
 
Номер 3
Любую модель теории D(A)
можно считать расширением интерпретации А
, если:
Ответ:
 
(1) отождествить
a
из
А
со значением константы из
 
 (2) расширить А
до В
 
 (3) интерпретировать В
как и А
 
Упражнение 2:
Номер 1
Нормальная интерпретация А
сигнатуры S
с равенством может быть расширена до нормальной модели теории Т
, если:
Ответ:
 (1) все П1
-формулы S
, выводимые из Т
, истинны в А
 
 (2) хоть одна П1
-формула S
, выводимая из Т
, истинна в А
 
 (3) все П1
-формулы S
, выводимые из Т
, ложны в А
 
Номер 2
Если все П1
-формулы сигнатуры S
с равенством, выводимые из теории Т
, истинны в А
, то:
Ответ:
 (1) нормальная интерпретация А
расширяема до нормальной теории Т
 
 (2) А
не расширяема до Т
 
 (3) А
и Т
совпадают 
Номер 3
Всякая коммутативная полугруппа с сокращением:
Ответ:
 (1) может быть вложена в коммутативную группу 
 (2) не может быть вложена в коммутативную группу 
 (3) пуста 
Упражнение 3:
Номер 1
Кольцо может быть в поле, если:
Ответ:
 (1) нет делителей (никаких) 
 (2) нет делителей нуля 
 (3) есть простые делители 
Номер 2
Если T1, T2
- теории сигнатуры с равенством, то:
Ответ:
 (1) существует нормальная модель T1
и ее расширение - нормальная модель T2
 
 (2) не существует нормальная модель T1
и ее расширение - нормальная модель T2
 
 
(3)  
Номер 3
Если T1, T2
- теории сигнатуры с равенством, то:
Ответ:
 (1) пресечение T1
со всеми П1
-теоремами T2
совместно 
 (2) объединение T1
со всеми П1
-теоремами T2
совместно 
 (3) дополнение T1
до T2
совместно 
Упражнение 4:
Номер 1
Если T1, T2
- теории сигнатуры с равенством, то:
Ответ:
 
(1) объединение
T2
со всеми
- теоремами
T1
совместно 
 
(2) объединение
T2
со всеми
- теоремами
T1
не совместно 
 (3) дополнение T2
до T1
совместно 
Номер 2
- теорема А
теории T1
и отрицающая ее П1
-теорема А
теории T2
:
Ответ:
 (1) существует 
 (2) не существует 
 (3) совпадают 
Номер 3
Теория Т
- П1
аксиоматизируема, если существуют П1
-формулы,из которых:
Ответ:
 (1) выводятся все теоремы Т
и другие 
 (2) не выводятся все теоремы Т
 
 (3) выводятся все теоремы Т
и только они 
Упражнение 5:
Номер 1
Чтобы задать подструктуру нормальной интерпретации В
, нужно взять подмножество носителя В
:
Ответ:
 (1) замкнутое относительно сигнатурных операций 
 (2) не замкнутое относительно сигнатурных операций 
 (3) разрешимое 
Номер 2
Теория П1
аксиоматизируема, если она:
Ответ:
 (1) устойчива относительно перехода к подструктурам 
 (2) позволяет переходить к подструктурам 
 (3) если она полна 
Номер 3
Если теория устойчива относительно перехода к подструктурам, то она:
Ответ:
 (1) П1
аксиоматизируема 
 (2) не аксиоматизируема 
 (3) не моделируема 
Упражнение 6:
Номер 1
Если теория П1
аксиоматизируема, то подструктура ее нормальной модели является:
Ответ:
 (1) ее моделью 
 (2) ее сигнатурой 
 (3) полной 
Номер 2
Если любая подструктура любой нормальной модели является ее моделью, то теория:
Ответ:
 (1) П1
аксиоматизируема 
 (2) П1
не аксиоматизируема 
 (3) противоречива 
Номер 3
Теория Т
- аксиоматизируема, если существуют -формулы, из которых:
Ответ:
 (1) выводятся все теоремы Т
и другие 
 (2) не выводятся все теоремы Т
 
 (3) выводятся все теоремы Т
и только они 
Упражнение 7:
Номер 1
Теория аксиоматизируема, если она:
Ответ:
 (1) устойчива относительно перехода к подструктурам 
 (2) позволяет переходить к подструктурам 
 (3) если она полна 
Номер 2
Если теория устойчива относительно перехода к подструктурам, то она:
Ответ:
 
(1) аксиоматизируема 
 (2) не аксиоматизируема 
 (3) не моделируема 
Номер 3
Если теория аксиоматизируема, то подструктура ее нормальной модели является:
Ответ:
 (1) ее моделью 
 (2) ее сигнатурой 
 (3) полной 
Упражнение 8:
Номер 1
Если любая подструктура любой нормальной модели является ее моделью, то теория:
Ответ:
 
(1) аксиоматизируема 
 (2) П1
не аксиоматизируема 
 (3) противоречива 
Номер 2
Любая теория, имеющая П2
-аксиоматизацию:
Ответ:
 (1) устойчива относительно объединения 
 (2) не устойчива относительно объединения 
 (3) не полна 
Номер 3
Любая теория, устойчивая относительно объединения:
Ответ:
 (1) имеет П2
аксиоматизацию 
 (2) не имеет П2
аксиоматизацию 
 (3) не полна