2.5.2. Примитивно рекурсивные функции
Базисными функцияминазываются следующие функции:– нулевая функция;– функция следования;– функция выбора.
Оператор суперпозиции (подстановки)ставит в соответствиеm-местной частичной функциииn-местным частичным функциямn-местную частичную функцию, удовлетворяющую тождеству:
Оператор примитивной рекурсииставит в соответствиеn+2-местной частичной функциииn-местной частичной функцииn+1-местную частичную функцию, удовлетворяющую схеме примитивной рекурсии:
Частична функция называетсяпримитивно рекурсивной(ПРФ), если существует последовательность частичных функций, в которойи всякаяявляется либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозицииили примитивной рекурсии.
Пример 2. Функция сложенияявляется ПРФ:
Пример 3. Функция умноженияявляется ПРФ:
- Введение
- Программа курса математическая логика и терия алгоритмов
- Логическое следствие в алгебре высказываний
- 2.1.3. Эквивалентные формулы алгебры высказываний
- 2.1.4. Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний
- 2.1.5. Совершенные дизъюнктивные и конъюнктивные нормальные формы
- Исчисление высказываний
- Определение формального исчисления
- Система аксиом и правил вывода
- Теорема о дедукции в исчислении высказываний
- Теорема о замене в исчисления высказываний
- Свойства выводимых и эквивалентных формул исчисления высказываний
- Основные эквивалентности исчисления высказываний
- Полнота и непротиворечивость исчисления высказываний
- Логика предикатов
- Алгебраические системы
- Пример 3. Построить подсистему алгебраической системы , порожденную множествомХ:
- Формулы логики предикатов
- Истинность формулы логики предикатов в алгебраической системе
- 2.3.4. Логическое следствие в логике предикатов
- 2.3.5. Эквивалентные формулы логики предикатов
- 2.3.6. Пренексная нормальная форма в логике предикатов
- X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
- X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
- Xφ≡X(φ)xφ≡X(φ)
- 2.4. Исчисление предикатов
- 2.4.1. Система аксиом и правил вывода
- 2.4.2. Эквивалентные формулы исчисления предикатов
- 2.4.3. Теорема Геделя о полноте. Непротиворечивость исчисления предикатов
- Элементы теории алгоритмов
- 2.5.1. Машины Тьюринга
- 2.5.2. Примитивно рекурсивные функции
- 2.5.3. Частично рекурсивные функции
- Задания для домашних и контрольных работ
- 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
- 3.2. Логическое следствие в алгебре высказываний
- Логическое следствие в логике предикатов
- Частично рекурсивные функции
- Список литературы
- Основная литература
- 4.2. Дополнительная литература
- Содержание