- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
11.3. Рекурсивные функции
Рекурсия – один из основных приемов программирования. Рекурсивные функции – функции, зависящие сами от себя. Когда мы рассматривали автоматы, то говорили о функциях переходов, которые в последующий момент автоматного времени зависят от своих значений в предыдущий момент времени. Так реализуется автоматная память. В теории рекурсивных функций, которая считается исторически первой формализацией понятия алгоритма, применяется нумерация слов в произвольном алфавите натуральными числами (N), и любой алгоритм сводится к вычислению некоторой функции при целочисленных значениях аргументов [22].
Функция вычислима, если существует такой алгоритм, то есть пошаговая процедура «от простого к сложному», которая по входному набору переменных вычисляет значение функции, если этот входной набор принадлежит к области определения функции, или выдает сообщение, что входной набор не принадлежит к области определения функции.
Функция полувычислима, если при задании входного набора, не принадлежащего области определения функции, алгоритм не заканчивает работу («зацикливается»). Теорию вычислимости разрабатывал А. Черч. Идея была похожа на изученную нами проблему функциональной полноты переключательных функций: выделить элементарные вычислимые функции (которые «интуитивно вычислимы») – то есть базис и предложить средства получения из этих элементарных вычислимых функций более сложных функций за конечное число шагов (как принцип суперпозиции в теории переключательных функций). Полученные таким образом функции тоже будут вычислимы.
Таковыми элементарными вычислимыми функциями являются:
1) S(x)=x+1, (NN), функция следования (указывает следующее натуральное число);
2) 0(х)=0, константа нуля;
3) Im(x1x2…xn)=xm – проектирующая функция, результатом которой является выбор m-го из n аргументов.
Для получения из одних полувычислимых функций других функций за конечное число шагов были предложены так называемые операторы.
Первым из них является известный нам оператор суперпозиции, т.е. подстановка в функцию функций вместо переменных. При этом увеличивается размерность функции.
Вторым оператором является оператор примитивной рекурсии.
Рассмотрим пример задания числового ряда Фибоначчи 1,1,2,3,5,8,13,21,… с использованием оператора примитивной рекурсии:
Здесь указываются два начальных значения функции f(0), f(1) и принцип формирования последующего значения. В отличие от функций переходов автомата, указывается не автоматное время, а шаг вычислений n, т.е. значение функции на некотором шаге, отличном от нулевого и первого, равно сумме значений функции на двух предыдущих шагах.
Тогда f(0)=1, f(1)=1, f(2)=f(0)+f(1)=1+1=2, f(3)=f(1)+f(2)=1+2=3, f(4)=f(2)+f(3)=2+3=5,…
Рассмотрим другой пример использования оператора примитивной рекурсии:
f(0)=1, f(1)=f(0)1=1, f(2)=f(1)2=2, f(3)=f(2)3=6, …
Таким образом, мы задали функцию факториала: x!
Функции, получаемые из элементарных, путем конечного числа применений операторов суперпозиции и примитивной рекурсии, называются примитивно-рекурсивными. Рассматривается и более сложная рекурсия, например, кратная, по нескольким переменным одновременно [19].
Все ли функции являются примитивно – рекурсивными? Можно показать, что множество всех одноместных целочисленных функций типа NN, где N – множество натуральных чисел, несчётно, тем более это верно для функции типа NnN. Каждая примитивно-рекурсивная функция имеет конечное описание, т.е. задаётся конечным словом в некотором фиксированном для всех функций алфавите [19]. Множество всех конечных слов счётно, поэтому примитивно-рекурсивные функции образуют не более чем счётное подмножество несчётного множества функций типа NnN. Более того, оказывается, не все вычислимые функции можно описать как примитивно-рекурсивные.
Третьим оператором является оператор минимизации m, который позволяет вводить в вычисления перебор для определения нужного значения.
Например:
f(x1x2)=m(y–x1=x2);
Напомним, что x1, x2 являются натуральными числами. Такие функции называются частично рекурсивными, то есть они не полностью определенные, в отличие от полностью определенных примитивно-рекурсивных. В соответствие с тезисом Черча функция полувычислима, если и только если она частично рекурсивна.
Имеются невычислимые функции, в которых связь между входными и выходными величинами столь сложна, что невозможно задать строго определенный пошаговый процесс преобразования исходных данных в результат [36], т.е. нельзя построить алгоритм решения соответствующей задачи.
Рекурсивные функции – основа функционального программирования. Примером языка функционального программирования является язык LISP, разработанный в 1960 г. Д Маккарти. Это один из первых языков обработки данных в символьной форме (LISP, от LISt Processing – обработка списков). Одним из наиболее существенных свойств языка LISP является то, что данные, программы и даже сам язык – представляют собой просто списки символов в скобках. Подобная структура позволяет писать программы или подпрограммы, способные обращаться сами к себе [37].
В LISP используется префиксная форма записи:
(+ху)=x+y;
(*х(+ху))=x*(x+y);
(+(*хх)(*уу))=x2+y2.
Определение функций и их вычисление в языке основано на так называемом лямбда-исчислении, введенном в 1931 г. А Черчем:
λ(х1,х2,…,хn)fn или (lambda(xy)(+(*xx)(*yy))),
где λ – определение функции, х1,…,хn – формальные параметры (лямбда список), fn – тело функции.
Рекурсии присутствуют и в языках структурного программирования.
Рассмотрим пример решения задачи на Паскале, использующий рекурсию [3].
З а д а ч а. Известно рекурсивное определение факториала:
Здесь n – неотрицательно. Записать эту функцию на языке Паскаль.
Решение. В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (n-1)! и умножить его на n. Уменьшающееся значение гарантирует, что в конце концов возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно.
program task5;
varn:integer; {исходное значение}
function fact(i:integer):integer;
begin if (i=1) or (i=0)
then fact:=1
else fact:=fact(i-1)*i;
end;
begin write(’Введите нужное значение n ’);
readln(n);
writeln(’Факториал ’,n,’ равен ’,fact(n));
end.
Заметим, что на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех переменных, объявляемых в нем, причем переменные других копий будут недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и все его переменные. Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4!. Основной алгоритм: вводится n=4, вызов fact(4). Основной алгоритм приостанавливается, вызывается и работает fact(4): 4<>1 и 4<>0, поэтому fact:=fact(3)*4. Работа функции приостанавливается, вызывается и работает fact(3): 3<>1 и 3<>0, поэтому fact:=fact(2)*3. В данный момент в памяти компьютера две копии функции fact. Вызывается и работает fact(2): 2<>1 и 2<>0, поэтому fact:=fact(1)*2. В памяти компьютера уже три копии функции fact и вызывается четвертая. Вызывается и работает fact(1): 1=1, поэтому fact(1)=1. Работа этой функции завершена, продолжает работу fact(2). fact(2):=fact(1)*2=1*2=2. Работа этой функции также завершена, и продолжает работу функция fact(3). fact(3):=fact(2)*3=2*3=6. Завершается работа и этой функции, и продолжает работу функция fact(4). fact(4):=fact(3)*4=6*4=24. После чего управление передается в основную программу и печатается ответ: «Факториал 4 равен 24».