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

Миссия математической логики. Краткая история логики
1. Преднамеренное нарушение логических правил - это
логическая ошибка
парадокс
софизм

Языки первого порядка
2. Универсум - множество вещественных чисел.
Предикат
x>y - число x больше числа y.
Выберите правильный перевод на язык логики предикатов
"Никакое из чисел a, b не является положительным"

Основы теории множеств
3. Теорема.
Множество натуральных чисел ... множеству всех его подмножеств.
не равномощно
равномощно
равно

Пропозициональная логика
4. Раймонд Смаллиан встретил на острове рыцарей и лжецов человека, который произнес:
"Я рыцарь или 2*2=4"
Кто этот человек?
Лжец
Он не может быть ни рыцарем, ни лжецом
Рыцарь
Он или рыцарь, или лжец. Точно сказать нельзя.

Аксиоматический метод
5. Дедуктивная система какого либо языка выделает среди всех формул те, которые объявляются {выполнимыми, доказуемыми, истинными}. Обычно доказуемость задается индуктивно при помощи {интерпретации, аксиом, теорем} и правил вывода.

Указания: Из предложенного в фигурных скобках выделите все необходимое для истинности утверждений.

Основы теорий множеств
6. Пусть Z - множество целых чисел и отображение f(n)=5 отображает Z и Z.
Какие утверждения об образах и прообразах множеств верны?

Алгоритмы и вычислимые функции. Сложность вычислений
7. Какие задачи имеют полиномальную сложность?
Сортировка n чисел.
Умножение целых чисел.
Построение множества всех подмножеств данного множества.
Соединение всех городов плоской страны телефонной связью так, чтобы общая длина телефонных линий была минимальной.
Решение систем уравнений с целыми переменными.
Определение, является ли данная формула логики высказываний тавтологией.
Вычисление (22)k для заданного натурального k.

Языки первого порядка
8. Универсум - множество животных.
Предикаты:
A(x)=истина тогда и только тогда, когда животное x - орел.
B(x)=истина тогда и только тогда, когда животное x - умеет летать.
Выберите правильный перевод на язык логики предикатов
"Всякий орел умеет летать"

Математическое доказательство
9. Какие утверждения верны?
Точную математическую модель сложного явления - доказательства - можно построить с помощью аксиоматического метода.
Математическое доказательство изначально было психологическим процессом убеждения собеседника в верности того или иного утверждения.
Аксиоматический метод убавляет математику от смысла: от разных геометрических представлений, от интуиции, поэтому от вреден.

Языки первого порядка
10. Задан некоторых язык первого порядка с константами a и b одноместными предикатными символами P и Q. Пусть задана интерпретация, носитель которой состоит из двух элементов {a,b}. Интерпретации предикатов: P(a)=1, P(b)=1, Q(a)=1, Q(B)=0.
Найдите истинностные значения формул в данной интерпретации (0 - ложь, 1 - истина)

Указания: Из предложенного в фигурных скобках выделите всё необходимое для истинности выражений.

Пропозициональная логика
11. Пусть - логическая связка такая, что утверждение A B ложно в том и только в том случае, когда A истинно, а B ложно, и истинно в остальных случаях. Такая связка называется...
эквиваленция
дизъюнкция
импликация
конъюнкция

Миссия математической логики. Краткая история логики
12. Амброс Бирс приводит пример силлогизма:
Большая посылка: Шестьдесят людей способны сделать определенную работу в шестьдесят раз быстрее, чем один человек.
Меньшая посылка: Один человек может выкопать яму под столб за 60 секунд.
Вывод: Шестьдесят людей могут выкопать яму под столб за 1 секунду.
Малая посылка неверна.
Это рассуждение логически правильное.
Вывод неверный.
Большая посылка неверна.

Основы теории множеств
13. Теорема:
Любое множество X ... множеству P(X) всех своих подмножеств.
равномощно
равно
не равномощно

Математическое доказательство
14. Дана гипотеза. Что доказывает контрпример?
Ложность гипотезы
Истинность гипотезы
Истинность отрицания гипотезы

Основы теории множеств
15. Какая из следующих трех функций является сюръективной?

Основы теории множеств
16. Пусть Z - множество целых чисел и отображение f(n)=n2 отображает Z в Z.
Какие утверждения об образах и прообразах множеств верны?

Аксиоматический метод
17. Какие формулы являются теоремами (или аксиомами) исчисления предикатов?

Алгоритмы и вычислимые функции. Сложность вычислений
18. Какие утверждения верны?
Тьюринг предложил определение своих машин ещё до создания первых вычислительных машин.
Машины Тьюринга - абстрактные вычислительные машины - рассматриваются для формального определения вычислимых функций.
В определении машины Тьюринга заложены ограничения на количество материала для запоминающего устройства и длину вычислений.

Основы теории множеств
19. Найдите область определения (ОО) отношений
{}
{}

Указание: В поля для ввода латинские буквы записывайте через запятую по алфавиту, а числа по возрастанию
Пример ввода ответов:
a,b,c
1,2,3

Языки первого порядка
20. На острове, где живут рыцари, и лжецы, Раймонд Смаллиан встретил человека, который произнес высказывание:
"Я лжец или на острове все лжецы"
Кто этот человек?
Рыцарь
Он или рыцарь, или лжец. Точно сказать нельзя.
Он не может быть ни рыцарем, ни лжецом
Лжец

Оценка: Удовлетворительно
14 из 20

Помогу с вашим вариантом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com