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

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

Номер 1

Арифметические формулы определяются сигнатурой S, носителем N вида:

Ответ:

(1) S=‹+,x,=›, N=‹1,2,3,…›

(2) S=‹+,-x›, N=‹1,2,3,…›

(3) S=‹+,-,=›, N=‹1,2,3,…›

Номер 2

Арифметическое множество - это множество:

Ответ:

(1) арифметических знаков

(2) арифметических формул

(3) натуральных чисел и арифметических знаков

Номер 3

Множество натуральных чисел, не являющееся арифметическим:

Ответ:

(1) не существует

(2) существует

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

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

Номер 1

Предикат определяемый формулой :

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Номер 2

Предикат определяемый формулой x=const:

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от const

Номер 3

Предикат определяемый формулой :

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

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

Номер 1

Предикат определяемый формулой :

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Номер 2

Предикат :

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Номер 3

Предикат z=НОД(x,y), :

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

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

Номер 1

Предикат "двоичное слово x состоит только из нулей":

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от числа нулей

Номер 2

Предикат "двоичные слова x и y имеют одинаковую длину":

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений длины

Номер 3

Предикат "z=x+y", где "+" - конкатенация двоичных слов:

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

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

Номер 1

Предикат "двоичное слово x - начало двоичного слова y":

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Номер 2

Предикат "двоичное слово x - конец двоичного слова y":

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Номер 3

Предикат "двоичное слово x входит в двоичного слова y":

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

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

Номер 1

Предикат "x - простое число номер n":

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,n

Номер 2

Предикат "x=2_n", n - натуральное:

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений n

Номер 3

Предикат "x=4_n", n - натуральное:

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений n

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

Номер 1

Предикат "x>y", x,y - целое:

Ответ:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Номер 2

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

Ответ:

(1) автономны

(2) совпадают

(3) устойчивы

Номер 3

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

Ответ:

(1)

(2)

(3)

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

Номер 1

Предикат, выразимый в данной интерпретации:

Ответ:

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

(2) совпадает с любым ее автоморфизмом

(3) истинен для любых автоморфизмов

Номер 2

Класс выразимых предикатов:

Ответ:

(1) бескванторные формулы

(2) кванторные формулы

(3) устойчивые формулы

Номер 3

Всякая формула в , где +1 - функция прибавления 1:

Ответ:

(1) эквивалентна некоторой бескванторной формуле

(2) эквивалентна некоторой кванторной формуле

(3) не эквивалентна никакой бескванторной формуле

Языки и исчисления - тест 6