Контрольная работа по предмету Логика на тему: Контрольная по математической логике и теории алгоритмов. Вариант 9

I. Логика и исчисление высказываний
Задание 1.3
Записать высказывания в виде формул логики высказываний.
1.3. Если х=5 и у=3, то х>y.
Задание 2.1
Построить таблицы истинности для формул.

Задание 2.2
Построить таблицы истинности для формул.

Задание 3.1
Доказать, что формулы являются тавтологиями

Задание 4.9
Доказать полноту (неполноту) систем булевых функций
{&, ⋁,→}
Задание 5.9
Получить СДНФ для формул, а затем перейти к СКНФ

Задание 6.9
Получить СКНФ, а затем перейти к СДНФ

Задание 7.1
Получить МДНФ для формул

II. Логика и исчисление предикатов. Автоматическое доказательство теорем.
Задание 1.9
Записать на языке предикатов: нечто обладает свойством В.
Задание 2.7
Получить множество дизъюнктов.
x P(x) y R(y)
Задание 3.4
Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
А1: Если робот обработал деталь, то ее забирает штабелер.
А2: Если деталь поступила на обработку, то ее обработает робот.
А3: Если человеку нужна деталь, то она поступит на обработку.
А4: Человеку нужна втулка.
Вопрос: Что заберет штабелер?
Задание 4.2
Для заданной системы аксиом доказать теорему.
А1:
Т:
III. Теория алгоритмов
Задание 1.9
Какую функцию вычисляет машина Тьюринга с программой, представленной таблицей, приведенной ниже, если на ленте записано подряд x + 1 единиц, а слева и справа от них – символы e. Маркер находится против левой единицы. Таблица имеет вид: q1 q2 q3 q4 q5 q6 e λ q1 S λ q3 S 1 q3 S 1 q3 S 1 q3 S 1 λ q2 R λ q6 R 1 q5 S 1 q4 R 1 q3 S Покажите по шагам, как вычисляется результат выполнения приведенной выше программы машины для числа 15, записав число в предложенной системе.
Задание 2.1
Доказать, что функции примитивно-рекурсивны.
f(x)=x+n
Задание 3.3
Построить нормальный алгоритм Маркова, который преобразует любое слово в алфавите {x,y,z} в слово zzx