Онлайн-тест по дисциплине: Математическая логика и теория алгоритмов.

Вопрос No1
На множестве натуральных чисел задан предикат P(x,y)="x+4=y". Определить область истинности предиката ∃xP(x,y):
пустое множество
все натуральные числа
целые числа, большие или равные 4
все целые числа
целые числа, большие 4

Вопрос No2
На множестве вещественных чисел задан предикат P(x,y)="x+4=y". Определить область истинности предиката ∃xP(x,y):
пустое множество
все целые числа
числа, большие или равные 4
все вещественные числа

Вопрос No3
Верно ли, что ∀x∃yP(x,y)≡∃y∀xP(x,y):
нельзя определить
верно
зависит от определения предиката P
не верно

Вопрос No4
Какие переменные в формуле являются свободными :
x
y, z
x, z, p
z
нет свободных переменных




Вопрос No5
Дана машина Тьюринга с алфавитом и программой Определить, через сколько шагов машина Тьюринга перейдет в заключительное состояние, если начальная конфигурация была
5
3
2
никогда не перейдет

Вопрос No6
Укажите формулы, которые не в предваренной форме:




нет ни одной формулы в предваренной форме

Вопрос No7
Какие из формул представлены в предваренной форме :




нет ни одной формулы в предваренной форме

Вопрос No8
Выяснить, является ли следующая формула тождественно истинной или тождественно ложной: (x&y → z) → (x → (y → z)):
является тождественно истинной
является тождественно ложной
невозможно определить


Вопрос No9
Если в логическом исчислении найдется такая выводимая формула А, что формула А также выводима, то логическое исчисление называется:
противоречивым
непротиворечивым
невыполнимым

Вопрос No10
Какие из выражений являются формулами исчисления предикатов:
1. P(x)
2.∀xQ(x)
3. ∃x∀xR(x,y)
1 и 2
2 и 3
все
нет формул ИП

Вопрос No11
Если алгоритмическое преобразование начальных данных происходит по шагам и на каждом шаге алгоритма из данных, имевшихся на предыдущем шаге, по предписанным правилам получается новая совокупность величин, можно говорить о:
дискретности алгоритма
непрерывности алгоритма
выполнимости алгоритма

Вопрос No12
Дана машина Тьюринга с алфавитом и программой Определить сколько единиц будет на ленте машины Тьюринга через 2 шага после начала работы, если начальная конфигурация была
4
3
2
1
Вопрос No13
Функция F(x,y) получена операцией суперпозиции функций f(x,y,z) и g1(x,y), g2(x,y), g3(x,y). f(x,y,z)=(x+y)z, g1(x,y)=x, g2(x,y)=y-x, g3(x,y)=x+y. Определите значение F(2,3):
10
15
9
6
значение функции неопределено

Вопрос No14
Функция F(x,y) получена операцией суперпозиции функций f(x,y,z) и g1(x,y), g2(x,y), g3(x,y). f(x,y,z)=(x+y)z, g1(x,y)=x, g2(x,y)=x-y, g3(x,y)=x+y. Определите значение F(5,3):
15
56
9
32
значение функции неопределено

Вопрос No15
Дана машина Тьюринга с алфавитом и программой Определить сколько единиц будет на ленте машины Тьюринга через 2 шага после начала работы, если начальная конфигурация была
4
3
2
1

Вопрос No16
Что из указанного НЕ является свойством алгоритма:
направленность
дискретность
детерминированность
вычислимость

Вопрос No17
Если имеется критерий, позволяющий определить, что является результатом работы алгоритма, значит алгоритм:
предсказуемый
элементарный
направленный
дискретный

Вопрос No18
Укажите неверные соотношения с кванторами:
∀x∀yQ(x,y)≡∀y∀xQ(x,y)
∀x∃yQ(x,y)≡∀y∃xQ(x,y)
∀xP(x)≡∃xP(x)

Вопрос No19
Чтобы узнать, выводима ли некоторая формула в исчислении высказываний, достаточно выяснить, является ли формула:
тождественно ложной
тождественно истинной
выводимой

Вопрос No20
На множестве целых чисел задан предикат P(x,y)="x+4=y". Определить область истинности предиката ∃xP(x,y):
пустое множество
все натуральные числа
целые числа, большие или равные 4
все целые числа
целые числа, большие 4