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

Контрольная работа «Математическая логика и теория алгоритмов»
Логика и исчисление высказываний
Записать высказывания в виде формул логики высказываний.
1.1. Сегодня мы пойдем в кино или поедем кататься на лыжах.
Построить таблицы истинности для формул
2.5. (A"~" B)⊕C;
2.7. (A→B)→(B⊕C).
Доказать, что формулы являются тавтологиями
3.7. (A(B∨B ¯))"~" A
Доказать полноту (неполноту) систем булевых функций
4.7. {→,0}
Получить СДНФ для формул, а затем перейти к СКНФ:
5.7. ((x|y)↓z)"~" y
Получить СКНФ, а затем перейти к СДНФ
6.7. "xy"∨x ¯z
Получить МДНФ для формул
7.7. ((x→y)→z) ¯∨x
Логика и исчисление предикатов. Автоматическое доказательство теорем.
Записать на языке предикатов
1.7. каждый студент выполнил, по крайней мере, одну лабораторную работу.
Получить множество дизъюнктов.
2.9. ∀x¬∃y(P(x)→Q(y))
Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
3.2. А1: Если х есть часть у и у есть часть z, то х есть часть z.
А2: Палец есть часть руки.
А3: Кисть есть часть руки.
Вопрос: Частью кого является рука?
Для заданной системы аксиом доказать теорему
4.4. ∀y(S(y)→C(y))
Т: ∀x(∃y(S(y)∧R(x,y))→∃z((C(z)∧R(x,z))
Теория алгоритмов
1. Построить машину Тьюринга (результат представить в форме таблицы):
1.7. Перевести число, записанное в двоичной системе счисления в формате байта, в дополнительный код (вычислить обратный код числа и прибавить к двоичному числу 1).
Построить нормальный алгорифм Маркова, который:
3.1. добавляет две единицы к входному слову, состоящему из последовательности единиц.