Шаг 3.
Основы языка Haskell. Индуктивные определения операций и предикатов, заданных на множествах слов. Рекурсивные определения функций
На этом шаге мы рассмотрим определения и задания таких функций.
- МетаОпределение (по [1, с.43-44]).
- Рекурсивными определениями (в математике) называются индуктивные определения операций и предикатов.
- Определение (по [2, с.66]).
-
Если линейно упорядоченное множество A разбито на две (непересекающиеся) части B и C, причём любой элемент B меньше любого элемента C, то B называют
начальным отрезком множества A.
Другими словами, подмножество B линейно упорядоченного множества A является начальным отрезком, если любой элемент B меньше любого элемента A\B.
Еще одна переформулировка: B ⊂ A является начальным отрезком, если из a,b ∈ A, b ∈ B и a ≤ b следует a ∈ B.
В частности, начальным отрезком вполне упорядоченного множества A является множество элементов A, меньших x (обозначается: [0,x)).
Пусть A - вполне упорядоченное множество. Мы хотим дать рекурсивное определение некоторой функции f: A → B, где B - некоторое множество. Такое определение должно связывать значение
f(x) на некотором элементе x ∈ A со значениями f(y) при всех y<x.
Другими словами, рекурсивное определение задает f(x), предполагая известным ограничение функции f на начальный отрезок [0,x).
Вот точная формулировка.
- Теорема (по [2, с.70]).
-
Пусть A - вполне упорядоченное множество, а B - произвольное множество. Пусть имеется некоторое рекурсивное правило, т.е. отображение F, которое ставит в соответствие
элементу x ∈ A и функции g:[0,x) → B некоторый элемент множества B.
Обозначим f¦[0,x) - ограничение функции f на начальный отрезок [0,x) - мы отбрасываем все значения функции на элементах, больших или равных x.
Тогда существует единственная функция f: A → B, для которой
при всех x ∈ A.
- Определение (по [3, с.146]).
-
Индуктивным определением (или построением) функции f(a) на множестве натуральных чисел называется её определение по следующим
двум свойствам:
- Задано значение функции f(0)=x0 для числа 0.
- Значение функции f(a) для натурального числа a>0 однозначно выражено через ее значения f(b) для натуральных чисел b<a при помощи данных рекурсивных правил.
- Теорема (о законности индуктивного определения) (по [3, с.146]).
- При заданных рекурсивных правилах существует одна и только одна функция f(a), заданная на множестве всех натуральных чисел и обладающая свойствами (1) и (2), указанными в предыдущем определении.
(1)Марков А.А., Нагорный Н.М. Теория алгорифмов.- М.: ФАЗИС, 1996.- 496 с.
(2)Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. 2-е изд., исправленное. М.:МЦНМО, 2002. - 128 с.
(3)Энциклопедия элементарной математики. Кн.1. - М.-Л.: ГИТТЛ, 1951. - 448 с.
На следующем шаге мы рассмотрим принцип трансфинитной индукции.
Предыдущий шаг
Содержание
Следующий шаг