lec16
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 16.
ЧРФ И НАМ.
16.1.Частично-рекурсивные функции.
16.2.Нормальный алгоритм Маркова.
16.3. Определение алгоритма и его характерные свойства. 16.4. Вычислимость по Тьюрингу ЧРФ.
Часть 1.
Частично-рекурсивные функции.
Рассматриваем аргументы и значения функций, которые будут целыми неотрицательными числами: f , x1,…, xn 0.
Функция f (x1,…,xn) называется частичной, если, по крайней мере, на одном наборе значений аргументов она определена.
Введем операции над частичными функциями:
I) Операция суперпозиции.
Пусть h(x1,…,xn), g1(x1,…,xm), …, gn(x1,…,xm) – частичные функции. Тогда про функцию f (x1,…,xm) = h(g1(x1,…,xm),…, gn(x1,…,xm)) будем говорить, что она получена из функций h;g1,…,gn при помощи операции суперпозиции.
II) Операция рекурсии (примитивная).
Будем говорить, что функция f (x1,…,xn,y) получена из функций g(x1,…,xn) и h(x1,…,xn,y,z) при помощи операции рекурсии, если значения функции f вычисляются по следующему правилу:
f (x1,…,xn,0) = g(x1,…,xn),
f (x1,…,xn,y+1) = h(x1,…,xn,y, f (x1,…,xn,y)).
5
III) Операция минимизации.
Пусть g(x1,…,xn-1,y) – частичная функция. Зафиксируем набор переменных x1,…,xn-1,xn и рассмотрим уравнение (относительно y):
g(x1,…,xn-1,y) = xn |
(16.1) |
Тогда минимальное значение y удовлетворяющее (16.1), обозначим через µ
µ = µy(g(x1,…,xn-1,y) = xn).
Очевидно, что µ есть функция относительно x1,…,xn-1,xn которая получена из функции g(x1,…,xn-1,y) применением операции минимизации.
Пример 16.1. С помощью операции минимизации из функции сложения получить функцию вычитания:
µy(x + y = z) = z – x.
! µy определена только при z ≥ x
6
Среди частичных функций выделим так называемые базисные
(элементарные) функции.
1.Нуль-функция: O(x) = 0 при любом x=0,1,2,...
2.Функция следования: S(x) = x+1 при любом x=0,1,2,...
3.Функция выбора: Imn (x1,…,xn) = xm, 1≤m≤n.
Функция называется примитивно-рекурсивной, если она может быть получена из элементарных с применением конечного числа операций суперпозиции и примитивной рекурсии.
Функция называется частично-рекурсивной, если она может быть получена из элементарных с применением конечного числа операций суперпозиции, примитивной рекурсии и минимизации.
Если ЧРФ всюду определена, то она называется рекурсивной.
7
Пример 16.2. Проверка рекурсивности функций.
а) Сложение – f |
(x,y) = x + y рекурсивно: берем g(x) = I2(x,y) = x; h(x,y,z) = S(z), |
||
1 |
|
|
1 |
тогда |
|
|
|
, 0 = + 0; , 0 = = I2 , = |
|||
1 |
1 |
1 |
|
1 , + 1 = , , 1 , |
= S 1 , |
= + ( + 1 |
|
б) Умножение – f2(x,y) = x·y рекурсивно: берем g(x)=O(x); h(x,y,z)= f1(x,z)= x + z, |
|||
тогда |
|
|
|
2 , 0 = ∙ 0; 2 , 0 = |
= O = 0 |
|
|
2 , + 1 = , , 2 , |
= 1 , 2 , |
= + ∙ = ∙ + 1 |
|
в) Возведение в степень – f3(x,y) = xy рекурсивно: берем g(x) = S(O(x)) = 1(= x0), |
||||||
h(x,y,z) = f2(x,z) = x·z, тогда |
|
|
|
|
|
|
, 0 |
= 0 = 1; |
, 0 |
= |
= S(0 ) = 1 |
||
3 |
3 |
|
|
|
|
|
, + 1 = , , , |
= , , |
= ∙ = +1 |
||||
3 |
|
2 |
|
2 |
3 |
8 |
|
|
|
|
|
|
|
Часть 2.
Нормальный алгоритм Маркова.
Алгоритмическая система, созданная А. Марковым (194х), основана на соответствии между словами в абстрактном алфавите A.
Слово в алфавите – любая конечная последовательность букв из A. Пустое слово – слово, не содержащие ни одной буквы и обозначаемое символом □. Два конкретных слова αi1…αin и bi1…bim в алфавите А равны,
если n=m и αik=bik. Если αi1… αin – слово, состоящие из n букв, то n – длина этого слова. Длиной □ будет число 0. НАМ – непустой конечный набор
подстановок (формул), реализующих отображение слов pi в слова qi:
{ pi qi (i=1..k).
Порядок подстановок зафиксирован. Объектом i-й элементарной операции алгоритма является слово P в алфавите A, операция состоит в нахождении в этом слове первого слева вхождения слова pi и замене его на qi.
Результатом операции будет изменённое слово Q, если вхождение найдено, или входное слово P, если не найдено. Факт замены фиксируется
и используется в организации следования операций. При этом pi |
|
называется левой частью формулы, а qi – правой частью. |
10 |