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

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

1. ;

2. ;

3. 

;

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. Пренексная нормальная форма

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

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

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

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

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

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

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

1. x+1;

2. x+y;

3. 

4. 

5. 

6. 

7. |x-y|;

8. max(x,y);

9. min(x,y);

10. 

11. 

12. 

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.

Частично рекурсивные функции

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

1. 

2. 

3. 

4. 

5. 

6. 

7. ;

8. ;

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

17. 

18. 

19. 

20. 

3. Список литературы

1. Основная литература

1. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987.

2. Судоплатов С.В., Овчинникова Е.В. Математическая логика и

теория алгоритмов. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004.

3. Новиков П.С. Элементы математической логики. – М.: Наука,1973.

4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука,1981.

5. Степанова А.А. Математическая логика и теория алгоритмов. Учеб.пособие.- Находка: Институт технологии и бизнеса, 2003.-56 с.

4.2. Дополнительная литература

1. Мендельсон Э. Введение в математическую логику. – М.: Наука,1976.

2. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. С.П.:Лань,1998.

3. Черч А. Введение в математическую логику. – М.: Наука. 1960.

Содержание

ВВЕДЕНИЕ 3 1.ПРОГРАММА КУРСА 4 2. ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ 6 2.1. Алгебра высказываний

2.2. Исчисление высказываний 12 2.3. Логика предикатов

2.4. Исчисление предикатов 25 2.5. Элементы теории алгоритмов 32 3. ЗАДАНИЯ ДЛЯ ДОМАШНИХ И КОНТРОЛЬНЫХ РАБОТ 33 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы 33 3.2. Логическое следствие в алгебре высказываний 33 3.3. Исчисление высказываний 34 3.4. Алгебраические системы 36 3.5. Формулы логики предикатов 37 3.6. Истинность формулы логики предикатов в алгебраической системе 3.7. Логическое следствие в логике предикатов 40 3.8. Исчисление предикатов 41 3.9. Пренексная нормальная форма 42 3.10. Машины Тьюринга 43 3.11 Примитивно рекурсивные функции 43 3.12. Частично рекурсивные функции 44 4. СПИСОК ЛИТЕРАТУРЫ 45

59