Логическое следствие в логике предикатов

Пусть – формулы логики предикатов,и .. Доказать следующие соотношения.

1. ;

2. ;

;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. .

Пусть – формулы логики предикатов. Проверить следующие соотношения.

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. ;

27. ;

3.8. Исчисление предикатов

Пусть -формулы исчисления предикатов.Построить вывод формулы исчисления предикатов из данного множества гипотез.

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

3.9. Пренексная нормальная форма

Пусть – атомарные формулы логики предикатов. Привести следующие формулы логики предикатов к пренексной нормальной форме.

3.10. Машины Тьюринга

Построить машину Тьюринга , вычисляющую следующую функцию.

Примитивно рекурсивные функции

Доказать, что следующие функции примитивно рекурсивны.

1. x+1;

2. x+y;

7. |x-y|;

8. max(x,y);

9. min(x,y);

13. – частное от деленияxнаy(здесь);

14. rest(x,y) – остаток от деления x на y( здесьrest(x,0)=x);

15. τ(x)– число делителей числаx, гдеτ(0)=0;

16. σ(x)– сумма делителей числаx, гдеσ(0)=0;

17. lh(x)– число простых делителей числаx, гдеlh(0)=0;

18. π(x) – число простых чисел, не превосходящих x;

19. k(x,y)– наименьшее общее кратное чисеxиy, гдеk(x,0)=k(0,y)=0;

20. d(x,y)– наибольший общий делитель чисеxиy, гдеd(0,0)=0.