Математическая логика и теория алгоритмов. Контрольная работа. Вариант № 19. СибГУТИ.

1. Проверить выводимость в исчислении высказываний методом Куайна, методом редукции и методом резолюций.
2. Пусть Омега - множество людей. На множестве Омега заданы следующие предикаты:
E(x, y) = И <=> x и y – один и тот же человек;
P(x, y) = И <=> x родитель y;
C(x, y) = И <=> x и y – супруги;
M(x) = И <=> x – мужчина;
W(x) = И <=> x – женщина.
С использованием этих предикатов записать формулы, выражающие следующее утверждение:
У некоторых людей есть сестры
3. Привести формулу к предваренной форме
4. Построить машину Тьюринга для перевода из одной конфигурации в другую. На ленте всех машин Тьюринга записаны лишь нули и единицы, при этом пустые ячейки содержат нули. ( x , y ,z≥1) Проверить работу машины Тьюринга для конкретных значений x , y , z .
q 1 1 x => q 0 1 y ,y – целая часть x /3
5. Показать примитивную рекурсивность функции f(x,y)

2013, СибГУТИ, Мачикина Е. П., зачтено.