Математическая логика и теория алгоритмов

Контрольная работа
По дисциплине: Математическая логика и теория алгоритмов

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

2009, Мачикина, зачет