Математическая логика и теория алгоритмов

МИНОБРНАУКИ РОССИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский государственный технологический университет «СТАНКИН» (ФГБОУ ВПО МГТУ «СТАНКИН») Факультет ИТС Кафедра «Прикладная математика» Елисеева Ю.В. Конспект лекций по дисциплине «Математическая логика и теория алгоритмов» Курс лекций по дисциплине «Математическая логика и теория алгоритмов» для студентов МГТУ «СТАНКИН», обучающихся по направлению __________09.03.02_ «Информационные системы и технологии» Москва 2016 г. Математическая логика Лекция 1. Основные понятия алгебры высказываний. Простые и сложные высказывания. Логические связки. Логичные, или правильные рассуждения. Определение формулы. Понятие логической функции и способы ее задания. Основные законы алгебры логики. Тавтология и противоречие. Двойственные формулы. Принцип двойственности. Высказывание – повествовательное предложение, про которое однозначно можно сказать истинно оно или ложно. Истинность или ложность, приписываемая высказыванию, называют его истинностным значением. Высказывание, не содержащее логических связок, называется простым. Высказывание, содержащее логические связки, называется сложным. ( Истинностное значение такого высказывания определяется по истинностным значениям входящих в него простых.) Логические связки: 1) отрицание: Ā Истинно тогда и только тогда, когда А – ложь. «Не», «неверно». А Ā И И Л Л 2) конъюнкция: А^В, А&В, А*В. Новое сложное высказывание истинно тогда и только тогда, когда А и В истинны одновременно. «и», «не только, но и», «А, хотя и В», «как А, так и В» А В А&В Л Л Л Л И Л И Л Л И И И 3) дизъюнкция: АVВ Новое сложное высказывание ложно, тогда и только тогда, когда А и В ложны. «или», «хотя бы одно», «А, если не В» А В АVВ Л Л Л Л И И И Л И И И И 4) импликация: А→В Новое сложное высказывание, которое ложно, когда А-истинно, а В-ложно. «если А, то и В», «А влечет В», «коль скоро А, то В», «А, только если В» А В А→В Л Л И Л И И И Л Л И И И 5) эквиваленция: А~B Новое сложное высказывание, которое истинно тогда и только тогда, когда истинностные значения А и В совпадают. « тогда и только тогда», «необходимо и достаточно», «если и только если», «равносильно». А В А~В Л Л И Л И Л И Л Л И И И Логические (правильные) суждения. Если из конъюнкции посылок следует заключение, т.е. всякий раз, когда все посылки истинны, то и заключение так же истинно, то такое суждение называется логическим (правильным). Форма записи рассуждения (клаузы). Р1, Р2, …Рn ├ D где Р1, Р2,…Рn – посылки, гипотезы; D – заключение. Пример (составить клаузу): Я заплатил бы за ремонт, только если бы телевизор стал работать; он не работает, значит я не буду платить за ремонт. З – заплачу за ремонт; Р – телевизор работает. З→Р, ├ З- клауза. Данное рассуждение логично, если сложное высказывание ((З→Р)&Р)→З всегда истинно. Действительно, импликация всегда равна истине, если ситуация ((З→Р)&Р)=и, а =л невозможна (см. определение импликации), следовательно рассуждение логично по определению. Пример 2: Профсоюзы штата будут поддерживать губернатора только если он подпишет билль, фермеры окажут ему поддержку, только если он наложит вето. Очевидно, что он либо не подпишет билль, либо не наложит вето. Следовательно, губернатор потеряет либо голоса профсоюзов, либо голоса фермеров. П – поддержка профсоюзов; Б – подписывает билль; В – наложит вето; Ф – поддержит фермеров; П→Б, Ф→В, БVВ├ П VФ Формулы логики высказывания. Алфавит – любое непустое множество символов. Слово – произвольная, конечная последовательность символов, может быть пустая. Символы алфавита: 1) Высказывательные переменные А, В, С, х, у,…z, x1,x2,…xn ; 2) Логические связки &,V,¯,→,~. 3) Скобки (); Правила построения формул. Слово в алфавите алгебры логики является формулой, если оно построено по следующим правилам: 1) Высказывательная переменная является формулой; 2) если известно, что А и В – формулы, то формулами являются (Ā), (АVВ), (А&В), (А→В), (А~В); Пример: ((х1)Vх2)V(х3&х4) • х2 является формулой по 1); • (х3&х4) формула по 2); • (х1) формула по 2); • ((х1)Vх2) формула по 2); Следовательно всё слово – формула по 2). Соглашение об упрощении. 1) внешние скобки опускаются; 2) порядок выполнения: • отрицание; • конъюнкция; • дизъюнкция; • эквиваленция, импликация; Понятие функции: Если любой высказывательной переменной придавать значение из множества истинностных значений, то формула определяет функцию, принимающую значения ИСТИНА/ЛОЖЬ. Если у функции n-переменных, то упорядоченный набор всех переменных называется списком. Конкретный набор называется оценкой списка. Способ задания функций: 1) формула; 2) таблица истинности; Пусть есть формулы, зависящие от равного числа переменных; они равносильны, если совпадают их таблицы истинности. Законы логики высказываний. 1) коммутативность; А°В=В°А, 2) ассоциативность; А°(В°С)=(А°В)°С, 3) идемпотентность; a. АVА=А; b. А&А=А; 4) дистрибутивность; ▪ А&(ВVС)=А&ВVА&С; ▪ АV(В&С)=(АVВ)&(АVС); 5) двойного отрицания: =А 6) правила де Моргана; а) =; б) =; 7) правило поглощения; а) АV(А&В)=А; б) А&(АVВ)=А; 8) правило «поглощения отрицания»; а) АV(Ā&В)=АVВ; б) А&(ĀVВ)=А&В; 9) правило расщепления; а) В=(ВVĀ)&(ВVА); б) В=(В&А)V(В&Ā); 10) связи между операциями; а) А→В=ĀVВ; б) А~В=(А→В)&(В→А)=; Формула называется тавтологией, если заданная ею функция ИСТИННА при всех значениях высказывательных переменных. Формула называется противоречием, если заданная ею функция ЛОЖНА при всех значениях высказывательных переменных. Свойства констант: 1) ĀVА=И; 2) Ā&А=Л; 3) АVЛ=А; 4) А&Л=Л; 5) АVИ=И; 6) А&И=А; Принцип двойственности Формула называется булевой, если она содержит только три связки: Утверждение. Любая формула может быть записана в равносильной булевой форме. Пусть Ф – Булева функция, тогда Ф* - двойственна по отношению к Ф, если все вхождения в Ф заменяются на в Ф* и наоборот, все вхождения заменяются на . Пример: Ф=((ĀВ) С) D; Ф*=((ĀВ) С) D; Свойства двойственных формул: 1) (Ф*)*=Ф**=Ф; 2) Пусть Ф – содержит высказывательные переменные х1,х2,…хn, тогда для любой оценки верно, что Ф*(х1,х2,…хn)= Теорема (принцип двойственности). Формулы А и В равносильны, т.е. А=В, тогда и только тогда, когда равносильны А* и В* (А*=В*); Доказательство: По определению равносильности, А=В тогда и только тогда, когда А(х1,х2,…хn)=В(х1,х2,…хn) для любого (х1,х2,…хn), или = для любого (х1,х2,…,хn), или, по свойству 2 двойственных формул, верно, что А*(х1,х2,…хn)=В*(х1,х2,…хn), что равносильно А*=В*, что и требовалось доказать. Лекция 2 Проблема разрешимости в логике высказываний. Определение формальной аксиоматической теории Проблема разрешимости в логике высказываний. КНФ и ДНФ. Алгоритмы приведения к КНФ и ДНФ. Решение проблемы разрешимости с помощью КНФ. Исчисление высказываний. Определение вывода формулы. Пример формальной аксиоматической теории. Проблема разрешимости: существует ли такая процедура, которая позволяет для произвольной формулы за конечное число шагов определить, является ли она тавтологией?! Ответ: Да. 1 способ: при помощи таблицы ( недостаток- рост таблицы) Пример: 2 способ: использовать КНФ формулы. КНФ и ДНФ Определение. Формула называется элементарной конъюнкцией, если она является конъюнкцией конечного числа переменных или отрицания переменных . Пример: А&В, В&, А&&С&D Определение. Формула называется элементарной дизъюнкцией, если она является дизъюнкцией конечного числа переменных или отрицаний переменных. Пример: АВ, АС, - элементарные дизъюнкции. Определение. КНФ- конъюнктивной нормальной формой называется конъюнкция элементарных дизъюнкций: Определение. ДНФ - дизъюнктивной нормальной формой называется дизъюнкция элементарных конъюнкций: Пример. Утверждение. Любая формула может быть записана в виде равносильной ей формулы, находящейся в КНФ (ДНФ) Алгоритм приведения к ДНФ: 1) Сделать формулу булевой (содержащей V,&, ⌐) 2) «Спустить» отрицания до переменных (закон де Моргана и двойного отрицания) 3) Использовать дистрибутивность Пример: привести к ДНФ формулу . Решение: 1) - ДНФ сумма произведений Переход от ДНФ к КНФ 1. Пусть Ф находится в ДНФ, тогда Ф* находится в КНФ Пример: 2. Переходим к ДНФ для Ф* , используя закон дистрибутивности: 3. Если Ф* находится в ДНФ, то находится в КНФ: - КНФ Решение проблемы разрешимости с помощью КНФ Теорема 1. Формула Ф является тавтологией тогда и только тогда, когда КНФ этой формулы удовлетворяет требованиям: любая элементарная дизъюнкция содержит некоторую переменную и её же отрицание. Теорема 2. Формула Ф- противоречие тогда и только тогда, когда ДНФ этой формулы удовлетворяет требованиям: любая элементарная конъюнкция содержит некоторую переменную и ее отрицание. Доказательство Т1: Пусть 2) содержит некоторую переменную и её же отрицание . Докажем последнее: а) Пусть и в , докажем, что = И. имеет вид: (здесь P – остальные переменные элементарной дизъюнкции) б) Пусть = И, докажем, что и . От противного и . Пусть имеет вид: , где l,p,q…r- по парно различны, тогда возьмем следующие значения переменных на данной оценке пришли к противоречию с предположением, что = И. Пример: Исчисление высказываний Формальная аксиоматическая теория считается заданной, если: 1) задан алфавит символов; 2) определены формулы в алфавите; 3) из множества формул алфавита выбирается фиксированный набор формул, называющийся множеством аксиом теории 4) задаются правила вывода из этих аксиом новых объектов -теорем теории. Вывод формулы формальной аксиоматической теории Определение. Формула выводится из списка гипотез (Обозначение: ), если список вывода , где Ф i – формулы теории, который удовлетворяет следующим требованиям: 1) последняя формула в списке совпадает с ; 2) Ф i , где i по правилу m.p. ├( А→В)→(А→А) (т.к. А→(В→А) – аксиома 1) В:=АВ, тогда по правилу подстановки ├(А→ АВ) →(А→А); (А→ АВ) – аксиома 6 => правилу м.п. ├А→А Теорема дедукции. Пусть Г – список гипотез, А,В –формулы, тогда если Г, А├В , то Г├А→В. Замечание. Также верно обратное: из того, что Г├А→В следует Г, А├В. Действительно, пусть Г├А→В, докажем, что Г, А├В Г├А→В <=>  список вывода (доказательство): Ф1,Ф2,…,Фn-1,А→В. Тогда доказательство для Г, А├В следующее: Ф1,Ф2,…,Фn-1, А→В, А, В (где В получено по m.p.). Замечание Все аксиомы и теоремы могут быть записаны как правила вывода и наоборот. Например. А1: ├А→(В→А) <=> А├В→А <=> А, В├А Обобщение теоремы дедукции Ф1,Ф2,…,Фn├ Фn+1 <=> Ф1,Ф2,…,Фn-1├ Фn→ Фn+1 <=> Ф1,Ф2,…,Фn-2├ Фn-1→( Фn→ Фn-1) <=> <=>├ Ф1→( Ф2→(… Фn-1→( Фn→ Фn+1))) Правило силлогизма. Если А→В и В→С, то А→С, т.е. А→В, В→С├А→С Доказательство правила силлогизма (по теореме дедукции): докажем сначала вывод (1) А→В, В→С, А ├ С. Тогда по теореме дедукции будет доказано правило силлогизма. Список вывода для (1): А, А→В, В, В→С, С Пример. Доказать теорему: ├(АВ)→(В→А). Доказательство: ├ АВ→А - акс 3 ├ А→(В→А) –акс.1, тогда по правилу силлогизма: ├ АВ→(В→А) Теорема 3 ├(А→В)→((В→С) →(А→С)) Доказательство: по теореме дедукции теорема 3 следует из А→В├(В→С) →(А→С), или следует из правила силлогизма А→В, В→С├А→С . Правило перестановки: А→(В→С)├ В→(А→С) Доказательство: по теореме дедукции А→(В→С),В├А→С <=> А→(В→С), В, А├ С, докажем последний вывод С: А, А→(В→С), В→С, В, С. Теорема 4 ├ (А→(В→С)) →(В→(А→С)) Доказательство: по теореме дедукции теорема 4 следует из правила перестановки А→(В→С)├ В→(А→С). Правила с конъюнкцией: а) А, В├АВ б) АВ├ А в) АВ├ В г) АВ├ ВА Доказательство б): аксиома 3 АВ→ А <=> АВ├А в): аксиома 4 АВ→ В <=> АВ├ В Доказательство а) состоит из двух частей: 1) докажем вспомогательную теорему ├(А→В) →(А→ АВ). По аксиоме 5 (А→В)→ ((А→С)→(А→(АС))) В:=А; ├ (А→А) → ((А→С)→(А→(АС))); ├ (А→А) – теорема 2 => ├(А→С)→(А→(АС)) по m.p. С:=В; ├(А→В)→(А→(АВ)) 2) доказательство правила: А,В├ АВ В, В→(А→В), А→В, (А→В) →(А→ АВ), А→ АВ, А, АВ Теорема 5. . Доказательство: по теореме дедукции теорема 5 следует из правила а) с конъюнкцией: А, В├АВ. Правило соединения посылок А→(В→С) ├ АВ→С Доказательство: А→(В→С), АВ├ С по дедукции, докажем вывод С: АВ, В, А, А→(В→С), В→С, С Теорема 6(а): ├ А→(В→С) →(АВ→С). Доказательство: по теореме дедукции теорема 6(а) следует из правила соединения посылок: А→(В→С) ├ АВ→С. Пример. Доказать теорему├ (А→В) (В→С) →(А→С). Доказательство: теорема 3: ├(А→В) →((В→С) →(А→С)) => по правилу соединения посылок: (А→В) (В→С) →(А→С). Правило разъединения: АВ→С├ А→(В→С) Доказательство: АВ→С, А├ В→С по дедукции <=> АВ→С, А, В├ С, докажем вывод С: А, В, АВ, АВ→С, С Теорема 6 (б): ├ АВ→С→ (А→(В→С)) Доказательство: по теореме дедукции теорема 6(б) следует из правила разъединения посылок: АВ→С├ А→(В→С). Правила с дизъюнкцией а) А├ АВ б) В├ АВ в) АВ├ВА д) доказательство разбором случаев. Пусть Г-список гипотез, А, В, формулы. Если Г, А├ С и Г, В├ С, то Г, АВ├ С Доказательство правила д): Дано: 1) Г, А ├ С <=> Г├ А→С Г, В ├ С <=> Г├ В→С 2) акс. 8: (А→С)→((В→С) → (АВ→С)) равносильна (по дедукции) А→С├(В→С)→ (АВ→С) равносильна (по дедукции) А→С, В→С├ АВ→С. Из 1) и 2) по свойству вывода 4 формулы следует Г├ АВ→С, что равносильно Г, АВ├ С . Пример: доказать клаузу про губернатора . Доказательство по правилу г): а) - докажем. Список вывода: (использована аксиома 9 и правило а) с дизъюнкцией) б) (использована аксиома 9 правило б) с дизъюнкцией) Непротиворечивость и полнота аксиоматической теории Определение: Аксиоматическая теория называется полной, если любая формула, выражающая логический закон (например, тавтология), выводима в этой теории (т.е. является теоремой) и верно обратное. Утверждение. Аксиоматическая теория с аксиомами 1-11 является полной, т.е. все теоремы являются тавтологией, если проверить с помощью таблиц. Доказательство состоит в доказательстве утверждения ├ Ф – теорема в исчислении вычисл <=> Ф – тавтология. Доказательство необходимости: Пусть ├ Ф – теорема => Ф – тавтология 1) все аксиомы являются тавтологией 2) если в тавтологию подставить формулу вместо буквы, получится новая тавтология 3) м.п., применяемое к тавтологии, приводит к новой тавтологии, и только Пусть ├А и А  И ├А→ В и А→ В  И по м.п. ├ В и является тавтологией, по определению импликации => Ф является тавтологией. Определение: Аксиоматическая теория является непротиворечивой, если А невозможны одновременно, что ├А и ├ Утверждение: Исчисления с высказываниями А1-А11 непротиворечивы. Доказательство: от противного – пусть А такое, что ├А и ├ => , что является противоречием. Определение: Система аксиоматических теорий независима, если не существует аксиом, выводимых из остальных. Утверждение: система А1-А11 является независимой, если существуют другие независимые системы:  Лекция 4. Логика предикатов. Определение предиката. Операции над предикатами. Формулы логики предикатов. Интерпретация формул. Законы логики предикатов. Приведенная форма формулы. Функция n-переменных Р(х1,х2,…хn) называется предикатом, если все переменные принимают значение из некоторых множеств, которые называются предметными (сами переменные также называются предметными), а функция Р принимает только два значения: И и Л. Число переменных n-местность предиката. Р(х) – одноместный предикат; Р(х,у) – двуместный предикат; Операции над предикатами. 1) Логические: &,V,¬,~,→; Пример: Р(х): «х-четное» Q(х): «х - делится на 3» Q(х)&Р(х): «х - делится на 6». 2) связывание квантором любой ; Пусть Р(х) – одноместный предикат, тогда (x)Р(х) - новый 0-местный предикат, который И тогда и только тогда когда Р(х)=И при любом х є М (предметное множество). Теорема. Если М – конечное множество, М = {х1,х2,…, хn}, то (х)Р(х)=P(х1)&P(х2)&…&P(хn). 3) связывание квантором существует ; Пусть Р(х) – одноместный предикат, тогда (x) Р(х) – 0-местный предикат, который И тогда и только тогда, когда существует х є М такое, что Р(х)=И Теорема. Если М – конечное множество, М = {х1, х2,…, хn}, то (х)Р(х)=р(х1)Vр(х2)V…Vр(хn). Определение формулы логики предикатов. 1) Алфавит: • Заглавные буквы: P,Q,R – символы предикатов; • Символы предметных переменных: xi, x, y, z; • Логические связки: ¬, &, V, →, ~; • Символы кванторов; • ( ); 2) Формула – слово, построенное по определенным правилам. Определение (формулы). 1) Пусть хi1, xi2,...,xik – предметные переменные, у которых индексы могут совпадать, тогда Р(хi1,xi2,...,xik) – атомарная формула, в которой все переменные называются свободными. 2) Пусть А –формула и известно, что х – её свободная переменная, тогда (х)А, (х)А – новые формулы, в которых х называется связанной, при этом А называется областью действия квантора . 3) Пусть А – формула, тогда (Ā) – формула, в которой все переменные, которые были свободные в А – свободны, а связанные – связаны. 4) Пусть даны две формулы А и В и не существуют переменных, которые одновременно свободны в А и связаны в В, или наоборот, тогда (АVВ), (А&В), (А~В), (А→В) – формулы, в которых все переменные, которые были связаны – остаются связанными, были свободными – остаются свободными. Интерпретация формул. Определение. Под интерпретацией понимают задание предметных множеств М и сопоставление каждому символу предиката, зависящему от n предметных переменных, входящих в формулу, индивидуального n – местного предиката, определенного на M. Пример. Ф1=Р(х,у)&Р(х,z); Ф2=Р(х,у)VР(у,z); x,y,z є М={-1,1}; 1)Интерпертация Р(х,у): «х=у»; х у z P(x,y) P(x,z) Ф1 P(y,z) Ф2 -1 -1 -1 И И И И И -1 -1 1 И Л Л Л Л -1 1 -1 Л И Л Л Л -1 1 1 Л Л Л И Л 1 -1 -1 Л Л Л И Л 1 -1 1 Л И Л Л Л 1 1 -1 И Л Л Л Л 1 1 1 И И И И И 2) Интерпертация Р(х,у): «х≤у»; x y z P(x,y) P(x,z) Ф1 P(y,z) Ф2 -1 -1 -1 И И И И И -1 -1 1 И И И И И -1 1 -1 И И И Л Л -1 1 1 И И И И И 1 -1 -1 Л Л Л И Л 1 -1 1 Л И Л И Л 1 1 -1 И Л Л Л Л 1 1 1 И И И И И Определение 1. Формулы Ф1 и Ф2 равносильны в данной интерпретации, если на любом наборе значений свободных переменных они принимают одинаковые значения. Определение 2. Формулы Ф1 и Ф2 равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М. Определение 3. Формулы Ф1 и Ф2 равносильны, если они равносильны на всех предметных множествах. Законы логики предикатов. 1) все законы логики высказывания; 2) Вынесение квантора из-под знака отрицания: ◦ ; ◦ ; 3) вынос квантора за скобки: • (х)(P(x)&Q(x))=(x)P(x)&(x)Q(x); • (x)(P(x)VQ(x))=(x)P(x)V(x)Q(x); 4) Пусть Q не зависит от х, тогда: • (х)(Р(х)&Q)=(x)P(x)&Q; • (x)(P(x)VQ)=(x)P(x)VQ; • (x)(P(x)VQ)=(x)P(x)VQ; • (x)(P(x)&Q)=(x)P(x)&Q; 5) Перестановка одноименных кванторов. Пусть х,у – свободные переменные формулы Р(х,у): • (x)(y)P(x,y)=(y)(x)P(x,y); • (x)(y)P(x,y)=(y)(x)P(x,y); *Разноименные кванторы переставлять нельзя. 6) Переименование свободных переменных: Пусть х – связанная переменная формулы А, тогда х можно заменить любой другой буквой, не входящей в А, в кванторе и всюду в области действия квантора. Формы записи формул. Определение. Формулы, в которых используются только ¯, &, V, а знаки ¯ стоят только над символами предикатов, называются приведенными. Утверждение. Для любой формулы логики предикатов существует равносильная ей приведенная формула. Алгоритм приведения. 1) сделать формулу булевой, используя законы логики высказывания; 2) использовать вынесение квантора из-под знака отрицания, далее законы де Моргана и двойного отрицания; Определение. Приведенная формула называется нормальной, если она или не содержит кванторов или все кванторы находятся впереди формулы. Лекция 5. Формы формул логики предикатов. Метод резолюций. Нормальная форма формулы. Сколемовская форма. Клаузальная форма. Выполнимость и общезначимость формул. Проблема разрешимости в логике предикатов. Метод резолюций в логике высказываний. Определение. Формула имеет скомлевскую форму, если : 1) она нормальная, 2) в ней удалены все кванторы существования по принципу: пусть - самое левое вхождение квантора существования в Ф и перед ним стоят кванторов всеобщности , тогда : I. Удаляем II. , где f- некоторая функция, называемая сколемовской (для каждого удаляемого квантора сколемовские функции обозначают различными буквами). 4. Клаузальная форма Определение. Формула имеет клаузальную форму, если она: • сколемовская • В скомлемовской форме опущены все кванторы • Оставшаяся часть формулы приведена к КНФ. Пример: Определение. Клаузальная форма в виде предложения: нужно заменить «» на «,» и получить список гипотез, являющихся элементарными дизъюнкциями. Пример : Выполнимость и общезначимость формул Определение. Формулой логики предиката называется выполнимой в данной интерпретации, если существует набор свободных переменных, на которых она истинна. Определение. Формула Ф выполнима в логике предикатов, если существует такая интерпретация, в которой она выполнима. Определение. Формула называется истинной в данной интерпретации, если она истинна на любом наборе свободных переменных из данного предметного множества. Определение. Формула называется общезначимой, если она истина в любой интерпретации. Утверждение. Формула общезначима тогда и только тогда, когда - не является выполнимой. Утверждение. равносильна в логике предикатов тогда и только тогда, когда - общезначима. Пример 1: Следующие формулы общезначимы: , где - фиксированное значение x , где - фиксированное значение x Проблема разрешимости в логике предикатов: существует ли алгоритм, который позволяет выяснить для любой формулы логики предикатов - является ли она общезначимой? Теорема Черча. Не существует алгоритма, который для любой формулы логики предикатов устанавливал бы, общезначима она или нет. Метод резолюции в логике высказываний Напомним, что доказать клаузу ├ D равносильно тому, чтобы доказать, что -тавтология. Определение. Клауза (Л- тождественная ложь) называется формой конъюнктивного противоречия для клаузы ├ D. Утверждение. Рассуждение логично тогда и только тогда, когда логично ├ D. Доказательство: ├ D равносильно → D= Определение. Множество функций {} называется невыполнимым, если конъюнкция формул - тождественная ложь, т.е. Л- противоречие. Любую клаузу ├ D можно заменить формой конъюнктивного противоречия , ├ Л, при этом данное рассуждение логично - невыполнимо. Правило резолюций: Доказательство: Определение (Резолютивный вывод): Пусть - элементарные дизъюнкции, тогда по правилу резолюций, если существует список вывода, такой, что: а) Последняя формула в списке совпадает с ; б) любая другая является или элементарной дизъюнкцией из списка , или получена из предыдущих по правилу резолюций. Теорема о полноте метода резолюции: Множество S элементарных дизъюнкций невыполнимо тогда и только тогда, когда из S выводится ложь по правилу резолюции Алгоритм метода резолюции: 1. записать клаузу ├ D в форме , ├ Л 2. все гипотезы , привести к КНФ, 3. в КНФ для любой гипотезы заменить на запятые , 4. сформировать новый список гипотез, 5. вывести Л по правилу резолюций. Лекция 6. Метод резолюции в логике предикатов Определение подстановки. Унификация формул. Правило резолюций для предикатов. Алгоритм метода резолюций в логике предикатов. Пример на доказательство методом резолюций. Хорновская клаузальная форма. Понятие о логическом программировании на языке ПРОЛОГ. Определение. Множество S= называется подстановкой в формулу Ф, где вместо переменных хi формулы Ф подставляется ti, где ti – некоторая функция, не зависящая от хi. Обозначение: S(Ф) – результат подстановки Пример: Пусть подстановка и Р(х, f(у), В), Р(х, f(В), В) –формулы, тогда произведем подстановку: S(Р(х, f(у), В)) = Р (А, f(В), В), S(Р(х, f(В), В) )= Р (А, f(В), В). После подстановки формулы стали одинаковыми. Определение. Пусть {Фi} – множество формул, S – подстановка. Тогда S унифицирует множество {Фi}, если S(Ф1)= S(Ф2)=…= S(Фn) Пример: Ф1=А(х)В(z); Ф2=А(f(у))В(g(t)) S={x/f(y), z/g(t) S(Ф1)=Ф2 Правило резолюции в логике предикатов Пусть S-подстановка, которая унифицирует Ф1 и Ф2, т.е. S(Ф1)= S(Ф2), тогда Ф1А, В├ S(А)S(В) Алгоритм метода резолюций для предикатов. *Замечание: нет алгоритма проверки на общезначимость в логике предикатов (т. Черча), но из логичности Р1,Р2,…,Рn├Д => Р1 Р2 … Рn→ Д - общезначимая формула. Сфера применения метода резолюций для предикатов: если известно, что рассуждение логично, то метод резолюции строит доказательство этого факта. Алгоритм: 1. Клауза Р1,Р2,…,Рn├Д записывается в эквивалентной форме Р1,Р2,…,Рn, ├Л (конъюнктивное противоречие) 2. Каждая гипотеза Р1,Р2,…,Рn, приводится к клаузальной форме. 3. Знаки конъюнкции заменяем на запятые в клаузальных формах гипотез (переходим к форме предложения). 4. Составляем S1,S2,…,Sn├Л (где S1,S2,…,Sn – элементарные дизъюнкции) и доказываем, используя правило резолюции (приводим резолютивный вывод из гипотез Si) Пример: Доказательство: 1.; (унификация и с помощью S={z/x}); 2. , (унификация и с помощью S={y/B}), 3. , (S={х/C}). Пример: F(x,y) «х является отцом у» S(x,y) «х,у – дети одного отца» M(x) «х - мужчина» B(x,y) «х брат для у» Известны правила: А1: ху(F(x,y) M(x)) А2: хуw((F(x,y) F(x,)  S(x, w)) А3: ху(S(x,y) M(x)  B(x,y)) Известны факты: А4: F(И,Б) А5: F(И,В) А6: F(В,Е), где И -Иван Б -Борис В -Василий Е –Елена. Запрос: Есть ли брат у Б? ( Д=zB(z,Б)). Доказать: А1, А2, А3, А4, А5, А6 ├Д 1) А1, А2, А3, А4, А5, А6,Д├л 2) а)А1: ху() – нормальная форма А1: -клаузальная в форме предложения, б) хуw= хуw А2: - клаузальная в форме предложения, А3: - клаузальная в форме предложения, А1, А2, А3 – хорновские клаузальные формы -клаузальная в форме предложения. Доказательство: S={х/И, у/B} S{y/Б}; S={z/B}. При этом известно, что z=B, следовательно, братом Б является В. Понятие о логическом программировании. Версии ПРОЛОГ берут за основу хорновскую клаузальную форму: Д:- Ф1,Ф2,…Фn - правило (гипотезы А1-А3) Пример: М(х):- F(x,y) S(y/w):- F(x,y), F(x,w) B(x,y) :- S(x,y), М(х) а) Д отсутствует: :-Ф1,Ф2,…Фn запрос :-В(z,Б)-пример запроса из примера б) Фi отсутствуют: Д:- факт (примеры фактов- гипотезы А4-А6) F(И,Б) :- F(И,В) :- F(В,Е) :- Программа – набор фактов и правил, которые мы создаем сами. По заданной программе и запросу система определяет, является ли запрос логическим следствием фактов и правил. Если в запросе существуют свободные переменные, то в процессе доказательства эти переменные конкретизируются и их значения являются ответом к поставленной задаче. Теория алгоритмов Лекция 7. Система рекурсивных функций Частичная числовая функция. Элементарные рекурсивные функции. Операторы суперпозиции и примитивной рекурсии. Определение 1 (частичной числовой функции): Пусть , пусть - функция переменных, тогда U- частичная числовая функция, если 1. 2. , где i= 1,2…n Определение 2: Если определение 1 для любого i и , то функция всюду определена. В противном случае, если существует , то функция частично определена Пример: всюду определена и частично, т.к Элементарные рекурсивные функции 1. Константа 0: 0(х)- равна 0 при любом х 2. Функция сдвига на 1: S(x)=x+1 3. Функция проектирования: Пример: Оператор суперпозиции Обозначается Определение. Функция n-переменных является результатом применения оператора суперпозиции к функции m -переменных и , где i=1...m, если Пример: а) h(x)=S(x) f(x)=0(x) Пример: б) Пример: Оператор примитивной рекурсии Обозначается: Пр 1 Оператор Пр для функции одной переменной , если f(x) удовлетворяет схеме Пример 1: Составить схему и найти f(3), если f(x)=Пр(2, х2+2у) f(1)=0+4=4; f(2)=1*1+2*f(1)=1+8=9; f(3)=2*2+2*f(2)=4+18=22; II Оператор Пр для f(x,y) f(x,y) – результат применения Пр к , если Пример 1. f(x,y) = Пр(2x,x+2y+3z) Составить схему и найти f(1,2) х=1 f(1,0)=2; f(1,1)=1+3f(1,0)=1+6=7; f(1,2)=1+2+3f(1,1)=1+2+3*7=24; Пример 2. f(x,y)=2(x+2y)2+1; Составить схему рекурсии. f(x,y)= Пр(2х2+1,z+8х+16у+8). III Общий случай: оператор Пр к f(х1,х2,…,хn, y) F – результат применения Пр к φ(х1,х2…, хn) и ψ(х1,х2,…,хn), если: Определение. Функция называется примитивно рекурсивной, если она получена из основных, элементарных функций (O,S,I) с помощью только двух операторов Пр и Snm, примененных конечное число раз. Утверждение 1. Пусть f(x1,x2,...,xn)=Snm(φ,x1,x2,...,xn) и известно, что φ,f1,f2,...fn) є Кпр следовательно, f(x1,x2,...xn) є Кпр. Утверждение 2. Пусть f(x1,x2,...xn,y) = Пр(φ(x1,...xn),ψ(x1,...,xn)) и известно, что φ и ψ є Кпр , тогда и f є Кпр. Примеры примитивно рекурсивных функций. Пример 1. f(x,y)=x+y f(x,y) = Пр(I(x),z+1) = Пр(I1(x), I3(x,y,z+1) = Пр(I1(x), S11(S(x),I3(x,y,z)) є Кпр. Пример 2. f(x,y)=xy Пр F(x,y) = Пр(O(x),z+x) = Пр (O(x),S32(x+y,I3(x,y,z),I1(x,y,z))) Пример 3. f(x,y)=xy f(x,0) = x0=1(x)=S(0,(x)) є Кпр f(x,y+1) = x(y+1)=xy*x=f(x,y)*x; f(x,y) = Пр(S(0(x)),z*x)= Пр(S(0(x)),S32(x+y,I3(x,y,z),I1(x,y,z)). Утверждение 3. Любая линейная частично числовая функция n–переменных f(x1,x2,...xn)=Ax1+Bx2+...+Cxn+D, где A,B,C,D є N={0,1,2...}, является примитивно рекурсивной. Док-во. 1) Любая линейная функция 0 переменных является примитивно рекурсивной, так как получается применением оператора суперпозиции к константе 0 (конечное, но произвольное число раз). 2) Предположим, что любая линейная функция k-переменных є Кпр. Докажем тогда, что линейная функция для k+1 переменных є Кпр. F(x1,x2,...xk,xk+1)=Ax1+Bx2+...+Cxk+Dxk+1+E Пр f(x1,...,xk+1) =Пр(Ax1+Bx2+...+Cx4+E,z+D) = Пр(φ,Sn+21,In+2(x1,x2,...,xn+1,z). Лекция 8 Оператор минимизации. Машины Тьюринга. Оператор минимизации для функции одной переменной. Оператор минимизации для функции двух переменных. Описание машины Тьюринга. Функции информационной ленты, управляющего устройства, считывающее-записывающей головки. Команда и программа машины Т. Конфигурация на ленте. Работа машины Т. I. Оператор минимизации для функции одной переменной. g(x)=μxf(x) Определение. G - Построена из f с помощью μ, если: 1) составлено уравнение минимизации: f(y)=a (*); 2) если уравнение (*) имеет решение y0 є N и при всех таких y є N, что y. Конфигурация на ленте в момент t. 1) Машинное слово, записанное на ленте, где Р0=а0 или P=ai1 ai2 ... ais; где ai1 ai2 ... ais –символы внешнего алфавита (причем первый и последний – не пустые). 2) Внутреннее состояние машины Т в момент времени t: qi. 3) Положение головки. Символьная запись конфигураций. ai1 ai2 ...q1aip ... ais ; aip - обозреваемый символ; 1 q1 q10R q20R q2 q01S q10R K1= q111101 1 1 1 1 K2= 0q21101; K3=q1101; K4=q201; K5=q011; Принцип работы машины Т. 1) начальное состояние работы: задана начальная конфигурация на ленте К1 где Р1 – слово в начальный момент t (входное слово); q1 – начальное состояние положения головки. 2) Принцип работы: пусть известна конфигурация в момент t, где qi – внутреннее состояние, а aj – слово, обозреваемой головкой, следовательно по программе Т находятся команды qiaj. 3) Остановка: А) нет команды, начинающейся с qiaj. Б) выход на одно из конечных состояний; При этом, если произошёл останов, то текущая конфигурация К0 – заключительная конфигурация с Р0 – заключительным словом. Применимость и неприменимость машины к слову. Если К1-начальная конфигурация для работы машин Т с входным словом Р1, то: 1) Т применима к Р1, если она остановится за конечное число шагов в некоторой заключительной конфигурации К0 с заключительным словом Р0. 2) Т неприменима к слову Р1, если она никогда не применима к слову. Пример. 1 q1 q10S q11S Не применима ни к одному слову. Обозначения. К1├К0 – случай остановки (заключительная конфигурация выводится из начальной) [P]n – повтор слова n раз. Р= 111110001111111=150317; Р= 101010=103; Начальная конфигурация по умолчанию: а) Р1≠а0 – входное слово; б) головка смотрит на крайнюю левую единицу; Пример. q11n├ 1n+10 - приписать справа 1. 1 q1 q21L q11R q2 q00R q21L Лекция 9. Операции над машинами Т. Произведение и итерация машин Тьюринга. Разветвление машин Тьюринга. Схемы машин. Вычислимость по Тьюрингу. I. Последовательное подключение (произведение машин). Пусть Т1=<А1,Q1, П1>, Т2=<А2,Q2, П2> Ai-внешний алфавит; Qi-внутренний алфавит; Пi-программа; Q1∩Q2=ø (внутренние состояния Т1 и Т2 обозначаются различно) Т=Т1*Т2, если конечное состояние qT10машины Т1 заменяется на начальное состояние qТ20 машины Т2, тогда Пример. T1 1 q1 q20L q11L q2 q20L q01S T2 1 q1 q00S q10L a) T=T1*T2; T 1 q1 q20L q11L q2 q20L q31S q3 q00S q30L K1=11q1011; K2=1q21011; K3=1q31011; K4=q310011; K5=q3000011; K6=q0000011; b) T́΄=T2*T1; T΄ 1 q1 q20S q10L q2 q30L q21L q3 q30L q01S K1=11q1011; K2=11q2011; K3=1q31011; K4=1q01011; Замечание: Т1*Т2≠Т2*Т1; Определение (степени машины). T2=T*T; Tn=(Tn-1)*T; Пример. A 1 q1 q10L q21L q2 q01S q10L T=A3; A 1 q1 q10L q21L q2 q31S q10L q3 q30L q41L q4 q51S q30L q5 q50L q61L q6 q01S q50L II. Итерация машины Т по паре состояний. Пусть программа Т имеет по крайней мере 2 конечных состояния и qi0 – одно из них. Пусть qj – любое состояние Т, не являющееся конечным. Тогда, заменяя состояние qi0 на qj, получаем Т(qi0,qj )=. Где Q’- внутреннее состояние, из которого выбрано qi0; П’- программа с заменой. Пример. Написать программу T(q20,q1) T 1 q1 q11R q21R q2 q100R q201R T` 1 q1 q11R q21R q2 q100R q11R K1=q10011001001; K2=1q1011001001; K3=11q111001001; K4=111q21001001; K5=1111q20001001; - работа Т остановлена; K5=1111q1001001; K6=11111q101001; K7=111111q11001; K8=1111111q2001; K9=170q1001; - работа Т` остановлена; III. Разветвление. Пусть Где Qi∩Qj ≠ ø и программа П1 имеет не менее двух конечных состояний. Тогда Т называется разветвлением Т2 и Т3, управляемых Т1, если в П1 заменить qi0 на qT21 начальное состояние T2, а в П2 заменить qj0 на qT31 начальное состояние T3. Тогда разветвление Т: где в П’1 производится замена состояний. Пример. A 1 q1 q21R q101S q2 q200L q11L B 1 q1 q21R q01S C 1 q1 q10R q21S q2 q11L q00L T 1 q1 q21R q31S q2 q50L q11L q3 q30R q41S q4 q31L q100L q5 q51R q201S Схемы машин Т. Условные обозначения: ТiTj – произвольное или последовательное подключение - разветвление; Итерация: Пусть Т=…Т1…Т2… - схема без итерации, тогда …- итерация по паре состояний {qT20,qT11} Где qT20 – конечное состояние Т2, qT11- начальное состояние Т1. * Если в схеме пары машин и , то проводится итерация по следующим параметрам: и . Пример. A 1 q1 q21R q101S q2 q201L q10R B 1 q1 q10L q01S C 1 q1 q11L q20R q2 q01S q11L T 1 q1 q21R q31S q2 q51L q10R q3 q30L q41S q4 q40L q101S q5 q61R q71S q6 q201L q50R q7 q70L q81S q8 q80L q91S q9 q90L q301S q10 q101L q110R q11 q401S q01L Вычисление частично числовых функций на машине Т. U= f(x1...xn) xi Кодирование чисел и наборов чисел. К(0)=1; К(1)=11: ……………. 2) Пусть , тогда Пример. К(0,1,5)=1011016; Вычислимые функции. Определение. Частично-числовая функция называется вычислимой по Тьюрингу, если машины Тьюринга Тf: 1) Если f определена на наборе , то машина Тf, начав работу в конфигурации закончит работу (через конечное число шагов) в заключительной конфигурации . 2) Если не определена на , то начав работу в конфигурации К1 (см. 1), машина не остановится. Пример. Доказать, что f(x,y)=x+y є Kвыч. q11x+101y+1├ q01x+y+1; q1 1 1 1 1 ... 1 X + 1 Y + 1 x+y+3 – убрать 2 единицы 1 q1 q11L q11R - проход х+1 единиц вправо q2 q30R q21L - переход х+1 раз влево q3 - q10R - стирание 1 q4 - q00R Лекция 10. Вычисление функции на машинах Тьюринга. Совпадение классов вычислимых и частично-рекурсивных функций. Алгоритмические схемы Ляпунова. Если f – определена на , то Если f не определена на , то зациклится Пример. f(x,y)=xy= Т=Т1*Т2, где Т1 – машина, Работа Т2: (x+y+1) единца , если x+y нечетно x+y+1 четно 1) q1111 0q211 00q11 000q20 2) q11111 0q2111 q111 q21 q10 q201 q211 Ответ: подкл. Т2 и Т1 Пример. f(x)>0 а) х=0 k1=q11├  б) x=1 k1=q111├q011 в) q11n├q01 n  3 Т 1 q1 q2OR q2 q2OS q3OR q3 q41L q4OR q4 q01L q4OR q11111 q2111 q311 q41 q40 q01 q111 q21 q30 q401 q011 Вычислимость частично-рекурсивных функций Теорема 1. Элементарные рекурсивные функции О(x), S(x), Im(x1,x2..xn)=xm вычислимы (Kвыч)/ Док-во. 1) прогр. выч. О(х); q11x+1├q01 T 1 q1 q01S q1OR 2) S(x)=x+1 q11x+1├q01x+2 T 1 q1 q01S q11R 3) прогр Im а) прогр I2(x,y,z)=y TI 1 q1 q2OR q1OR q2 q3OR q21R q3 q4OL q3OR q4 q4OL q51L q5 q5OR q51L q1110111011 q10111011 000q2111011 111q2011 110q311 111000q30 111000q30 11q41 1q511 q5011 q50111 б) общий случай 1 q1 q2OR q1OR q2 q3OR q21R qm-1 qm qm-1OR qm qm+1 qm1R qm+1 qm+2 qm+1OR qn qn+1OL qn OR qn+1 qn+1OL qn+21L qn+2 q0OR qn+21L Теорема 2 1) Пусть . Если 2) Если f = Пр() и 3) Если и g  kвыч Напомним: fkr.p., если f может быть построена из основных элементов функций с помощью , примененное конечное число раз. Следствие (из T1, T2) kr.p.  kвыч (если f kr.p. => f  kвыч ) Алгоритмические схемы Ляпунова Исходные объекты: операторы 3х типов: 1) Операторы преобразований: А, В, С (со скобками и условными символами) *Ф(1 ) пример: преобразование записи на ленте, движение на ленте и т.д. 2) Операторы проверки логических условий: р - вычисляют значение некоторых предикатов. 3) Служебные операторы:  - конец работы алгоритма, * - указание на начало вычисления в момент t Определение схемы Ляпунова: Последовательность операторов трех типов, в которых для всех стрелок операторов проверок логических условий указано, куда ведут эти стрелки. Пример: Принцип работы схемы 1) t должен выполняться тот оператор, перед которым стоит  2) если …А…, где А – оператор преобразования, то работает А и схема преобразования …А… 3) если …р…, где р - оператор проверки логического условия а) Если рИ (значение предиката выч операт), то …р… (выполняется следующий оператор) б) Если, то …р…, (выполняется тот оператор, на который указывает стрелка) 4) … – конец работы Пример 1. схема произведения, когда Т1 имеет 2 конечных состояния и Т2 подключается по одному из них. Интерпретация 1) А0 –работа машины Т1. 2) р Пусть - конечное состояние Р и л 3) А1 – работа Т2 Работа схемы: 1) 2) сделала работа Т1 если Т1 закончит работу в q0, то 3) должна работать Т2 4) остановка Если Т1 завершит работу в 3) остановка (т.е. Т2 не работала) Пример. Схема для разветвления машин 1) А1 – работа Т1, которая управляет разветвлением А2 – работа Т2 А3 – работа Т3 2) р - аналогично предыдущему примеру - конечное состояние Т1 3) рЛ (безусловный переход по ) Работа схемы: 1) 2) 3) Т1 заканчивает работу в q0 4) проработали Т1 и Т2 5) остановка 3*) 4*) Пример. Схема Ляпунова для f(x) = 2x; Замечание Интерпретация: 1) а’ – обзор в момент t; аn – следует за а’ p 1 q1 - q21R q2 OL 1L 2) О(а’) – стирание обозреваемой единицы; O() 1 q1 - q00R А1 1 q1 q20R q11R q2 q00S q21R q111 1q11 11q10 110q20 1100 q111011 1q11011 11q1011 110q211 1101q21 11011q21 11011q20 11011q00 4) Ф(011) приписываем в конце слова 2 единицы 5) L – проход влево на начальные записи L 1 q1 q20L q11L q2 q00R q21L 6) РЛ (всегда по стрелке) 7) Ф’(011) приписываем 1 в конце записи Ф‘ 1 q1 q01S - L’ 1 q1 q00R q11L 8) L’ - поход на начальный ответ f(x,y) = x-y, max(x,y) f(x,y) = x-y, min(x,y) Лекция 11 Нормальный алгоритм Маркова. Алгоритм- понятие неопределяемое. Существует интуитивное представление об алгоритме. Например, алгоритм в произвольном алфавите можно представить как предписание, определяющее потенциально осуществимый процесс последовательного преобразования абстрактных слов в алфавите А, который допускает любое слово в данном алфавите в качестве начального. Пример. А ={а, b} Описание алгоритма: 1) Если X = аР, где Р – слово, то зам х на Y = Рb. 2) Если X = bаР, то Х зам на Y = Раbа; применяется до тех пор, пока не получится слово вида  X = ааР, тогда Р – результат работы. В противном случае считать, что алгоритм не имеет результата; а) R0=abaab; R1=baabb; ; R2=abbaba; R3=bbabab; б) R0=babaa; R1=baaaba; ; R2=aabaaba; рез P=baaba; в) R0=baba; R1=abaaba; ; R2=baabab; R3=abababa; R4=bababab… - никогда не остановиться Любой интуитивный алгоритм в алфавите может быть реализован нормальным алгоритмом Маркова (тезис Маркова). Параметры, определяющие нормальный алгоритм Маркова. 1)Алфавит с выделенным пустым символом Л; слово в алфавите –последовательных символов в алфавита, может быть пустое 2) система подстановок (важен порядок) Определение. Пусть P,Q – слова в алфавите А. P Q – подстановка, означает заменить P на Q Определение. Пусть R – слово в А, тогда P Q применяет и R, если P – подслово R? т.е. R=apb Пример. А={a,b,c} R0=cabbacb R1=ccabacb R2=cccaacb Правила работы алгоритма 1) Для начала работы нужно задать входное слово R0 2) Пусть Rn - текущее слово. Находится первая применимая к слову подстановка. Подстановка применяется 1 раз и получается новое слово Rn+1, а затем применяем правило сначала 3) а) завершение, если не применяется ни одна подстановка б) завершение, если только что была применена последняя подстановка в списке Пример. +11 11 А={+,1} R0=11+111+11+1; R1=111111+11+1; R2=111111111+1; R3=11111111111 R4= R3 Пример 2. А={1,+, л} 1++1 +++ +л R0=11+11+1; R1=1+111+1; R2=+1111+1; R3=+111+11; R4=+11+111; R5=+1+1111; R6=++11111; R7=+11111; R8=л11111. Пример 3. А={1,, а, л} 1x1x111; x1a; a1л R0=111*11; R1=11*1111; R2=1*111111; R3=*11111111; R4=а1111111; R5=111111 Пример 4. А={1,, Т, Ф} *11 Т*1 *1Т 1 Т Т1Ф Ф Т  Т Ф Ф11Ф Т1 Т ТФ Ф Ф 1 л1 Общие вопросы теории алгоритмов Под интуитивным алгоритмом понимают непотн точное описание, которое задает вычислительный процесс для обработки совокупности исходных данных и направленный на получение полностью определенных этими данными результата. В случае, если процесс заканчивается, алгоритм применим к совокупности исходных данных, в противном случае не применим. Общие черты алгоритмов 1) элементарность шагов 2) детерминированность (ясно, что делать дальше) 3) направленность (указано, что является результатом алгоритма) 4) массовость Параметры, характеризующие алгоритм 1) совокупность исходных данных 2) совокупность возможных результатов 3) совокупность возможных промежуточных результатов 4) правило начало работы алгоритма 5) правило непосредственной обработки промежуточных результатов 6) правило окончания работы 7) правило извлечения результата Тезис Черча: Любая эффективно-вычислительная функция является частично-рекурсивной. Тезис Тьюринга: любой интуитивный алгоритм можно реализовать при помощи машины Тьюринга. Тезис Маркова: Любой интуитивный алгоритм может быть реализован при помощи нормального алгоритма Маркова. Лекция 12. Неразрешимые проблемы теории алгоритмов. Элементы теории сложности. Проблема самоприменимости. Проблема применимости к входному слову. Вычислительная сложность. Проблемы классов Р и NP. Недетерминированные машины Тьюринга. I проблема самоприменимости: а) нумерация по Гёделю машин Т. Пусть А – внешний алгоритм всех существующих машин Т. Q – внутренний алфавит всех машин Т, {R,L,S}- функции движения. Введем нумерацию символов А начинаем с 0; Q начинаем с q0, вводим нумерацию команд движения R-1, L-2, S-3. Используем последовательность всех простых чисел, начиная с 2: 2,3, 5… Тогда, например, первая команда машины Т q1aq1bR будет закодирована 213a517b111. Определение. Номер машины Т (по Геделю) U(T)= - номер состояния (в момент t) - номер обозреваемого символа - номер состояния, в котором нужно идти по команде - номер символа, который нужно записать вместо обозреваемого. - номер символа движения Пример Найти номер машины, заданной программой Т: q11q11R, q10q01S. U(T)=21*31*51*71*111*131*170*190*231*293 Определение. Машина Т называется самоприменимой, если она применима к своему номеру, в противном случает Т- несамоприменима. Пример: (самоприменимая Т) 1 Т- применима к любому слову и к коду своего номера Пример: (несамоприменимоая) 1 Проблема самоприменимости алгоритмически неразрешима Существует ли алгоритм, который для любой машины Т устанавливает самоприменима она или нет? Ответ: Данная проблема алгоритмически неразрешима (т.е. не существует алгоритма, который решает данную проблему для произвольной машины Т) . По тезису Тьюринга достаточно доказать, что нет такой машины Т, которая решает данную проблему . Доказательство (от противного): 1) А должна быть применима ко всем U(T) 2) Пусть А останов. В конфигурации - обозреваемый символ, если Т- применима к U(T) 3) А останавливается в конфигурации , если Т неприменима к U(T) Если А существует, когда построена новая машина В: 1) В- применима к U(B) (коду), если Т неприменима к конфигурации U(T) 2) В неприменима к коду U(T), если Т применима к коду U(T) Программирование для В, полученное из А,если 1) заменили на , не являющеюся конечной 2) 11S- зацикленная остановка () 3) все остальные команды без изменений, т.к. в работе для любой Т, положим Т=В, тогда существует В ,тогда не существует. Проблема применимости к входному слову. Существует ли алгоритм, который для любой Т и любого входного слова Х устанавливает, применима ли Т к Х или нет. Утверждение. Проблема применимости к входному слову алгоритма неразрешима. Доказательство. Пусть существует D- машина Т, которая решает проблему Тогда: 1. D применима к входным словам U(T) OX 2. Остановка в конфигурации , если Т применима или Т неприменима к Х, т.к. D работает для любого Х, то положим Х=U(T), тогда подставляем в определение D, где D решает проблему самоприменимости, что есть противоречие. Теория сложности вычислений Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа. Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размеров входных данных, но и от самих данных. Например, количество операций алгоритма сортировки вставками значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать этой трудности рассматривают понятие временная сложность алгоритма в худшем случае. Временная сложность алгоритма — это, в худшем случае, функция размера входных данных (n) , которая показывает максимальное количество элементарных операций, затрачиваемые алгоритмом для решения экземпляра задачи указанного размера. Аналогично определяется понятие временная сложность алгоритма в наилучшем случае. Несмотря на то, что функция времени работы алгоритма в некоторых случаях может быть определена точно, в большинстве случаев выполнять точную оценку не стоит. При увеличении размера входных данных постоянные множители и слагаемые низшего порядка, фигурирующие в выражении для точного времени работы, подавляются эффектами, вызванными увеличением размера входных данных. Рассматривая входные данные большого размера, исследуя порядок роста времени работы алгоритма, мы изучаем асимптотическую эффективность алгоритмов (при n). Обычно алгоритм более эффективный в асимптотическом смысле будет более эффективным для всех входных данных, за исключением очень маленьких. Быстродействие (время выполнения) – количество элементарных шагов для выполнения алгоритма. Для машины Т- количество рабочих тактов для выполнения одной команды Определение. f(n)=0(g(n)), если существует С>0 , при любом nm Пример: Пример: найти временную сложность алгоритма сложения матриц А+В Число операций: - для АВ, где N-max размерность Класс сложности — это множество вычислительных проблем, для решения которых известны алгоритмы, схожие по сложности (например, времени исполнения). Два важных представителя: Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть полиномиально зависящим от размера ввода. Сюда относится сортировка, поиск во множестве, В класс NP входят проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера ввода, а это значит, неэффективные для больших задач. Вопрос о равенстве двух классов P и NP считается одним из самых сложных в области теоретической информатики, так как на него уже много десятилетий не было найдено ответа. Математический институт Клэя даже объявил награду размером в один миллион долларов тому, кто докажет равенство или неравенство P и NP. Пример: Выяснить является число составным максимальная длина входного b B=4 : 15=1111 Алгоритм: 1) 1