Решение задач 35 и 36: Предикаты и квантор существования

Задание 35. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Пусть \(P(x)\) - некоторый предикат, принимающий значение истина или ложь для каждого элемента \(x\) множества \(M\). Под выражением \(\exists x P(x)\) будем подразумевать высказывание, истинное противном случае

1. когда будем подразумевать высказывание
2. когда существует элемент множества \(M\), для которого \(P(x)\) истинно, ложно в противном случае
3. когда существует элемент множества \(M\), для которого \(P(x)\) ложно, истинно в противном случае
4. когда \(P(x)\) - истинно, для любого \(x\) из множества \(M\), ложно в противном случае

Ответ: 2) когда существует элемент множества \(M\), для которого \(P(x)\) истинно, ложно в противном случае

Задание 36. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Тезис Черча

1. Множество всех рекурсивных функций совпадает с множеством всех алгоритмических функций
2. Множество всех рекурсивных функций совпадает с множеством всех вычислимых функций
3. Для всякой вычислимой функции может быть построена машина Тьюринга
4. Всякая машина Тьюринга вычисляет рекурсивную функцию
5. Для всякой рекурсивной функции может быть построена машина Тьюринга

Ответ: 1) Множество всех рекурсивных функций совпадает с множеством всех алгоритмических функций

Задание 37. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Тезис Тьюринга

1. Множество всех рекурсивных функций совпадает с множеством всех алгоритмических функций
2. Множество всех рекурсивных функций совпадает с множеством всех вычислимых функций
3. Всякий алгоритм может быть реализован соответствующей машиной Тьюринга
4. Всякая машина Тьюринга вычисляет рекурсивную функцию
5. Для всякой рекурсивной функции может быть построена машина Тьюринга

Ответ: 3) Всякий алгоритм может быть реализован соответствующей машиной Тьюринга

Задание 38. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Свойство алгоритма записываться в виде только тех команд, которые находятся в Системе Команд Исполнителя, называется:

1. понятность;
2. определенность;
3. дискретность;
4. результативность.

Ответ: 1) понятность

Задание 39. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Свойство алгоритма записываться только директивами однозначно и одинаково интерпретируемыми разными исполнителями:

1. дискретность;
2. понятность;
3. определенность;
4. результативность.

Ответ: 3) определенность

Задание 40. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Свойство алгоритма, что при точном исполнении всех предписаний ответом на поставленную прекратиться за конечное число шагов с определенным ответом на поставленную задачу:

1. понятность;
2. детерминированность;
3. дискретность;
4. результативность.

Ответ: 4) результативность

Задание 41. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. В машине Тьюринга предписание \(L\) для лентопротяжного механизма означает:

1. переместить ленту вправо;
2. переместить ленту влево;
3. остановить машину;
4. занести в ячейку символ.

Ответ: 2) переместить ленту влево

Задание 42. Решите задачу. Определить степень вершины V3:

Для решения этой задачи необходимо изображение графа, в котором находится вершина V3. Поскольку изображение графа не предоставлено, я не могу определить степень вершины V3. Пожалуйста, предоставьте изображение графа.