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

1. Отношение задано на множестве целых чисел  {53,43, 54, 42, 44, 60, 50, 20}. Для каждого из следующих отношений:
I.    проверить, является ли отношение рефлексивным, симметричным, антисимметричным (строгим, нестрогим), транзитивным;
II.    построить матрицы и графы этих отношений;
III.    определить являются ли эти отношения отношениями эквивалентности, частичного порядка, линейного порядка;
IV.    для отношений эквивалентности построить классы эквивалентности;
V.    для отношений частичного порядка применить алгоритм топологической сортировки и получить отношение строгого порядка;
VI.    построить транзитивные замыкания всех отношений.
•    xGy   каждая из цифр числа x больше цифры числа  y, стоящей в соответствующем разряде;
•    xSy    |x-y|<5

2. Будет ли логичным следующее рассуждение: Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.

3. Провести исследование булевой функции  f(x,y,z)=((z+y) v y)((xy)+(z v x)):
a.    построить таблицу функции; ответ записать в виде набора значений, упорядоченного в соответствии с лексикографическим порядком набора аргументов;
b.    построить СДНФ этой функции; ответ записать, упорядочив элементарные конъюнкции в лексикографическом порядке;
c.    упростить полученное выражение с помощью методы минимизирующих карт, ответ записать в виде минимальной ДНФ;
d.    построить многочлен Жегалкина исходной функции;
e.    построить таблицу двойственной функции; ответ записать в виде упорядоченного набора значений;
f.    построить СКНФ двойственной функции; ответ записать, упорядочив элементарные дизъюнкции в лексикографическом порядке;
g.    проверить исходную функцию на принадлежность основным классам замкнутости  ;
h.    можно ли через эту функцию выразить все остальные булевы функции.

4. Машина Тьюринга имеет алфавит из трех символов {2,1,*}  (символ * означает отсутствия символа на ленте), два состояния {q2,q0}, из которых q2  - начальное, q0  - конечное. Символ R означает сдвиг читающей головки вправо на ленте, L  - влево, E  - головка остается на месте. В начальный момент головка указывает на крайний левый символ записи. Команды машины задаются набором: q02->q01R, q01->q02L, q0*->q22E. Какой результат даст машина на наборе 22122?

5. Построить порождающую грамматику для языка  L={(ac)^n,(cb)^n,n>0}