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

1. Контрольная работа «Математическая логика и теория алгоритмов»
1.1 Вариант №5
I. Логика и исчисление высказываний
1. Записать высказывания в виде формул логики высказываний.
1.5. Иванов сдал экзамен и получил 5 неравнозначно тому, что Иванов сдал экзамен и получил 5.
2. Построить таблицы истинности для формул

2. Доказать, что формулы являются тавтологиями
3.5.
4. Доказать полноту (неполноту) систем булевых функций
4.5. {⌐,}
4. Получить СДНФ для формул, а затем перейти к СКНФ:
5.5.
5. Получить СКНФ, а затем перейти к СДНФ
6.5.
7. Получить МДНФ для формул
7.5. .
II. Логика и исчисление предикатов. Автоматическое доказательство теорем
1. Записать на языке предикатов
1.5. для любого числа можно найти большее число;
2. Получить множество дизъюнктов.
2.1. xy, z, v(R(x, y, z, v)&L(y, z))
3. Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
3.5. A1: Некоторые пациенты любят своих докторов.
А2: Ни один пациент не любит знахаря.
Теорема: Никакой доктор не является знахарем.
4. Для заданной системы аксиом доказать теорему.
4.1. А1:
А2:
А3:
А4:
Т:
III. Теория алгоритмов
1. Построить машину Тьюринга (результат представить в форме таблицы):
1.5. Умножить на 2 целое положительное число x (вычислить функцию F(x) = 2×x)). Числа записываются в двоичной системе (используется алфавит A = {0, 1, λ }).
2. Доказать, что функции примитивно-рекурсивны:
2.5. f(x,y)=xy;
Покажите порядок вывода формулы и пример вычисления функции для 0 и 3, подставляя указанные значения в построенную формулу. При построении функций можно использовать полученные другие примитивно-рекурсивные функции, расширяя ими базовый набор.

3. Построить нормальный алгорифм Маркова, который:
3.5. Каков результат действия на слово P = nnnnnnnnnn нормального алгорифма со схемой Z = | nnn → abc | ca → ac | ba → nnnn | ?

нет