 |
Исполнители Безопасность заказов и сделок Время на проверку работ |
 |
|
|
|
|
|
|
Математическая логика алгоритмМАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВИ С Ч И С Л Е Н И Я 1. И с ч и с л е н и е в ы с к а з ы в а н и й ……………………………………….. 1.1. Алгебра высказываний ……………………………………………… … … 1.2. Приложения алгебры высказываний ………………………………….… 1.2.1. Функции алгебры высказываний (булевы функции) …… 1.2.2. Метод синтеза релейно-контактных схем …………………… 1.2.3. Приложение в теории множеств ……………………………. 1.3. Аксиоматическая система в исчислении высказываний ……………….. 2. И с ч и с л е н и е п р е д и к а т о в …………………………………………… 2.1. Предикаты ……………………………………………………………………. 2.2. Система аксиом в исчислении предикатов ……………………………… 2.3. Формальная арифметика …………………………………………………… А Л Г О Р И Т М Ы 1. А л г о р и т м ы и в ы ч и с л и м ы е ф у н к ц и и ………………………… . 1.1. Машины Тьюринга ……………………………………………………….. 1.2. Частично рекурсивные функции ………………………………………….. 1.2.1. Класс примитивно рекурсивных функций …………………… 1.2.2. Рекурсивно перечислимые множества и предикаты …… … 1.2.3. Порожденные множества……………………………………… 1.2.4. Функции на n-ках ……………………………………………… . 1.2.5. Рекурсия второй ступени ……………………………………… 1.2.6. Универсальная функция ………………………………………… 1.2.7. Универсальные частично рекурсивные функции …………….. 2. П р и л о ж е н и я т е о р и и а л г о р и т м о в …………………………….. 2.1. Теоремы о рекурсии и неполноте ………………………………………… 2.2. Разрешимость и неразрешимость формальных систем ……………….… 3. С л о ж н о с т ь в ы ч и с л е н и й …………………………………………….. 3.1. Меры сложности ……………………………………………………………. 3.2. Теорема об ускорении ……………………………………………………… 3.3. Классы сложности. Элементарные функции ……………………………. ВВЕДЕНИЕ Логика возникла в культуре Древней Греции. Первое дошедшее до нас сочинение по ло-гике - “Аналитики” Аристотеля (384-322гг. до н.э.). Независимо развивалась буддистская логика, но достоянием европейской науки она стала сравнительно недавно, поэтому извест-ная нам логика “вышла” из логики Аристотеля. Математическая логика отличается тем, что пользуется языком математических символов. Ее основоположниками были: Д.Буль (исчис-ление высказываний), Г.Фреге, Г.Пеано, Б.Рассел. Выдвинутая в 20-е годы Х1Х века про-грамма Д.Гильберта обоснования математики с помощью логики привела к формализации математических теорий, много частных задач было решено. К настоящему времени доказана непротиворечивость элементарной геометрии, арифметики, анализа, аксиоматической сис-темы теории множеств Цермело-Френкеля и т.д. Некоторые важные теории оказались пол-ными: исчисление высказываний и исчисление предикатов, элементарная геометрия, теория векторных пространств и т.д. Но в других теориях получены предложения, которые нельзя ни доказать, ни опровергнуть. Так, в аксиоматической теории множеств Цермело-Френкеля это аксиома выбора и континуум-гипотеза. Как следует из теорем Геделя о неполноте, вся-кая достаточно богатая теория необходимо содержит такие предложения. В математической логике было дано точное определение алгоритма и вычислимости. Во-прос о существовании алгоритмов имеет для математики первостепенное значение (напри-мер, алгоритм существования решений для системы уравнений). Были получены разрешаю-щие алгоритмы для ряда теорий, например, элементарной геометрии, упорядоченного поля действительных чисел, атомной булевой алгебры и т.д. Неразрешимы теории (т.е. не сущест-вует единого алгоритма для решения всех задач) элементарной арифметики, анализа, класса всех конечных симметрических групп (т.е.групп перестановок), аксиоматических систем теории множеств. В последние годы большое внимание уделяется теории сложности алгоритмов и вычисле-ний. Выяснилось, что одного только существования алгоритма, решающего ту или иную массовую проблему, далеко не достаточно для практики. После уточнения понятия сложно-сти вычисления стали исследовать вопросы такого рода, как внутренняя сложность вычис-лимой функции, ее криптографическая стойкость, приобретающие особую актуальность с развитием сетей связи, вычислительной техники и автоматизированных систем управления. 1.ИСЧИСЛЕНИЯ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ 1.1. Алгебра высказываний Содержание любой науки составляют утверждения об объектах ее предметной области. Логика высказываний абстрагируется от конкретного содержания утверждений (высказыва-ний) и изучает структуру сложных высказываний и их логические связи. Высказывание есть повествовательное предложение, истинное или лож- ное. Примеры высказываний: “Снег белый” , “2>3”, “Если идет дождь, то я беру зонт” и т.д. Изучать математическую логику мы будем с помощью математических методов в некото-ром метаязыке, который будем отличать от предметного языка изучаемой логики. Предмет-ный язык логики высказываний состоит из алфавита и формул: А л ф а в и т: (1) P, Q, R, ... - переменные для простых высказываний (пропозициональные буквы); (2) &, , , , - символы операций над высказываниями (логические связки); (3) ( , ) - вспомогательные символы (скобки). Ф о р м у л ы, или сложные высказывания: (1) P, Q,R, ... – пропозициональные буквы – эле-ментарные формулы (атомы); (2) если А, В - формулы, то А&В, АВ, АВ, А В, А - формулы. В определении формул использованы метабуквы А, В, т.е. символы, не принадлежащие предметному языку. Примеры формул: (P&Q), (R (P R)). Подформула - это часть формулы, сама являющаяся формулой. Задав язык, мы построили формальную систему. Представим теперь ее как содержа-тельную алгебру высказываний, для чего придадим смысл символам алфавита и форму-лам. Пропозициональные буквы и логические операции определим на области из двух элементов {И, Л}: P Q PQ PQ P PQ PQ И И И И Л И И И Л Л И Л Л Л Л И Л И И И Л Л Л Л Л И И И Значение формулы E[P1, ... , Pn] при данной интерпретации входящих в нее пропозициональных букв (входов) : {P1, ... , Pn} {И,Л} определим индукцией по построению формулы:. E = P : E[] = (P); E = A&B : E[] = (A&B)[] = A[] & B[]; E = A : E[] = A[]; E = AB : E[] = (AB)[] = A[] B[]; аналогично для остальных логичеcких связок. Истинностная таблица формулы составлена из строк, задающих значения всех под-формул данной формулы: P Q R P&Q (P&Q) R PQ (PQ) (P&Q)R (PQ) И И И И И И Л Л И И Л И И И Л Л И Л И Л И И Л Л И Л Л Л Л И Л И Л И И Л И И Л Л Л И Л Л Л И Л И Л Л И Л И Л И И Л Л Л Л Л Л И И Т а в т о л о г и я (общезначимая формула, логический закон) - формула, истинная при всех интерпретациях входящих в нее пропозициональных букв, другими словами, - столбец значений которой содержит одни истинные значения (обозначается знаком =). ТЕОРЕМА 1 (Подстановка вместо атомов). Пусть формула Е[P1, . . . ,Pn] содержит про-позиционные буквы P1, . . . ,Pn , а формула Е* [А1, . . . ,Аn] получена одновременной под-становкой формул А1, . . . ,Аn вместо атомов P1 , . . . ,Pn , соответственно. Тогда если |= E, то |= Е*. Обратное неверно. Д о к а з а т е л ь с т в о проведем индукцией по построению формулы E: Рассмотрим случай E = (A&B)[P1, . . . ,Pn] . Пусть |= (A&B)[P1, .. ,Pn], т.е. (A&B) [P1, .. ,Pn][ ] =И для всех интерпретаций . Тогда по определению значения формулы: A[P1, .. ,Pn][] = И и B[P1, .. ,Pn][] = И для всех интерпретаций . Откуда = A[P1, . . . ,Pn] и =B[P1, . . . ,Pn] и, по индукционному допущению, |= A* [A1, ... ,An] и |= B* [A1, ... ,An] . Таким образом, |= A* & B*, т.е. |= (A&B)*, следовательно, |= E*. Пример применения теоремы 1 : Чтобы проверить, является ли формула (P&Q) &(RP) (P&Q) тавтологией, достаточно убедиться в том, что общезначима формула E(P,Q) =P&Q P. Поэтому в истинностной таблице на входы можно помещать метабуквы. ТЕОРЕМА 2 (Основные тавтологии). 1а. |=A(BA) 1б. |=(AB)((A(BC))(AC)) 2. |=A(BA&B) 3а. |=A&BA 3б. |=A&BB 4а. |=AAB 4б. |=BAB 5. |=(AC)((BC)(ABC)) 6. |=(AC)((AC) A) 7. |=AA 8. |=(AB)((BA)(AB)) 9а. |=(AB)(AB) 9б. |=(AB)(BA) 10. |=(A(AC) Д о к а з а т е л ь с т в о. Применяем теорему 1 и таблицы истинности формул. Д р у г и е т а в т о л о г и и : 1) |=AA (закон исключённого третьего) 2) |=AA (закон тождества) 3) |=(AB) A&B (1-й закон де Моргана) 4) |=(A&B) ~ AB (2-й закон де Моргана) 5) |=A&AA, =AAA 6) |= AB ~ A B 7) |=(AB) ~ (AB)&(BA) 8) |=(AB) ~ (BA) (закон контрапозиции) 9) |=A&B B&A (коммутативность конъюнкции) 10) |=A B B A (коммутативность дизъюнкции) 11) |= A&(B&C) (A&B)&C (ассоциативность конъюнкции) 12) |=A (B C) (A B) C (ассоциативность дизъюнкции) 13) |=A & (B C) (A&B) (A&C)(1-й закон дистрибутивности) 14) |= A (B&C) (A B) & (AC)(2-й закон дистрибутивности) 15) =A&(AB) A, =A(A&B)A (законы поглощения) 16) =A&ИA, =A&ЛЛ, =AИИ, =AЛA. 17) |=A(BC) ~ A&BC ТЕОРЕМА 3. Если |= A и = A B, то = B. Д о к а з а т е л ь с т в о. Пусть = A и = A B и P1, ... , Pn - все переменные, входящие в эти формулы. Допустим противное, что при некоторой интерпретации : {P1, ... , Pn} {И,Л}, B[] = Л. По условию, для всех интерпретаций, в частности, для интерпретации , A[] = И и (A B)[] = И, что однако противоречит определению операции . Формулы А и В назовем эквивалентными, если = A B. ТЕОРЕМА 4 (Эквивалентность формул). Формулы А и В эквивалентны т.и т.т., когда A и B имеют одинаковые истинностные таблицы. Д о к а з а т е л ь с т в о. Для всех интерпретаций пропозициональных букв, (A B)[] =И т.и т.т., когда A[] = B[]. Откуда следует утверждение теоремы. ТЕОРЕМА 5(О замене). Пусть формула E[A] содержит подформулу A. Формула Е[B] есть результат замены выделенного вхождения формулы A на формулу B. Тогда, если |=A ~ B, то |=E[A] ~ E[B]. Д о к а з а т е л ь с т в о получается с помощью теоремы 4. Следствие. Если |=A ~ B и |=E[A], то |=E[B]. Пример. Упростить формулу ((PS)Q)& S((SRQ) P): ((PS)Q)&S((SRQ) P) ((PS Q) &(QPS)&S) ( S R Q P) ((PS Q) &(QPS)&S) ( S R Q P) (( (PS) Q) & ( Q P S) & S) ( S R Q P) ( (PS) Q) (Q P S) S) (S & R & Q & P) ((P S) & Q) (Q&P&S) S (S & R & Q & P) (P&Q) (S&Q) (Q&P&S) S (P&Q) (Q&P&S) S (P&Q) ((Q S )&(P S)&(S S)) (P&Q) (Q&P) S. Формула называется формулой с тесными отрицаниями, если операция применяется только к атомам. ТЕОРЕМА 6. Пусть Е формула с тесными отрицаниями, не содержащая других опера-ций, кроме , , . Формула EX есть результат замены в E (на всех местах) конъюнк-ции на дизъюнкцию, дизъюнкции на конъюнкцию и каждой пропозициональной буквы на ее отрицание. Тогда |= Е ~ ЕX. Д о к а з а т е л ь с т в о теоремы проведем индукцией по построению фор мулы E. Базис индукции: ЕР : Е Р и, по определению оперaции ‘X’, ЕХ Р, ч.т.д. Индукционный шаг : а) E АB, b) E АB, c) E A.. a) EАB: = Е ( АB) (по закону де Моргана) AB (по индукционному до-пущению и теореме 5) AX BX (по определению операции ‘крест’) (АB)Х ЕХ. b) EAB: = E (AB) (по закону де Моргана и теореме 5) A&B (по индукцион-ному допущению и теореме 5) AX&BX (по определению операции ‘крест’) (AB)X EX. c) EA: тогда AP, EPP и EXP, ч.т.д. ТЕОРЕМА 7 (Принцип двойственности). Пусть формулы E, F такого же вида, как в теореме 6. Формулы E, F, полученные из E,F одновременной заменой всюду & на и на &, называются двойственными к формулам E, F, соответственно. Имеют место сле-дующие утверждения: a) Если = E, то = E. b) Если = E, то = E. с) Если = E F, то = E . F . d) Если = E F, то = F E. Д о к а з а т е л ь с т в о. a): = E (допущение) = E EX (теорема 6) = EX (следствие из теоремы 5) = (EX)PP (теорема 1); = ((EX)PP)PP (следствие из теоремы 5),т.е. = E. b): = E (допущение) = E (следствие теоремы 5) = (E) (EX ) (теорема 6 и теорема 5) = (EX ) (следствие из теоремы 5) = ((EX))PP (теорема 1) = (EX)PP (по определению операции подстановки) = ((EX)PP)PP (следствие из теоремы 5) = ((EX)PP)PP (по определению операции замены), т.е. = E . Назовем формулу B логическим следствием формул A1,A2,...,Am (m1) (обозначается A1,A2,...,Am=B), если в таблице истинности в строках, где формулы A1,A2,...,Am (посылки) одновременно истинны, истинна также и формула B (заключе-ние). ТЕОРЕМА 8. a) A = B т.и т.т., когда = A B. b) A1,A2,...,Am-1,Am = B т.и т.т., когда A1,A2,...,Am-1 = AmB (m1). Следствие. A1,A2,...,Am-1,Am = B т.и т.т.,когда = A1(...(Am-1( AmB))...) (m1). 1.2. Приложения алгебры высказываний 1.2.1. Функции алгебры высказываний (булевы функции) Функцией алгебры высказываний (булевой функцией) называется n-местная операция на множестве {0,1}. А л ф а в и т: (1) x,y,...,x1,x2,... - предметные переменные; (2) f,g,...,f1,f2,... функциональные символы. Т е р м: (1) x,y,...,x1,x2,... - предметные переменные являются термами; (2) если f( n) -функциональный символ, t1,...,tn - термы, то f( n) (t1,...,tn) - терм. Значение терма: (1) если t - предметная переменная x, то зн t = (x); (2) если t = f (n) (t1,...,tn ) , то зн t = f (n) (зн t1,..., зн tn). Функция f (n) (x1,...,xn ) представима термом t (v1, ..., vm), если {v1, ..., vm} {x1,...,xn} и t = f (n) для всех интерпретаций : {x1,...,xn} {0,1}. ТЕОРЕМА. Для каждой формулы A алгебры высказываний существует функция алгебры высказываний f (A) такая, что A1 A2 f(A1) = f(A2). Функция f есть суперпозиция функций f1, ..., fm , если f представима термом, все функциональные символы которого содержатся среди f 1,...,fm. Система функций называется полной, если любая функция алгебры высказываний может быть представлена суперпозицией функций из . Назовем элементарной конъюнкцией (дизъюнкцией) произвольную конъюнкцию (дизъ-юнкцию), составленную из пропозициональных букв или их отрицаний. Дизъюнктивной нормальной формой (д.н.ф.) называют дизъюнкцию элементарных конъюнкций. Совер-шенной дизъюнктивной нормальной формой (с.д.н.ф.) называется дизъюнктивная нор-мальная форма, каждая элементарная конъюнкция которой содержит все пропозициональ-ные буквы (возможно с отрицанием), входящие в формулу. ТЕОРЕМА. Всякая выполнимая (опровержимая ) формула эквивалентна подходящей с.д.н.ф. (с.к.н.ф.)1. Д о к а з а т е л ь с т в о теоремы следует из более общей формулы разложения функции по части входящих в нее переменных : f(x1,...,xn ) = x11 &...&xmm & f(1,...,m, xm+1,...,xn), (1,...,m) где i {0,1}, xi0 = xi, xi1 = xi (i = 1,...,m). В частности, f(x1,...,xn ) = x11 &...&xnn . (1,...,n) f(1,...,n) = 1 1.2.2. Метод синтеза релейно - контактных схем Проинтерпретируем булевы функции как электрические сети, содержа- щие двухпозиционные переключатели x, x - соответственно, замыкаю- щий и размыкающий контакты; &, - соответственно, последовательное и параллельное соединения контактов; 1 и 0 - соответственно, «ток прохо- дит» и «ток не проходит». Две цепи называются эквивалентными, если через одну из них ток проходит т.и т.т, когда он проходит через другую. Пример 1. Упростить следующую релейно-контактную схему, получив ее функцию проводимости, и минимизировать ее. x y z x z y Решение: (x,y,z) = (x& y) z ((x y)&z)) = (x& y) z x y z Пример 2. Используя с.д.н.ф.(с.к.н.ф.), найти формулу для функции про водимости f и начертить соответствующую ей релейно-контактную схе- му, если f(1,0,0,0) = f(1,1,0,0) = f(0,1,1,0) = 1. Решение: f(x,y,z,u) = (x&y&z&u) (x&y&z&u) (x&y&z&u) = ((x&z&u)&( yy)) (x&y&z&u) = (x&z&u) (x&y&z&u)= . ((x&z) (x&y&z))&u. x z u x y z Пример 3. Имеется одна лампочка в лестничном пролете двухэтажного дома. Постройте схему так, чтобы на каждом этаже своим выключателем можно было бы гасить и зажигать лампочку. Решение. Функция проводимости такой схемы меняет свои значения, если меняет значе-ние один из ее аргументов: f(0,0) = f(1,1) = 1, f(0,1) = f(1,0) = 0. Воспользовавшись с.д.н.ф., получим функцию f(x,y) = (x&y)(x&y). 1.2.3. Приложение в теории множеств Множеством называют вполне определенную совокупность различаемых объектов. Например, множество ‘всех книг данной библиотеки’, или множество ‘всех людей, живших в XX веке’. Имеются два способа задания множеств: (1) путем явного перечисления его элементов, например, целые числа между 0 и 5, т.е. {0,1,2,3,4,5}; (2) указанием свойства, определяющего принадлежность элемента данному множеству, т.е. {x; (x)}. Рассмотрим язык, предназначенный для описания свойств множеств. А л ф а в и т содержит переменные x,y,z,..., пробегающие множества, символ принадлежности ‘’ и символы логики высказываний. Т е р м ы и ф о р м у л ы определим одновременно: 1. x,y,z,... - предметные переменные, пробегающие множества, - термы; 2. если t, r - термы, то t r элементарная формула (атом) ; 3. если , - формулы, то &, , , , - формулы; 4. если x - переменная, и - формула, то {x; (x)} - терм. Определим операции (пересечение, объединение, разность, дополнение) и отношения (включение, равенство) над множествами (для удобства объекты-множества будем обозна-чать заглавными буквами, а объекты, являющиеся элементами множеств, малыми буквами): 1. 2. 3. 4. A B 1)x (x A x B) 5. A = B x (x A x B) 6. U = {x : x = x}, = {x : x x} 7. (перечеркнутые символы = и означают, что соответствующие = - и - отношения не имеют места). Свойства операций и отношений 1) , 2) , 3) , 4) A A B, A B A, A \ B A, A A = A, A A = A, , A, A U, A \ = A 5) A B A B = B A B = A 6) A B & C D A C B D A B & C D A C B D A B & C D A \ D B \ C Можно заметить, что существует тесная связь, между множествами и высказывания-ми, между операциями над множествами и логическими операциями. Пусть мы имеем несколько высказываний. Образуем множество всех логических возможностей для рас-сматриваемых высказываний и назовем его универсальным множеством. Поставим каж-дому высказыванию в соответствие подмножество тех логических возможностей уни-версального множества, для которых это высказывание истинно - его множество истин-ности. Очевидно, что множествами истинности высказываний P&Q, P Q, P будут, соответственно, множества PQ, PQ, P, где P, Q - множества истинности высказы-ваний P, Q. Пусть булева функция f(x1,...,xn ) представима термом, содержащим только логические символы &, , . Обозначим через f (x) формулу теории множеств, полученную из терма f подстановками вместо переменных x1,..., xn формул x A1,..., x An , соответ-ственно. Обозначим через Zf выражение, полученное из терма для f(x1,..., xn) заме-ной переменных x1,...,xn символами Z1,...,Zn, и символов &, , символами , , , со-ответственно. При интерпретации Zf символы Zi будут обозначать подмножества уни-версума U (множества, содержащего в качестве подмножеств все другие множества). 1.3. Аксиоматическая система в исчислении высказываний А к с и о м а м и1) (классического) исчисления высказываний объявляем тавтологии из теоремы 2. В качестве единственного п р а в и л а в ы в о д а принимаем процедуру пе-рехода от двух формул вида A, A B (посылок) к формуле B (заключению): (modus ponens) (Требования, которым должны удовлетворять правила вывода, – из истинных посылок должны получаться истинные заключения.) Д о к а з а т е л ь с т в о м ф о р м у л ы Ф (т е о р е м ы) называют конечный список фор-мул B1,...,Bl, заканчивающийся формулой Ф (Ф = Bl), где каждая формула Bi (i=1,...,l) есть аксиома или получена из предыдущих формул по одному из правил вывода (обозна-чается Ф). Пример 1 (Доказательство теоремы). AA : 1. A(AA) (аксиома 1а ) 2. A((AA) A) (аксиома 1а) 3. (A(AA))((A((AA)A))(AA)) (аксиома 1б) 4. (A((AA)A))(AA) (modus ponens, 2,3) 5. AA (modus ponens, 1,4) В ы в о д о м ф о р м у л ы Ф и з г и п о т е з A1, ..., Am (m 1) называют конечный спи-сок формул B1,...,Bl, заканчивающийся формулой Ф (Ф = Bl), где каждая формула Bi (i=1,...,l) есть аксиома или одна из гипотез A1,... ,Am, или получена из предыдущих формул по правилу вывода ( A1,... ,Am Ф). Пример 2 (Вывод формулы из гипотез). A&BC, A BC: 1. A&BC (гипотеза) 2. (BA&B) ((B(A&BC)) (BC)) (аксиома 1б) 3. (A&BC) (B(A&BC)) (аксиома 1а) 4. B(A&BC) (modus ponens,1,3) 5. A (гипотеза) 6. A (BA&B) (аксиома 2) 7. BA&B (modus ponens,5,6) 8. (B(A&BC)) (BC) (modus ponens,7,2) 9. BC (modus ponens,4,8) ТЕОРЕМА 9 (Cвойства вывода) 1. A1,...,Am i (i= ) 1,...,Am j (j= ) и B1,...,Bk C A1,...,Am C 3. A1,... ,Ai, ..., Aj, ..., Am B A1,...,Aj, ..., Ai, ..., Am B. 4. A1, ..., Am B A1, ..., Am , Am+1B. ТЕОРЕМА 10. (1) Если AB, то AB. (2) Если A1, ... , Am-1 AmB, то A1, ... , Am (m1). Следствие. Если A1( A2 ... (AmB) ...), то A1, ..., Am (m1). ТЕОРЕМА 11 (О дедукции). (1) Если AB, то AB . (2) Если A1, ..., Am то A1, ..., Am-1 AmB (m1). Д о к а з а т е л ь с т в о (2): Формулы данного вывода (I):A1,..., Am обозначим списком B1, ..., Bl. Переделаем вы-вод (I)в схему : Am B1 . . . Am Bi . . . Am Bl , a затем в вывод (11), обосновав выводимость каждой импликации Am Bi (i=1,...,l) из списка гипотез A1,...,Am -1 . 1случай: Если Bi есть аксиома или одна из гипотез Aj (j=1,...,m-1) в вы воде (I), то Bi также входит и в вывод (II), так что вхождение импликации AmBi в вывод (II) имеет обоснование с помощью аксиомы 1а: Bi Bi (Am Bi) (аксиома 1a) Am Bi (modus ponens) 2 случай: Если Bi есть гипотеза Am в выводе (I), то доказательство импликации AmAm приведено в примере 1. 3 случай: Bi получена в выводе (I) из предыдущих формул Bp, Bq=BpBi по правилу modus ponens. Обоснование вхождения импликации Am Bi в вывод (II) проводится с помощью аксиомы 1б индукцией по построению вывода (11) : . . . AmBp (по индукционному допущению) . . . Am(BpBi) (по индукционному допущению) (AmBp)((Am(BpBi)) (AmBi)) (аксиома 1б) (Am(BpBi)) (AmBi) (modus ponens) Am Bi (modus ponens) Пример, иллюстрирующий доказательство теоремы о дедукции : Если AB, CA, C |– B, то A B, CA |– C B. Вывод (I): 1. A B (гипотеза из списка A1,...,Am -1 ) 2. C A (гипотеза из списка A1,...,Am –1 ) 3. C (гипотеза Am ) 4. A (modus ponens, 3,2) 5. B (modus ponens, 4,1) Вывод (II): AB (гипотеза из списка A1,...,Am –1 ) (A B)(С(AB)) (аксиома 1а) 1* C(AB) (modus ponens) СA (гипотеза из списка A1,...,Am –1 ) (СA)(С(CA)) (аксиома 1а) 2* С(CA) (modus ponens) С(CC) (аксиома 1а) (С(CC))((С((СС)С))(СС)) (аксиома 1б) (С((СС)С))(СС) (modus ponens) С((СС)С) (аксиома 1а) 3* CС (modus ponens) (CC)((C(CA))(CA)) (аксиома 1б) (C(CA))(CA) (modus ponens) 4* CA (modus ponens) (CA)((C(AB))(CB)) (аксиома 1,б) (C(AB))(CB) (modus ponens) 5* CB (modus ponens) Следствие. Если A1,...,Am B, то A1(A2...(AmB)...) (m1). ТЕОРЕМА 12 (Непротиворечивость исчисления высказываний). Всякая доказуемая фор-мула общезначима, т.е., если B, то = B. Д о к а з а т е л ь с т в о следует из того, что аксиомы выбираются среди тавтологий, а правила вывода сохраняют истинность заключения при истинных посылках. Следствие. Не существует формулы B, такой, что B и B. ТЕОРЕМА 13 (Производные правила вывода). Аксиомы: Производные правила вывода: (введение ) (AC)((BC)(ABC)) (удаление ) (AB)(AB), (AB)(AB) (введение ) AA (AB)((A B) A) A(AC) Д о к а з а т е л ь с т в о. 1) : 3) A (допущение) A (допущение) АA (аксиома) ••• A (modus ponens) B (из первой посылки) A B (теорема о дедукции) A (допущение) 2) A,A C: ••• C,A,A A (теорема 9(1)) B (из второй посылки) C,A,A A (теорема 9(1)) A B (теорема о дедукции) A, A C (введение ) (A B) ((A B) A) A,A C (удаление ) A (modus ponens 2раза) Примеры построения доказательств 1) Первый закон де Моргана : (AB) A&B: (AB),A (AB) (AB), B (AB) (AB),A AB (AB), B AB (AB) A (AB) B (AB) A&B (AB) A&B A&B,A A A&B, B B A&B,A A A&B, B B A&B,A (AB) A&B, B (AB) A&B,AB (AB) A&B,AB (AB) A&B (AB) A&B (AB) (AB) A&B 2) AB AB 1. AB (допущение) 2. (AB) (допущение противного) 3. (AB) A&B (1-ый закон де Моргана) 4. (AB) A&B (удаление , 3) 5. A&B (удаление , 2,4) 6. A (удаление &,5) 7. A (удаление ,6) 8. B (удаление ,7,1) 9. B (удаление &, 5) 10. (AB) (введение , 2,8,9) 11. (AB) (удаление , 10) 12.(AB) AB (теорема о дедукции, 1,11) 13. AB (допущение) 14. A (допущение) 15a. A (допущение) 15b. B (допущение) 16a. B (слабое удаление ) 17. B (удаление , 13) 18. AB (теорема о дедукции, 14,17) 19. AB ( AB) (теорема о дедукции, 11,18) 20. (AB) AB (введение , 12,19) 3) Второй закон де Моргана : (A&B) AB (A&B), A, B A&B (введение &) (A&B), A, B (A&B) (теорема 9(1)) (A&B), A B (введение ) (A&B) A B (теорема о дедукции) (A B) AB (теорема из примера 2) (A B) AB (удаление ) (A B) AB (теорема 10(1)) (A&B) AB (теорема 9(2)) (A&B) AB (теорема о дедукции) A, A&B A B, A&B B (теорема 9(1)) A, A&B A B, A&B B (удаление &) A (A&B) B (A&B) (введение ) AB (A&B) (удаление ) AB (A&B) (введение) AB (A&B) (введение ) 4) Первый закон дистрибутивности: A&(B C) (A&B)(A&C): 1. A&(B C) (допущение) 2. A (удаление &) 3. BC (удаление &) 4а. B (допущение) 4б. C (допущение) 5а. A&B (введение &) 5б. A&C (введение &) 6а. (A&B)(A&C) (введение ) 6б. (A&B)(A&C) (введение ) 7. (A&B)(A&C) (удаление , 3) 8. A&(BC)(A&B)(A&C) (теорема дедукции,1,7) 9. (A&B)(A&C) (допущение) 10а. A&B (допущение) 10б. A&C (допущение) 11а. A (удаление &) 11б A (удаление &) 12a. B (удаление &) 12б. C (удаление &) 13а. BC (введение ) 13б. CB (введение ) 14а. A&(BC) (введение &) 14б. A&(BC) (введение &) 15. A&(BC) (удаление ,9) 16. (A&B)(A&C)A&(BC) (теорема дедукции,9,15) 17. A&(BC) (A&B)(A&C) (введение ) 5). Для множеств A,B,C верно утверждение AB C A C : 1. AB C (допущение) 18. A C (допущение) 2. x AB x C 19. x A x C 3. x A (допущение) 20. xAB (допущение) 4. (x C) (допущение противного) 21. xA&xB 5.(x xC) 22. xA (удаление &) 6.(x )(xC) (закон де Моргана) 23. xB (удаление &) 7.(x ) (удаление &) 24. x C (удаление ,22,18) 8. (xC) 25. x xC 9. x B 26а.x (допущение) 26б.xC(допущение) 10. xA&xB (введение &) 27а. xC (сл. уд.,23,26a) 11. xAB 28. xC (удаление ,25) 12. xC (modus ponens,11,2) 29. xAB xC 13.(x C) (введение ,12,8) 30. ABC 14. x C (удаление ,13) 31. A C ABC 15.xA x C (введение ,3,14) 32. AB C A C 16.A C 17.AB C A C(введение ) ТЕОРЕМА 14(Теорема о полноте исчисления высказываний). |= E |– E. Д о к а з а т е л ь с т в о будет получено с помощью следующих лемм: ЛЕММА 1. Для каждой из логических связок имеют место выводимости: A B A&B AB A И И И И Л A A И Л Л И Л A A Л И Л И И A A Л Л Л Л И A A Д о к а з а т е л ь с т в о. , B : 1. (допущение) 1. (допущение) 2. B (допущение) 2. (допущение) 3. A&B (допущение противного) 3. AB (допущение противного) 4. A (удаление &, 3) 4а. A (допущение) 4б. B (допущение) 5 (введение ) 5а. (сл. уд.) 5б. (сл.уд. ) 6. (удаление ,3) 7. (введение , 3, 6) ЛЕММА 2. Соответствующий вывод имеется для любой интерпретации (строки таблицы истинности) любой формулы. Д о к а з а т е л ь с т в о на примере формулы P(QR(RP)): P Q R QR P RP QR (RP) P (QR (RP)) 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 для шестой строки: 1. P,Q,R QR (лемма 1) 2. P,Q,R P (лемма 1) 3. P,Q,R RP (допущение противного) 4. P,Q,R P (*) 5. P,Q,R ( RP) (введение ,3) 6. P,Q,R QR(RP) (допущение противного) 7. P,Q,R RP (теорема 1(2)) 8. P,Q,R P (*) 9. P,Q,R (QR(RP)) (введение ,6) 10. P,Q,R P(QR(RP)) (допущение противного) 11. P,Q,R QR(RP) (*) 12. P,Q,R RP (теорема 1(2)) 13. P,Q,R P (*) 14. P,Q,R (P(QR(RP))) (введение ,10) ЛЕММА 3. Если = E[P1,...,Pn], где P1,...,Pn список всех переменных, входящий в форму-лу E, то P1P1,..., Pn Pn E. Д о к а з а т е л ь с т в о проведем на примере формулы E[P1,P2]: ЛЕММА 4. |– AA . Д о к а з а т е л ь с т в о. A, (AA) |– AA (введение ) A, (AA) |– (AA) (теорема 9(1)) ••• (AA) |– A (введение ) (AA) |– A (AA) (вве-дение ) |– AA (удаление ) Д о к а з а т е л ь с т в о теоремы о полноте: Пусть = E[P1,...,Pn]. По лемме 3 существует вывод . Вставляя в этот вы- вод дока-зательство каждой из формул Pi Pi (i=1,...,n), получим доказательство формулы E. 2 ИСЧИСЛЕНИЕ ПРЕДИКАТОВ 2.1. Предикаты В логике высказываний изучается структура сложных высказываний, составленных из элементарных неделимых высказываний. Логика предикатов анализирует субъектно-предикатную структуру простых суждений. Например, структура элементарного сужде-ния «снег белый» может быть представлена предикатом (свойством) «быть белым» и субъектом «снег», а, к примеру, структура элементарного cуждения «два делит пять» - предикатом «x делит y» и субъектами «два» и «пять». Абстрагируясь от конкретного содержания предикатов и субъектов, будем называть предикатами функции истинности J(n) (x1,...,xn), заданные на непустой области D (на-туральных чисел) и принимающие значения во множестве {И,Л}. Предикат J(n) (x1,...,xn) становится высказыванием после означивания входящих в него переменных на элементах множества D. А л ф а в и т: (1) x,y,z,...,x1,x2,... - предметные переменные; (2) P(n) (x1,...,xn),... - предикатные буквы (n=0,1,...); (3) &, , , , , , - логические связки и кванторы; (4) ( , ) - вспомогательные символы. Ф о р м у л ы: (1) P (n) (x1,...,xn), - элементарные формулы или атомы; (2) если A, B - формулы, то A&B, AB, A, AB, AB - формулы; (3) если A(x) - формула со свободной переменной x, то x A(x), x A(x) - формулы. Свободные и связанные вхождения переменных Переменные, находящиеся в области действия квантора по этой переменной называются связанными, иначе - свободными. Примеры: 1) : x - свободная переменная, n - связанная переменная. 2) y - свободная переменная, x - связанная переменная. 3) x (rm(y, x)=0)=f(y): y - свободная переменная, x - связанная переменная. 4) y P(y) & x Q(x,z)z (P(y,z)Q(z)) : первое вхождение переменной y - связанное, второе – свободное; x - связанная переменная; первое вхождение переменной z - свободное, второе -связанное. Значение формулы E[P1,...,Pm ; x1,...,xn] при интерпретации предикатных букв : P(n) J(n) и означивании : {x1,...,xn} D (D) предметных переменных, обозначается E[,], определим индукцией по построению формулы E : 1) E = P(n) (x1,...,xn), то E[,] = J[]; 2) E = (A&B)[P1,...,Pm ; x1,...,xn], то E[,] = A[,] & B[,]. Аналогично для остальных логических связок. 3) E=x1 A[P1,...,Pm;x1,...,xn], то E[,] = x1A[,x1,]=И, где : {x2,...,xn}D, если A [,a,] = И для любого aD. 4) E=x1A[P1,...,Pm; x1,...,xn], то E[,] = x1A[,x1,] = И, где : {x2,...,xn}D, если A [,a,] = И для некоторого aD. Формула E[P1,...,Pm; x1,...,xn] называется о б щ е з н а ч и м о й и л и т а в т о л о г и е й, если для любой области D , для любых интерпретаций преди-катных букв и любом означивании предметных переменных в области D, E[,] = И. Сразу становится понятным, что проверка общезначимости для предикатных формул с помощью таблиц истинности невозможна. Однако можно говорить, соответственно, об 1-общезначимости, 2-общезначимости и т.д. предикатных формул. Пример 1. Покажем, что формула P(x,y) Q(x) не 1-общезначима, следовательно, не обще-значима. Решение. D={1} - одноэлементная область, I1 и I2 - интерпретации буквы P, а J1 и J2 - интерпретации буквы Q: X y I1 I2 J1 J2 1 1 и л и л Истинностная таблица формулы P(x,y)Q(x) : x y P(x,y) Q(x) P(x,y)Q(x) 1 1 и и и 1 1 и л л 1 1 л и и 1 1 л л и Пример 2. Покажем, что формула x(x P(x)P(x)) не 2-общезначима. Решение. D={1,2}, J1, J2, J3, J4 - интерпретации буквы P : x J1 J2 J3 J4 1 и и л Л 2 и л и Л Истинностная таблица формулы x (x P(x)P(x)): x P(x) x P(x) x P(x)P(x) x(xP(x)P(x)) 1 2 J1 J1 И И И И 1 2 J2 J2 И И Л Л 1 2 J3 J3 И Л И Л 1 2 J4 J4 Л И И И ПРИМЕР 3. Покажем, что формула x y P(x,y)y x P(x,y) не общезначима. Решение. Пусть D={1,2}, тогда интерпретации предикатной буквы P(x,y) зададим сле-дующей таблицей: X y J1 J2 J3 J4 J7 1 1 и и и и И 1 2 и и и и Л 2 1 и и л л Л 2 2 и л и л И В частности, для интерпретации J7 получим: при x=1: y J7(1,y)И; при x=2: y J7(2,y)И, тогда x y J7(x,y) = И. При y=1: x J7(x,1)=Л, при y=2: x J7(x,2)=Л, тогда yx J7(x,y)=Л. Откуда x y J7(x,y)y x J7(x,y) = Л. Перенесение теорем об общезначимых формулах исчисления высказываний на исчис-ление предикатов требует осторожности. Частный случай теоремы 1 имеет место, если E[P1,...,Pn] - формула исчисления выска-зываний, а A1,...,An - произвольные формулы исчисления предикатов. Доказательство ос-тается прежним. Поэтому будут верны и теоремы 2,3, где A, B, C - произвольные фор-мулы исчисления предикатов. Из определения логических операций с кванторами следует общезначимость следующих формул: = P(y) x P(x), = x P(x) P(y). Чтобы распространить эти результаты на произвольные формулы A исчисления пре-дикатов, необходимо соблюдение следующего условия: ‘подстановки переменной ‘y’ вместо всех свободных вхождений переменной ‘x’ в формулу A(x) остаются свободными в формуле A(y) ’. Назовем такую подстановку ‘y’ свободной для ‘x’ в A(x). УТВЕРЖДЕНИЕ 1. а) = A(y) x A(x), б) = x A(x) A(y), где ‘y’ свободна для ‘x’ в A(x). УТВЕРЖДЕНИЕ 2. а ) = A(x)C = x A(x)C, б) = C A(x) = C x A(x), где формула ‘C’ не содержит свободных вхождений переменной ‘x’. Приведем набросок доказательства для случая б): Обозначим через FV(E) список свободных переменных формулы E. Допустим, что существует область D , такая, что при некоторой интерпретации предикатных букв и некотором означивании предметных переменных : FV(C x A(x)) D имеем (C x A(x)) [,] = Л, т.е.C[,] = И и (x A(x)) [,] = Л. Тогда (A(a)) [,] = Л для некоторого a D, но (C A(x)) [,] = И для всех , , что противоречит общезначимости формулы C A(x). Подстановка формулы A(w1,...,wn) вместо предикатной буквы P(w1,...,wn) на всех местах вхождения P(y1,...,yn) в формулу E[P(y1,...,yn)] называется свободной, если: (1) переменные y1,...,yn , соответственно, свободны для w1,...,wn, в формуле A(w1,...,wn); (2) после подстановки y1,...,yn вместо w1,...,wn, соответственно, ни одна свободная перемен-ная формулы A(y1,...,yn) не окажется связанной в формуле E* [A(y1,...,yn)]. Примеры подстановки формулы A(w) вместо предиката (атома) P(w) в формулу P(y) x P(x): (в примерах 1,3,5 подстановка будет свободной). A(w): P(y) x P(x) : 1. z Q(w,z,w) z Q(y,z,y) xz Q(x,z,x) 2. y Q(w,y,w) y Q(y,y,y) xy Q(x,y,x) 3. Q(w,u,w) Q(y,u,y) x Q(x,u,x) 4. Q(w,x,w) Q(y,x,y) x Q(x,x,x) 5. w P(w)Q(w) w P(w)Q(y) x (w P(w)Q(x)) ТЕОРЕМА 1 (Подстановка вместо атомов). Если подстановка формул A1( ,, ), , Am( ,, ) свободна в формуле E[P1,,Pm] для предикатных букв P1( ,, ),,Pm( ,, ), соответственно. Тогда, если = E[P1,...,Pm], то = E* [A1,,Am ]. Следствие. Если подстановка переменных y1,...,yn свободна для w1,...,wn, соответственно, в формуле A(w1,,wn), то = A(w1,,wn) = A(y1,,yn). ТЕОРЕМА 4 (Эквивалентность формул). = A B т.и т.т., когда для любой предметной области D и при любой интерпретации предикатных букв, и любом означивании предметных переменных на элементах области D, A[,] = B[,]. Формулы называются конгруентными, если после стирания в них всех связанных вхождений переменных, получаем одно и то же выражение. УТВЕРЖДЕНИЕ 3. Для конгруентных формул A и B верно = A B. Основные тавтологии исчисления предикатов (с кванторами): x A(x) xA(x) x A(x) xA(x) xy A(x,y) yx A(x,y) xy A(x,y) yx A(x,y) x A(x) &xB(x) x (A(x) & B(x)) x A(x)x B(x) x (A(x)B(x)) x A(x)x B(x) x (A(x)B(x)) x (A(x)&B(x)) x A(x) & x B(x) x (A(x)B(x)) (x A(x) x B(x)) Если формула C не содержит свободно x, то : x C C x C C x A(x) C x (A(x)C) x A(x) &C x (A(x)&C) Теоремы 6 и 7 могут быть обобщены в исчислении предикатов, если в описание операций ‘X’(‘крест’) и ‘/’ (‘штрих’) включить замену на и на . Формула B является логическим следствием формул A1,...,Am , если для любой об-ласти D и любых интерпретаций , , входящих в формулы A1, ... , Am , B преди-катных букв и свободных предметных переменных, в строках таблицы истинности, где A1[,] = ... =Am[,] = И, также и B[,] = И. Обозначим как A1, ... , Am = B. Данное определение соответствует условной интерпретации переменных в математике, при которой предикатные буквы и предметные переменные остаются фиксированными в контексте доказательства : x (x2-5x-6=0 x=6x = -1), в отличие от интерпретации всеобщности переменных : xy(x+y=y+x)2+3=3+2. При таком определении логического следствия теорема 8 и ее следствие обобщаются на исчисление предикатов. Доказательства там и здесь по сути совпадают. Примеры отношений логического следования: P(x)= P(x); P(x)=xP(x); P(x) = P(y); P(x)= xP(x); xP(x)= P(x); P(x) = xP(x). Из таблицы истинности увидим, какие из них имеют место. Пусть D={0,1}, проинтерпрети-руем на D предикатную букву P(1), так что: x y P(x) P(x) x P(x) P(y) x P(x) x P(x) 0 0 0 1 1 0 1 1 J1=и J1=и J1=и J1=и Л Л Л Л Л л л л л И Л 0 0 0 1 1 0 1 1 J2=и J2=и J2=л J2=л Л Л И И Л л и л и Л И 0 0 0 1 1 0 1 1 J3=л J3=л J3=и J3=и И И Л Л Л и л и л Л И 0 0 0 1 1 0 1 1 J4=л J4=л J4=л J4=л И И И И И и и и и Л И Очевидно, что верны следующие отношения логического следования: P(x)= P(x), P(x)= xP(x), xP(x)= P(x). Убедиться, что они верны без ограничений на число элементов области D. А отношения P(x)= xP(x); P(x) = P(y); P(x) = xP(x) не имеют места. 2. 2. Система аксиом в исчислении предикатов Схемы аксиом и правил вывода остаются теми же, что и для исчисления высказы-ваний, с формулами языка исчисления предикатов, к которым добавляются схемы ак-сиом и правил вывода, связанные с кванторами. А к с и о м ы: 1а A(BA) 1б (AB)((A(BC))(AC)) 2 A(BA&B) 3а A&BA 3б A&BB 4а AAB 4б BAB 5. (AC)((BC)(ABC)) 6. (AB)((A B) A) 7. AA 8. (AB)((A B) (A B)) 9а. A B (AB) 9б. A B (BA) 10. A (AC) и п р а в и л о в ы в о д а modus ponens . Н о в ы е а к с и о м ы и п р а в и л а в ы в о д а: 11 С A(x) C x A(x) (- введение) 12 x A(x)A(t) (- удаление) 13 A(x)C x A(x)C ( - удаление) 14 A(t)x A(x) ( - введение), где подстановка терма t свободна для переменной x в формуле A(x), и формула C не содержит свободно x. Ф о р м у л а B в ы в о д и м а и з ф о р м у л A1, , Am , если существует список фор-мул B1,,Bl такой, что Bl=B, и каждая формула Bi есть аксиома или одна из формул A1, …, Am , или получается из предыдущих формул по одному из правил вывода, где все свободные переменные формул A1, …, Am остаются фиксированными, т.е. правила с кванторами (, ) не применяются ни к какой переменной, входящей свободно в форму-лы A1, …, Am, кроме случаев, когда эти правила применялись до использования формул A1, …, Am в качестве допущений. ТЕОРЕМА (О дедукции). Если A1, …, Am B, то A1, …, Am-1 AmB, где примене-ние правил -введения и -удаления фиксированно для свободных переменных формул A1, …, Am . Д о к а з а т е л ь с т в о: Пусть вывод (I) - цепочка формул : . По выводу (1) строим схему: Переделаем эту схему в вывод (II): 1 случай: Bj – аксиома или одна из гипотез A1,…,Am в выводе (I). Если j < n, вывод (1) формулы Bj остается выводом (11). Для j > n и j = n доказательство как в исчислении высказываний. Рассмотрим вывод (11) для случая j > n : 2 случай. Если Bi получена в выводе (I) по правилу modus ponens, то рассмотрим сле-дующие случаи: (1) Bj появилась до Bn , т.е. j<n, тогда (I) и i,g<n. Поэтому вывод (1) есть вывод (11). (2) j>n : а) Если i,g<n, то (I) и в схеме: . Обоснуем вхождение Am Bj в вывод (II) : б) Если i>n и g<n, то в схеме соответственно имеем : AmBi и Bi Bj и AmBj . Тогда в (II): . Аналогично получается вывод (11), для c) g>n и i<n и d) i,g >n. 3 случай. Bj получена в выводе (I) по правилу - введения из формулы Bi: a) Если j<n, то i<n: обоснование формул Bi=CA(x), Bj=Cx A(x) в выводе (1) и выводе (II) совпадают. b) Если i<n и j>n, тогда в (II) : (правило - введения применимо в выводе (II): ‘x’ не входит свободно в формулы C и Am , т.к., соответственно, оно применялось в выводе (1) и переменная ‘x’ фиксированна относи-тельно Am в выводе (1) для j>n ). с) Если i>n, то j>n, тогда в схеме имеем AmBi и AmBj. Дальше доказательство AmBj строится, используя индукционное допущение, как в случае b). 4 случай. Формула Bj получена из Bi по правилу - удаления. Вывод (11) строится аналогично 3 случаю. Теорема дедукции на примере: x (P(x)Q(x)), x P(x) x Q(x) x (P(x)Q(x)) x P(x) x Q(x) Вывод (1): 1. x (P(x)Q(x)) (гипотеза Aj, jm) 2. x (P(x)Q(x)) (P(x)Q(x)) (аксиома) 3. P(x)Q(x) (modus ponens, 1 и 2) 4. x P(x) (гипотеза Am) 5. x P(x)P(x) (аксиома) 6. P(x) (modus ponens, 4,5) 7. Q(x) (modus ponens, 6,3) 8. Q(x)((PP)Q(x)) (аксиома 1а) 9. (PP)Q(x) (modus ponens, 7,8) 10. (PP)x Q(x) (-введение, 9) 11. PP (аксиома) 12. x Q(x) (modus ponens, 11,10). Переделаем вывод (I) в схему: 1. x (P(x)Q(x)) 2. x (P(x)Q(x)) (P(x)Q(x)) 3. P(x)Q(x) 4. x P(x) x P(x) (AmAm) 5. x P(x)(x P(x)P(x)) 6. x P(x)P(x) 7. x P(x)Q(x) 8. x P(x)(Q(x)((PP)Q(x))) 9. x P(x)((PP)Q(x)) 10. x P(x)((PP)x Q(x)) 11. x P(x)((PP)) 12. x P(x) x Q(x). Построим вывод (II): 1. x (P(x)Q(x)) (гипотеза Aj , j m) 2. x (P(x)Q(x)) (P(x)Q(x)) (аксиома) 3. P(x)Q(x)) (modus ponens, 1,2) ••• 4. x P(x)x P(x) (доказательство теоремы AA) ; x P(x)x P(x) (4) x P(x)(x P(x)P(x)) (5) (x P(x)x P(x)) ((x P(x)(x P(x)P(x)))(x P(x)P(x))) 6. x P(x)P(x) (modus ponens 2 раза) P(x)Q(x) (3) (P(x)Q(x)) (x P(x)(P(x)Q(x))) (аксиома 1a) x P(x)(P(x)Q(x)) (modus ponens) x P(x)P(x) (6) (x P(x)P(x))((x P(x)(P(x)Q(x)))(x P(x)Q(x))) 7. x P(x)Q(x) (modus ponens 2 раза) ; ; xP(x)(PP) (11) xP(x)((PP)xQ(x)) (10) (xP(x)(PP))((xP(x)((PP)xQ(x))) (xP(x) xQ(x))) (аксиома 1б) 12. xP(x) xQ(x) (modus ponens 2 раза) ТЕОРЕМА (Производные правила вывода). Производные правила исчисления высказыва-ний с формулами исчисления предикатов и новые правила с кванторами. ••• (-удаление) ( - введение) ( - введение) ( -удаление), где t свободно для x в A(x). где x не входит свободно в Г,C. ТЕОРЕМА 5(О замене). Если - A ~ B и E[A] -формула с выделенным вхождением под-формулы A, а E[B]=E[A] - результат замены этого вхождения на формулу B, x1,...,xp - свободные переменные формул A, B, попадающие в область действия кванторов фор-мул E[A] или E[B] при построении их, начиная с A, B, соответственно. Тогда если Г A B, то Г - E[A] ~ E[B], где Г список формул, не содержащих свободно переменные x1,...,xp . ЛЕММА. Пусть x – некоторая переменная, A(x) – произвольная формула, а y произволь-ная переменная, не обязательно отличная от x, такая, что: (a) ‘y’ свободна для ‘x’ в A(x), (ii) ‘y’ не входит свободно в A(x) (кроме случая, когда ‘y’ есть ‘x’), а A(y) есть результат подстановки ‘y’ вместо свободных вхождений ‘x’ в A(x). Тогда: (a) x A(x) y A(y); (b) x A(x) y A(y). УТВЕРЖДЕНИЕ. Если формулы A и B конгруентны, то - A ~ B. Примеры построения доказательств : 1). - x A(x)~x A(x) : 1. x A(x) (допущение) 2. A(x) (допущение противного) 3. x A(x) ( - введение) 4. A(x) ( - введение,2) 5. x A(x) ( - введение, 4) 6. A(x)x A(x) (теорема дедукции,1,5) 7. x A(x) (допущение) 8. x A(x) (допущение противного) 9. A(x) (допущение) 10 A(x) (- удаление,8) 11. x A(x) (слабое удаление ) 12. x A(x) ( - удаление,7) 13. x A(x) (-введение,8) 14. x A(x) x A(x) (теорема дедукции,7,12) 15. x A(x) x A(x)( - введение, 6,13). 2) x (P(x)Q(x)) x P(x) x Q(x) : x (P(x)Q(x)), x P(x) P(x)Q(x) (удаление) x (P(x)Q(x)), x P(x) P(x) (удаление) x (P(x)Q(x)), x P(x) Q(x) (удаление) x (P(x)Q(x)) x P(x) Q(x) (введение) x (P(x)Q(x)) x P(x) x Q(x) (введение) Формула вида Q1 x1…Qn xn A, где A бескванторная формула, а Qi есть или , назы-вается предваренной (или пренексной) нормальной формой. ТЕОРЕМА 9. У всякой формулы исчисления предикатов есть эквивалентная ей предва-ренная нормальная форма. ТЕОРЕМА (Геделя о полноте исчисления предикатов). - E = E. (Без доказательства). Следствие. Исчисление предикатов непротиворечиво. 2.3 Формальная арифметика Опишем теперь одну формальную систему, предназначенную для формализации элементарной теории чисел. А л ф а в и т: (1) символы алфавита исчисления предикатов: предикатные буквы, предметные переменные, логические связки и кванторы; (2) предикатная константа : = ; (3) функциональные константы : , +, • ; (4) предметная константа : 0 ; (5) вспомогательные символы : ( , ). Т е р м ы : (1) а , b, c , …- предметные переменные ; (2) 0 – предметная константа ; (3) если t, s – термы, то t , t + s, t • s – термы. Ф о р м у л ы: (1) t = s, где t, s – термы, - элементарные формулы; (2) если A, B – формулы, то A&B, AB, A, A B, A B, x A(x), x A(x) – формулы. А к с и о м ы и п р а в и л а в ы в о д а: (1) аксиомы исчисления предикатов 1-12 и правило вывода modus ponens; (2) нелогические аксиомы 1: 13* (Аксиома индукции) (A(0)& *a (A(a) * A(a*))) * *a A(a), где A(a) - произвольная формула; 14*. a* = b* * a = b; 15*. * (a* = 0); 16*. a = b * (a = c * b = c); 17*. a = b * a* = b*; 18*. a + 0 = a; 19*. a + b* = (a + b)*; 20*. a • 0 = 0; 21*. a • b* = a • b + a. ТЕОРЕМА 1. a = a. Д о к а з а т е л ь с т в о: 1. a=b*(a=c*b=c) (аксиома 16) 2. 0=0*(0=0*0=0) (аксиома 1а) 3. (a=b*(a=c*b=c))*((0=0*(0=0*0=0))*(a=b*(a=c*b=c)) (аксиома 1а) 4. (0=0*(0=0*0=0))*(a=b*(a=c*b=c)) (modus ponens) 5. (0=0*(0=0*0=0))**c (a=b*(a=c*b=c)) (введение *) 6. (0=0*(0=0*0=0))**b*c (a=b*(a=c*b=c)) (введение *) 7. (0=0*(0=0*0=0))**a*b*c (a=b*(a=c*b=c)) (введение *) 8. *a*b*c (a=b*(a=c*b=c)) (modus ponens) 9. *a*b*c (a=b*(a=c*b=c))* *b*c (a+0=b*(a+0=c*b=c)) (удаление *) 10. *b*c (a+0=b*(a+0=c*b=c)) (modus ponens) 11. *b*c (a+0=b*(a+0=c*b=c))* *c (a+0=a*(a+0=c*a=c)) (удаление *) 12. *c (a+0=a*(a+0=c*a=c)) (modus ponens) 13 *c (a+0=a*(a+0=c*a=c))*(a+0=a*(a+0=a*a=a)) (удаление *) 14. a+0=a*(a+0=a*a=a) (modus ponens) 15. a+0=a (аксиома 18) 16. a=a (2 раза modus ponens). ТЕОРЕМА 2. a=b * b=a. ТЕОРЕМА 3. a=b&b=c * a=c. ТЕОРЕМА 4. a=b * a+c=b+c. Д о к а з а т е л ь с т в о использует аксиому индукции. Докажем A(0) ( где A(0) a=b*a+0=b+0). 1. a=b (допущение) 2. a+0=a (аксиома 18) 3. b+0=b (аксиома 18) 4. ? =a+0*(?=b+0*a+0=b+0) (аксиома 16) 5. a+0=a * a=a+0 (теорема 2) 6. a=a+0 (modus ponens,2,5) (? есть a) 7. a=b+0 * a+0=b+0 (modus ponens 6,4) 8. ??=a * (??=b+0*a=b+0) (аксиома 16) 9. a=b * b=a (теорема 2) 10. b=a (modus ponens 1,9) (?? есть b) 11. b=b+0 * a = b+0 (modus ponens 10,8) 12. b+0 = b * b = b+0 (теорема 2) 13. b = b+0 (modus ponens 3,12) 14. a = b+0 (modus ponens 13,11) 15. a+0 = b+0 (modus ponens 14,7) 16. a = b*a+0 = b+0 (теорема дедукции 1,15) (т.е. A(0)) 17. A(c) (допущение) (докажем A(c*)) 18. a = b (допущение) 19. a+c = b+c (modus ponens 18,17) 20. a+c* = (a+c)* (аксиома 19) 21. b+c* = (b+c)* 22. a+c = b+c * (a+c)* = (b+c)* (аксиома 17) 23. (a+c)* = (b+c)* (modus ponens 19,22) 24. a+c* = (a+c)* & (a+c)* = (b+c)* * a+c* = (b+c)* (теорема 3) 25. a+c* = (a+c)* & (a+c)* = (b+c)* (введение & 20,23) 26. a+c* = (b+c)* (modus ponens 24,25) 27. b+c* = (b+c)* * (b+c)* = b+c* (теорема 2) 28. (b+c)* = b+c* (modus ponens 21,27) 29. a+c* = (b+c)* & (b+c)* = b+c* (введение & 26,28) 30. a+c* = (b+c)* &(b+c)* =b+c* * a+c*=b+c* (теорема 3) 31. a+c* = b+c* (modus ponens 29,30) 32. a=b * a+c* = b+c* (теорема дедукции 18,31) ( т.е. A(c*)) 33. A(c) * A(c*) (теорема дедукции 17,32) 34. *c (A(c)*A(c*)) (введение *,33) 35. A(0)&*c (A(c)*A(c*)) (введение & 16,34) 36. A(0)&*c (A(c)*A(c*))**c A(c) (аксиома 13) 37. *c A(c) (modus ponens 35,36) 38. A(c) (удаление *,37). ТЕОРЕМА 5. a=b * a•c=b•c ТЕОРЕМА ГЕДЕЛЯ (О неполноте формальной арифметики). Если *A13 ,..., *A21 Ф, то *A13,..., *A21 = Ф. Обратное неверно. (Без доказательства) Теорема Геделя о неполноте применима к любой рекурсивно аксиомати- зируемой системе, в которой представимы все разрешимые предложения. В частности, это верно для более сильных систем, чем арифметика Пеано. Тем самым нельзя избавиться от неполноты арифметики добавлением новых аксиом.2 2 . А Л Г О Р И Т М Ы 1 АЛГОРИТМЫ И ВЫЧИСЛИМЫЕ ФУНКЦИИ А л г о р и т м есть точное предписание, согласно которому по любому входному объекту из данного класса входных объектов можно эффективно получать выходные объекты. На-пример, алгоритм деления целых (вещественных) чисел “углом” или алгоритм умножения двух квадратных матриц порядка n. Ограничимся дискретными предписаниями, входные и выходные данные которых представляют собой конструктивные объекты. Конструктивные объекты можно кодировать словами в некотором алфавите, отсюда свойство массовости ал-горитма. Получив входное слово, алгоритм через конечное число элементарных шагов дол-жен построить выходное слово и закончить работу, или на данном входном слове предписа-ние ведет к бесконечной последовательности элементарных шагов, тогда алгоритм не опре-делен на этом слове. Алгоритм должен обладать свойством детерминированности, т.е. каж-дый элементарный шаг определяется предыдущей ситуацией. Наконец, выполнение вычис-лений определяется только предписанием (программой) и не зависит от внешних факторов. Точное (математическое) понятие алгоритма было дано А.Тьюрингом в 1936 году, ко-торое получило название машины Тьюринга. А.Тьюринг привел ряд доводов в пользу того, что любые вычислительные процедуры могут быть реализованы на его машине. ТЕЗИС ЧЕРЧА – ТЬЮРИНГА: Все интуитивно вычислимые функции являются эффективно вычислимыми. 1.1. Машина Тьюринга М а ш и н а Т ь ю р и н г а снабжена потенциально бесконечной памятью - лентой, раз-деленной на ячейки, где накапливается информация. В каждый момент количество инфор-мации конечно и не имеет верхней грани. На ленте записывается входное слово, черновая работа и выходное слово. Это - слова над внешним алфавитом А. У нас алфавит А = {0, 1} предназначен для вычисления арифметических функций f: NkN. Собственно машина, которая осуществляет вычисление, имеет конечное число возможных “состояний” – внутренний алфавит Q = {q0, q1,...,qs}, и преставляет собой конечный список правил вида: qia bqj, где i= 1,...,s; j=0,...,s; {R,L,S}; a,b A; qi, qjQ. В каждой ячейке рабочей части ленты записан один из символов внешнего алфавита. В каждый момент вре-мени t=0,1,... считывается содержимое одной ячейки и, согласно команде qia bqj,, символ a заменяется символом b и происходит сдвиг на следующую ячейку, соответственно, вправо (R), влево (L), на месте (S), после чего управление передается команде qjc ... , где с - сим-вол ячейки, куда сдвинулась головка. Состояние q0 означает прекращение работы машины. Машина Тьюринга вычисляет частичную арифметическую функцию f(k)(x1,...,xk), если ма-шина Тьюринга всякий набор (a1, ...,ak ) Arg f перебатывает в число b=f(k)(a1,...,ak). Функция называется вычислимой на машине Тьюринга, если сущеставует вычисляющая ее машина. Для удобства вычислений договоримся о следующем: 0 будет изображаться , 1,соответственно, - и т.д. ; вычисления начинать с левого конца слова, записанного на лен-те машины, и заканчивать в начале заключительного слова, стерев предварительно черновую работу; кортежи изображать наборами с пробелами - 0. Примеры вычислений на машине Тьюринга : 1. “x+y”: 2. “rm(x,3)”: 3. ‘x<y(x,y)”: q11 1Rq1 q11 0Rq2 q1 1 1Rq1 q600Lq6 q1 01Lq2 q21 0Rq3 q10 0Lq2 q611Sq2 q2 11Lq2 q3 10Rq4 q21 0Lq3 q300Sq7 q20 0Rq3 q410Rq2 * q31 1Rq4 q700Rq7 q31 0Rq4 q 2 01Sq0 q40 0Rq4 q710Rq8 q41 0Rq0 q 301Lq2 q4 1 0Rq5 q 4 01Lq3 * q51 1Lq6 (x=y) (x<y) (xy) 1.2. Частично рекурсивные функции Второе направление уточнения понятия алгоритма проходило по пути уточнения класса вычислимых объектов (вычислимых функций и разрешимых множеств). Рассмотрим здесь систему С.Клини - класс рекурсивных функций. Доказано, что вычислимая на машине Тью-ринга функция является рекурсивной и, наоборот, для всякой рекурсивной функции найдется вычисляющая ее машина Тьюринга. Это говорит об эквивалентности данных определений. В настоящее время известно несколько эквивалентных понятий алгоритма и вычислимости (машины Тьюринга, нормальные алгоритмы Маркова, продукции Поста, Эрбран-Геделевское исчисление равенств, частично рекурсивные функции С.Клини и др.) . 1.2.1. Класс примитивно рекурсивных функций Начнем с определения простейшего класса рекурсивных функций – класса п р и м и т и в н о р е к у р с и в н ы х ф у н к ц и й, строящегося из базисных функций с помощью вы-числимых операторов. Базисные примитивно рекурсивные функции: O(x)=0 ; S(x)=x+1 (функция следова-ния); (i=1,…,n) (проектирующие функции). Вычислимые операторы: 1) О п е р а т о р с у п е р п о з и ц и и C[g,g1,,gm] = f: g(m)( = f(x1,,xn). (x1,,xn)- -(y1,,ym)-g(y1,,ym) = f(x1,,xn), останов. 2) О п е р а т о р п р и м и т и в н о й р е к у р с и и R(gn,hn+2)= f n+1 : (рекурсия ведется только по одному аргументу и функция на каждом шаге вычисляется че-рез себя же на предыдущем шаге). Вычислим функцию f на кортеже (x,y,z): (0,y,z) - (y,z) - g(y,z)=w0, останов, если x=0 (где w0=f(0,y,z)), а если x0, то (1,y,z) -(o,y,z,w0) - h(0,y,z,w0 ) = w1, останов, если x=1 (где w1=f(1,y,z)) и т.д. В частности, для одноместной функции f(y) = . Примеры примитивно рекурсивных функций (прф): 10. Неправильная суперпозиция задает ПРФ. Покажем это на примере: g (g1(x), g2(x,z), g3(y,z)) = f(x,y,z). Сведем эту суперпозицию к правильной: f(x,y,z) = g(g1(x), g2(x,z),g3(y,z))= g(g1(x),g2(x,z),g3(y,z))=g(g1(I (x,y,z)),g2(I (x,y,z),I (x,y,z)),g3(I (x,y,z),I (x,y,z))) =g( (x,y,z), (x,y,z), (x,y,z)). 20. Введение (удаление) фиктивных переменных сохраняет примитивную рекурсивность функций. Покажем на примере: Пусть f(x,y) – ПРФ и g(x,y,z) = f(x,y). Тогда g(x,y,z) = f(x,y) = f(I (x,y,z), I (x,y,z)) - имеет примитивно рекурсивное описание. 30. f (x,y) = x+y = ; 40. Усеченная разность x y = Свойства усеченной разности: (1) x • y = S(x) • S(y) (2) x +(y • x) = y+(x • y) (3) x • (y+z) = (x • y) • z (4) (x • y) • z = (x • z) • y Докажем свойство (3): Индукция по y : Базиc y =0: x • (0+z) = x • z = (x • 0) • z. Индукционный шаг: x • (y+z) = (x • y) • z (индукционное допущение). Докажем равенство : x • (y+z) = (x • y ) • z (‘y’ - фиксировано). Индукция по x (внутри индукционного шага по y): Базис: x = 0: 0 • (y +z) = (0 • y ) • 0. Индукционное допущение по x: x • (y +z) = (x • y ) • z (x ,y – фиксированы). Докажем для x : x • (y + z ) = x • S(y + z ) = (по свойству 1) x • (y + z) = (по индукци-онному допущению по y) (x • y ) • z ; (x • y ) • z = (по свойству 1) (x • y ) • z. Таким образом, для всех x, x • (y + z ) = (x • y ) • z, откуда для всех y : x • (y+z) = (x • y) • z, ч.т.д. Рассмотрим частный cлучай усеченной разности: J(x)=x 1 = . Докажем ее примитивную рекурсивность: . Примитивно рекурсивное описание функции x • y : x • 0 = x = I11(x) x • y / = x • (y+1) = (x • y) • 1 = J(x • y), далее из примера 20. 50. Модуль разности x - y - ПРФ (см. упражнение). 70. sg (x)= , (x) = 1 • x - ПРФ (см. упражнение) 80. Остаток от деления ‘x’ на ‘y’, т.е. rm (x,y) – ПРФ : = S(rm (x,y)) sg y - S(rm (x,y)). 90. (x) – число делителей числа x - ПРФ (см упражнение). О п е р а т о р м и н и м и з а ц и и ( - о п е р а т о р) : [g] = f f (x1,,xn) = z (g (x1,,xn,z) = 0): (x1,,xn) - g (x1,,xn,0) Эта процедура может быть бесконечна, тогда появляются точки разрыва, т.е. - оператор может порождать не всюду определенные функции. О г р а н и ч е н н ы й - о п е р а т о р : f(x1,,xn) = z a (g(x1,,xn,z)=0). Заметим, что если на интервале [0, a] для всех z g(x1,,xn,z) 0, то в точке (x1,...,xn) функция f (x1,,xn) может быть доопределена (в отличие от случая задания функции посредством произвольного - оператора, где в этом случае может быть нарушена од-нозначность функции). 100. Ограниченный - оператор определяет примитивно рекурсивные функции. Докажем на примере функции f (x) = z a (g (x,z) = 0) : g (x;0) 0 g (x,0)g (x;1) 0 ••• g (x,0)g (x,1)...g (x, i) = 0 ••• g (x,0)g (x,1)... g (x,a) Тогда f (x) = z a (g (x,z) = 0) = . Множество (отношение, предикат) называют примитивно рекурсивным, если такова его характеристическая функция. 110. Свойство ‘быть простым числом’ представимо предикатом Pr (x) ( (x) = 2) (| (x) - 2 = 0), т.ч. Pr (x) = sg | (x) - 2|, т.е. Pr (x) – ПРП. Последовательность простых чисел: Р0 = 2, Р1 = 3, Р2 = 5, Р3 = 7, ... 120. (x) - число простых чисел, предшествующих x, –ПРФ (см. упражнение). 130. Функция Pn = P(n) - (n+1)- е простое число - ПРФ: Pn+1 = z ((z) = n+2) = z ( |(z) - (n+2)| = 0). Покажем, что Pn+1 < : P0 = 2 P1 = 4 ••• Pn . Докажем, что Pn+1 , перемножая вышестоящие неравенства: = ,т.ч. P0P1...Pn+1< . Т.к. для всех j = 1,...,n Pj не делит P0P1...Pn+1, представление P0P1...Pn+1 в виде произ-ведения степеней простых чисел начинается с некоторого Pk, где k n +1, так что Pn+1 = P0P1...Pn+1 , т.е. .Pn+1 . 140. Пусть , то k = exp(n,x) – ПРФ. Для доказательства воспользуемся ограниченным -оператором: k = exp(n,k) = z n ( . 150. x = у , x y - ПРО (см. упражнение). 160. Конечное множество - ПРМ. Покажем это на примере множества А={a,b}. Его характеристическая функция Таким образом, А(x) = sg (|x - a||x - b|) - ПРФ. ТЕОРЕМА. Класс примитивно рекурсивных множеств (отношений) замкнут относитель-но операций ,, (дополнение). Т.е. если А,В - ПРМ, то АВ, АВ, А - ПРМ. Д о к а з а т е л ь с т в о проведем для : {АВ - ПРМАВ - ПРФ) 1 A,B - ПРФ 2 А, В - ПРФ (по определению ПРМ) 3. хАВ хАхВ А(x) = 0 В(x) = 0 А(x)В(x) = 0, т.е. АВ(x) = А(x)В(x) – ПРФ. ТЕОРЕМА. Класс ПРП замкнут относительно &, , . Д о к а з а т е л ь с т в о проведем для & : P(x), Q(x) - ПРП, т.e. P, Q - ПРФ. Тогда P &Q = sg (P +Q ) - ПРФ. 170. Примитивную рекурсивность функции - константы можно доказать индукцией по n (см. упражнение). ТЕОРЕМА. Класс ПРП замкнут относительно ограниченных кванторов. Д о к а з а т е л ь с т в о. P(x) - ПРП, докажем ПРП xa P(x): xa P(x) P (0) ... P (a), что доказывает примитивную рекурсивность ограниченного квантора . (Аналогично для ограниченного квантора ). Возвратная рекурсия Функция f (x1 ,…,xn ,y) получается из функций gn, hn+s+1, 1,…,j возвратной рекурсией, если она определена схемой: где функции i (y+1) y (i=1,…,j) задают один из предыдущих шагов. ТЕОРЕМА. Возвратная рекурсия сводится к примитивной рекурсии, т.е. функция, заданная возвратной рекурсией - примитивно рекурсивна. Д о к а з а т е л ь с т в о. Введём вспомогательную функцию . Покажем, что F(x1,...,xn,y) – ПРФ, откуда f (x1,...,xn,y) = exp (F(x1,...,xn,y),y) также ПРФ. =H(x1,...,xn,F(x1,...,xn,y)) . Таким образом, F(x1,...,xn,y) – ПРФ, ч.т.д. Пример функции, задаваемой возвратной рекурсией - числа Фибоначчи : F(0)=1, F(1)=1, F(n+2)=F(n)+F(n+1). Упражнение 1. Построить машины Тьюринга, вычисляющие функции: 2•x, x - y, sg x, max (x,y), min (x,y), x • y, [x /2], [ ], [x /y], x•y. 2. Построить машины Тьюринга, вычисляющие простейшие ПРФ: O,S,In, и машины, моделирующие операторы : суперпозиции, примитивной рекурсии, ограни-ченный - оператор. 3. Построить машины Тьюринга, разрешающие отношения: x = y, x y, x + 2 y, ‘x – четное’, ‘3 делит x’, ‘x = y (mod 4)’, ‘x • 3 = y’. 4. Доказать, тотальность (всюду определенность) ПРФ. 5. Доказать примитивную рекурсивность функций из примеров 50, 60, 70, 90, 100, 120,140, 160,170 , 190. 6. Доказать, что функции f и g – ПРФ, если функции h1, h2 – ПРФ: 7. Доказать ПРФ: d (x,y)(нод) и k (x,y)(нок). 8. Доказать ПРФ long(x) – номер наибольшего простого делителя числа x. 9. Доказать, что график ПРФ есть ПРМ. 10. Доказать, что сумма делителей числа ‘x’ есть ПРФ. 11. Доказать, что число простых делителей числа ‘x’ есть ПРФ. 12 .Доказать, что множество значений возрастающей функции есть ПРМ. 13. Доказать, что всякая ПРФ может быть получена из функций S(x), q (x) = x • [ ]2 с помощью операций суперпозиции, итерации и сложения двух функций (теорема Робинсона). 14. 1(x1,…,xn), если f1(x1,…,xn) = 0, g(x1,…,xn) = ••• s(x1,…,xn), если fs(x1,…,xn) = 0, где 1,…, s,f1,…,fs – ПРФ и одно и только одно из условий fi = 0 (i=1,…,s) имеет место. Доказать, что g – ПРФ. 15. Доказать, что функция f (x), получающаяся с помощью оператора примитивной ре-курсии из числа ‘a’ и функции ‘g(x,y)’, может быть получена c помощью операторов итерации1) и суперпозиции из ‘a’ и функций g, O, S, In и c, l, r2). 16. Класс функций, строящихся из простейших функций O,S, In с помощью операторов суперпозиции, примитивной рекурсии и ‘тотального’ -оператора, называют общерекур-сивными ( или рекурсивными) функциями. Доказать, что существует в точности 0 рекурсивных функций; 17. Приведем пример общерекурсивной функции A(x), не являющейся, примитивно рекурсивной, функции Аккермана : B(0,y) = 2+y, B(x+1,0) = sg(x), B(x+1,y+1) = B(x,B(x+1,y)), где A(x) = B(x,x). (Доказательство см. в [3]). Канторовская нумерация Канторовская нумерация есть нумерация пар и n - ок натуральных чисел. Располо-жим упорядоченные пары натуральных чисел в порядке возрастания суммы их членов, а в группах с одинаковой суммой - по возрастанию первого члена: (0,0)<(0,1)<(1,0)<...<(0,x+y)<...<(x,y)<...<(x+y,0)<... S=0 S=1 S=x+y Число членов в группе с суммой S равно S+1. Обозначим через c(x,y) канторовский номер пары (x,y), который равен числу пар, предшествующих паре (x,y). Таким образом, c(0,0)=0, c(0,1)=1, c(1,0)=2,..., c(x,y)=1+2+...+(x+y)+x=(1+x+y)(x+y)/2+x= +x. Покажем, что отображение c:NxNN взаимно однозначно «на». Однозначность c(x,y) оче-видна, т.к. (x,y) = (a,b) x = a & y = b, откуда c(x,y) = c(a,b). Доказательство обратной однозначности функции c(x,y) проведем средствами формальной арифметики, определяя отношение x>a формулой r (r>0&x=a+r). Докажем импликацию: c(x,y) = с(a,b)(x,y)=(a,b): 1. c(x,y)=c(a,b) (допущение) 2. 3. (x,y) (a,b) (допущение противного) 4. (x = a & y = b) 5. x a y b (по закону де Моргана) 6a. x a (допущение) 6б. y b (допущение) 7a. x > a x < a 7б. y < b y > b 8a. x>a (допущение) 8a. x<a (допущение) 8б. xa(допущение противного) 9a. r (r>0&x=a+r) 10a. r>0&x=a+r (допущение) ••• 11а. r>0 (удаление &) (далее, как на ветке (а), 12a. x=a+r (удаление &) получаем противоречие) 13a. 9б. x = a (введ., удал.) 14a. &c=a+r+y+1 10б. 15a. 11б. 16a. 12б. y=b 17a. 13б. противоречие 18a. 19a. a+r+y+1<a+b+1 (из 16а и свойств ) 20a. y+r < b (из 19a) 21a. s (s>0&b= y+r+s) 22a. s>0&b=y+r+s (допущение) 23a. s>0 (удаление &) 24a. b=y+r+s (удаление &) 25a. & s>0 26 a. &s>0 (из 18a и 25а), т.е. противоречие 27a. противоречие (удал.,21a) ••• 28 а противоречие (удал.,9a) 28а. противоречие (получено как на а) 29а. противоречие (удал.,7a) 30. противоречие (удаление, 5) 31.(x,y) = (a,b) (введение ,3, удал.) 32 c(x,y) = c(a,b) (x,y) = (a,b) (введ.,1,31). Покажем, что c(x,y) есть отображение «на», т.е. nN (x,y) n = c(x,y). Доказательство проведем индукцией по n. Базис: n=0 c(0,0)=0, n=1 c(0,1)=1. Индукционный шаг: n = c(x,y) = (индукционное допущение) если y>0. если y=0, так как (x,0) < (0,x+1) и c(x,0) = n, то n+1 = c(0,x+1). Обратные канторовские функции l(n), r(n): c(l(n),r(n)) = n и l(n) n, r(n) n. Как следует из их описания в [3], обратные канторовские функции l(c(x,y)), r(c(x,y)) при-митивно рекурсивны. Определим по индукции канторовские функции для произвольной n-ки: cn+1(x1,...,xn+1) = c(cn(x1,...,xn),xn+1). Если cn(x1,...,xn) = z, то xn = r(z), xn-1 = rl(z), xn-2 = rll(z), . . . , x2 = rl....l(z), x1 = l....l(z), n-2 n-1 которые, очевидно, также примитивно рекурсивны. 1.2.2. Рекурсивно перечислимые множества и предикаты Класс функций, построенных из базисных функций o(x), s(x), (i=1,…,n) c помощью операторов C, R, , называется классом частично рекурсивных функций (ЧРФ). Если ограничиться тотальным - оператором (порождающим тотальные функции), то по-лучим класс всюду определенных ЧРФ или общерекурсивных функций (ОРФ). ТЕЗИС ЧЕРЧА-КЛИНИ: Любая интуитивно вычислимая функция является частично ре-курсивной функцией. Подобно тому, как с примитивно рекурсивными функциями были соотне-сены примитивно рекурсивные множества (отношения и предикаты), так и с частично рекурсивными (общерекурсивными) функциями соотносятся ре-курсивно перечислимые (рекурсивные) множества (отношения и предика-ты). Множество (отношение, предикат) называют рекурсивно перечислимым, если найдется ПРФ g такая, что соответственно xA y (g(x,y)=0) (P(x) y (g(x,y)=0)) УТВЕРЖДЕНИЕ 1. Всякое примитивно рекурсивное множество (предикат) является рекур-сивно перечислимым. Обратное не верно. Д о к а з а т е л ь с т в о по определению. ТЕОРЕМА. (1) Класс рекурсивно перечислимых множеств замкнут отно -сительно опе-раций , . (2) Класс рекурсивно перечислимых предикатов замкнут относительно операций , , . Д о к а з а т е л ь с т в о. Докажем некоторые из утверждений. (1) Пусть A,B – рекурсивно перечислимые множества, докажем для AB: xAB xA & xB y (g(x,y)=0) & y (f(x,y)=0) (где f,g – ПРФ) y (g(x,y)=0 & y (f(x,y)=0)) y z (g(x,y)=0 & f(x,z)=0) n (n=c(y,z) & g(x,l(n))=0 & f(x,r(n))=0) n (g(x,l(n))+f(x,r(n))=0) n (Ф(x,n)=0), где Ф – ПРФ, как суперпозиция ПРФ. (2) Пусть P(x,y) – РПП, докажем для y P(x,y): P(x,y) z (f(x,y,z)=0), y P(x,y) yz (f(x,y,z)=0) n (n=c(y,z) & f(x,l(n),r(n))=0) n Ф(x,n)=0), где Ф – ПРФ, как суперпозиция ПРФ. УТВЕРЖДЕНИЕ 2. Если f – ПРФ, то Val f (множество значений функции f) – РПМ. УТВЕРЖДЕНИЕ 3. Если f – ПРФ и f – монотонно возрастает, то Val f – ПРМ. Д о к а з а т е л ь с т в о проведем для случая, когда Val f бесконечно. Допустим, что xy (y = f(x)). Тогда x (x > y y f(x)), т.е. x (y = f(x) x > y). Ввиду того, что функция f монотонно возрастает: x > y f(x) > f(y), или x > y = f(x) > f(y) = ff(x). Отсюда x > y = f(x) > ff(x) > >fff(x) и т.д., так что на конечном интервале [0,y] располагается бесконечно много натуральных чисел, что составляет противоречие. Следовательно, yVal f x y (y = f(x)), т.е. Val f – ПРМ. ТЕОРЕМА (Н. и д. условие рекурсивной перечислимости множеств). A , то A – РПМ f – ПРФ (A = Val f). Д о к а з а т е л ь с т в о. 1. A и A – РПМ (допущение) 2. bA (допущение) 3. xA y (g(x,y)=0), где g – ПРФ. 4. xA y (g(x,y)=0) 5. xA (допущение) 6. y (g(x,y)=0) ( удаление) 7. g(x,y) (допущение) 8. найдем z=y (g(x,y)=0) 9. и по паре (x,z) вычисляем с(x,z)=t. Положим f(t) = l(t) g(l(t),r(t))+b sg g(l(t),r(t)). Тогда очевидно A = Val f. Обратно, если A=Val f, где f – ПРФ, то, по утверждению 2, A – РПМ. ТЕОРЕМА (Поста). Если множества A, – РПМ, то A (тогда и ) -рекурсивное множе-ство. Д о к а з а т е л ь с т в о. Множества A, – РПМ, поэтому существуют ПРФ f, g, такие, что xA y(g(x,y)=0), x y (f(x,y)=0). Функция h(x) = y (f(x,y)g(x,y)=0) – ОРФ, т.к. f(x,y)g(x,y)=0 определено для любого x. Тогда, очевидно, A(x) = sg f(x,h(x)) – ОРФ, следовательно, A – рекурсивное множество. Обратное также верно. 1.2.3. Порожденные множества Алгеброй называют непустое множество A с определенными на нем частичными опера-циями F(m): AmA. Непустое подмножество множества A, замкнутое относительно операций алгебры A, на-зывается подалгеброй алгебры A. УТВЕРЖДЕНИЕ. Пусть VA и {Ai; iI} – семейство подалгебр алгебры A, содержащих подмножество V. Тогда есть наименьшая подалгебра алгебры A, содержащая подмножество V, обозначим ее через <V>. Д о к а з а т е л ь с т в о (см. упражнение). ТЕОРЕМА. <V> = T, где T – множество всех значений термов в A. Д о к а з а т е л ь с т в о (cм. упражнение). ТЕОРЕМА. Множество <V>, порожденное РПМ ‘V’ с помощью конечной системы ПРФ {Fi; i=1,…,n}, будет РПМ. Д о к а з а т е л ь с т в о. 1. Пусть V – РПМ, тогда существует ПРФ ‘v’ такая, что V = Val v. 2. <V> = {t(a1,…,am); a1,…,amV}, или, учитывая 1, <V> = {t(v(b1),…v(bm)); b1,…,bmN}. 3. Закодируем v - термы: код терма v(b) есть 3b ; код Fi (t1,…,t m ) есть 2i p1C …pm Cm , где c1,…,cm соответственно коды термов t1,…,tm . Очевидно, что не каждое натуральное число является кодом v-терма, но декодирование од-нозначно. 4. Строим функцию f таким образом, что f(n) есть значение v-терма с кодом n, если n - код v-терма, в противном случае f(n) есть значение какого-то v-терма: f(0)=v(0) F1(f(exp(n+1,1)),…,f(exp(n+1),m1)), если exp(n+1,0) = 1 . f(n+1)= . F1(f(exp(n+1,1)),…,f(exp(n+1),ms)), если exp(n+1,0) = s v(exp(n+1,1)) – для остальных n или f(0)=v(0) f(n+1)=G(n, f(exp(n+1,1)),…,f(exp(n+1,t))), где t = max{m1,…,ms}, где G(n,x1,…,xt) = v(exp(n+1,1)) sg Функция f(x) задана возвратной рекурсией, следовательно, f – ПРФ. 5. Индукцией по n докажем, что f(n)<V> для всех n. Базис: n=0 или n=1: f(0) = f(1) = v(0)<V>. Индукционный шаг: Допустим, что f(m)<V> для всех m n и докажем для f(n+1): (1) (n+1) – код v-терма Fi (t1,…,tm ): n+1 = 2i p1A … pm Am , где A1,…,Am – коды термов t1,…,tm ; из 4: f(n+1) = Fi (f(A1),…,f(Am )). Так как Aj n (j=1,…,mi), то f(Aj) = tj, так что f(n+1) = Fi (t1,…,tm )<V>. (2) (n+1) – не является кодом v-терма: exp(n+1,i) = Ai n; из 4: f(n+1) = Fi (f(A1),…,f(Am )) (i=1,..,s) или f(n+1)=v(A1). Т.к. Aj n, то f(Aj) = tj (где tj – терм, не обязательно с кодом Aj), тогда f(n +1) = Fi (t1,…,tm )<V> или f(n+1) = v(A1)<V>. Таким образом, для всех n, f(n)<V>, т.е. Val f <V>. Обратное включение следует из по-строения функции f. Т.к. <V>=Val f, где f – ПРФ, тогда по утверждению 2, <V> - РПМ. 1.2.4. Функции на n - ках Множество A n-ок натуральных чисел называется примитивно рекурсивным (рекур-сивным, рекурсивно перечислимым), если таковым является множество C(A) номеров n-ок из A. Например, A – ПРМ, если явля ется ПРФ его характеристическая функция: C(A)(z) = A(сn1(z),…,сnn(z)) или C(A)(с(x1,…,xn)) = A(x1,…,xn). Доказанные прежде утверждения о множествах переносятся на множества n-ок. ТЕОРЕМА (О параметризации). A – множество n – ок, A , то A – РПМ т. и т. т .,когда f1,…,fn – ПРФ (x1,…,xn)A t ((x1,…,xn)=(f1(t),…,fn(t)). Д о к а з а т е л ь с т в о. (1) Пусть A – РПМ, тогда, по определению, C(A) – РПМ и по утверждению 2 C(A) = Val f, где f – ПРФ. Тогда (x1,…,xn)A t C(x1,…,xn)=f(t) и xi = Cni (f(t)) = fi (t) , где fi – ПРФ как суперпозиция ПРФ. (2) Пусть f1,…,fn – ПРФ ((x1,…,xn)A t (x1,…,xn)=(f1(t),…,fn (t))), тогда C(x1,…,xn)=C(f1(t),…,fn (t))=f(t), т.е. f – ПРФ. Таким образом, C(A)=Val f, т.е. C(A) - РПМ, следовательно, A – РПМ. ТЕОРЕМА (О графике ЧРФ). f - ЧРФ график f – РПМ . (без доказательства) Следствие 1. Область определения ЧРФ есть РПМ. Следствие 2. Множество значений ЧРФ есть РПМ. Следствие 3. Множество решений уравнения f(x1,…,xn)=0, где f – ЧРФ, есть рекурсивно перечислимое множество (РПМ). Д о к а з а т е л ь с т в о. (x) = t (x + t=0) – ЧРФ, определенная только для x=0. Тогда {(x1,…,xn); f(x1,…,xn) = 0} = Arg (f(x1,…,xn)) – РПМ. ТЕОРЕМА. Если F(n) – тотальная функция, график которой – РПМ, то F(n) – общерекурсивная функция (ОРФ). Д о к а з а т е л ь с т в о. График F = {(x1,…,xn,y); y = F(x1,…,xn)} - РПМ, то по теореме о параметризации существуют ПРФ f1,….,fn, fn+1 такие, что (x1,…,xn,y)гр F t ((x1,…,xn,y) = (f1(t),…,fn(t),fn+1(t))). Так как F(x1,…,xn)=fn+1 ( t (x1-f1(t)+…+xn-fn(t)) = 0), то F – ОРФ. С функцией F(1,…,m)=, где i = (xi1,…,xin) (i=1,…,m), = (y1,…,yn) связаны координат-ные функции: yj = fj(x11,…,x1n,…, xm1,…,xmn ) (j=1,…,n) и представляющая функция: f(a1,…,an)=a, где ai=C(i) (i=1,..,m), a=C(). Функция F(1,…,m)= называется ЧРФ (ОРФ, ПРФ), если такова её представляющая функция f(a1,…,an) = a. УТВЕРЖДЕНИЕ. Функция F(1,…,m)= - ЧРФ (ОРФ, ПРФ) т. и. т. т., когда таковы её коор-динатные функции (представляющая функция). 1.2.5. Рекурсия 2-ой ступени Допустим, что мы хотим задать функцию F(x,y) рекурсией не по одному, а сразу по двум аргументам. Тогда надо предварительно упорядочить пары натуральных чисел (x,y), скажем следующим образом: (0,0)<(0,1)<…<(1,0)<(1,1)<…<(2,0)<(2,1)<… , т.е. (x1,y1)<(x2,y2), если x1<x2 или если x1=x2, то y1<y2. Функция F(x,y) задана рекурсией 2-ой ступени через тотальные функции G(x0,…,xm), H(x0,…,xk), fi(x)x, gj(x)x (i=1,…,m; j=1,…,k), если для всех значений n, x: F(0,x) = h(x), F(n+1,0) =H(n, F(g1(n),F(g2(n),0)), F(n,0),F(g3(n),0),…,F(gkk(n),0)), (*) F(n+1,x+1)=G(n+1,F(f1(n),F(n+1,x)),F(f2(n),F(f3(n),x+1)),F(f4(n),x+1),…, F(fm(n),x+1)) ТЕОРЕМА (О рекурсии 2-й ступени). Функция F(x, y), заданная рекурсией 2-й ступени относительно ПРФ G, H, h, fi (i=1,…,m), gj (j=1,…,k), есть ОРФ. Д о к а з а т е л ь с т в о. Не теряя общности, рассмотрим случай m=4, k=3. 1). Как следует из построения, функция F всюду определенная. Если график F – РПМ, то по теореме F(x, y) – ОРФ. 2). Из первого равенства имеем: (a, x, h(x)) графику F. 3). Из второго равенства (*) имеем : (g2(n),0,u),(g1(n),u, v),(n,0,p),(g3(n),0,q)гр F (n+1,0,H(n, v, p, q))гр F. Для удобства переобозначим координаты троек: (x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4)гр F (x3+1,y3,H(x3,z2,z3,z4))гр F, где z1=y2 x1=g2(x3) y1=y3=y4=0 (**) x2=g1(x3) x4=g3(x3) Определим на N3 операцию B: B((x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4)) = (x3+1,y3,H(x3,z2,z3,z4)), если условия (**) выполнены,B((x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4)) = (0,0,h(0))–иначе. 4). Из третьего равенства (*) имеем: (n+1,x,u),(f1(n),u,v),(f3(n),x+1,p),(f2(n),p,q),(f4(n),x+1,w)гр F (n+1,x+1,G(n+1,x,v,q,w))гр F. Снова переобозначим тройки: (x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4),(x5,y5,z5)гр F (x1+1,y1+1,G(x1+1,y1,z2,z4,z5))гр F , где x2 = f1(x •1) y1 = y5 = y1+1 x3 = f3(x •1) y2 = z1 (***) x4 = f2(x •1) y4 = z3 x5 = f4(x •1) Определим на N3 операцию A: A((x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4),(x5,y5,z5)) = (x1,y1,G(x1,y2,z2,z4,z5)), если условия (***) выполнены, A((x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4),(x5,y5,z5)) = (0,0,h(0)) – иначе. 5). A, B – ПРФ, т.к. их координатные функции – ПРФ. 6). M0={(0,x,h(x))}={(0(x), ,h(x))} – РПМ (по теореме о параметризации). 7). M* = <M0>A,B – РПМ (по теореме о порожденной совокупности). 8). M0 гр F и гр F – подалгебра относительно операций A,B, т.ч. гр F M* (т.к. M* - наименьшая подалгебра). 9). Покажем, что гр F M* : (n, x, F(n, x))гр F, индукцией по n, x докажем, что (n, x, F(n, x))M *. Базис: n=0 : (0,x,h(x))гр F & (0,x,h(x))M 0M* . Индукционное допущение: для rn, sx , (r, s, F(r, s))гр F & (r, s, F(r, s))M *. а). Покажем, что (n+1,0,F(n+1,0))M * : (g2(n),0,u), (g1(n), u, v), (n,0,p), (g3(n),0,q)M * (по индукционному допущ.) B((g2(n),0,u), (g1(n), u, v), (n,0,p), (g3(n),0,q))=(n+1,0,H(n, u, v, p))M * (ввиду замкнутости множества M* относительно операции B). б). (n+1,x,u,), (f1(n),u,v), (f3(n),x+1,p), (f2(n),p,q), (f4(n),x+1,w)M* (по индукционному допущению). А((n+1,x,u),(f1(n),u,v),(f3(n),x+1,p),(f2(n),p,q),(f4(n),x+1,w))= =(n+1,x+1,G(n+1,x,v,q,w))M* (ввиду замкнутости , множества M* относительно операции A). Таким образом, гр F M*, т.е. гр F = M*. 10). Поскольку F – тотальная функция, график которой – РПМ, то F – ОРФ. 1.2.6. Универсальная функция Функция F(x0,x1,…,xn) называется универсальной для семейства n-местных функций, если выполнены два условия: 1) для каждого фиксированного i : F(i,x1,…,xn) = f(x1,…,xn), f 2) для каждой функции f(x1,…,xn) существует i такое, что F(i,x1,…,xn) =f(x1,…,xn). ТЕОРЕМА. Класс n-местных рекурсивных (примитивно рекурсивных) функций не имеет рекурсивной (примитивно рекурсивной) универсальной функции (n=1,2,…). Д о к а з а т е л ь с т в о. Пусть F(x0,x1,…,xn) – универсальная функция для класса n всюду определенных n-местных функций. Положим F(x1,x1,x2,…,xn)+1 = g(x1,…,xn). Если g n, то i F(i,x1,…,xn) = g(x1,…,xn) для всех значений x1,…,xn. В частности, F(i, i,…,i) = g(i, i,…,i) = F(i, i,…,i)+1. Полученное противоречие доказывает тео-рему. ТЕОРЕМА. Класс одноместных ПРФ имеет общерекурсивную универ -сальную функ-цию. Д о к а з а т е л ь с т в о. 1). По теореме Робинсона, все одноместные ПРФ можно полу-чить из элементарных функций s(x), q(x)(=x• ) с помощью операторов +, •, J1). 2). Так что одноместные ПРФ являются значениями термов над алфавитом {s,q, +, •, I}. Введем следующую нумерацию термов (следовательно, и одноместных ПРФ): (1)=1, (q)=3; (t1+t2)=213a5b, где a, b – коды термов t1, t2, соответственно; (t1*t2)=223a5b, где a, b – коды термов t1, t2, соответственно; (I(t))= 233a , где a – код терма t. 3). Обозначим fn(x)=F(n, x), где fn(x) – терм с кодом n. Для натуральных чисел n, являющихся кодами подходящих термов, имеем: fa(x)+fb(x), если n = 213a5b; fa(fb(x)), если n = 223a5b; F(n, x) = fa(fn(x)), если n = 233a , x=0; q(x), если n = 3; s(x), если n = 1. или, вводя обозначение exp(n,i)=(n)i , F((n)1,x)+F((n)2,x), если (n)0=1; F((n)1,F((n)2,x)), если (n)0=2; F(n, x) = F((n)1,F(n,x-1), если (n)0=3, x>0; 0, если (n)0=3, x=0; Q(n,x) – для остальных n, x, где Q(n,x)=s(x) n-1 + q(x) n-3. 4). Доопределим функцию F(n,x) до всюду определенной функции D(n,x): D(0,x)=0; D(f1(n),0)+D(f2(n),0), если (n+1)0=1; D(n+1,0) = D(f1(n),D(f2(n),0)), если (n+1)0=2; 0 – для остальных n; D(f1(n),x+1)+D(f2(n),x+1), если (n+1)0=1; D(f1(n),D(f2(n),x+1)), если (n+1)0=2; D(n+1,x+1)= D(f1(n),D(n,x+1)), если (n+1)0=3; Q(n+1,x+1) – для остальных n; где fi (n)=(n+1)i (i=1,2), или D(0,x) = 0; D(n+1,0) = H(n, D(f1(n),D(f2(n),0)),D(f1(n),0),D(f2(n),0); D(n+1,x+1) =G(n+1,x,D(f1(n),D(n,x+1)),D(f1(n),D(f2(n),x+1)),D(f1(n),x+1),D(f2(n),x+1), где G(m,x,y,z,u,v) = (u+v) (m)0 - 1+z (m)0 - 2+ y (m)0 - 3+ Q(m,x) sg((m)0 - 1(m)0 - 2(m)0 - 3), H(m, y, z, u)=(z+u) (m)0 - 1+y (m)0 - 2, fi (x) x (i=1,2). Таким образом, функция D(n, x) задана рекурсией 2-ой ступени, т.е. ОРФ. 5). Индукцией по n докажем, что D(n, x) = fn (x), если n – код терма, D(n, x) = g(x) – одноместная ПРФ – для остальных n. Базис: n=0,1,2,3 : D(0,x) = D(2,x) = 0; D(1,x) = s(x); D(3,x) = q(x). Индукционный шаг: Допустим, что утверждение верно для n и докажем для n+1: (1) n+1 – код терма. Тогда описания функций D(n+1,x), F(n+1,x) совпадают с точностью до замены D(fi (n),x) на F(fi (n),x). Последние совпадают по индукционному допущению, т.к. fi(n) n (i=1,2). Откуда D(n+1,x) = F(n+1,x). Таким образом, для всех n D(n, x) = F(n, x), если n – код терма. (2) n+1 – не является кодом терма. Тогда D(n+1,x) получается примитивной рекурсией из функций D(f1(n),x), D(f2(n),x). Последние ПРФ по индукционному допущению, т.к. fi (n) n (i=1,2). Следовательно, D(n+1,x) получается возвратной рекурсией, т.е. D(n,x) есть ПРФ. Таким образом, для всех n D(n, x) – ПРФ, обладающая свойствами: 1) для фиксированного n D(n, x) есть одноместная ПРФ; 2) для каждой одноместной ПРФ f: n D(n,x) = f(x) = fn (x). Это означает, что D(n,x) – универсальная функция для класса одноместных ПРФ. Следствие 1. Существуют ОРФ, не являющиеся ПРФ. Д о к а з а т е л ь с т в о. D(x,x) - ОРФ, не является ПРФ, в противном случае D(x,x) + 1 = g(x) – ПРФ, следовательно, i D(i,x) = g(x) = D(x,x)+1 для всех значений x. В частности, D(i,i) = D(i,i) +1, что есть противоречие. Следствие 2. Для каждого n=1,2,… класс n n-местных ПРФ имеет общерекурсивную уни-версальную функцию. Д о к а з а т е л ь с т в о. Покажем, что универсальная функция этого класса D(n+1)(x0,x1,…,xn) = D(x0,c(x1,…,xn))? (1) При фиксированном значении x0 = c: D(c,z)1, т.е. D(c,c(x1,…,xn)) = D(n+1)(c,x1,…,xn)n. (2) Для любой g(x1,…,xn)n, ее представляющая функция f(x)=g(cn1(x),…,cnn(x))1. Тогда i (f(x) = D(i,x)) или g(x1,…,xn)=g(cn1(x),…,cnn(x))=f(x)=D(i,x)=D(i,c(x1,…,xn))=Dn+1(i,x1,…,xn). Следствие 3. Существуют рекурсивные множества, не являющиеся РПМ. Например, множество A с характеристической функцией A(x)= D(x,x). 1.2.7. Универсальные частично рекурсивные функции ТЕОРЕМА (Клини о нормальной форме). Каждая ЧРФ f(x1,…,xn) предста вима в форме f(x1,…,xn) ) U( t F(n+1)(x1,…,xn,t)=0) , где F(n+1) – ПРФ. Д о к а з а т е л ь с т в о. f(x1,…,xn) - ЧРФ, то гр f(x1,…,xn) есть РПМ, т.е. (x1,…,xn,y)гр f(x1,…,xn) z (g(x1,…,xn, y, z)=0), где g – ПРФ t = c(x, y) (g(x1,…,xn, l(t),r(t)) & y=l(t)). Откуда f(x1,…,xn) = U(t g(x1,…,xn,l(t),r(t))=0) = U(t (F(n+1)(x1,…,xn, t)=0)), где F(n+1) – ПРФ, как суперпозиция ПРФ. ТЕОРЕМА (Об универсальной функции). Существует ЧРФ T(n+1)(x0,x1,…,xn), универсальная для класса n-местных ЧРФ. Д о к а з а т е л ь с т в о. T(n+1) (x0,x1,…,xn) = U( t D(n+2)(x0,x1,…,xn, )=0)), где D(n+2) - уни-версальная функция для класса (n+1)-местных ПРФ. Покажем, что T(n+1)(x0,x1,…,xn) – универсальная функция для класса n-местных ЧРФ: (1) При фиксированном значении x0=e : T(n+1)(e,x1,…,xn)=U( t (D(n+2)(e,x1,…,xn, t)=0))=U( t (fe(n+1)(x1,…,xn, t)=0)), где fe(n+1) – ПРФ. Тогда t (fe(n+1)(x1,…,xn, t)=0) – ОРФ. Таким образом, T(n+1)(e,x1,…,xn) – ОРФ. (2) Для любой ЧРФ fn(x1,…,xn) по теореме Клини о нормальной форме имеем: F(n) (x1,…,xn)=U( t (F(n+1)(x1,…,xn, t)=0)), где F(n+1) – ПРФ. Тогда e (D(n+2) (e,x1,…,xn, t)=F(n+1)(x1,…,xn, t)), т.е. f(x1,…,xn) = U( t (D(n+2) (e,x1,…,xn, t)=0)) = T(n+1)(e,x1,…,xn), e. ТЕОРЕМА. Никакая ЧРФ Tn+1(x0,x1,…,xn), универсальная для класса n-местных ЧРФ, не имеет общерекурсивных доопределений. Д о к а з а т е л ь с т в о. 1). Пусть V(x) = T(n+1) (x, x,…,x) – ЧРФ. Допустим, что она имеет общерекурсивное доопределение W(x). Представим W(x1)= (W(x1), x2,…, xn). По оп-ределению универсальной функции e x1, x2,…, xn W(x1) = T(n+1) (e,x1,…,xn).В частности, W(e)=T(n+1) (e, e,…,e). Так как T(n+1) (e, e,…,e) определено, то V(e) = T(n+1) (e, e,…,e) определено. W(x) - продолжение функции V(x), тогда W(e) = V(e) = T(n+1) (e, e,…,e), что противоре-чит тому, что W(e) = T(n+1) (e, e,…,e). 2). Допустим, что P(x0,x1,…,xn) – общерекурсивное доопределение функции T(n+1)(x0,x1,…,xn). Тогда функция P(x,…,x) была бы общерекурсивным доопределением ЧРФ V(x) = T(n+1) (x, x,…,x), что не верно. Следствие. Существуют нерекурсивные рекурсивно перечислимые множества. Д о к а з а т е л ь с т в о. Возьмем частично рекурсивную функцию V(x) = = T2(x, x), не имеющую общерекурсивных доопределений. Из следствия 3 теоремы о гра-фике ЧРФ, множество решений уравнения V(x)=0 является рекурсивно перечислимым мно-жеством. Оно не рекурсивно, в противном случае функция V(x) имела бы общерекурсив-ное доопределение. 2 ПРИЛОЖЕНИЯ ТЕОРИИ АЛГОРИТМОВ 2.1. Теоремы о рекурсии и неполноте Важнейшими задачами для формальной аксиоматической системы является установ-ление ее неразрешимости (разрешимости) и неполноты (полноты), которые решаются вложением формальной системы в формальную арифметику Ar с помощью процедуры геделизации. Геделевской нумерацией (геделизацией) множества слов в алфавите А называют взаимно однозначное отображение : N, для которого существует алгоритм, вы-числяющий по слову его номер (), и наоборот, по натуральному числу n N выдающий слово , если n (), и число 0, - если n не является кодом никакого слова из . Объекты формальной системы, а также программы машины Тьюринга, или рекурсив-ные описания функций есть слова в конечных алфавитах и поэтому геделизуемы, что позволяет изучать их свойства в рамках формальной арифметики Ar . Приведем пример одной геделевской нумерации машин Тьюринга. Командам машины Тьюринга: qj ai ar Sqr, qj ai ar Rqr, qj ai ar Lqr присвоим соответственно г.н.: 2j 3i 5r 7s, 2j 3i 5r 7s 11, 2j 3i 5r 7s 13. Тогда, если c1,c2,…,ck - геделевские номера всех команд машины Тьюринга, то ее код (г.н.) есть число z = . Характерным свойством г.н. является то, что его всегда можно вычислить и обратно – по любому натуральному числу z можно установить, является z г.н. некоторой программы машины Тьюринга , и если – да, то восстановить саму программу. Через {z}(x1,…,xn) будем обозначать функцию, вы-числимую на машине Pz (с г.н.z). Известна теорема об эквивалентности классов функций, вычислимых на машине Тьюрин-га, и ЧРФ, так что все полученные результаты о вычислимых функциях распространяются на обе теории. Отметим одну их важную особенность, а именно, инвариантность по отно-шению к геделевской нумерации, что означает независимость данных теорий от конкретно-го вида выбранной геделевской нумерации. Это свойство г.н. позволяет доказать такие принципы программирования, как теоремы об универсальной функции и неподвижной точке и s-m-n-теорему. Пусть машина Pz вычисляет функцию {z}(x,y) = (x,y). При фиксированном значении x = a, функция (a,y) также вычислима и ее г.н. может быть эффективно найден по z и x. ТЕОРЕМА (s-m-n-теорема). Существует ПРФ такая, что Д о к а з а т е л ь с т в о. (Рассмотрим случай m = n = 1). Для каждого x эффективно строится программа Qx, преобразующая аргумент ‘y’ в пару (x,y). Искомая функция дает номер w машины, которая : на аргументе y порождает программу Qx и применяет ее к аргументу ‘y’, а затем к паре (x,y) приме-няет программу машины z , так что В силу эффективного характе-ра г.н. номер w строится эффективно по z и x, поэтому является рекурсивной и даже ПРФ. Из s-m-n-теоремы как следствие можно получить теорему о неподвижной точке. Следствие. (Теорема о неподвижной точке). Пусть (z,x1,…,xn) – вычислимая функция. Тогда существует машина e такая, что для любых (x1,…,xn) : {e}(x1,…,xn) (e,x1,…,xn). Д о к а з а т е л ь с т в о проведем для случая n = 1. Очевидно, что функция ( ) по прежнему вычислима на некоторой машине Pr . Положим e = , тогда {e}(x) = { }(x) {r}(r,r) ( ) = (e,x), ч.т.д. Поскольку язык Ar беден, расширим его до Ar+, вводя функциональные символы для каждой примитивно рекурсивной функции. Аксиоматика Ar+ кроме аксиом Ar (аксиом равенства и аксиом Пеано) содержит определяющие аксиомы для примитивно рекур-сивных описаний. Так что каждая примитивно рекурсивная функция представима в Ar+ подходящим термом. По существу же Ar и Ar+ эквивалентны, т.к. термы Ar+ выра-зимы в Ar. ЛЕММА 1. (О нумерической выразимости ПРФ в Ar+). Для любого набора натуральных чисел k1, ... , kn , если f (k1, ... , kn ) = ( )g (k1, ... , kn), то Ar+ t ( k1, ... , kn) = (1) ) r (k1, ... , kn), где t, r - термы , представляющие функции f, g, соответственно; ki - терм, представляющий натуральное число k i ( i=1,...,n) в Ar+. ТЕОРЕМА (О неподвижной точке). Пусть A(x) - формула Ar+ , где x - свободная пере-менная. Тогда найдется формула B такая, что Ar+ B A ( B ), где B - терм, представляющий число (B) в Ar+. Д о к а з а т е л ь с т в о. Пусть y = (C (x)) (x-свободная переменная). Рассмотрим прф SUB (y, z ) = (C (z )), где Sub (y , z ) - представляющий терм в Ar+. Для A* = Sub (x, x)) и B = A*(A* ) имеем (B) = SUB ( (A* ), (A* )), и по лемме 1: Ar+ B = Sub (A* , A* ). Из вышесказанного имеем Ar+ B A* (A* ) A(Sub (A* , A* )) A (B ). Следствие. Для всюду определенной функции f найдется натуральное число n , такое, что f(n) = n. С помощью геделевской нумерации выводимость в Ar+ можно изучать средствами самой Ar+ . Рассмотрим примитивно рекурсивный предикат PRF(y,x): « y есть г.н. вы-вода в Ar+ формулы с г.н. x » и рекурсивно перечислимый предикат PR(x) y PRF(y,x): « x есть г.н. формулы, выводимой в Ar+ ». Соответственно, Prf (y,x), Pr(x) y Prf (y,x) - представляющие их в Ar+ формулы. По теореме о неподвижной точке, существует формула , утверждающая свою собст-венную невыводимость: Ar+ Pr(). ЛЕММА 2. Если теория Ar+ непротиворечива, то не ( Ar+ ). Д о к а з а т е л ь с т в о. 1. Ar+ - непротиворечива (допущение) 2. Ar+ (допущение противного) 3. y PRF(y,()) (из п.2) 4. Ar+ y Prf (y, ) 5. Ar+ Prf ( p, ) (допущение) 6. Ar+ Pr ( ) (-введение) 7. Ar+ Pr() (теорема о неподвижной точке) 8. Ar+ (по правилам вывода) 9. Ar+ (-удаление) 10. не ( Ar+ ) ( - введение) 11. Ar+ - непротиворечива не (Ar+ ) ( - введение) Теория1) T в языке Ar+ называется - непротиворечивой , если не существует та-кой формулы A (y ) с единственной свободной переменной, что (1) T y A (y) и (2) T A (m) для любого натурального m. УТВЕРЖДЕНИЕ. Если теория T - непротиворечива, то T непротиворечива ЛЕММА 3. Если теория Ar+ - непротиворечива, то не ( Ar+ ). Д о к а з а т е л ь с т в о. 1. Ar+ - непротиворечива (допущение) 2. Ar+ - непротиворечива (из п.1 и утверждения перед леммой) 3. Ar+ Pr([]) (теорема о неподвижной точке) 4. Ar+ (допущение противного) 5. Ar+ Pr ( ) (из п. 3, 4 с помощью правил вывода) 6.Ar+ y Prf (y, ) (по определению формулы Pr ([])) 7. не (Ar+ ) (в силу непротиворечивости Ar+ и п.4) 8. PRF (m, () ) для любого m (из п.7) 9. Ar+ Prf (m, ) для любого m (из п.8 по лемме 1) 10. не (Ar+ y Prf (y, ) (из -непротиворечивости Ar+) 11. не (Ar+ ) ( - введение, 4) 12. Ar+ - непротиворечива не ( Ar+ ) ( - введение) Теория T полна, если для любой формулы Ф из T имеет место T Ф или T Ф. ТЕОРЕМА ГЕДЕЛЯ О НЕПОЛНОТЕ. Если теория Ar+ - непротиворечива, то фор-мулы и не выводимы в Ar+. Д о к а з а т е л ь с т в о следует из лемм 2 и 3. Обозначим через ThL(U) множество всех предложений языка L, истинных в модели U, а через [T]- множество всех теорем теории T. Теория T полна относительно модели U, если [T] = ThL(U). Через обозначим элементарную арифметику, ее называют стандартной моделью Ar+. ТЕОРЕМА. Если Ar+ - непротиворечива, то она существенно неполна относительно модели . Д о к а з а т е л ь с т в о. Формула истинна в стандартной модели , но не выводима в Ar+, т.е. Ar+ неполна относительно модели . Рассмотрим теорию T = Ar+ {}. Тео-рия T непротиворечива, тaк как в противном случае Ar+ , что невозможно. Таким образом, T Prf (m, []) для любого натурального числа m, и T y Prf (y,[]) ( т.к. y Prf(y, [])), т.е. T -противоречива. Покажем, что нельзя доказать непротиворечивость теории только средствами са-мой этой теории. Рассмотрим замкнутую формулу Con y Prf (y, [0=S(0)]) (где Ar+ [0=S(0)]), утверждающую непротиворечивость теории Ar+. ВТОРАЯ ТЕОРЕМА ГЕДЕЛЯ. Если теория Ar+ непротиворечива, то не (Ar+ Con). Сначала докажем вспомогательные утверждения. УТВЕРЖДЕНИЕ 1. Ar+ Con Pr[]. Д о к а з а т е л ь с т в о следует из леммы 2. УТВЕРЖДЕНИЕ 2. y PRF (y, ()) ( Ar+ - непротиворечива). Д о к а з а т е л ь с т в о. Пусть верно y PRF (y, ()) .Допустим противное : Ar+ противоречива. Тогда в Ar+ выводима любая формула, в частности, и формула . Пусть D есть вывод формулы в Ar+, тогда истинно PRF((D), ()), следовательно, y PRF(y,()), что противоречит условию. УТВЕРЖДЕНИЕ 3. Ar+ y Prf ( y, ) Con. УТВЕРЖДЕНИЕ 4. Ar+ Con. Д о к а з а т е л ь с т в о второй теоремы Геделя о неполноте следует из утверждения 4 и леммы 2. 2.2. Разрешимость и неразрешимость формальных систем Аксиоматическая формальная система T разрешима, если по любому выражению Ф из T можно эффективно узнать, является Ф теоремой (выводима в T ) или нет. В силу Тезиса Черча вопрос о разрешимости исчисления, допускающего геделизацию, сводится к вопросу о рекурсивности множества геделевых номеров теорем теории T. Приведем необходимые сведения из теории алгоритмов. Множества A0, A1 N называются рекурсивно отделимыми, если существуют ре-курсивно перечислимые множества B0 и B1 , такие, что A0 B0, A1 B1, B0 B1 = , B0 B1 = N. УТВЕРЖДЕНИЕ. Если множества A0 , A1 рекурсивно неотделимы и не пересекаются, то они нерекурсивны. Напомним, что предикат Tn (e, x1,...,xn, z ) e (x1,...,xn ) = z. Возьмем два примитивно рекурсивных предиката : W0 (x, y) T1 (r (x), x, y ) z y T1 ( l(x), x, z ), W1 (x, y) T1 (l (x), x, y ) z y T1 (r (x), x, z ). Определим два рекурсивно перечислимых множества: V0 = x ; y W0 (x, y) , V1 = x ; y W1 (x, y) . ТЕОРЕМА. Рекурсивно перечислимые множества V0 , V1 не пересекаются и являются рекурсивно неотделимыми. Д о к а з а т е л ь с т в о. Допустим, что V0 V1 и x V0 V1. По определению множеств V0 , V1, найдутся y0, y1 , такие, что W0 (x, y0 ), W1 (x, y1 ), т.е. (1) T1 ( r (x), x, y0 ) z y T1 ( l (x) ,x, z ) (2) T1 ( l(x ), x, y1 ) z y T1 ( r (x), x, z ). Отсюда имеем : y0 y1 и y1 y0 , что дает противоречие. Таким образом, V0 V1 = . Для доказательства второй части утверждения допустим, что существуют рекурсивно перечислимые множества B0 , B1 такие, что V0 B0 , V1 B1 , B0 B1 = . Покажем, что B0 B1 N. Пусть B0 = Val m 0 , B1 = Val m1 и m = c(m0 , m1). Докажем, что m B0 и m B1. Допустим, что m B0 , тогда m Val m 0 , т.е. y T1 (m0, m1, y ) или y T1 (l( m ), m , y ). Т.к. m B0 и B0 B1 = , то m B1 , т.е. m Val m1, т.е. y T1 (m1 , m, y) или y T1 ( r (m), m, y). Таким образом, имеем: y ( T1 ( l (m),m, y) z y T1 (r (m),m, z) ), то есть y W1 (m,y), следовательно, m B1 , что однако противоречит тому, что m B1. Та-ким образом, m B0. Аналогично доказывается, что m B1. Рекурсивная неотделимость множеств V0 , V1 доказана. ТЕОРЕМА. Множества Ar+0 и Ar+1 всех номеров, выводимых и, соответственно, опровержимых предложений Ar+ , рекурсивно неотделимы. Д о к а з а т е л ь с т в о. Как в предыдущей теореме, рассмотрим примитивно рекурсивные предикаты W0 (x, y) , W1 (x, y). Они представляются в Ar+ арифметическими формулами, которые мы будем также обозначать как W0(x,y) и W1(x,y) . Множества V0 ,V1 не пересекаются, т.е. Ar+ y W1 (x, y) y W0 (x, y). Обозначим через B(x) y W0 (x, y). Если m V0 , то существует натуральное число k такое, что W0 (m, k), от-куда Ar+ W0 (m, k), т.е. Ar+ y W0 (m, y), или Ar+ B(m). Значит, (B (m)) Ar+ 0. По теореме о дедукции : mV0 (B(m)) Ar+ 0. Пусть теперь m V1 , тогда существует натуральное число k такое, что W1 (m, k), от-куда Ar+ W1 (m, k), т.е. Ar+ y W1 (m, y). Так как Ar+ y W1 (x, y) y W0 (x, y), то Ar+ y W0 (m, y), т.е. Ar+ B (m) и B (m) Ar+ 1. Таким образом, m V1 (B(m)) Ar+ 1 . Допустим противное, - множества Ar+ 0 , Ar+ 1 рекурсивно отделимы и B0 , B1 -рекурсивно отделяют множества Ar+ 0, Ar+ 1 , т.е. B0 , B1 рекурсивно перечислимые множества и Ar+ 0 B0 , Ar+ 1 B1 , B0 B1 = , B0 B1 = N. Определим рекурсивно перечислимые мно-жества Bi* = m; (B(m)) Bi (i=1,2). Из предыдущего имеем : Vi Bi* (i=1,2) и B0* B1* = , B0* B1* = N. Таким обра-зом, множества V0 , V1 рекурсивно отделимы, что не верно. ТЕОРЕМА (O неразрешимости). Если T непротиворечивая теория в языке Ar+, в кото-рой выводимы все нелогические аксиомы Ar+, тогда T неразрешима. Д о к а з а т е л ь с т в о. Очевидно, что T0 Ar+0. Ввиду непротиворечивости T, T0 Ar+ 1 = . Если бы теория T была разрешимой, то множество T0 было бы рекур-сивным, но тогда и множество N \ T0 было бы рекурсивным. Но тогда множества T0 и N \ T0 отделяют множества Ar+0 и Ar+1, что противоречит рекурсивной неотделимости множеств Ar+ 0 и Ar+ 1 . Следствие 1. Если Ar+ непротиворечивая теория, то Ar+ - неразрешимая теория. Следствие 2. Все предыдущие реэультаты распространяются на теории T, обладающие следующими двумя свойствами : 1. Теория T аксиоматизируема и геделизируема. 2. Теория T содержит арифметику Ar+ . Этими свойствами обладают, в частности, теории Ar, Ar+, ZF (аксиоматическая теория множеств), так что при условии их непротиворечивости они неполны и нераз-решимы, а множества их выводимых и опровержимых предложений рекурсивно неот-делимы. ТЕОРЕМА(О неразрешимости исчисления предикатов). Множество теорем исчисления предикатов не рекурсивно. Д о к а з а т е л ь с т в о. Язык исчисления предикатов содержится в Ar. Допустим, что множество теорем ИП рекурсивно. Тогда существует общерекурсивная функция f такая, что f ((B)) = 0 B, для произвольной формулы B. Пусть Ar -- - произвольный фраг-мент Ar, содержащий лишь конечное число нелогических аксиом из Ar, конъюнкцию которых обозначим формулой A. Определим общерекурсивную функцию h : h(x) = 0 “x есть г.н. некоторой формулы B языка Ar и f ((AB))=0”. Тогда h ((B)) = 0 Ar -- B и теория Ar -- разрешима, что противоречит неразреши-мости теории Ar+ . 3 СЛОЖНОСТЬ ВЫЧИСЛЕНИЯ В реальных вычислениях важно не только то, что функция вычислима (имеется вы-числяющая ее процедура), но не менее существенно – какова ее сложность вычисления (зависящая от внутренней сложности функции, а также – можно ли найти наилучшую программу для ее вычисления.Эти вопросы относятся к теории сложности вычислений. Теорема Блюма об ускорении показывает, что существуют вычислимые функции, не имеющие “наилучшей программы”. Но есть класс функций, для которых существует быстро работающая программа, вычисляющая функцию, совпадающую с данной почти всюду. 3.1. Меры сложности Мерой сложности может быть время вычисления, число шагов машины Тьюринга, длина рабочей ленты машины Тьюринга, использованной в вычислении, и др. Мерой вычислительной сложности называют семейство функций Фe со следующими свойствами : (1) Arg(Фe) = Arg(e), (2) предикат Фe(x) y разрешим. Семейство временных функций te(x) = t {P(x) за t шагов} является примером вы-числительной сложности. ЛЕММА. (1) Arg te = Arg e для всех n, e. (2) Предикат te(x) = t разрешим. Предикат P(n) выполняется почти для всех n, или почти всюду (п.в.), eсли P(n) выполняется для всех nN, кроме конечного множества натуральных чисел, т.е. n0 n n0 P(n). ТЕОРЕМА 1. Пусть g – тотальная вычислимая функция. Существует тотальная вычис-лимая функция f = e , принимающая только значения 0 и 1, такая, что te(n) > g(n) п.в. Д о к а з а т е л ь с т в о. Мы хотим иметь следующее: если ti(m) g(m) для бесконечно многих m, то f отличается от i хотя бы в одном из этих значений. Определим f ре-курсией: пусть f(0), f(1),…,f(n-1) уже определены, тогда если i n = i { i n & i i0,…,in-1 & ti(n) g(n)} и i n (n) = 0, то f(n) = 1, в противном случае f(n) = 0. Поскольку проверка отношения ti(n) g(n) yg(n) (ti(n)y) эффективна, то функция f(n) рекурсивна. f(n) i (n) и e in, покажем, что если ti(m) g(m) для бесконечно многих m, то i = i n для некоторого n,cледо- вательно, i e. Этого достаточно, чтобы доказать, что te (m)> g(m) п.в. Пусть ti(m) g(m) п.в.; положим p = 1+ max{k; i k & i k<i}, p = 0 – в противном случае. Возьмем n, такое, что n i и ti(n) g(n). Если i = i k для некоторого k < n, то все доказано. Если i i k для всех k < n, то i i0,…,i n-1 и ti (n) g(n). Таким образом, по определению i n : i n и i n i. Но поскольку n p, то i n i. Следовательно, i = i n. 3.2. Теорема об ускорении Пусть P и Q - программы для вычисления тотальной функции f, такие, что k tQ (x) < tP (x) для всех x. Тогда программа Q в k раз быстрее (лучше) программы P. Теорема об ускорении говорит, что существует функция f, для которой не сущест-вует наилучшей программы т.к. любую ее программу можно улучшить, ускорив на любой (вычислимый) множитель. В теореме о псевдоускорении не требуется найти j (x) = f(x) для всех x. ТЕОРЕМА 2 (О псевдоускорении). Пусть r тотальная вычислимая функция. Существует тотальная вычислимая функция f, такая, что по любой данной вычисляющей f про-грамме Pi можно найти такую программу Pj, что: a) j – тотальная вычислимая функция и j (x) = f(x) п.в., b) r(t j (x)) < t i (x) п.в. Д о к а з а т е л ь с т в о. 1) e (u,x) s(e,u) (x) (s-m-n - теорема). 2) g u (x) =e (u,x) (теорема об универсальной функции). 3) Строим f со следующими свойствами : a) g0 = f, b) g u (x) = g0(x) п.в., с) если f = i , то для g i+1 найдется j, такое, что r(tj(x)) < ti(x) п.в. (достаточно взять j = s(e,i+1)). 4) Фиксируем u и строим g рекурсией по x: Построим вспомогательные множества Cu,x (вычеркнутых индексов): пусть g(u,0), g(u,1),…,g(u,x-1), Cu,0, Cu,1,…,Cu,x-1 уже определены, тогда Cu,x = {i; uix & i Cu,y & ti(x) r(ts(e,i+1) (x))}, если ts(e,i+1) для u i<x; Cu,x = для x u. Тогда g(u,x) = 1+max {i (x); i Cu,x}, если Cu,x . По следствию из второй теоремы рекурсии, g(u,x) e (u,x), e. 5) Покажем, что g(u,x) = e (u,x) удовлетворяет требованиям из п.3: (1) g(u,x) – тотальная функция: для фиксированного x и u x имеем Cu,x = , т.е. g(u,x) =1; для u < x, покажем, что g(u,x): допустим, что g(x,x), g(x-1,x),…,g(u+1,x) определены, тогда s(e,x)(x), s(e,x-1)(x),…, s(e,u+1)(x) определены, следовательно, и t s(e,i+1) для u i <x. Отсюда Сu,x , т.е. g(u,x), ч.т.д. (2) g u (x) = g(u,x) = e(u,x) = s(e,u) (x) и проверим свойства a)-c): (a)Для f = g0 функция f тотальна, ч.т.д. (b) Фиксируем u и покажем, что g(0,x) и g(u,x) отличаются только на конечном множестве точек x. По построению множества Cu,x ясно, что для всякого x, Сu,x = C0,x {u,u+1,…, x-1}. Так как все множества C0,x попарно не пересекаются, то существует v = max {x; i<u i C0,x }. Для x > v, имеем C0,x {u,u+1,…,x-1}, следовательно, С0,x = Cu,x, т.е. g(0,x) = g(u,x) для x>v. Таким образом, g0 (x) = gu (x) п.в. (c) Пусть f = i & j = s(e,i+1), тогда j = s(e,i+1) = g i+1 и r(tj (x)) = r(t s(e,i+1)(x)) > ti (x) для всех x>i, в противном случае - x > i & i C0,x, и тогда g(0,x) i (x), что означает противоречие. Заметим, что теорема о псевдоускорении эффективна: по данной программе P для f можно эффективно найти другую программу, которая вычисляет f п.в. и п.в. быстрее, чем P. ТЕОРЕМА 3 (Об ускорении). Пусть r тотальная вычислимая функция. Существует тотальная вычислимая функция f, такая, что, для всякой программы Pi , вычисляющей f , существует другая программа Pk для вычисления f, для которой r(tk (x)) < ti (x) п.в. Д о к а з а т е л ь с т в о. Без потери общности можно считать, что функция r возрас-тающая. По теореме 2, существует тотальная вычислимая функция f , где Pi - вычисляющая f программа, и найдется программа Pj , такая, что a) j – тотальная и j (x) = f(x) п.в.; b) r(tj (x) + x) < ti (x) п.в. Для этого в определении Cu,x заменим неравенства r(x) r(t s(e,i+1)(x)) на r(x) r(t s(e,i+1)(x) + x). Покажем, что полученная таким образом функция f удовлетворяет требуемым условиям. По условию f = i и j удовлетворяет условиям a) и b). Изменим програм му Pj, чтобы получить программу Pj* ,такую,что Pj* (x) = f(x) для всех x: Пусть j (m) = f(m) для всех m> v & f(m) = bm для m v. Изменим Pj, поместив в начало программы некоторые команды, задающие значения f для m v, как показано на блок-схеме: Начало да r1=0 r1: = b0 нет да r1=1 r1: = b1 нет • • • • • • нет да r1=v r1: = bv нет Pj Останов Очевидно, что Pj* (x) = f(x) для всех x, и найдется c, такое, что tj* (x) tj (x)+c для всех x. Ввиду того, что функция r возрастает: r( tj* (x)) r( tj (x)+c) r( tj (x)+x) (для всех x с) < ti (x) п.в. Для k = j* теорема доказана. Можно показать, что теорема об ускорении не является эффективной. Теорема об ускорении является серьезным препятствием определения внутренней сложности функции f, которую нельзя таким образом определить, как сложность вычисляющей ее программы, поскольку для функции f не существует наилучшей программы (или быстрейшего алгоритма). 3.3. Классы сложности. Элементарные функции Класс сложности тотальной вычислимой функции f определим как G b = { e; e – тотальная & t e(x) b(x) п.в.}. ТЕОРЕМА 4 (О пробелах). Пусть r тотальная вычислимая функция, для которой r(x) x для всех x. Тогда существует тотальная вычислимая функция f , такая, что a) e ( x e & te(x) & te(x) f(x) te(x) > r(f(x)); b) Gf = Grf . Д о к а з а т е л ь с т в о. Определим последовательность чисел k0<k1<…<kx так, что k0 = 0; ki+1 = r(ki)+1 (i < x). Рассмотрим непересекающиеся интервалы [ki, r(ki)] для 0 < i < x. Существует (x +1) таких интервалов, значит по крайней мере один из них не содержит ни одного числа te(x) для e < x, поскольку определено не более чем x таких чисел. Определим ix = i (te(x) [ki, r(ki)]) для всех e < x, и положим f(x) = ki . По Tезису Черча функция f(x) - вычислимая функция. Предположим, что x > e & te (x) f(x), тогда te (x) [f(x), r(f(x))], следовательно, te (x) r(f(x)). Докажем пункт b): Пусть Gf Gr f . Если g Grf \ Gf, то g вычислима программой Pe c te (x) < r(f(x)) п.в. Однако te (x) > (f(x)) п.в. (иначе gGf ), что противоречит a). Таким обра-зом, G f = Gr f . В терминах временной сложности очень просто может быть охарактеризован класс всех практически вычислимых, функций, получающихся с помощью обычных арифме-тических операций. Класс элементарных функций является наименьшим классом, таким, что: (i) функции x+1, Uin (1in), x • y, x+y, xy входят в ; (ii) класс замкнут относительно суперпозиции; (iii) класс замкнут относительно операций ограниченного суммирования и ограниченного умножения. Элементарный предикат (множество) имеет элементарную характеристическую функцию. ЛЕММА. Класс замкнут относительно (1) ограниченного - оператора, операций , &, и ограниченных кванторов z<y, z<y. ТЕОРЕМА 5. Класс замкнут относительно примитивной рекурсии, если определяемая функция элементарно ограничена. Д о к а з а т е л ь с т в о. Пусть f (x1,…,xn), g(x1,…,xn,y,z) – ПРФ, h (x1,…,xn,0) = f (x1,…,xn) h (x1,…,xn,y+1) = g(x1,…,xn,y, h(x1,…,xn,y)) и существует функция b, такая, что h(x1,…,xn,y) b(x1,…,xn) для всех x1,…,xn,y. Положим s = 2h(x,0) 3h(x,1)…Ph(x,y) = П Ph(x,z) < П Pb(x,z) = k(x,y), где k(x,y) – элемен-тарная функция. Тогда h(x,y) =[ s < k(x,y) ((s)1 = f(x) &z<y((s)z+2 = g(x,z,(s)z+1)))]y+1, откуда cледует элементарность функции h. Следствие 1. Предикат Tn(e,x1,…,xn,y) нормальной формы Клини элементарен. Следствие 2. a) Пусть b(x1,…,xn) – элементарная функция, e (x1,…,xn) – тотальная вычислимая функция, такая, что te (x1,…,xn) b(x1,…,xn) п.в., тогда e (x1,…,xn) – элементарная функция. b) Если b(x1,…,xn) – элементарная функция, тогда Gb G. Обозначим число через bk(z): b0 (z) = z, b1 (z) = 2z , bk+1(z) = 2b (z) . Очевидно, что bk (z) возрастающая ПРФ. ТЕОРЕМА 6. Если f((x1,…,xn) – элементарная функция, то найдется число k, такое, что для всех x1,…,xn f((x1,…,xn) bk (max (x1,…,xn)). Следствие. Функция f(z) = - ПРФ, но не элементарная. Д о к а з а т е л ь с т в о. f(z) = g(z,z), где g(z,0) = z g (z,y+1) = 2g(z,y) , т.е. g – ПРФ. Так как, c одной стороны, f(k+1) = bk+1 (k+1)<bk (k+1), a с другой - f(k+1) = =g (k+1,k+1) = =2g(k+1,k) = … = = bk(k+1) для каждого k, то получено противоречие. Элементарные функции могут быть вычислены за элементарное время. ТЕОРЕМА 7. Если функция f(x1,…,xn) элементарна, то существует вычисляющая f программа P, такая, что t p(x1,…,xn) – элементарна. (Без доказательства). для покупки работы нужно авторизоваться
Для продолжения нажмите Войти, Регистрация
|
|
| Программистам | Дизайнерам | Сайты | Сервис | Копирайтерам | Файлообменики | Заработок | Социальная сеть | Статистика |
|
|
|
|
|
|
файлообменниках |
программа |
|
|