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

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

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.

СПИСОК ЛИТЕРАТУРЫ

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

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

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

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

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

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

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

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

 

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

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

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

 

СОДЕРЖАНИЕ

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

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

2.4. Исчисление предикатов 26 2.5. Элементы теории алгоритмов 30 3. ЗАДАНИЯ ДЛЯ ДОМАШНИХ И КОНТРОЛЬНЫХ РАБОТ 34 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы 34 3.2. Логическое следствие в алгебре высказываний 34 3.3. Исчисление высказываний 35 3.4. Алгебраические системы 36 3.5. Формулы логики предикатов 37 3.6. Истинность формулы логики предикатов в алгебраической

системе 39

3.7. Логическое следствие в логике предикатов 40 3.8. Исчисление предикатов 41 3.9. Пренексная нормальная форма 42 3.10. Машины Тьюринга 43 3.11 Примитивно рекурсивные функции 44 3.12. Частично рекурсивные функции 45 4. СПИСОК ЛИТЕРАТУРЫ 47