5.1 Привести формулу к предваренной форме (3 б.)

5.2 Проверить общезначимость формулы методом резолюций (5 б.)

Варианты

1. ($x"yA(x,y))&($x"yB(x,y))

2. ($x"yA(x,y))®($x"yB(x,y))

3. ($x"yA(x,y))Ú($x"yB(x,y))

4. ($x"yA(x,y))®("x$yB(x,y))

5. ($x"yQ(x,y))®("y$xQ(x,y))

6. ("x$yQ(x,y))®($y"xQ(x,y))

7. ("x$yQ(x,y))®(($yQ(x,y))ÚR(x,y))

8. "x$yQ(x,y)®(($y"xP(x,y))®Q(x,y))

9. ("xQ(x,y))®(($yQ(x,y))Ú($xR(x,y)))

10. "x$yQ(x,y)®(($yP(x,y))®("xQ(x,y)))

11. ($x"yA(x,y))Ú($x"yB(x,y))

12. ($x"yA(x,y))®Ø("x$yB(x,y))

13. Ø($x"yQ(x,y))®("y$xQ(x,y))

14. ("x$yQ(x,y))®Ø($y"xQ(x,y))

15. ("xQ(x,y))®(($yQ(x,y))Ú($xR(x,y)))

16. "x$yQ(x,y)®(($yP(x,y))®("xQ(x,y)))

17. ($x"yA(x,y))Ú($x"yB(x,y))

18. ($x"yA(x,y))®Ø("x$yB(x,y))

19. Ø($x"yQ(x,y))®("y$xR(x,y))

20. ("xQ(x,y))®(($yQ(x,y))Ú($xR(x,y)))

21. "x$yQ(x,y)®(($yP(x,y))®("xQ(x,y)))

22. ($x"yA(x,y))Ú($x"yB(x,y))

23. Ø($xA(x,y))®("x$yB(x,y))

24. ($x"yA(x,y))&($x"yB(x,y))

25. ($x"yA(x,y))®($x"yB(x,y))

6.1 Придумать рассуждение (не менее трех гипотез) (10 б.)

6.2 Проверить рассуждение методом резолюций (5 б.)

Теория алгоритмов

7.1 Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны лишь нули и единицы, при этом пустые ячейки содержат нули. (10б)

7.2 Проверить работу машины Тьюринга для конкретных значений x,y (2 б.).

3. Нарисовать граф, соответствующий построенной МТ. (2 б.)

1. q₁ 1^x01^y0 q₀ 1^y01^x0

2. q₁ 1^x01^y0 q₀ 1^x+y 01^x 0

3. q11x01y	q0 1x, если y>x
   	q0 0, если yx

4. q11x01y0	q0 1y, если x>2
   	q0 1x, если x2

5. q₁ 1^x0 q₀ 1^x01^x01^x

6. q₁ 1^x01^y0 q₀ 1^x+y01^y+20

7. q11x01y	q0 1x, если x>y
   	q0 1y, если xy

8. q11x01y0	q0 1y, если x четно
   	q0 1x+2, если x нечетно

9. q11x01y0	q0 1y, если y>2
   	q0 1x, если y2

10. q₁ 1^x q₀ 1^y, y – целая часть x/3

11. q11x01y0	q0 1y0, если x>y
    	q0 0, если xy

12. q₁ 1^x q₀ 1^x+20101^x+2

13. q₁ 1^x q₀ 1^x+20101^x-2

14. q₁ 1^x q₀ 1^y, y – целая часть x/2

15. q11x01y	q0 1y, если x>2
    	q0 1y+3, если x2

16. q11x01y	q0 1x+y, если y>2
    	q0 1x, если y2

17. q₁ 1^x01^y0 q₀ 1^y01^x0

18. q₁ 1^x01^y0 q₀ 1^x+y 01^x 0

19. q11x01y	q0 1x, если y>x
    	q0 0, если yx

20. q11x01y0	q0 1y, если x>2
    	q0 1x, если x2

21. q₁ 1^x0 q₀ 1^x01^x01^x

22. q₁ 1^x01^y0 q₀ 1^x+y01^y+20

23. q11x01y	q0 1x, если x>y
    	q0 1y, если xy

24. q11x01y0	q0 1y, если x четно
    	q0 1x+2, если x нечетно

25. q11x01y0	q0 1y, если y>2
    	q0 1x, если y2