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

Пермский Государственный Технический Университет Кафедра Информационных технологий и автоматизированных систем Викентьева О. Л. Математическая логика и теория алгоритмов конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ Пермь, 2007 г. Введение Математическая логика - это современный вид формальной логики. Логика – это наука правильно рассуждать, имея какие-то утверждения, истинность которых проверена, например, на опыте. С помощью утверждений можно придти к новому утверждению, которое также может оказаться истинным. Исходное утверждение называется посылкой, результирующее утверждение – заключением. Пример 1. П1: Все люди смертны. П2. Сократ – человек. З: Сократ смертен. Пример 2. П1: Все граждане России имеют право на образование. П2: Иванов – гражданин России. З: Иванов имеет право на образование. Оба эти вывода имеют одну и ту же форму: Все А есть В; С есть А; Следовательно, С есть В. В этих рассуждениях нам не интересна истинность или ложность отдельных посылок. Нам важно знать вытекает ли истинность заключения из истинности посылок. Таким образом, основная задача логики – это формализация правильных способов рассуждения. Если при этом применяется математический аппарат, то такую логику можно назвать математической. Тема 1. Логика высказываний 1.1. Понятие высказывания Рассмотрим логику высказываний, которая лежит в основе всех других разделов математической логики (МЛ) и необходима для их понимания. Логика высказываний строится также как и другие математические теории. В качестве основных понятий берется некоторый класс объектов, а также некоторые свойства, отношения и операции над этими объектами. Основным объектом логики высказываний служат простые высказывания. Высказывание – это предложение, о котором можно сказать истинно оно или ложно. Примеры. 1. Число 100 делится на 5. 2. Число 3 больше числа 5. 3. Луна больше Земли. 4. Сегодня светит солнце. 5. Вечером мы пойдем в кино. Из простых высказываний с помощью некоторого числа логических операций можно построить сложные высказывания. 1. Число 100 делится на 5 и число 100 делится на 10. 2. Неверно, что 3 больше 5. 3. Сегодня мы пойдем в кино или мы пойдем в театр. При изучении логики высказываний не обращают внимание на содержание простых высказываний, а интересуются только их истинностью или ложностью. Сложные высказывания, получаемые из простых, будут также истинными или ложными. Их истинность или ложность будет зависеть от истинности образующих их простых высказываний. 1.2. Логические операции Для изучения логических операций введем следующую систему обозначений: • простые высказывания будем обозначать буквами a, b, c, …, x, y ,z; • значения истинности будем обозначать 1 – истинно, 0 – ложно. Действия логических операций будем представлять в виде таблиц истинности. 1. Отрицание или инверсия ( – НЕ) Пример. а: 7 делится на 5 без остатка. а: Неверно, что 7 делится на 5 без остатка. а а 1 1 Эта таблица и принимается в качестве определения операции отрицания. 2. Конъюнкция ( ,, ·, логическое И ) Действие операции определяется следующим образом: сложное высказывание аb истинно только в том случае, когда оба высказывания (а и b) имеют значение истинно. а b аb 1 1 1 1 1 Примеры. а. 6 делится на 3 без остатка (1); b. 10 больше 5 (1); с. 7 делится на 3 без остатка (0); d. 3 больше 7 (0); a&b=1 a&c=0 c&d=0 3. Дизъюнкция (,+,логическое ИЛИ) Действие операции определяется следующим образом: сложное высказывание ав ложно только в том случае, когда оба высказывания (а и в) ложны. a b ab 1 1 1 1 1 1 1 Примеры. аb=1 ac=1 cd=0 4. Импликация () “если а, то b” Действие операции определяется следующим образом: сложное высказывание аb ложно только в том случае, когда а истинно, а b – ложно. a b ab 1 1 1 1 1 1 1 А называется антецедентом, а b – консеквентом. 5. Эквивалентность (~) Действие операции определяется следующим образом: сложное высказывание а~b истинно, если а истинно и b истинно, или если а ложно и b ложно. a b a~b 1 1 1 1 1 1 Эквивалентность примерно соответствует употреблению выражения «тогда и только тогда». 6. сумма по модулю два a b ab 1 1 1 1 1 1 7. Штрих Шеффера ( , обратная конъюнкция И – НЕ) a b a  b 1 1 1 1 1 1 1 8. Стрелка Пирса (, обратная дизъюнкция ИЛИ – НЕ ) a b ab 1 1 1 1 1 1 1 Используя эти логические операции можно строить сколь угодно сложные высказывания. Приоритет выполнения операций: ⌐   ~  Пример: Сложное высказывание: «Если вы не пропускаете занятия и успешно занимаетесь, то Вы сдадите экзамен хорошо» можно записать следующим образом. Обозначим: П – пропускаете занятия; Y – успешно занимаетесь; Х – сдадите экзамен хорошо, тогда все высказывание запишется: Значение истинности всего выражения будет зависеть от истинности переменных обозначающих простые высказывания. Пример. Пусть a=1, b=0, c=0, d=1. Символы ⌐   ~  называются пропозициональными связками, a, b, c, … и т. д. - пропозициональными переменными. Выражение, построенное из пропозициональных переменных с помощью пропозициональных связок, называется пропозициональной формой или формулой. 1.3. Булевы функции 1.3.1. Некоторые определения из теории множеств Множество – фундаментальное неопределяемое понятие. Множество – это совокупность объектов, которые, с одной стороны, различны и отличимы друг от друга, а с другой стороны воспринимаются как единое целое. Пусть А и В – два множества. - упорядоченная пара, где первый элемент , а второй элемент . Декартово произведение - это множество пар Бинарным отношением f из множества А в множество В называется подмножество : . Функция - это такое отношение, что из и следует, что x=z, т. е. функциональность – это однозначность. Пример. А={1,2,3,4,5} B={1,4,9,16,25} ={<1,1>, <1,4>, <1,9>, <1,16>, <1,25>, <2,1>, <2,4>, <2,9>, <2,16>, <2,25>,….<3,9>, …. ,<4,16>,…..<5,25>} f={<1,1>, <2,4>, <3,9>, <4,16>, <5,25>} – это функция, где b=a2. 1.3.2. Булевы функции Функция называется функцией алгебры логики. y=f(x1,x2) – бинарная функция, y=f(x1,x2,…., xn) – n- арная функция. Пример. Т. о. каждое элементарное высказывание может принимать значение либо 0, либо 1. Каждому набору значений a, b, c соответствует одно значение всего сложного высказывания (0 или 1). Булеву функцию от n переменных можно задать таблицей истинности x1 ….. xn-1 xn f(x1, …,xn) 1 1 1 1 Переменные, которые принимают значения 0 или 1 называются булевыми переменными. Некоторые функции всегда принимают значение 1 (на любом наборе переменных). Такие функции называются тавтологиями. Некоторые функции всегда принимают значение 0 (на любом наборе переменных). Такие функции называются противоречиями. 1.4. Формулы Пусть - множество булевых функций. Формулой над F называется выражение либо переменная, либо формула над F. F называется базисом формулы, f – главной (внешней) операцией, ti – подформулами. Всякой формуле однозначно соответствует некоторая функция f. Это соответствие задается алгоритмом интерпретации, который позволяет вычислить значение функции при заданных значениях переменных. Зная таблицы истинности для функций базиса можно вычислить таблицу той функции, которую реализует данная формула. Примеры. 1. x1 x2 x1 x2 1 1 1 1 1 1 1 1 1 1 1 1 Функция реализует дизъюнкцию на базисе . 2. x1 x2 x1~ x2 1 1 1 1 1 1 1 1 1 Функция реализует дизъюнкцию на базисе . Таким образом каждая формула определяет некоторую логическую функцию, которую можно представить в виде таблицы истинности для этой формулы. Если в формуле имеется n переменных, то возможны 2n различных истинностных значений для этой формулы. Следовательно, таблица истинности будет иметь 2n строк. 1.5. Равносильные формулы Одна функция может иметь множество реализаций над данным базисом (т. е. ее можно записать с помощью различных формул). Формулы, реализующие одну и ту же функцию, называют равносильными. Обозначают . Пример. Пусть , . Доказать, что. Равносильность двух формул можно доказать с помощью таблиц истинности. Формулы равносильны, если их значения истинности совпадают на любом наборе значений истинности, входящих в них переменных. Таблица истинности для формулы А. x y z x~y xz A 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Таблица истинности для формулы B. x y z xz B 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Тот факт, что равносильность формул логики высказываний можно проверить непосредственно, связан с тем, что переменные, входящие в формулу могут принимать конечное число значений (2n). Но, если в формуле большое количество переменных, то вычисление всех значений истинности для формулы становится очень трудоемкой задачей. Равносильность формул логики высказываний аналогична тождествам элементарной алгебры, известным из средней школы. Но тождественное равенство алгебраических формул нельзя проверить простым перебором значений, т. к. число возможных значений переменных неограниченно, следовательно, доказательство равносильности никогда не закончится. В элементарной алгебре тождественные равенства формул устанавливаются с помощью небольшого числа основных тождеств – законов, связывающих между собой арифметические операции. Для логики имеют место следующие равносильности (рассмотрим только формулы, которые содержат знаки ): 1. Коммутативный А ВВ А АВ=ВА 2. Ассоциативный А(В С)(А В)  С А(ВС)=(АВ)С 3. Дистрибутивный А(ВС)(А В)(А С) А(В С)=АВ АС 4. Идемпотентности А АА А·АА 5. Поглощения А АВА А(А В)А 6. А 0 А А· 0 = 0 7. А 1=1 А·1=А 8. А =1 А =0 9. Закон де Моргана 10. = 0 = 1 11 Двойное отрицание = А 12. АВ В 13 А~В=А·В 14 АВ= ·В А· 15. А В = А В = А·В 16. А  В = =  1.6. Подстановка и замена Если в формулу входит переменная х, то это можно обозначить как . Если в формулу входит подформула , то обозначим это как . Вместо подформулы или переменной можно подставить другую формулу или переменную. В результате получится новая правильно построенная формула. Если подстановка производится вместо всех вхождений заменяемой переменной или подформулы, то результат обозначим: {, т. е. все вхождения переменной х заменяем на подформулу . Если подстановка производится вместо некоторых вхождений, то результат обозначим , т. е. первое вхождение заменяем на . Примеры. 1. Замена всех вхождений переменной х 2. Замена всех вхождений подформулы 3. Замена первого вхождения переменной х 4. Замена первого вхождения подформулы • Правило подстановки. Если в равносильных формулах вместо всех вхождений некоторой переменной x подставить одну и ту же формулу, то получатся равносильные формулы. • Правило замены. Если в формуле заменить некоторую подформулу на равносильную, то получится равносильная формула. 1.7. Формы представления высказываний Нормальная форма – это синтаксически однозначный способ записи формулы, реализующей данную функцию. Любую булеву формулу можно привести к равносильной ей формуле простого стандартного вида, которой будет являться дизъюнкция элементов, каждый из которых представляет собой конъюнкцию отдельных различных логических переменных либо со знаком отрицания, либо без него. Пример. Такая форма называется дизъюнктивной нормальной формой (ДНФ). Отдельный элемент ДНФ называется элементарной конъюнкцией или конституентой единицы. Аналогично любую формулу можно привести к равносильной ей формуле, которая будет являться конъюнкцией элементов, каждый из которых будет представлять собой дизъюнкцию логических переменных со знаком отрицания или без него. Такая форма называется конъюнктивной нормальной формой (КНФ). Пример. Отдельный элемент КНФ называется элементарной дизъюнкцией или конституентой нуля. СДНФ (совершенная ДНФ) – это такая ДНФ, в которой каждая элементарная конъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные конъюнкции не повторяются. Пример. СКНФ (совершенная КНФ) – это такая КНФ, в которой каждая элементарная дизъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные дизъюнкции не повторяются. Пример. Каждая формула имеет одну единственную СДНФ и одну единственную СКНФ. Тавтология не имеет СКНФ, а противоречие – СДНФ. Как мы знаем, каждая формула логики высказываний представляет некоторую булеву функцию. Возникает обратный вопрос: можно ли всякую булеву функцию представить некоторой формулой логики высказываний? Можно указать алгоритм, который позволяет по таблице истинности произвольной булевой функции от любого числа переменных построить некоторую формулу логики высказываний в СДНФ. Пример. Рассмотрим частный случай. Пусть f(x,y,z)=1 только в одном единственном случае. x y z f(x,y,z) 1 1 1 1 1 1 1 1 1 1 1 1 1 Тогда этой формуле будет соответствовать функция . Если рассматривать произвольную функцию, то необходимо выделить все наборы переменных, для которых функция принимает значение 1 и каждому набору поставить в соответствие конъюнкцию переменных и их отрицаний. Рассматриваемая функция будет представлена дизъюнкцией этих конъюнкций. Таким образом, установлена процедура, которая позволяет для всякой булевой функции записать соответствующую ей формулу. Пример. x y z f(x,y,z) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Выводы: 1. Каждая формула логики высказываний представляет собой некоторую булеву функцию и наоборот. 2. Различные формулы могут представить одну и ту же функцию (равносильные формулы) . 3. Существует много дизъюнктивных форм равносильных между собой. 1.8. Минимизация сложных высказываний методом Квайна Алгоритм: 1. Получить СДНФ. 2. Получить сокращенную ДНФ (СкДНФ), используя следующие равносильности: - неполное склеивание; - поглощение. 3. Построить импликантную матрицу, с помощью которой получить МДНФ. Пример. 1. - ДНФ - СДНФ 1 2 3 4 5 6 2. Применяя операции склеивания, получаем СкДНФ. 1-2: 1-5: 2-3: 3-4: 4-6: 5-6: 3. Импликантная матрица + + + + + + + + + + + + Выбираем импликанты, которые поглощают все конституенты единицы. 1.9. Полные системы функций 1.9.1. Система функций {} Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции . Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2n строк. Каждую строку можно представить в виде конъюнкции переменных х1,…хn, куда входит либо , либо . Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций. Пример. x y f(x,y) 1 1 1 1 1 1 1 Получим СДНФ, используя таблицу истинности. Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции? 1.9.2. Замкнутые классы Пусть множество булевых функций от n переменных. Замыканием F ([F]) называется множество всех булевых функций, реализуемых формулами над F. Множество функций (класс) называется замкнутым, если [F]=F. Рассмотрим следующие классы функций. 1. Класс функций, сохраняющих 0: . 2. Класс функций, сохраняющих 1: 3. Класс самодвойственных функций: , где . 4. Класс монотонных функций где . 5. Класс линейных функций , где + - означает сложение по модулю 2, а знак конъюнкции опущен. Теорема. Классы Т0, Т1, Т*, ТМ, TL – замкнуты. Доказательство. Чтобы доказать, что некоторый класс F замкнут достаточно показать, что, если формула реализована в виде формулы над F, то она принадлежит F. Рассмотрим доказательство для одного класса функций Т0. Пусть и . Тогда . Аналогичные доказательства можно привести для остальных классов. 1.9.3. Функциональная полнота Класс функций F называется полным, если его замыкание совпадает с Pn: . Другими словами, множество функций F образует полную систему, если любая функция реализуема в виде формулы над F. Теорема. Пусть заданы две системы функций и . Тогда, если система F – полная и все функции из F реализуемы формулами над G, то система G тоже полная. Доказательство. Пусть h – произвольная функция, . Тогда [F]=Pn, следовательно, h реализуема формулой , базисом которой является F (). Если выполнить замену подформулы fi на подформулу в формуле , то мы получим формулу над G. Следовательно, функция h реализуется формулой . Примеры: 1. Система {} – полная, т. к. любая логическая операция может быть выражена через дизъюнкцию, конъюнкцию и отрицание; 2. Система {} – полная, т. к. 3. Система {} – полная, т. к. 4. Система {|} – полная, т. к. , а {}и{} – полные системы. 5. Система {} – полная, т. к. Представление логической операции системой{}называется полиномом Жегалкина. Таким образом, всякая логическая операция представима в виде где - сложение по модулю 2, знак · обозначает конъюнкцию, . Теорема Поста: Система логических операций полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую 0, одну функцию, не сохраняющую 1, хотя бы одну несамодвойственную функцию, хотя бы одну нелинейную функцию и хотя бы одну немонотонную функцию. Пример. Докажем полноту системы {,,1}. f T0 T1 T* TL TM В каждом столбце должен быть хотя бы один «-» xy + - - + - xy + + - - + 1 - + - + + 1. Проверка на принадлежность классу T0. 2. Проверка на принадлежность классу T1. 3. Проверка на принадлежность классу T*. 4. Проверка на принадлежность классу TL. 5. Проверка на принадлежность классу TM. f(0,0)=0 f(0,1)=1 f(1,0)=1 f(1,1)=0 f(0,0)=0 f(0,1)=1 f(1,0)=1 f(1,1)=1 Тема 2. Логические исчисления Основная задача математической логики – формализация правильных способов рассуждения. Элементами логических рассуждений являются утверждения, которые либо истинны, либо ложны (простые высказывание или пропозициональные переменные). Из простых высказываний с помощью логических связок (операций) могут быть построены сложные высказывания. Таблицы истинности позволяют ответить на многие вопросы, касающиеся формул логики высказываний: о равносильности формул, о противоречивости и т. п. Но более сложные вопросы решить с помощью таблиц истинности нельзя. Поэтому рассмотрим другой метод – метод формальных аксиоматических теорий. 2.1. Интерпретация формул Пусть A(x1,x2,…xn) – пропозициональная формула, где x1,x2,…xn – пропозициональные переменные. Конкретный набор значений, который принимают переменные x1,x2,…xn называется интерпретацией. I(A) – значение формулы в интерпретации I. В одной интерпретации формула может быть истинной, а в другой – ложной. Формула, истинная в какой- то интерпретации – выполнимая. Формула истинная во всех интерпретациях – тавтология (тождественно истинная формула), иначе – противоречие. Пример 1. Докажем, что формула является тавтологией. Пример 2. Докажем, что формула является выполнимой. 2.2. Примеры тождественно истинных формул высказываний • Закон тождества. «Всякое высказывание является логическим следованием себя самого» x->x Доказательство сводится к построению таблиц истинности x 1 1 1 • Закон противоречия. «Для всякого высказывания неверно, что истинно и высказывание х и его отрицание. Доказательство сводится к построению таблиц истинности x 1 1 1 • Закон исключенного третьего. «Для каждого высказывания х истинно или само высказывание, или его отрицание» Доказательство сводится к построению таблиц истинности x 1 1 1 • Закон двойного отрицания. Отрицание от любого высказывания равносильно самому высказыванию. • Добавление антцедента (истина из чего угодно). Если х – истина, то для любого у истинно, что y->x. • Из ложного что угодно. • Modus ponens. Если x->y – истинно и x – истинно, то согласно закону mp можно заключить, что истинно у. Этот тип заключения очень часто используется при математических доказательствах. Пример. 1. Все простые числа, большие 2 – нечетны. 2. 7 – простое число. 3. Следовательно, 7- нечетное число. Здесь применяются 2 закона. Первый закон – закон заключения от общего к частному будет рассмотрен в логике предикатов. На основании этого закона преобразуется первая посылка заключения: Для всех х, если х – простое число большее 2, то х – нечетно. Согласно заключению от общего к частному высказывание если 7 – простое число большее 2, то 7 – нечетно – истинно. (А) 7 – нечетно (В) A->B – Истинно А – истинно Применяем mp, следовательно, высказывание 7-нечетно – истинно. • Modus tollens Или Этот закон применяется при доказательствах от противного. Он является двойственным к mp. • Закон силлогизма Этот закон позволяет строить сколь угодно длинные цепочки рассуждений. 2.3. Формальные теории Рассмотрим один из методов получения всех тождественно истинных формул логики высказываний. До сих пор мы рассматривали формулы как выражения для булевых функций. Теперь мы будем рассматривать формулы как последовательности символов, построенные по определенным правилам. Для этого нам сначала надо задать алфавит (латинские буквы, знаки логических операций и скобки). Затем определим понятие слова. Слово – конечная последовательность символов. Формула – это 1) любая переменная (x,y,z,…) 2) Если слова A и B – формулы, то слова и т. д. – формулы. Свойство формулы: Можно описать процедуру, которая устанавливает, является слово формулой или нет. Для преобразования формул применяются правила, которые называются правилами вывода. 1. Правило подстановки. 2. правило mp. Таким образом: Формальная теория - это 1. Множество символов, образующих алфавит А. 2. Множество слов в этом алфавите, которые называются формулами (). 3. Подмножество формул, которые называются аксиомами(). 4. Множество отношений между формулами, которые называются правилами вывода (R). Алфавит может быть конечным или бесконечным. Алфавит и множество формул (А и Ф) образуют сигнатуру теории. Множество аксиом (B) также может быть конечным или бесконечным. Если множество аксиом бесконечно, то оно задается с помощью конечного множества схем аксиом и правил порождения конкретных аксиом из схем аксиом. Аксиомы делятся на два вида: логические (общие для целого класса формальных теорий) и нелогические (собственные) аксиомы, которые определяют специфику и содержание конкретной теории. Множество правил вывода R – конечно. Выводимость. Пусть F1,F2,….Fn,G – формулы теории (Ф). Применяя к ним правила вывода R можно получить некоторую совокупность формул Ф1, такую, что . Про формулы из Ф1 можно сказать, что они выводятся из Ф за один шаг. Далее можно рассматривать множество формул Ф2, выводимых из Ф1 за один шаг, т. е. из Ф они выводятся за два шага , и т. д. Некоторая формула А будет считаться выводимой из Ф, если она выводима из Ф за конечное множество шагов, т. е. принадлежит множеству Фm. Примеры. 1. Пусть Ф=х1. Тогда x1{…}=A, т. е. с помощью правила подстановки можно получить любую однобуквенную формулу. Вывод: х,А., т. е. если из некоторого заданного множества формул выводима однобуквенная формула хi, то из этого множества выводимы все формулы. 2. Пусть Ф=(x1->x2). Тогда (x1->x2){( x1->x2)//x1}=( (x1->x2)->x2). Следовательно из Ф выводима формула ( (x1->x2)->x2) и сама формула (x1->x2). Применим к этим двум формулам правило mp. Получим формулу х2. Если A произвольная формула, то мы можем получить ее из х2 по правилу подстановки. Вывод: Если все формулы некоторого множества Ф’ выводимы из множества Ф, а А выводима из Ф’, то А выводима из Ф 3. Пусть Ф={A,}. Тогда из Ф выводима любая формула. Применяя mp к формулам , получаем формулу .Еще раз применим mp к , получим х. Следовательно, мы можем вывести любую формулу. Вывод: Если из какой-то системы формул можно вывести А и то такая система формул называется противоречивой, из нее выводится любая формула. Выводом формулы G из формул F1,F2,….Fn в формальной теории называется такая последовательность формул E1,E2,….Ek, что Ek=G, а любая формула Ei (i. Программу МТ можно представить в виде последовательности команд вида: , где D={Л, П, С}. (Л- переход влево, П – переход вправо, С – остаться на месте). Программу также можно представить в виде таблицы: q1 q2 …. qn a1 a2 …. am Пример. МТ добавляет к слову единицу. 1 1 1 Программа: (Если в воспринимаемой ячейке символ , и МТ находится в состоянии q1, то состояние не меняется, символ не меняется, УУ сдвигается вправо). (Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q1, то это значит, что УУ находится на начале слова, состояние меняется на q2, символ не меняется, УУ сдвигается вправо). ( Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q2, то это значит, что УУ передвигается по слову, состояние не меняется, символ не меняется, УУ сдвигается вправо). ( Если в воспринимаемой ячейке символ , и МТ находится в состоянии q2, то это значит, что УУ дошло до конца слова, состояние меняется на заключительное, символ меняется на 1, УУ останавливается). В виде таблицы эту программу можно записать следующим образом: q1 q2 1 Конфигурация МТ (машинное слово) – это слово вида , где p1 – слово в алфавите МТ (может быть пустое), qs – внутреннее состояние М, ai – воспринимаемый символ, p2 – слово в алфавите МТ. МТ переводит конфигурацию в конфигурацию ( ), если имеет вид , имеет вид , - одна из команд МТ. Для рассмотренного выше примера: 1. Команда переводит МТ из конфигурации в конфигурацию 2. Команда переводит МТ из конфигурации в конфигурацию и т. д. МТ останавливается при конфигурации , если не существует такой конфигурации , что (т. е. входит в , а среди команд МТ нет такой, которая бы начиналась с ). Тезис Тьюринга: Любой интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга. 5.2.3. Рекурсивные функции Будем рассматривать только числовые функции, т. е. функции, аргументы и значения которых принадлежат множеству натуральных чисел N (N=0,1,2,…). Если область определения функции совпадает с множеством , то функция называется всюду определенной, иначе – частично определенной. Пример: f(x,y)=x+y – всюду определенная функция, f(x,y)=x-y – частично определенная функция, т. к. она определена только для . Рекурсивное определение функции – это такое определение, при котором значение функции для данных аргументов определяется значениями той же функции для более простых аргументов или значениями более простых функций. Примеры: 1. Числа Фибоначчи (1, 1, 2, 3, 5, 8, …) это последовательность чисел f(n), где f(0)=1, f(1)=1, f(n+2)=f(n)+f(n+1). 2. Факториал (n!=1*2*3*…*n) f(0)=1, f(n+1)=f(n)*(n+1). Рекурсивные функции строятся на основе трех примитивных (заведомо однозначно понимаемых и реализуемых) функций. Их также называют простейшими. 1. S(x)=x+1 – функция следования. Примеры: S(0)=1, S(1)=2, S(-5) – не определена. 2. О(х)=0 – нуль-функция; Примеры: О(0)=0, О(1)=0, О(-5) – не определена. 3. Im(x1,x2,…,xn)=xm, (m=1,2,…n) – функция проектирования (выбора аргумента). Пример: I2(1,2,3,4,…n)=2. С примитивными функциями можно производить различные манипуляции, используя три оператора: суперпозиции, примитивной рекурсии и минимизации. 1. Оператор суперпозиции (подстановки). Пусть f – m-местная функция, g1,…gm – n-местные операции на множестве N. Оператор суперпозиции S ставит в соответствие операциям f и g1,…gm n-местную функцию h. Примеры: 1) Используя оператор суперпозиции, можно получить любую константу. S(O(x))=0+1=1 S(S(O(x)))=0+1+1=0+2=2 S(S…(O(x))…)=0+n, где число вложений функций следования n. 2) Используя оператор суперпозиции, можно выполнить сдвиг на константу n. S(x)=x+1 S(S(x))=x+1+1=x+2 S(S…(S(x))…)=x+n. 2. Оператор примитивной рекурсии Оператор R каждой (n+2)-местной операции f и n-местной операции g ставит в соответствие (n+1)-местную операцию h=R(f,g), удовлетворяющую следующей схеме: Для n=0 схема примитивной рекурсии имеет вид: , где а – константа, Пример: Вычисление факториала с использованием оператора примитивной рекурсии будет выглядеть следующим образом. Схема примитивной рекурсии образует процесс построения функции h, при котором на нулевом шаге используется функция g, а на каждом последующем шаге значение функции f от аргументов , номера y предыдущего шага и значения функции h, вычисленного на предыдущем шаге. Функция называется примитивно-рекурсивной (ПРФ), если она может быть получена из простейших функций с помощью оператора суперпозиции или оператора примитивной рекурсии. Примеры: 1) - примитивно-рекурсивная функция. Схема примитивной рекурсии: 2) - примитивно-рекурсивная функция. 3. Оператор минимизации (-оператор) , где y – выделенная переменная. Работу -оператора можно описать следующим образом. Выделяется переменная y, затем фиксируются остальные переменные . Значение у последовательно увеличивается, начиная с 0. Значением -оператора будет то значение у, при котором функция впервые обратилась в 0. Если функция не обратилась в 0 или принимает отрицательное значение, то значение -оператора считается неопределенным. Пример: g(x,y)=x-y+3; Зафиксируем х=1 и будем менять y. , т. к. 1-1+3=3 , т. к. 1-2+3=2 , т. к. 1-3+3=1 , т. к. 1-1+3=0 Следовательно, . Функция f(x1,x2,…,xn) называется частично рекурсивной (ЧРФ), если она может быть получена из простейших функций с помощью конечного числа применений операций суперпозиции, примитивной рекурсии и минимизации. Пример. f(x,y)=x-y - частична, т. к. она не определена, если x0. Про задачу П говорят, что она разрешима за полиномиальное время, если существует машина Тьюринга Т, решающая ее за полиномиальное время. Обозначим через Р класс задач, разрешимых за полиномиальное время. Имеется существенное различие между алгоритмами полиномиальной и экспоненциальной сложности. Ясно, что любой полиномиальный алгоритм более эффективен, кроме того, такие алгоритмы лучше реагируют на рост производительности компьютеров. Рассмотрим такой параметр как размер решаемой задачи на ЭВМ за единицу времени с помощью данного алгоритма. Тогда изменение данного параметра при переходе к ЭВМ в 100 раз и в 1000 раз большей производительности для различных функций временной сложности показан в таблице: Функция временной сложности Размер решаемой задачи за сутки То же на ЭВМ в 100 раз быстрых То же на ЭВМ в 1000 раз быстрых n N1 100 N1 1000 N1 n2 N2 10 N2 31,6 N2 n3 N3 4,64 N3 10 N3 2n N4 6,64+N4 9,97+N4 3n N5 4,19+N5 6,29+N5 Из таблицы видно, что в случае полиномиальных алгоритмов размер решаемой задачи при увеличении производительности ЭВМ увеличивается на мультипликативную константу, тогда как для экспоненциальных алгоритмов имеет место увеличение на аддитивную константу. Полиномиальные алгоритмы обладают свойством “замкнутости”, их можно комбинировать полиномиальные, используя один в качестве “подпрограммы” другого и при этом результирующий алгоритм будет полиномиальным. В силу приведенных причин используется следующая терминология: полиномиальные алгоритмы называют эффективными, полиномиально решаемые задачи называют легкорешаемыми, а экспоненциально решаемые задачи называют труднорешаемыми. Для практики важным является классификация задач по признаку труднорешаемости, хотя следует заметить, что установление легкорешаемости задачи еще не означает ее практическую решаемость. Например, установление полиномиальной оценки O(n1000) не гарантирует практической решаемости уже при начальных значениях n. Аналогичное замечание можно сделать относительно труднорешаемости. Заметим, что труднорешаемость задачи может быть связана с тем, что ее решение настолько велико, что не может быть записано в виде выражения, длина которого была бы ограничена полиномом от длины входа. Чтобы исключить этот тип труднорешаемости, рассматривается только такие задачи, которые имеют «короткий» ответ. Рассмотрим несколько примеров. Пусть М={1,2,…, n} – конечное множество, бинарное отношение на М. Рассмотрим задачу проверки – является ли R отношением эквивалентности (рефлексивное, симметричное, транзитивное). Будем задавать индивидуальную задачу матрицей Ясно, что R будет отношением эквивалентности тогда и только тогда, когда матрица AR имеет единичную диагональ, симметрична и выполнено соотношение где - матрица отношения R2. Кроме того, выполнено , где имеется в виду булево умножение матриц. Ясно, что сложность рассматриваемой задачи О(n2). 2. Бинарное отношение R называется связным, если для любых выполняется iRj или jRi. Бинарное отношение называется Эйлеровым, если элементы R R:(i1,j1);(i2,j2);…(it,jt), можно упорядочить так, что выполнено . Можно доказать, что связное отношение R является эйлеровым тогда и только тогда, когда число единиц в матрице AR совпадает в i-ом столбце и в i-ой строке для каждого . Это дает алгоритм сложности O(n2), проверяющий эйлеровость отношения R. 3. Бинарное отношение R называется гамильтоновым, если элементы М i1,i2,…,in можно упорядочить так, что выполняется соотношение (*) В настоящее время неизвестно полиномиального алгоритма, который проверял бы гамильтоновость отношения R. Тривиальный алгоритм требует n! упорядочений множества М и проверки условий (*), что, конечно, превосходит по величине любой полином от n. 4. Пусть f(x1,…,xn) – формула от булевых переменных x1,…,xn в некотором фиксированном базисе В. Формула f(x1,…,xn) называется выполнимой, если существует набор значений переменных x1 ,..., xn , такой, что f(x1,…,xn)=1. Формула f(x1,…,xn) называется мультиафинной, если она имеет вид где a1,…,at – константы. То есть f представляет собой конъюнкцию линейных форм. Рассмотрим задачу проверки выполнимости мультиафинной формулы. Ясно, что существование выполняющего набора для мультиафинной формулы сводится к существованию решения линейной системы уравнений. Алгоритм Гаусса дает оценку O(n3), поэтому рассматриваемая задача полиномиальна. Пусть формула f(x1,…,xn) имеет конъюнктивную нормальную форму, т.е. имеет вид: . Рассмотрим задачу проверки выполнимости для формул КНФ. В настоящее время неизвестно алгоритма полиномиальной сложности решения данной задачи. Тривиальный алгоритм требует перебор 2n наборов значений переменных и вычисления для каждого из них значения формулы. 5.5.2. NP задачи Определим теперь класс NP задач распознавания, т.е. имеющих ответ «ДА» или «НЕТ». Для того, чтобы задача I содержалась в классе NP требуется , чтобы если I имеет ответ “ДА”, существовало бы слово с(I) длины, ограниченной полиномом от размера I, такое, что задача с начальными данными с(I), I принадлежит Р. Слово с(I) называется удостоверением или догадкой для задачи I. Рассмотрим примеры. 1. Пусть дана задача проверки гамильтоновости бинарного отношения на множестве М={1,2,…,n}. Если R – гамильтоново отношение, то удостоверением этого будет последовательность элементов М: с(R)=i1i2…in. Имея пару с(R), R, можно проверить соотношение (*) и убедиться является ли R – гамильтоновым отношением. Следовательно, задача проверки гамильтоновости бинарного отношения лежит в классе NP. 2. Пусть дана задача проверки выполнимости формул КНФ. Если f(x1,…,xn) – выполнимая функция, то удостоверением этого будет соответствующий набор . Имея пару , f(x1,…,xn), легко убедиться, что f(x1,…,xn) выполнима. Формализуем эти идеи. Класс NP определяется через понятие недетерминированного алгоритма. Введем понятие недетерминированной машины Тьюринга. Схема недетерминированной машины Тьюринга: …… -3 -2 -1 1 2 n * x1 x2 ……... xn Отличие недетерминированной машины Тьюринга от обычной заключается в том, что недетерминированная машина (НТ) имеет дополнительно угадывающий модуль (УМ), который может только записывать на ленту слова из внешнего алфавита. Поскольку речь идет о задачах распознавания, то удобно считать, что машина имеет два заключительных состояния qY и qN, соответствующие ответам «ДА» и «НЕТ» соответственно. Работа машины имеет две стадии: 1-я стадия – угадывание. В начальный момент на ленте записано слово x=x1…xn – код индивидуальной задачи I, начиная с ячейки 1. В ячейке 0 записан знак раздела *. Угадывающий модуль просматривает ячейку –1. Затем УМ пишет произвольное слово с(х) по одной букве за такт в каждой ячейке с номерами – -1,-2,-3,… . В итоге 1-ой стадии конфигурацией машины будет с(х)*q1x. 2-ая стадия – решение. На этой стадии недетерминированная машина работает как обычная машина Тьюринга с конфигурацией с(х)*q1x. Если машина через конечное число шагов приходит в состояние qY, то говорим, что она принимает конфигурацию с(х)*q1x. Будем говорить, что недетерминированная машина принимает x, если существует слово с(х), такое что конфигурация с(х)*q1x принимается. Определим время работы недетерминированной машины (если х принимается) где t1(x) – время работы на стадии 1, т.е., по определению, ; t2(x) - время работы на стадии 2, т.е., по определению, , где tT – время работы обычной машины Тьюринга. Определим Недетерминированная машина НТ решает задачу П за полиномиальное время, еслидля некоторого полинома р. Временная функция определена только для тех индивидуальных задач х, которые принимаются машиной НТ. Определим класс задач NP как множество задач, для которых существует недетерминированная машина Тьюринга, принимающая за полиномиальное время те и только те слова, которые соответствуют индивидуальным задачам с ответом «ДА». Разберем теперь вопрос о взаимоотношении между введенными классами Р и NP. Ясно, что. Имеется много причин считать это включение строгим, однако этот факт пока не доказан (1992). Теорема. Если задача ПNP, то существует такой полином р, что П может быть решена детерминированным алгоритмом со сложностью O(2p(n)), где n – размер П. Выводы. 1. Алгоритм с трудоемкостью O(n) называется линейным. Линейный алгоритм ограниченное число раз просматривает входную информацию и для большинства практических задач является неулучшаемым. Если найден линейный алгоритм для решения задачи, то на этом ее решение заканчивается. 2. Алгоритм, сложность которого равна О(nc), где с – константа называется полиномиальным (класс Р). Говорят, что массовая задача решается эффективно, если существует алгоритм, имеющий полиномиальную сложность. Такая формализация не лишена недостатков. Например, алгоритм имеющий порядок О(n 1000000) вряд ли будет эффективно работать. Но на практике появление какого-нибудь полиномиального алгоритма приводит в конце концов к алгоритму, трудоемкость которого оценивается полиномом небольшой степени. В большинстве случаев эта степень не превосходит 3: O(n3), O(n2), O(n log(n)), . Пример: нахождение кратчайшего маршрута во взвешенном графе. 3. Алгоритм, сложность которого равна О(сn), где называется экспоненциальным (класс E). Пример: задача проверки совпадения булевых функций f(x1,…,xn) и g(x1,…,xn). Решение задачи состоит в составлении таблиц истинности функций с количеством строк 2n. 4. NP-сложные задачи. Пример: Задача коммивояжера из теории графов. Перебор всех маршрутов в графе из n вершин требует рассмотрения n! вариантов. Но n! растет быстрее, чем 2n. В недетерминированном алгоритме варианты выбираются случайным образом. Тогда, если повезет, то можно относительно быстро найти вариант, который буде удовлетворять заданным ограничениям. Такие задачи, имеющие недетерминированное решение, которое иногда удается найти за полиномиальное время и называют NP сложными. Существует мнение, что детерминированных алгоритмов решения таких задач не существует. NP сложные задачи не имеют гарантированных оценок времени решения. Даже незначительное изменение исходных данных приводит к резкому увеличению времени решения. Примеры. 1. Выполнимость. Дана КНФ, представляющая булеву функцию. Выяснить является ли она выполнимой. 2. Клика. Определить содержит ли граф клику мощности К. 3. Независимость. Определить содержит ли граф независимое множество из К вершин. 4. Ядро графа. 5. Гамильтонов цикл. 6. Раскраска графа. Определить существует ли правильная раскраска графа посредством К цветов. Имеется ряд задач, входящих в NP класс, для решения которых не найдено полиномиальных алгоритмов.