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

1.Проверить выводимость в исчислении высказываний методом
Куайна, методом редукции и методом резолюций.
A&(BvC) |- (A&B)v(A&C)
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 ;) Проверить работу машины Тьюринга для конкретных значений x , y , z .
5.Показать примитивную рекурсивность функции f(x,y) f(x,y)=(x+y) mod 2
Функция называется примитивно-рекурсивной, если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции и примитивной рекурсии. Если некоторые функции являются примитивно-рекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции. Существует три возможности доказательства того, что функция является примитивно-рекурсивной: а) показать, что заданная функция является простейшей; б) показать, что заданная функция построена с помощью оператора суперпозиции; в) показать, что заданная функция построена с помощью оператора примитивной рекурсии. Сначала докажем примитивную рекурсивность функции f1(x, y) = x + y.