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

СОДЕРЖАНИЕ 1 ВВЕДЕНИЕ 3 1.1 История развития математической логики. Аспекты математической логики 3 1.2 Логические антиномии (парадоксы) 4 1.3 Теория алгоритмов. Задачи неразрешимые на ЭВМ 6 1.4 Понятие сложности алгоритмов 10 2 ЛОГИКА (АЛГЕБРА) ВЫСКАЗЫВАНИЙ 10 2.1 Логические операции 10 2.2 Формулы алгебры высказываний. Равносильность формул 11 2.3 Классы логических функций. Полнота и замкнутость 12 2.4 Булева алгебра и теория множеств 15 2.5 Нормальные формы логических (булевых) функций 16 2.6 Минимизация булевых функций 16 3 ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ 19 3.1 Исчисления предикатов 19 3.1.1 Понятие предикатов 19 3.1.2 Кванторы 20 3.1.3 Формула логики предикатов 21 3.1.4 Методы доказательства в логике предикатов 24 3.1.5 Кванторы по предикатным переменным 25 3.1.6 Исчисление предикатов 1-го порядка как формальная система 26 3.1.6.1 Семантика и основные понятия 26 3.1.6.2 Формальная система исчисления предикатов 27 3.2 Метод резолюции 29 3.2.1 Задачи формального доказательства теорем. Приведение к противоречию. Метод резолюции для исчисления высказываний 29 3.2.2 Метод резолюции для исчисления предикатов 32 4 АЛГОРИТМИЧЕСКИЕ МОДЕЛИ 35 4.1 Элементы теории алгоритмов 35 4.1.1 Классификация универсальных алгоритмических моделей 35 4.1.2 Нормальный алгоритм Маркова (НАМ) 36 4.2 НАМ и алгоритмически неразрешимые задачи 37 4.3 Машина Тьюринга 39 4.4 Рекурсивные функции 47 4.5 Тезис Чёрча. Вычислимость и разрешимость 52 4.6 Основные неразрешимые проблемы (задачи) на языке РФ 52 4.7 Рекурсивные и рекурсивно-перечислимые множества (РМ и РПМ) 53 4.8 Теорема Райса 54 5 СЛОЖНОСТЬ АЛГОРИТМОВ 56 1 ВВЕДЕНИЕ 1.1 История развития математической логики. Аспекты математической логики Logikẽ - с греческого систематический метод рассуждений, заключений. Подразумевает разумность и внутреннюю закономерность. В научном смысле, логика – это наука о законах и формах мышления, анализ и практика мышления. Рассуждая, мы из исходных данных выводим заключения: Заключение может быть верным и не верным. Заключение не верно, когда неверны исходные данные или правило построения рассуждения содержит ошибки. Если рассуждения проводились в соответствии с нормами, а исходные данные выбраны из верной аксиоматики, то на заключение можно полагаться. С точки зрения философии, рассуждение должно быть последовательным, доказательным, непротиворечивым. Существует 4 закона философской логики: 1. Закон тождества. Все понятия в процессе рассуждения должны иметь определенные, присущие им, признаки и не должны подменяться другими понятиями, имеющими другое содержание. 2. Закон противоречия. Какому – либо объекту нельзя приписывать в одно и тоже время и в одном и том же отношении противоположные признаки. 3. Закон исключенного третьего. Из двух противоречащих (противоположных) суждений истинно только одно, т. е. третьего не дано. 4. Закон достаточного основания. Требует, чтобы истинность наших суждений была обоснована. Рассмотрим 3 аспекта математической логики: 1. Логика для математики. Математическая логика – это раздел математики, для исследования математических систем, связанных с логикой. В этом аспекте изучать математическую логику, значит изучать логику, используемую в математике. Это не исключает использование математической логики для изучения других логик. Математическая логика занимает особое место по отношению к другой математике. Математика является дедуктивной наукой, в том смысле, что понятие строгого доказательства является центральным для всех ее разделов. Задача объяснения природы строгости доказательства принадлежит математической логике. Это одна из ее основных задач. Усиленное внимание к основаниям математики, критический пересмотр ее фундаментальных положений, аксиом, способов построения строгой системы, доказательств, а также пересмотр логических приемов – все это привело к появлению и развитию математической логики. Самым фундаментальным понятием в математике является понятие множества. С этой точки зрения, любая математическая теория имеет дело с одним или несколькими множествами объектов. Все необходимые формальные свойства отношений самих объектов, необходимые для развития теории, фиксируются в виде аксиом. Теория логически строго построена, если в ней не используются никакие не упомянутые в аксиомах свойства объектов и отношений, а новые свойства и отношения выводятся по мере развития теории. Некоторая математическая теория называется дедуктивной, если она развивается из конечного числа аксиом при помощи построения сколь угодно длинных цепей рассуждения, каждое звено которых принадлежит конечному множеству. Возникает вопрос: почему многие математические задачи очень простые по формулировке, до настоящего времени, не имели решения или решались очень долго? Либо из-за того, что цепь звеньев из множества элементарных правил слишком длина, либо из-за того, что для решения новых задач нужны новые, не употребляемые ранее звенья логического вывода, либо множество аксиом недостаточно. Современная математическая логика дала ответ на этот вопрос – никакая единая дедуктивная теория не может исчерпать все разнообразие математических проблем. Даже в теории целых чисел существует множество неразрешимых проблем. 2. Математика для логики. Математическая логика – это логика, развиваемая с помощью математических методов. Зададимся вопросом: для изучения логики с помощью математики придется пользоваться логикой? Да. Оба аспекта верны. Мы встречаемся на первый взгляд с парадоксом. Но здесь нет парадокса, т.к. необходимо четко различать логику как предмет исследования (предметная логика) и логику как средство такого исследования. Для нее вводится специальный язык – метаязык. Примеры предметной логики: алгебра высказываний, Булева алгебра, исчисление предикатов, теория доказательств, вычислимость алгоритмов и т.д. 3. Теория алгоритмов. Как развитие математической логики в 20-х – 30-х годах 20-века появилась теория алгоритмов и связанная с ней задача алгоритмической разрешимости. Математический алгоритм – это строго определенный рецепт решения некоторого класса проблем. Все результаты, полученные в пределах определенной дедуктивной теории, могут быть также получены и вычислением, производимым по заданным правилам. И поэтому, ограниченности фиксированных дедуктивных теорем в теории алгоритмов соответствует теорема о невозможности существования универсальных алгоритмов, и соответственно неразрешимости общих классов математических проблем. 1.2 Логические антиномии (парадоксы) В конце 19 века в теории множеств были обнаружены противоречия, названные парадоксами. Открытие антиномий привело к появлению определенного недоверия к непогрешимости оснований математики. Некоторые парадоксы были известны раньше, но им не предавали необходимого значения. Противоречие получается, если в некоторой системе логических выводов могут быть получены формула (вывод), а также ее (его) отрицание. До конца 19 века математическое доказательство считалось строгим, если оно было логическим, причем эта строгость опиралась на логическую интуицию и не формулировалась. 1. Парадокс Кантора (1899 г.) Пусть М – это множество всех множеств. Его мощность известна: n=Р(М). С одной стороны мы можем для М образовать множество всех его подмножеств F(M). M={a,b,c}, n=3; F(M)={Ø, {a,b}, {b,c}, … ,{a,b,c}} Его мощность: |F(M)|=P(F(M))=2n, где n – мощность исходного множества. Получаем, что МÍF(M), т.к. n≤2n. С другой стороны, из определения множества М следует, что М – множество всех множеств и его любые подмножества, являясь множествами, являются элементами множества М, а их множества являются подмножествами множества М. Поэтому получим, что F(M) – подмножество M, следовательно|F(M)|≤|M|. Итак, одновременно |M| ≤|F(M)| и |F(M)| ≤|M| В этом парадоксе участвует своеобразное множество всех множеств, для него характерно, что М является своим собственным элементом: ММ. Пример: В библиотеке созданы разделы книг, для каждого раздела составим каталог и оформим его в виде книги. Этот каталог может содержать данные о самом себе как о книге. 2. Парадокс Рассела (1902 г.). Если парадокс Кантора возник на множестве, которое содержит само себя в качестве элемента, то парадокс Рассела связан со множествами, не содержащими себя в качестве своих элементов. Такие множества называются собственными. Множества, содержащие себя в качестве элементов, называются несобственными. Парадокс: существование множества всех собственных и только собственных множеств. Оно обозначается как R и называется Расселово множество. Парадоксальность заключается в том, что R является одновременно собственным и несобственным множеством. Сначала предположим, что R – собственное множество, тогда т.к. R является множеством всех собственных множеств оно должно содержать и себя, тогда оно по определению несобственное. Предположим, что R – несобственное множество, но, будучи, по определению множеством только собственных множеств, оно не может содержать себя в качестве элемента. Стало быть – оно собственное. Выразим этот парадокс в символической форме. Пусть х – элемент из R. Из определения Расселово множества следует, что xR<=>или xx. Заменяя xна Rполучим: RR<=>RR, что является противоречием. Парадокс Рассела можно сформулировать и для каталога книг библиотеки. Также, парадокс может быть сформулирован без привлечения понятия множества. 3. Парадокс Брадобрея. «Командир полка приказал полковому Брадобрею побрить всех, и только тех, кто сам себя не бреет». 4. Парадокс лжеца В обществе, состоящем только издвух типов людей: говорящих всегда только и говорящих всегда только ложь, любой человек говорящий «я лгу», противоречит себе, т.е. x=. Высказывание «я говорю правду» - всегда истинно, т.е. x=^. Парадокс иного вида включает в себя понятия отношения и определения. 5. Парадокс Берри. Множество всех натуральных чисел, которые могут быть названы прописью по-русски, с помощью конечного числа букв безусловно конечно. Следовательно, существует наименьшее из тех чисел, которое не может быть названо с помощью конечного числа букв, но фраза «наименьшее целое число, которое не может быть названо по-русски, меньше чем в сто букв» определяет число, лежащее за диапазоном (границей). Появление антиномии привело к сомнениям в фундаментальных положениях в математике, причем кризис в математике еще не преодолен до сих пор на 100%, но та часть теории множеств, которая необходима для обоснования остальных математических дисциплин, уже разминирована и достаточна. Само появление антиномии инициировало усиленное изучение основ математик и привело к появлению различных подходов, переработке, переосмысливанию этих оснований. Одно из тих направлений: конструктивное направление в математике, внесшее наибольший вклад. Конструктивное направление различает 2 типа бесконечных множеств: - актуально бесконечные множества (АБМ); - потенциально бесконечные множества (ПБМ). АБМ – готовое бесконечное множество, проверить свойства всех элементов невозможно. Правила логики, основанные на АБМ являются сомнительными. ПБМ – потенциально осуществимое бесконечное множество. Оно в каждый момент времени конечно, но существует правило, позволяющее добавить к нему еще несколько элементов, потом еще и т. д.. Поэтому анализ элементов ПБМ можно провести, исследуя правило, которое позволяет получать новые элементы. 1.3 Теория алгоритмов. Задачи неразрешимые на ЭВМ Слово «алгоритм» произошло от латинского перевода «Аль-Хорезми» - имени арабского математика 9 века. При интуитивном понятии алгоритма, под ним подразумевается решение поставленной задачи как последовательность некоторых операций, выполняемых по определенным правилам и инструкциям. Свойства алгоритмов 1. Дискретность. Алгоритм- это процесс последовательного построения величин, идущий в дискретном времени. Таким образом, в начальный момент задается исходная система величин, а в следующие моменты получается новая система величин по определенному закону из предыдущей системы величин. 2. Однозначность. Система величин, полученных в любой дискретный момент времени, определяется системой величин, полученных в предыдущий момент времени. 3. Элементарность шагов алгоритма. Закон получения последующих систем величин из предыдущих должен быть простым и локальным. 4. Результативность. Направленность на конечный результат. Если способ получения последующей величины не дает результата, то должно быть указано, что надо считать результатом в этом случае. 5. Массовость. Начальная система величин может выбираться из некоторого потенциального бесконечного множества. Введение 5 свойств не делает определение алгоритма строгим. Оно остается интуитивным. Области применения теории алгоритмов ТА возникла из-за необходимости разрешения внутренних потребностей математики. Такие разделы, как математическая логика, основание математики, анализ, алгебра остаются одной из областей приложения логики и теории алгоритмов. Другая область приложения возникла в 40-х гг. в связи с созданием ЭВМ. Далее появилась база данных, искусственный интеллект и т.д. Кроме того, теория алгоритмов оказалась тесно связана с такими областями, как лингвистика, экономика, физиология мозга, психология и т.д. Формальные модели представления алгоритмов Рассмотрим 2 вопроса теории алгоритмов: - доказать, что существует алгоритм решения некоторой конкретной задачи; - доказать, что для решения некоторой задачи нет алгоритма. Для ответа на 1-й вопрос достаточно интуитивного понятия алгоритма. Но его не достаточно для ответа на 2-й вопрос. Здесь нужно точно знать, что такое алгоритм. Такое определение получено в середине 30-х гг. 20 века в работах Черча, Гильберта, Геделя, Клини и Тьюринга, Поста. Они разработали две модели представления алгоритмов. 1. Рекурсивная функция (РФ). На основе гипотезы Черча, класс РФ тождественен классу вычислимых функций. Этого тезиса оказалось достаточно, чтобы обеспечить необходимую точность алгоритмических проблем и в необходимых случаях доказать алгоритмическую неразрешимость определенных проблем. 2. Тьюринг и Пост определили алгоритмические процессы как процессы, которые может совершить подходяще устроенная машина. Они в точных математических терминах описали очень узкие классы машин. Было доказано, что все алгоритмические процессы, описываемые математиками, могут быть представлены на этих примитивных машинах. Принято считать, что алгоритмы, реализованные на машине Тьюринга, являются эталонным представлением алгоритма решения соответствующей задачи. Позже было доказано, что класс функций, вычисляемых на данных машинах, совпадает с классом рекурсивных функций. Позже была разработана 3-я алгоритмическая модель: 3. Нормальные алгоритмы Маркова (НАМ). Это наиболее абстрактное представление алгоритмов, основанное на том, что все данные представляются в виде слова в каком-то алфавите, и существует система преобразований одних подслов в другие. Все три алгоритмические модели однозначно преобразуются одна в другую. Далее приведем ряд алгоритмически неразрешимых проблем (задач). (Что не могут делать машины). Пример 1. Может ли любая функция отображающая натуральное число в натуральное, вычисляться процедурой на некотором алгоритмическом языке? N→N или Nn→N Нет, не может. Мощность алфавита А: m=|A|; Длина любого алгоритмаконечна и пусть меньше или равняетсяn; Общее число алгоритмов, которое может быть разработано: mn, оно конечно, а множество всех N→N функций несчетно (несчетное бесконечное множество). Это результат был доказан Кантором в конце 19 века с помощью элементарного диагонального процесса. Пусть дан некоторый пересчет: f1(ј), f2(ј), f3(ј)…всех функций, отображающих натуральные числа ј в натуральные fі(ј) єN. Для наглядности, представим пересчет в виде бесконечной таблицы, строками у которой будут сами функции, а столбцами – аргумент. Определим новую функцию f(ј)=fј(ј)+1 , которая формируется только из диагональных элементов и отличается от них на 1. Она не входит в исходный пересчет, так как отличается от любой из уже перечисленных функций. Мы получили новую функцию f(ј), что противоречит тому, что исходный пересчет был пересчетом всех функций. Но результат этого примера ничего не говорит о том, какова природа невычислимости функции. Пример 2. Алгоритмическая неразрешимость проблемы останова произвольной процедуры по ее описанию и произвольному значению входных данных Представим, что у нас есть «умная» процедура Н, которая для любой процедуры P(n), где n - произвольное входное слово, позволяет решить, остановится ли вычисление процедуры P(n) или нет. Процедура H(n) Вычисления, определяющие остановится ли процедура P(n) (Р, n) Если P(n) останавливается, то H(n)=1 Иначе H(n)=0 Конец Н. Процедура P(n) L: Если H(n)=1 то идти к L Иначе возвратить n Конец P. Рассмотрим вычисление H(n). Если H(n)=1, то из описания процедуры Р следует, что она зацикливается , при этом H(n)=0 – противоречие. И наоборот H(n)=0, то из этого следует, что H(n)=1 – опять противоречие. Таким образом, H(n) не может существовать. Существует теорема: Не существует такой процедуры, которая для произвольной процедуры P и произвольногоn может установить, закончится ли вычисление P(n). Пример 3. Упростим постановку задачи в примере 2. Избавимся от непонятной хитроумности процедуры H. Удалим из Н проблему определения остановок Р и заменим его противоречием. Процедура H(n) Если Р(n)=0 то возвратить 1 Иначе возвратить 0 Конец Н. Процедура Р(n) Если H(n)=0 то возвратить 0 Иначе возвратить 1 Конец Р. Итак, H(n)= P(n)=H(n) -зацикливание и противоречие так как P(n)=. Неразрешимые задачи Пример 410-я проблема Гильберта. (1900 г.) Найти алгоритм, определяющий для любого диофантового уравнения, имеет ли оно целочисленное решение. F (x1,x2,…,xm)=0 степени n, все коэффициенты целочисленные В 1970 г эта проблема была решена ленинградским математиком Матиасевичем. Он доказал алгоритмическую неразрешимость этой задачи. Пример 5 Проблема Гольдбаха (1742 г.) Доказать, что любое целое число (≥6) может быть представлено в виде суммы 3-х простых чисел. Для нечетных больших чисел это было доказано Виноградовым в 1937 г. Для четных чисел это задача еще не решена. Пример 6 Доказать истинность хР(х) Если Р(х)- любой предикат. Другой пример – очень сложной, но алгоритмически разрешимой задачи. Пример 7 Теорема Ферма (сформулирована автором в 1647 г.). Он утверждал, что располагает доказательством того, что уравнение xn+yn=zn , x,y,z,nN при n>2 не имеет решения. Теорема была доказана в 1995 г. То есть эта задача оказалась разрешимой через ~ 350 лет. 1.4 Понятие сложности алгоритмов Существует 2 меры сложности: временная и емкостная. С точки зрения временной сложности, алгоритмы делятся на: - полиномиально сложные алгоритмы - экспоненциально сложные алгоритмы Задача решается с полиномиальной сложностью, если время решения пропорционально 0 (nm) , где n-размерность, m-степень полинома 0 (n1) – линейно сложная задача (например сумма векторов длиной n). 0(n2) – квадратичная сложность (например сумма матриц размерностью nхn). Задача решается с экспоненциальной сложностью, если время решения пропорционально 0 (cn) , где n-размерность, c-константа. Все экспоненциально-сложные задачи основаны на переборе всех вариантов и имеют экспоненциальную сложность. Например: подбор пароля, выбор наилучшего хода в шахматах и т.п. Емкостная сложность связана с объемом памяти. 2 ЛОГИКА (АЛГЕБРА) ВЫСКАЗЫВАНИЙ Учение о высказывании (алгебра высказываний) – первая начальная форма логической теории. Она является основой для изучения следующих разделов математической логики и имеет собственное значение в приложении – как математическая основа цифровых двоичных вычислительных машин. Далее будем рассматривать высказывания, имеющие два значения: «Истина» и «Ложь» (или 1 и 0), не имеющие сказуемого и подлежащего. Все высказывания должны удовлетворять закону исключающего третьего и закону противоречия. 3<5 – «И» Все ли предложения являются высказываниями? Нет. (Например, вопрос, поздравление, сожаление, приказ и т.д.) Различают простые и сложные (составные) высказывания, полученные с помощью логических операций. Термин сложности носит относительный характер. В алгебре высказываний игнорируется смысловая, семантическая характеристика сложного высказывания. Важна только истинность или ложность высказывания. 2.1 Логические операции Рассмотрим логические операции, которые позволяют из простых высказываний сделать составные: - отрицание (ך) или ( ¯ ) - конъюнкция (&) - дизъюнкция () - импликация (→) - эквивалентность (~) Таблицы истинности этих операций: В высказываниях логическим операциям соответствуют следующие сочетания слов: & : и, но, а, ’,’ : или →: если…то ~: тогда и только тогда, когда При учете смыслового содержания, высказывание «если…то» подразумевает причинную связь между посылкой х и заключением y. С точки зрения алгебры высказывания, импликация означает лишь то, что если истинна посылка х, то истинно следствие y, а если х ложно, то следствие может быть каким угодно, а сама импликация при этом истинна. В обычной речи мы не ставим вопрос об истинности высказывания в целом. Всякая теорема имеет вид импликации, в которой х то, что дано, а в y – то, что надо доказать. 2.2 Формулы алгебры высказываний. Равносильность формул Формула – всякое сложное высказывание, составленное из нескольких простых высказываний посредством применения основных 5 операций. Для всякой формулы можно построить таблицу истинности, при этом последовательно используя таблицы истинности этих 5 операций. Равносильными формулами будем считать формулы, которым соответствуют одинаковые таблицы истинности. Пусть А и В – две формулы, при этом х1,х2,…,хn – набор простых высказываний, входящих по крайней мере в одну из формул А или В. Формулы А и В называются равносильными, если при всех значениях х1,х2,…,хnзначения А и В совпадают. (А=В) Пример: х11 = 1 х1&х2х1&2=х1 х1&(х22)=х1 А В Связь между «=» и «~» : А~В= «И» <=> А=В Порядок выполнения логических операций: 1. ך или ( ¯ ) 2. &, 3. →,~ Операции (1-5) не являются независимыми друг от друга. Одни из них могут быть выражены через другие. Каков минимальный состав логических операций? Это либо (¯,v) лили (¯,&), так как x~y=(х→y)&(y→x); x→y=y; и по правилам Де-Моргана: х1&х2= х1х2= Важнейшие примеры для равносильных формул на базе операций ך,&, 1. Законы коммутативности x&y=y&x; xy=yx 2. Законы ассоциативности (x&y)&z=x&(y&z); (xy)z=x(yz) 3. Законы дистрибутивности xyxz=x(yz) - конъюнкции относительно дизъюнкции (xy)(xz)=xyz - дизъюнкции относительно конъюнкции 4. Закон двойного отрицания x= 5. Законы поглощения относительно конъюнкции и дизъюнкции x(xy)=x;xyх=х 6. Законы отрицания (правила Де-Моргана) = - конъюнкции = - дизъюнкции 7. Законы идемпотентности x&x=x xx=x 8. Закон исключающего третьего x= «И» x&= «Л» 9. Операции с константами х & «И» = х х & «Л» = «Л» х «И» = «И» х «Л» = х 2.3 Классы логических функций. Полнота и замкнутость Система логических функций S называют функционально полной, если любая логическая функция может быть представлена формулой над S. Функционально полные системы: S0={&,,ך}S3={ ↓ } – стрелкаПирса S1={&, ך }S4={ | } -штрих Шеффера S2={, ך }S5={&, , 1 } – алгебра Жегалкина х↓у= х|у= х1= ху===(x1)&(y1)1=x&yxy1 Любая логическая функция n- переменных (формула алгебры высказываний) может быть представлена в виде полинома Жегалкина следующего вида: a0a1x1a2x2…anxnan+1x1x2an+2x1x3…amx1…xn, где ai={0,1} Свойство двойственности: Две логические функции f1(x1,…,xn) иf2(x1,…,xn) называются двойственными, если f1(x1,…,xn)= Пример двойственных функций: f1=xyf2=x&y Правило, основанное на двойственности & и Если в некоторой формуле А, представляющую функцию f , все конъюнкции заменить на дизъюнкции, а все дизъюнкции заменить на конъюнкции, истину на ложь, а ложь на истину, то получим формулу А*, представляющую собой функцию f*, двойственную функции f. Если функции равны, то и двойственные им функции равны. Пример: xxy=x и x&(xy)=x Замкнутые классы Множество логических функций М называется замкнутым классом, если любая суперпозиция функции из М снова принадлежит М. Всякая система S логической функции порождает некоторый замкнутый класс. Такой класс называется замыканием множества S и обозначается [S]. Если [S]=Р2 , то система S функционально полная. Р2 – множество всех двоичных (логических) функций. Какова мощность всех логических функций от n-переменных |Р2|? |Р2|=2|G|, где |G| - число наборов: |G|=2n n=2 |G|=4 |Р2|=16 n=3 |G|=8 |Р2|=256 Примеры: S={} и S={} – не функционально полные системы Рассмотрим важнейшие примеры замкнутых классов логических функций, для которых S = [S], то есть множество S совпадает со своим замкнутым классом (не расширяется после всевозможных суперпозиций функций из S). 1. Класс функций, сохраняющих 0. Функция М называется сохраняющей 0 если на нулевом наборе она равна 0. Число таких функций 2|G|-1 2. Функция, сохраняющая единицу, если она равна 1 на единичном наборе. Число таких функций 2|G|-1 3. Монотонные функции. f(x1, x2, …, xn) – монотонна, если для любых двоичных наборов δ=(δ1, δ2, …, δn) и τ=(τ1, τ2, …, τn) из того, что δ≤τ =>f(δ)≤f(τ). Неравенство δ≤τ выполняется, если для всех i δi≤τi. Пусть n=2 1 и 2 наборы несравнимы 0<1<3 0<2<3 4. Линейная функция. Функция вида f(x1, x2, …, xn) = a0a1x1a2x2…anxn – линейная функция, то есть представима полиномом Жегалкина 1-го порядка. ai = {1,0}; │{ai}│= n+1 Общее число линейных функций 2n+1. 5. Класс самодвойственных функций. Функция самодвойственная, если она f(x1, x2, …, xn) = (1, 2, …, n). Для каждого из этих 5-ти классов верны аналогичные теоремы и следствия из них: Сформулируем ее для линейных функций: 1) Любая суперпозиция линейных функций порождает линейную функцию. Sn={f1, …, fn}, где f1, …, fn – линейная функция. [Sn]= Sn Следствие: функциональная полная система функций должна включать хотя бы одну нелинейную. Теорема о функциональной полноте: Для того чтобы система функций S была полной, необходимо и достаточно, чтобы она целиком не содержалась не в одной из следующих 5-ти замкнутых классов: сохраняющих ноль, сохраняющих единицу, монотонных, линейных, самодвойственных. Доказательство следует из 5-ти следствий к теоремам по каждому классу. Так как обычно, для реализации нуля и единицы в схемотехнике не требуется аппаратурных затрат, то исключив эти функции можно сформулировать требования функциональной полноты в слабом смысле. Определение: Система S функционально полная в слабом смысле, если любая логическая функция может быть представлена над системой SV{0,1}, то есть является суперпозицией над исходной системой S и логическими константами. Теорема о функциональной полноте в слабом смысле: Чтобы система функций была функционально полной в слабом смысле, необходимо и достаточно, чтобы она содержала хотя бы одну нелинейную и хотя бы одну немонотонную функцию. Таблица всех функций при n=2 │G│=2n= 4; │P2│= 2│G│ = 24 = 16 Переменная Наборы Названия функций Обозначения Классы Линейная Монотонная Сохраняющая 0 Сохраняющая 1 Самодвойст-венная х1 х2 01 1 11 Z Z Z Z Z Z Z Z Z Z Z Z Z Z f0 f1 00 00 00 01 константа 0 конъюнкция х1&х2 * * * * * * f2 f3 00 00 11 01 запрет по х2 переменная по х1 х1∆х2 х1 * * * * * * f4 f5 00 11 00 1 запрет по х1 переменная по х2 х2∆х1 х2 * * * * * * f6 f7 00 11 11 01 сумма mod 2 дизъюнкция х1х2 х1vх2 * * * * * f8 f9 11 00 00 01 стрелка Пирса эквивалентность х1$х2 х1~х2 * * f10 f11 11 00 11 01 отрицание х2 импликация 2,┐х2 х2х1 * * * * f12 f13 11 11 00 01 отрицание х1 импликация 1,┐ 1 х1х2 * * * f14 f15 11 11 11 01 штрих Шеффера константа 1 х1│х2 1 * * * Функционально полная система в таблице пробелами должна закрывать все 5 столбцов. 2.4 Булева алгебра и теория множеств Пусть задано множество U, множество всех его возможных подмножеств F(U) и называется булеаном множества U. Если │U│=2, то │F│=4 │U│=3, то │F│=8 Алгебра B=(F(U), , ,) – системный булеан, где В – булева алгебра множеств над U, ее тип определяется вектором (2, 2, 1), где элемент вектора – арность операции (2 – двухместная, 1 - одноместная). Для любого подмножества U’множества U, B’=(F(U’), , , ) является подалгеброй алгебры В. Логические формулы, содержащие кроме скобок только функции дизъюнкции, конъюнкции, отрицания называются булевыми функциями. Общий термин «булева алгебра» для алгебры множеств и логических функций не случаен. Всякая алгебра типа {2, 2, 1} для которой выполняет все тождества (см. п.2.2), называемые булевой алгеброй. Можно легко убедиться, что все соотношения из п.2.2 будут верны, если трактовать x, y, z как множества & как , v как , ┐ как , «Л» как , «И» -Ψ (универсальное множество). Алгебра теории множеств и алгебра булевых функций изоморфны (совпадают после переименования). Теорема 1: Если мощность множества (U)=n, то булева алгебра (F(U), ,, ) изоморфна булевой алгебры логических функций (Bn, &,V,┐ ), где Bn – множество двоичных векторов длинной n. Каждому подмножеству соответствует двоичный вектор. Если элемент aiявляется элементомU, то соответственно элемент двоичного вектора δi=1, если нет то δi=0. (где набор δ=( δ1, …, δn), δi={1, 0}) Эта теорема позволяет заменить теоретико–множественные операции поразрядными логическими операциями над двоичными векторами. P2 – множество всех логических функций.m – количество переменных. P2(m) – это множество замкнуто относительно операций &, , ┐и образуют конечную булеву алгебру. Эта алгебра является подалгеброй булевой алгебры логических функций. Теорема2: Если мощность множества U, │U│=2m, то булева алгебра множеств изоморфна булевой алгебры логических функций (P2(m), &, V, ┐), aiU(δi, …, δm). Эти алгебры равномощны и содержат 2|G| элементов, где |G|=2m 2.5 Нормальные формы логических (булевых) функций Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конъюнкций. Например: f(x1, x2, x3)=x1x2V2x3V3V1x2x3. Совершенная ДНФ – ДНФ, в которой каждая конъюнкция состоит ровно из n – переменных. Например: f(x1, x2, x3)= 12х3Vх1х23 Конъюнктивная нормальная форма (КНФ) – конъюнкция дизъюнкций. Например: f(x1, x2, x3)=(х1Vх2)&2&(1Vx2V3). Совершенная КНФ – КНФ, в которой каждая дизъюнкция состоит ровно из n – переменных. Теорема: В совершенной ДНФ или совершенной КНФ представима любая булева функция. 2.6 Минимизация булевых функций При минимизации булевых функций используется закон (правило) склеивания. Для ДНФ: х1х2Vх12=х1 Условно обозначим использование этой эквивалентности слева направо – скл, справа налево – скл -1. х1х2Vх12=х1 ДНФ Общая схема минимизации булевских функций для ДНФ (для КНФ аналогично). скл-1скл ДНФ совершенная ДНФ сокращенная ДНФ Формирование тупиковых ДНФ Пример: n=3 f(x1, x2, x3)= 13 V1x23V1x2x3Vx12x3Vx1x2x3 Совершенная ДНФ f(x1, x2, x3): f(x1, x2, x3) = 123 V1x23 V1x2x3 Vx12x3Vx1x2x3 1 2 3 4 5 Сокращенная ДНФ: 1 и 2: 13 все исходные дизъюнкты должно склеиваться хотя бы 2 и 3: 1х2 один раз, в противном случае, их надо 3 и 5: х2х3 будет добавить через дизъюнкцию 4 и 5: х1х3 f(x1, x2, x3) = 13V1x2Vx2x3Vx1x3 – сокращенная ДНФ Тупиковые ДНФ выбираются из таблицы перекрытия сокращенной ДНФ совершенной ДНФ: В первую очередь остаются строки для которых в столбцах одна *. Это 1-я и 4-я строки. Остальные столбцы перекрываются с помощью двух вариантов: Тупиковая ДНФ1: 13Vx1x3V1x2 Тупиковая ДНФ2:13Vx1x3Vx2x3 Для более удобной ручной минимизации булевых функций используют специальные графические формы таблиц истинности (карты Карно или диаграммы Вейча), по которым удобно проводить правила склеивания. Для 2-х переменных: x1x2Vx12V1x2 = x1Vx2 Для 3-х переменных: n=3 Для 4-х переменных: n=4 Для 5-х переменных: n=5 Правила образования контуров: а) Минимальным числом максимальных по размеру контуров (одна и та же единица может входить много раз в разные контуры) соединить все единицы. б) Размеры контуров кратны степени 2. в) Не должно быть зигзагообразных контуров. Минимизация неполностью определенных булевских функций, когда число используемых наборов ≤ 2n. В клетках соответствующих безразличным значениям функции представляются звездочки и эти клетки со звездочками могут каждый раз принимать любое выгодное значение (либо 1, либо 0). Для получения МКНФ надо склеивать не 1, а 0. Каждому контуру соответствует дизъюнкт, причем переменная входит в дизъюнкт с инверсией, если она в контуре без инверсии и наоборот. 3 ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ 3.1 Исчисления предикатов 3.1.1 Понятие предикатов Это обобщение алгебры высказываний, где вводятся двоичные функции нескольких переменных P(x,y) (т.е. предикаты могут принимать только 2 значения: истина и ложь, являясь функцией нескольких переменных, имеющих различную природу). Предикат – это логическое сказуемое, т.е. то, что в предложении высказывается об объекте. Определение: Пусть М – система множеств М={М1, М2, …, Mn}. Всякая функция P(x1, x2, …, xn), где xiMi, i= , а P(x1, x2, …, xn) которая принимает только 2 значения: ложь и истина, называется n -местным предикатом на системе множеств М. Множество Mi называется предметной областью для переменной xi. В частных случаях некоторые Mi могут совпадать или могут все совпадать, тогда обозначают как М. Примеры: 1. х – простое число. P(x), где хN, одноместный предикат. Замечание: Не для всех предикатов по умолчанию очевидна предметная область. 2. Прямая а проходит через точку А. P(a, A), это двухместный массив, где а – множество всех прямых, А – множество всех точек. аМП, АМТ – предметная область у них разная. 3. Студент факультета учиться на отлично. 4. Прямая L проходит через точки A и B. Это трехместный предикат. У двух переменных предметная область совпадает. 5. x=y – двухместный предикат. Предметная область совпадает и её суть может быть любой. 3.1.2 Кванторы Так как предикаты принимают значение 0 и 1, над ними можно производить все известные логические операции. Но имеются и специфические, только для предикатов характерные операции, которые относятся ко всему множеству значений предикатной переменной. Пусть А(х) одноместный предикат, рассмотрим следующие нульместные предикаты: 1, если А(х)=1 для всех хМ х А(х) = 0, в противном случае 1, если А(х)=1 хотя бы для одного хМ х А(х) = 0, в противном случае Имеет место тождества: =х илиА(х) =х В первом случае, мы говорим, что предметная переменная х связана квантором всеобщности, а во втором – квантором существования. Кванторы превращают одноместный предикат в логические константы. В общем случае для n-местного предиката P(x1, x2, …, xn) можно применить кванторы по какой-либо переменной хi: хiP(x1, x2, …, xn) хiP(x1, x2, …, xn) Причем подразумевается, что остальные переменные могут принимать любые значения. В результате, в обоих случаях, мы получим (n-1)-местный предикат. P’(x1, …,xi-1, xi+1, …, xn) Говорят, что xi здесь является связанной переменной, несвязную переменную называют свободной. Смысл связанных и свободных переменных в предикате различен. Свободная переменная – это обычная переменная, которая может принимает различные значения из своей предметной области и влияет на возможные значения предиката. От связанных переменных значение предиката не зависит. Аналогичные понятия: y= - от х значение y не зависит y= - от x значение y не зависит Примеры: 1. M={0, 1}, x, y M x(x)=0 x()=0 x(x)=1 x()=1 2. (x≥y) (x≥y) x, yM: (x≥y)=0 (x≥y)=1 3.1.3 Формула логики предикатов Индуктивно определим формулу вычисления предикатов. При этом одновременно даются определения свободных и связанных переменных. 1. Все отдельно взятые предикаты, в которых все места замещены предметными постоянными или предметными переменными, из соответствующих предметных областей, являются формулами. Логическая константа сама по себе считается нульместным предикатом. Все входящие в предикаты переменные свободные, связанных нет. 2. Если U – формула логики предикатов, содержащая свободную переменную х, то кванторы от xUиxU также формулы, в которой х уже связанная переменная, а все остальные переменные те же и того же характера, что и в U. 3. Если U – формула логики предикатов, то и также формула, все переменные в которой те же и того же характера, что и в U. Если U и V – формулы, причем нет такой переменной, которая в одну из них входит свободно, а в другую связано, то U&V, UV, UV и U~V также формулы. Причем, в них входят все переменные, входящие в U и в V и их вхождение имеет тот же характер. 4. Каждая формула получается за конечное число шагов из элементарных формул (1) при помощи операций из (2) и (3). Замечание: Так как переобозначение связных переменных не изменяет значения предикатов, то: • ограничение в пункте (3) на формулы, соединенные знаком логических операций, не приводит к ограничению на класс представимых формул; • можно так переобозначить связанные переменные, что все кванторы будут применяться к переменным, обозначенным разными буквами. Понятие равносильности формул Равносильность формул вычисления предикатов имеет 2 аспекта, которые связаны с равносильностью формул при конкретных предметных областях или равносильностью формул для любых предметных областей. Поэтому существуют понятие абсолютно равносильных предикатных формул (формулы, которые равносильны на любых системах М={М1, …, Мn}). И есть не абсолютно равносильные предикатные формулы – равносильны не на всех системах M. Примеры: 1). U=A(x); V=1. Если x, yM и │M│=1, то U и Vравносильны. Тогда можно записать: A(x)=1 2). A(x)A(y) = xM1, yM2 Эти формулы абсолютно равносильны на любой системе множеств М={М1, М2}. Свойства формул логики предикатов 1. Пусть область определения М={а1, а2, …, аn} конечна. Тогда на М каждой предикатной формуле на которую навешан квантор найдется равносильная ей формула, не содержащая квантора. А(а1)& А(а2)&…& А(аn) А(а1)vА(а2)v…v А(аn) В случае бесконечности множества М кванторы можно рассматривать как & и v над бесконечным числом переменных. 2. На конечной области М всякий предикат может быть представлен формулой, содержащей только одноместные предикаты. Введем следующий одноместный предикат: 0, если ха δа(х)= 1, если х=а Тогда предикат: δа1(х1)& δа2(х2)&…& δаn(хn)=1 (*) на единственном наборе =(а1, а2, …, аn), то всякий предикат можно представить в виде дизъюнкции предикатов вида (*), т.е. в виде СовДНФ одноместных предикатов δаi(хi). 3. Свойство абсолютной дистрибутивности квантора всеобщности относительно конъюнкции. 1) (P(x)&Q(x))= P(x) &Q(x) Доказательство: Пусть левая часть истина для некоторых P и Q, тогда для любого элемента аМ истинно P(a) &Q(a), поэтому P(a) и Q(a) одновременно истины для любого а и, следовательно, и правая часть истина. Предположим, что левая часть ложна, тоаМ ложно либо P(a), либо Q(a). Следовательно, ложно либо P(а), либо Q(а), т. е. и правая часть также ложна. 2) (P(x)v Q(x)) = P(x) vQ(x) Доказательство: Аналогично предыдущему. Если кванторы всеобщности и существования в равносильных 1 и 2 поменять местами, то получиться соотношение, верное лишь в одну сторону (импликация). 3) (P(x)&Q(x))P(x) &Q(x) 4) P(x) vQ(x) (P(x)v Q(x)) В общем случае, всеобщность не дистрибутивна дизъюнкции, а существование не дистрибутивно конъюнкции. Примеры: • Пусть P(x) задан на ряде натуральных чисел как х – четное, а Q(x) как х – нечетное. Тогда правая часть 4) формулы означает, что всякое натуральное число х (четное или нечетное) это абсолютная истина. Однако, высказывание левой части означает, что натуральное число четное или всякое натуральное число нечетное – это абсолютная ложь. • Из того, что все студенты пошли в кино или в театр не следует, что все студенты пошли в кино или все студенты пошли в театр. • Для 3) формулы в левой части требуется, чтобы P(а) и Q(а) были истины для одного и того же а, тогда как в правой части P и Q могут быть истины для различных значений (например b и c). xN, P(x) – делится на 2, Q(x) – делится на 3. Тогда левая часть означает, что числа делятся и на 2 и на 3. В правой части импликации «существует число, которое делится на 2 и существует число, которое делится на 3». Эти числа могут не совпадать. Поэтому из этого не всегда следует что существует число, которое делится на и 2 и на 3. Например 2 и 3, 8 и 9. • Считаем, что обязательно оба глаза одного цвета, тогда из того, что «существует студент с голубыми глазами и существует студент с зелеными глазами» не следует, что «существует студент с голубым и зеленым глазом одновременно». Необходимо рассмотреть во что переходят дистрибутивности кванторов и для конечных областей определения переменных (М - конечно), пользуясь свойством 1. 4. Свойство вынесения константы Если предикат Q не зависит от х, то есть х не является свободной переменной предиката Q, то предикат Q можно выносить за область действия квантора, связывающего переменную х. (P(x)& Q) = P(x) & Q (P(x)& Q) = P(x) & Q (P(x)v Q) = P(x) v Q (P(x)v Q) = P(x) v Q 5. Свойство коммутативности кванторов 1) Одноименные кванторы можно переставлять местами. P(x, y)=P(x, y) P(x, y)=P(x, y) Доказательство: хМ1, yM2 (x, y) М1M2 и каждой паре (x, y) соответствует пара (y, x). 2) Разноименные кванторы в общем случае переставлять нельзя. P(x, y) ≠ P(x, y) Примеры: • (xy) x, yN Для всякого натурального числа существует меньше число. Это абсолютная ложь. (x>=y) – существует натуральное число меньшее или равное любого натурального числа. Это абсолютная истина. • Каждую книгу читал какой-либо человек (хотя бы ее автор), но предикат «существует человек, который читал все книги» - всегда ложен. Можно доказать абсолютную истинность следующей формулы: P(x, y)P(x, y) = 1 В этом легко убедиться на геометрической интерпретации, когда x, y вещественные числа: 6. Свойство двойственности кванторов. или (1) или (2) Доказательство: (1) P(x) имеет место не для всех х, тогда и только тогда, когда существует х, для которого P(x) не имеет место. (2) Не существует х, для которогоP(x) имеет место, тогда и только тогда, когда P(x) не имеет место для всех х. Эти две равносильности свойства 6 вместе с правилами Де-Моргана позволяют любую формулу логики предикатов преобразовать в равносильную формулу, в которой символ отрицания стоит только над элементарными предикатами. Кроме этих 6 свойств, все равносильности из логики (алгебры) высказываний остаются в силе и для логики предикатов. 3.1.4 Методы доказательства в логике предикатов В алгебре высказывания существует простой метод доказательства истинности формул. Это вычисление формул на всех наборах. Аналогичная процедура в логике предикатов, в общем случае, невозможна, т.к. могут существовать бесконечные предметные области. В этом случае прямой перебор всех значений невозможен. Применяется косвенный прием. Для построения множеств правильных формул используются формальные процедуры, которые называются правилами вывода. При этом не происходит обращения к семантики (смыслу) формул, а используются лишь формальные внешние свойства формул, как последовательности символов. Эти свойства описываются правилами вывода. Благодаря такому подходу, удается избежать обращения к бесконечным областям и на каждом шаге преобразования оперировать только с конечным набором символов и правил преобразования формул (финитный метод). 3.1.5 Кванторы по предикатным переменным Исчисление предикатов, в которых кванторы, применяются только к предметным переменным, называется исчислением предикатов 1-го порядка. В расширенном исчислении предикатов можно использовать кванторы по предикатным переменным PP(x, y). Применение таких кванторов позволяет более удобно характеризовать необходимый предикат. Определение формул в расширенном исчислении аналогично определению предикатов 1-го порядка за исключением того, что в шаге (2) определения, переменная х может быть как предметной, так и предикатной. Свойство дистрибутивности всеобщности относительно конъюнкции и существование относительно дизъюнкции, свойство вынесения констант и свойство двойственности сохраняются. Примеры привидения кванторов по предикатной переменной. Определение предиката тождественного равенства. х (х=х) (1) Pxy (x=y(P(x) P(y))) Покажем, что предикат тождественного равенства x=y однозначно определяется двумя требованиями для любой предметной области М. Пусть на М имеются отличные от тождественного равенства предикаты (x=y)’, удовлетворяющие этим 2 условиям. Пусть a и b – 2 различных элемента из множества М, для которых истинен данный предикат (a=b)’. Заметим, что в силу равенства (1) истинен предикат (a=a)’. Рассмотрим P(b)=0, тогда получим, что высказывание a=b(P(a) P(b)) ложно. Мы пришли к противоречию. Другая, очень часто используемая возможность – это применение кванторов по предикатной переменной для задания множества предметных областей, состоящего из определенного числа элементов. 1) Аxy (А(х)v) Для любого предиката А этот предикат абсолютно равносилен 1 только на единственной предметной области мощностью 1. 2) =Аxy=Аxy(&A(y)) мощность будет больше 1 (│М│>1) Другой вариант: xy 3) Определение множества, в котором содержится меньше или ровно 2 элемента (│М│≤2). Аxyz(A(x)vA(y)v) будет истинен абсолютно на предметных областях, состоящих из 1-го или 2-х элементов. Система аксиом, которая характеризует натуральный ряд. В этих аксиомах используются индивидуальные предикаты х=у, х<у, δ(х,у) - равенства порядка и предикат непосредственного следования. δ(х,у)=x, …, быть четным,… - функциональные символы f(x,y), +, -, … - связка (логические операции) →, &, ~,… - скобки, определяющие порядок действия (, ) - кванторы , - специальные метасимволы ╞ - тождественная истинность,├ - выводимость. Множество всех ППФ и правил построения этих формул (F) Правила построения ППФ даны в п.3.1.3. Аксиомы (А) 1) А→(В→А); действительно В→А = А = 1В = 1 2) А&В→А; А&В→В 3) А→АВ; В→АВ 4) (А→В) →(ךВ→ךА) 5) а) хР(х) →Р(у) б) Р(у) →хР(х) Правила вывода (R) RiR Если есть отношение Ri(Fi,…, Fn, F0), то говорят, что F0 выводимо непосредственно из Fi,…, Fn. Графическое обозначение: Fi,…,Fn - посылки F0 - следствие Fi может быть аксиомой или ранее доказанным следствием из другого правила. Факт выводимости посылки F0 из всех предыдущих в том числе и промежуточных посылок обозначается: F1,…,Fn├ F0 Т.к. в исчислении предикатов всякая теорема является общезначимой формулой, то справедлива и другая форма записи: ╞ F1&…&Fn→F0 Замечание. В логическом программировании для уменьшения вычислительной сложности тождественные истины представляются в виде дизъюнктов Хорна (через правило Де-Моргана). F1&…&Fn →F0 = … F0 Классические правила вывода Ri 1) Все аксиомы выводимы (т.е. истинны) 2) Правило подстановки (ПС) Пусть А – ППФ, содержащая атом Х. Атом – это некоторое исходное высказывание или предикат от этих высказываний, т.е любая часть формулы, являющаяся в свою очередь также ППФ. Заменив атом Х всюду, куда он входит в произвольную ППФ на В получим также теорему. При подстановке надо учитывать, что в ППФ В переменные должны быть свободны для предметных переменных в атоме Х. 3. Правило дедуктивного вывода - правило ModusPonens (MP). Если А – теорема и из А выводится B, то и В – теорема. 4. Правило обобщения Gen. Если из В выводится предикат А(х), то выводима и формула хА(х) из В. Это правило верно, если В – не содержит свободной переменной х. Если В → A(x), то В → xA(x) 5. Правило конкретизации Ex. 6. Любую связанную переменную в теореме А можно заменить на любую другую переменную, отличную от всех свободных переменных в А. Причем, замена производится во всех областях действия квантора и в самом кванторе, причем, полученная ППФ после замены – так же теорема. Понятие выводимости сводится к понятию доказуемости с помощью теоремы о дедукции (Эрбрана). Теорема: Если из посылок А1, А2, …, Аn выводится B (А1& А2&… Аn├ В), то выводима следующая логическая формула: ├ (А1(…(АnВ))…). Верна и обратная теорема. Важен частный случай: n=1, A├ B =├ AB Пример: • Пусть P – выводимая ППФ. Доказать, что ├ х P – выводима, т. е. - воспользуемся аксиомой 1: ├ А(ВА); - сделаем подстановку А на P, В на X (2-ое правило): ├ P(XP); - воспользуемся третьим правилом МP: 3.2 Метод резолюции 3.2.1 Задачи формального доказательства теорем. Приведение к противоречию. Метод резолюции для исчисления высказываний Задачи проверки истинности какой-либо формулы при заданных посылках называется задачей формального доказательства. Она может быть решена вручную (применением аксиом и правил вывода), но это может привести к значительным затруднениям при отсутствии определенного метода (алгоритма). Методы автоматического (формального) доказательства теорем имеют начало от основополагающей теоремы Эрбрана. Он разработал механическую процедуру дедуктивного вывода. Идея этой процедуры основана на поиске специальной области интерпретации, которая называется Эрбранова база или универсум. Эта база должна быть такой, чтобы легко можно было проверить истинность или ложность следствия для любых других интерпретаций. Недостаток: экспоненциальная сложность метода как функции от числа исходных посылок. Совершенно другой подход предложил Джон Робинсон, который ввел принцип резолюции. Этот принцип и стал теоретической базой для построения большого количества методов автоматического доказательства. Метод резолюции имеет полиномиальную сложность и быструю сходимость. Этот метод при доказательстве теорем применяется совместно с методом опровержения или приведения к противоречию. Метод приведения к противоречию При доказательстве теоремы F1&…&FnF0 (*) можно применять правило силлогизма и правило МР к посылкам F1,…,Fn в случайном порядке или методом полного перебора вариантов и ожидать появления следствия F0. Это так называемой метод прямой волны. Он имеет тенденцию порождать лавину промежуточных результатов. Здесь большинство траекторий движения доказательства идут по неверному пути, который не имеет отношения к цели F0. Другая возможность: использование эквивалентности или аксиому 4 (АВ=), то есть 0 ך(F1&…&Fn ) (**). То есть идем от отрицания следствия к отрицанию конъюнкции всех посылок. Делается предположение, что заключение ложно и делается попытка опровергнуть хотя бы одну посылку. Двигаемся назад: от посылки к следствиям (метод поиска от цели). Наилучшие результаты дает комбинация этих 2-х методов. Это называется методом опровержения или приведения к противоречию. При доказательстве теоремы (*) допускается одновременно истинность F1&…&F2 и ложность 0. То есть предполагается, что теорема – ложна, то есть = = F1&…&Fn&0 (***) Имеет место теорема: Теорема: Формула F0 – логическое следствие формул F1, …, Fn тогда и только тогда когда формула (***) противоречива, то есть равна нулю («Л»). Такой подход позволяет двигаться вперед от конъюнкции посылок и назад от отрицания следствия. Если F0 выводима из посылок, то при движении вперед, допустив истинность F1&…&Fn мы получили бы F0, а т. к. мы допустили 0, то приходим к противоречию. При движении назад из 0 получим ך(F1&…&Fn), что противоречит истинности посылок (опять противоречие). В общем случае, двигаясь с обоих сторон, выводя некоторые предположения, получим P, двигаясь вперед, и его отрицание , двигаясь назад. Замечание: Если (*) – не теорема, то применяя данный метод невозможно получить противоречие при сколь угодно большой глубине вывода. Метод резолюции для исчисления высказываний Метод резолюции основан на применении следующего правила вывода: По сути дела, это специальным образом записанное правило силлогизма, которое в данном виде удобно применять для формального доказательства теорем. Соответствующее этому правилу правило силлогизма выглядит следующим образом: Самому правилу резолюции соответствует всегда абсолютно истинная формула: (XP)&(Y)(XY) = 1 Действительно избавляясь от импликации и применяя правило Де-Моргана: xy = pxy = pxy = 1xy = 1 Пара литеров P и в исходных дизъюнктах (XP) и (Y) называется контральной парой. Правило резолюции формально сходится к вычеркиванию контральной пары в 2-х дизъюнктах. Робинсон расширил правило на случай произвольных дизъюнктов с любым количеством литер. С1: х1х2…хnP С2: y1y2…ym С3: х1х2…хny1y2…ym В результате применения правила резолюции получается новый дизъюнкт С3, который называется резольвентой исходных дизъюнктов С1и С2. Пример: С1: АС С2: ВА С3: АС Если в процессе вывода новых дизъюнктов (резольвент) мы получим два однолитеральных дизъюнкта, образующих контральную пару, то резольвента этих двух дизъюнктов будет пустой □ (тождественно ложной). Выводом пустого дизъюнкта из множества дизъюнктов S называется конечная последовательность дизъюнктов C1,C2,…Ck, такая, что для любого CiS, является или дизъюнктом из S или резольвентой, полученной методом резолюции, и Ck = □. Вывод пустого дизъюнкта можно наглядно представить в виде дерева Стратегия просмотра дизъюнкт и резольвент может быть различной. Цель заключается в как можно более быстром поиске пустой (ложной) резольвенты, т.е. в соответствие с методом приведения к противоречию – логического следствия исходных дизъюнктов и получаемых резольвент. Пример. Пусть требуется доказать, что если PQ, P, Q то P&Q или ├ (PQ)& (P)&(Q) P&Q. F1 F2 F3 F0 Посылки Следствие В соответствии с теоремой F0 тогда и только тогда, когда F1&F2&F3&0 = □. Таким образом множество исходных дизъюнктов S={F1,F2,F3, 0} = { PQ, P, Q, }. Применяя метод резолюции для системы S, получим: то есть (PQ)& (P)&(Q) P&Q теорема. 3.2.2 Метод резолюции для исчисления предикатов При применении метода резолюции к исчислению предикатов имеем 2 новых обстоятельства, которых не было при использовании его для исчисления высказываний: 1) могут присутствовать кванторы; 2) у предикатов есть аргументы (предметные переменные). Пусть есть 2 дизъюнкта: С1: Р(х) (x) C2: (g(x)) Q(y) Замену можно производить только сужая предметную область действия ППФ. С1: Р(g(х)) (g(x)) C2: (g(x)) Q(y) C3 :(g(x)) Q(y) Если же C2: (g(x)) Q(y), а С1: Р(t(х)) (x) , то никакой контральной пары нет. В общем случае, при применении метода резолюции в логике предикатов, выполняются следующие этапы, которые позволяют свести формулы исчисления предикатов к формулам исчисления высказываний и применить метод резолюции для исчисления высказываний. Этапов всего 6. 1) Представить исходные знания и факты (посылки и следствия) в виде ППФ. 2) Преобразовать ППФ к префиксной нормальной форме. Здесь все кванторы выносятся из логических формул и записываются слева. 3) Преобразование к сколемовской нормальной форме, т.е. избавление от кванторов вообще. 4) Преобразование в форму хорновский дизъюнкт (в виде КНФ). 5) Выполнение подстановки и унификации. Цель: избавится от переменных, подставляя вместо них константы или функции или если нельзя, унифицировать имена переменных. 6) Собственно применить метод резолюции. Замечание. В настоящее время существуют языки и компьютерные системы логического программирования (Например, ПРОЛОГ). В них все этапы, кроме 1-го, выполняются автоматически. Второй этап: а) исключение из ППФ операции ~ и → А~В=А→В&В→А А→В=В б) остались &,, ך=А =х = & =х в) вынести все кванторы налево xP(x) Q=x(P(x) Q) xP(x) Q=x(P(x) Q) x P(x) &Q=x(P(x) &Q) x P(x) &Q=x(P(x) &Q) xP(x) xQ(x)= x(P(x) Q(x)) xP(x) &xQ(x)= x(P(x) &Q(x)) xP(x) &xQ(x)= x(P(x) &yQ(y))= xy(P(x) &P(y)) xP(x) xQ(x)= xy(P(x) Q(y)) Третий этап 1) Если квантор всеобщности стоит слева и в его зоне действия нет ни одного квантора существования, то его можно опустить. хА(х)=А(х) хуА(х,у)= уА(х,у)=А(х,у) 2) Если переменная х связана квантором существования, который сам по себе не находится в области действия никакого квантора всеобщности, его можно опустить, но все вхождения переменной х, которые были связаны этим квантором, заменить на новую константу, которую называют сколемовской. 3) Если квантор существования находится в зоне действия квантора всеобщности, то опускать этот квантор также можно, но необходимо ввести сколемовскую функцию. Рассмотрим пример: ух Р(х,у) ух Л(у,х): y любит х Т.е. для каждого у найдется х, для которого у любит х. х зависит от у, это можно рассматривать как функцию, поэтому можно записать f(y) вместо x. y Л(у,f(y))=Л(у,f(y)) Замечание. Введение сколемовской функции в предикат обеспечивает то, что в качестве аргумента в нем остаются только те переменные, которые влияют на переменные, связанные квантором всеобщности. Рассмотрим более сложный случай хуzP(x,y,z) избавляемся от квантора: хzP(x,f(x),z), P(x,f(x),z) Если хzyP(x,y,z), то хzP(x,f(x,z),z) Четвертый этап Преобразование в КНФ. Мы должны получить посылки и отрицание следования в виде совокупности (т.е. конъюнкции) дизъюнктов, т.е. в виде КНФ. Пятый этап Рассмотрим 2 резольвенты: Ci=Li1Li2…LinL(x) Cj=Lj1Lj2…Ljm Контральную пару ищем на базе L(x) и Для применения метода резолюции надо провести подстановку между х и у, причем предикат с большей описательной мощностью заменяется на предикат с меньшей описательной мощностью. Например, а – константа у - переменная; у заменяется на а: Ө ={а/y} – вместо y подставляется а. Унификация. Группа подстановок, которая сделает 2-е ППФ одинаковыми, называется унификатором. Шестой этап Собственно метод резолюции. После шестого этапа может опять потребоваться пятый. Пример xyz (отец(x,z)&отец(z,y) →дед(х,у)) Отец(Иван, Петр) Отец(Петр, Сидор) дед (Иван, Сидор) - ? 1) xyz (дед(х,у)) 2)-3) выполнение 2 и 3 этапов не требуется 4) а) дед(х,у) б) отец(Иван, Петр) в) отец(Петр, Сидор) г) (Иван, Сидор) Ищем контральные пары и применяем подстановки. д) (а-г) {Иван/х,Сидор/у} е) (д-б) {Петр/z} ж) (е-в) - пустой дизъюнкт Ответ: Да, это теорема. 4 АЛГОРИТМИЧЕСКИЕ МОДЕЛИ 4.1 Элементы теории алгоритмов Основные свойства алгоритма: (см. введение). Следует различать: • описание алгоритма; • механизм реализации алгоритма; • процесс реализации алгоритма (последовательность шагов, которые вызваны применением алгоритма к конкретным исходным данным). Все эти три сущности (описание, механизм и процесс) конечны. Допускается быть бесконечным только внешней памяти (промежуточная память). Она потенциально бесконечна. Замечание: Выбор механизма реализации алгоритма будет влиять на сам характер уточнения характеристик алгоритма. 1. ЭВМ + Ассемблер больше нужна детализация 2. ЭВМ + АлЯз (Паскаль) 3. ЭВМ + ОбОрПрог 4. Человек меньше нужна детализация 4.1.1 Классификация универсальных алгоритмических моделей 1. Нормальные алгоритмы Маркова. Модель основана на преобразовании слов в произвольном алгоритме путем подстановки. 2. Машины Тьринга. Основана на представлении алгоритма в виде элементарных действий (сдвиг, чтение, запись). 3. Рекурсивные функции. Модель основана на связи понятия алгоритма с вычислениями и числовыми функциями. Преимущества каждой модели: 1. Максимальная абстрактность и применимость к объектам произвольной природы. 2. Не остается сомнений в однозначности алгоритма и элементарности его шагов. Понятие МТ близко к ЭВМ и, следовательно, к инженерной интуиции. 3. Элементарнейший алгоритмический язык для вычисления любой исходной функции. Модели уточняют понятие алгоритма. Они не предназначены для решения практических задач. Нужны для ответа на вопрос алгоритмической разрешимости или неразрешимости той или иной задачи. Все они эквивалентны в теоретическом отношении. 4.1.2 Нормальный алгоритм Маркова (НАМ) Существует некоторый произвольный алфавит А, в его рамках задана система подстановок. Эти подстановки просматриваются последовательно и применяются к первой попавшейся. Пример. А={a, b, c} СП: (cbcc, ccaab, abbca). 1) ba b a a c bb c a aa c 2) cbacacb – входное слово cc a c a c b cc a c a c cc a b c a c cc b c a c a c cc – выходное слово 3) b c a c a b c b c a c b c a c bcacccac бесконечное число шагов (зацикливание) bcacabc Задается алфавит А и фиксируется схема подстановок. Алгоритм предписывает исходя из произвольного слова P из алгоритма А: 1-ый шаг: просмотреть подстановки в той последовательности, в которой они заданы в системе, разыскивая подстановки с левой частью, входящие в P, если такой подстановки нет, то остановка, если была использована последняя подстановка, то остановка. Если не было остановок по первому признаку, то берется правая часть и делается замена вхождения левой части в слове P, это дает новое слово P1 из алфавита А. 2-ой шаг: тоже самое, но вместо P используется P1 и т. д. В обоих случаях алгоритм перерабатывает входное слово P в Pn (PPn), где n – число шагов. Пример: Сложение чисел в унитарном коде • А={1, +} S=(1++1, +11, 11) P=1111+11+111=19 111+111+111 +111 111+111 ++111 111 111 +111 111 111 111 111 111 • A={1, +} S={1++1, +++, +}, - пустой символ (отсутствие символа). • Алгоритм умножения 2-х чисел в унитарном коде. 1x* 1y=1xy A={1, *, V, x} S=(*11V*1 (1) *1V (2) 1VV1x (3) xVVx (4) x11x (5) V1V (6) Vxx (7) x1 (8) 11 (9) • Функция инкремента в двоичной системе счисления. fz=z+1, где z – двоичное число f11100 f100101 A={0, 1, f, x, y} S=( 0y1 (1) 1yy0 (2) y1 (3) x00x (4) x11x (5) 0x0y (6) 1x1y (7) fx (8) (9) 4.2 НАМ и алгоритмически неразрешимые задачи Гипотеза Маркова (принцип нормализации) – всякий алгоритм в алфавите А эквивалентен некоторому НАМ в том же алфавите. Эта теорема не может быть строго доказана. На гипотезу надо смотреть как на закон. Таким образом, НАМ можно рассматривать как удобную стандартную форму для записи любого алгоритма вообще. Эта гипотеза позволяет строго доказывать алгоритмическую разрешимость или неразрешимость задачи. Рассмотрим задачу эквивалентности слов PPn. Каждая пара (A, S) – ассоциативное исчисление. Например, любую логическую формулу можно трактовать как записи слов в некотором алфавите. То есть, процесс вывода следствий из посылок может быть записан в виде формального преобразования НАМ. Тогда вопросы выводимости следствий в исчислениях становятся эквивалентными вопросу исчисления эквивалентных слов в НАМ. В 1946 г. Марковым, а в 1947 г. Постом была доказана алгоритмическая неразрешимость, проблема распознавания эквивалентности слов в ассоциативном исчислении. Было доказано, что не существует НАМ, позволяющая для любого другого НАМ (любого другого ассоциативного исчисления) и для произвольно заданных слов P и Q, ответить на вопрос: эквивалентны эти слова или нет? Приведенные примеры Марковым и Постом очень громоздки, поэтому мы рассматриваем частный случай алгоритмической неразрешимости в рамках доказательства не существования НАМ для решения задачи распознавания самоприменимости. Это доказательство было предложено Марковым в 1956 г. Оно похоже на распознавание зацикливания. Докажем проблему самоприменимости: Пусть в некотором алфавите A={a1, …, an} определен некоторый НАМ: U=(A, Sn). В записи алгоритма U, кроме символов А, используются некоторые служебные символы. Попробуем теперь применить алгоритм U к слову, которое его изображает. Определение: Если алгоритм U перерабатывает слово, которое его изображает в некоторое иное слово, после чего наступает остановка, то U называется самоприменимым, в противном случае – несамоприменимым. Возникает задача распознавания самоприменимости, то есть по записи алгоритма U, определить самоприменим этот алгоритм или нет. Для того, чтобы решить эту задачу, надо построить НАМ V, который, будучи, применим к любому другому алгоритму U перерабатывал бы его запись и выдавал М – если U самоприменим и L – если U несамоприменим. Марков, а затем Пост доказали, что алгоритма V не существует. Доказательство: методом от противного. Пусть V – существует. Тогда путем некоторого изменения системы подстановок S этого алгоритма, можно построить новый алгоритм , который для всякой записи самоприменимого U был бы несамоприменим. Остановка не наступает. А для всякой записи несамоприменимого U он так же переработал бы в L, то есть - применим ко всякой записи несамоприменимого алгоритма и неприменим для записи самопроизвольного алгоритма. Это приводит к противоречию. 1) Если - самоприменим, то есть он применим и к собственной записи, то это свидетельствует о том, что несамоприменим. 2) Пусть - несамоприменим, тогда вследствие определения он применим к своей записи, так как применим к любой записи несамоприменимого алгоритма. Это означает, что самоприменим. Опять противоречие. Следовательно, алгоритма не существуети следовательно V не существует. Замечания: 1 Несуществование алгоритма решения какой-либо задачи не означает алгоритмическую неразрешимость вообще, а означает то, что эта задача была поставлена слишком широко. То есть, единого эффективного метода решения широко поставленной задачи нет. Но это не значит, что при сужении постановки задачи для некоторых классов алгоритмов, эта задача не может быть решена. 2 Наличие гипотезы о существовании стандартной формы (НАМ) позволило: • в точных терминах формально определить понятие алгоритма; • в точных терминах определить проблемы алгоритмической неразрешимости. 4.3 Машина Тьюринга Основные определения 1) Машина должна быть детерминирована и действовать в соответствии с заданной системой правил. 2) Должна допускать ввод различных начальных данных. 3) Система правил работы машины и класс решаемых задач должны быть согласованы так, чтобы всегда можно было «прочитать» результат работы машины. Q=(q1, q2,…, qn) ajaj’ d={L,R,S} Бесконечная лента Машина Тьюринга (МТ) состоит из: 1) Устройство управления, которое может находиться в состоянии q1…qn. Одно состояние выделено qz. Если машина попадает в него, она останавливается. 2) Бесконечная лента, состоящая из ячеек, в каждой из которых может находиться 1 символ алфавита А. 3) Устройство, обращающееся к ленте (считывает, записывает), которое в каждый момент времени обозревает 1 ячейку. Головка в зависимости от считывающего символа аj и состояния qj , в котором находится устройство управления, записывает в ячейку символ аj’ и сдвигается на 1 ячейку влево или вправо, или остается на месте. Память МТ состоит из 2х частей: - внутренняя память, состоящая из набора состояний (q1-начало, qz- конец) - внешняя память – слово, записанное на ленте: начальное слово, промежуточные слова и выходное слово после останова. В А добавляют всегда символ λ – пусто. На ленте все λ находятся по краям. Любой МТ может соответствовать МТ с полубесконечной лентой. Вводятся стандартные начальная и конечная конфигурации МТ. Формы записи МТ (всего 3): - табличная - графическая - аналитическая Все эти формы связаны со следующими 3-мя преобразованиями: aj(t+1) =fa(aj(t),qi(t)) qi(t+1)=fq(aj(t),qi(t)) d(t+1)=fd(aj(t),qi(t)) - движение головки d={S,L,R}; S – stop, R – вправо, L – влево Аналитическая (с помощью записи команд) k: qiaj → qi’aj’d Табличная Симв сост а1 а2 … аm q1 q11a11d11 q2 … qijaijdij qn-1 qz qza1S qza2S qzamS Графическая a2→a3R a1→a1La2→a1R a1→a2L Не должно быть: ai ai Пример 0→1R 0→0L λ → λL 1 →1Lλ → λR 1 →0R Аналитическая форма: СК: q10 →q11R, q11 →q10R, q1λ →q2λL, q2 →q20L, q21 →q21L, q2λ →qzλR Полное состояние машины позволяет определить развитие процесса в дальнейшем. Такое полное состояние называется конфигурацией МТ (К). К=α1qi α2 , где q1 – текущее состояние УУ α= α1 α2 – общее слово на ленте в данный момент времени t, причем символы, входящие в α1 находятся слева от головки, а символы, входящие в α2: первый под головкой, остальные справа. Стандартные начальные и конечные конфигурации, те у которых головка над крайним левым не пустым символом. К1=q1 α – начальное состояние, α – входное слово Кn=qz α – конечное состояние, α – выходное слово Последовательность конфигураций в МТ (К1→ К2→…) однозначно определяется К1 и полностью описывает работу МТ. Эта последовательность будет конечна, если в этой цепочке появится Кz. Она может быть бесконечной, если встретится Кj=Ki (jПРФ, при xn. Таким образом, класс ПРФ не охватывает всех вычислительных функций, вследствие конкретной ограниченности формы индукции в 5-ом операторе – операторе примитивной рекурсии. Нельзя заранее фиксировать эту схему. Даже если предложить другую схему рекурсии (например, кратную рекурсию), то все равно нет гарантии, что эта схема не будет ограничена. Поэтому было решено не фиксировать заранее схему рекурсии. Явная форма ЧРФ Введем сначала понятие ограниченного оператора наименьшего числа или ограниченного μ-оператора. Пусть дан предикат Р(х1,…,хn,y), зависящий от (n+1)-переменных, который является ПРФ. P={0,1}. Функция f(x1,…,xn,z)=μyzP(x1,…,xn,y) определяется как наименьшее значение yz, при котором предикат истинен. Если предикат ложен на всех значениях 0yz, то функция равна z. Пример Предикат Р(х1,х2,у) , y делится на х1 и на х2. F(x1,x2,z)=μyZP(x1,x2,у) – НОК(наименьшее общее кратное) Ограниченный μ-оператор является ПРФ. Ограничение z в ограниченном μ-операторе дает гарантию окончания вычисления всегда. Приведем пример, показывающий эффективность μ-оператора. Применение μ-оператора для вычисления функций, обратной заданной f(y). g(x) = μyZ (f(y)=x) или надежней - целая часть [g(x)] = μyZ (f(y)+1>x). Тогда: []=μyx (y•y+1 > x) [z/x]= μyZ ((y+1)•x > z) Рассмотрим случай, когда ограничение с μ-оператора снято. Схема вычислений № 6. 6. Неограниченный μ-оператор: f(x1,…,xn,)= μyP(x1,…,xn,y) Алгоритм реализации μ-оператора 1. у:=0 2. Если Р=1, то (f:=y, выход из цикла) иначе (у:=у+1 и идти к оператору Если (т.е. к шагу 2)). Возможны такие предикаты Р, для которых ни при каких у не будет истинно значение Р, в этом случае происходит зацикливание. Тогда говорят, что μ-оператор не определён. Механизм возникновения неопределенности μ-оператора такой же, как у машины Тьюринга (МТ) (в случае неопределенности никогда не останавливается). Пример S1(y) =y+1; Через μ-оператор вычислим обратную функцию. х-1= μу(у+1 = х) Если х=0, то у=0 у=1 у=2 … и так далее, до бесконечности. Если x>0, то вычисления закончатся на y = x-1. Определение ЧРФ: Функция f(х1,…,хn) называется частично рекурсивной функцией, если она может быть определена с помощью конечного применения схем 1-6. ПРФ является частным случаем ЧРФ, т.к. использует только схемы 1-5. ЧРФ является наиболее общим классом конструктивно определенных вычислимых функций. Определение ОРФ: ЧРФ, определенная на всех наборах, называется обще рекурсивной функцией. Таким образом, ПРФ ОРФ ЧРФ. 4.5 Тезис Чёрча. Вычислимость и разрешимость Всякая вычислимая функция является ЧРФ. То есть, класс ЧРФ расширять не потребуется. В 1936 г. Чёрч выдвинул тезис: Всякая функция, вычислимая некоторым алгоритмом, является ЧРФ. Все замечания по тезису Маркова относятся и к тезису Чёрчя. Тезис Чёрча означает, что задача алгоритмически разрешима, если можно построить соответствующую ЧРФ. Алгоритмическая неразрешимость проблем и задач означает, что функция, к которой сводится эта задача или проблема, не является ЧРФ, т.е. доказательство отсутствия алгоритма сводится к доказательству, что функция, соответствующая этой задаче или проблеме не ЧРФ. Понятие нумерации алгоритма Множество всех алгоритмов счётно, т.е. каждому алгоритму можно поставить в соответствие число натурального ряда. Введем φ(A)=n – функция нумерации алгоритмов, nN. По описанию алгоритма возвращает его номер. Существует и обратная функция: φ-1(n)=A. По номеру алгоритма возвращает его описание. Фактически, раньше мы уже строили одну из систем нумерации, разрабатывая подход к реализации универсальной МТ, где φ определялся методом кодирования. Нумерация всех алгоритмов является нумерацией всех вычислимых функций. Для любой системы нумераций φ можно выбрать 2 пути построения универсального алгоритма U(х,у), где х – номер алгоритма, у - входное слово, с которым алгоритм работает. 1. Путь построения нового транслятора - каждый раз строить новый U, работающий с номерами порожденной функции φ. 2. Построить алгоритм перевода любой φ в некоторую φ*, для которой уже построен алгоритм U(х,у). 4.6 Основные неразрешимые проблемы (задачи) на языке РФ Каждой проблеме соответствует теорема. Приведем пять основных в терминах ЧРФ. Теорема 1 Не существует алгоритма, который бы по номеру х любого алгоритма А и исходным данным у определил бы, остановится ли алгоритм при исходных данных y. В(х,у)= Теорема 2 Проблема самоприменимости алгоритма алгоритмически неразрешима, т.е. не существует алгоритма В1(х,у), который для любого другого алгоритма А(х,у) вычислял бы следующую функцию: В1(у)= Это не частный случай теоремы 1. ЗамечаниеВсе алгоритмы, которые соответствуют ЧРФ, могут быть эффективно перечислены числами натурального ряда. Теорема 3 Для любого перечисления φ, любого множества S, существует ОРФ, не входящая в это перечисление φ, т.е. множество ОРФ невозможно эффективно перечислить. Из 3-ей теоремы следует неразрешимая проблема: Теорема 4 Проблема определения общей рекурсивности (всюду определимости) алгоритмически неразрешима. Т.е. не существует алгоритма В2(х), который бы для любого алгоритма Ах вычислил бы: В2(х)= Теорема 5 Существует такая ЧРФ f, что никакая ОРФ g не является ее доопределением, т.е. не существует универсального метода доопределения ЧРФ. Итоги (общая семантика теорем 1-5) Все эти теоремы объясняют роль понятия частичной определенности в теории алгоритмов, естественно с практической точки зрения, одно из ключевых свойств алгоритма – результативность. Первый удар по результативности – теорема 1-проблема неразрешимости остановки. Возникает желание исправить эту ситуацию: есть 3 варианта: 1) вообще убрать из теории алгоритмов ЧРФ 2) ввести некоторый стандартный метод доопределения ЧРФ. Невозможность 1-го варианта следует из теоремы 4 2-й вариант опровергается теоремой 2. 3) попробуем построить язык, описывающий все доопределенные алгоритмы и только их. Невозможность существования такого языка доказывает теорема 3, т.к. описание в этом языке можно упорядочить и наличие такого языка означало бы, существования полного перечисления всех всюду определенных функций (ОРФ), что противоречит теореме 3. Таким образом, при определении понятия алгоритма мы должны решится на одно из двух: 1) либо определение будет достаточно общим и в него попадут все алгоритмы. 2) либо во главу узла ставится требование результативности алгоритма. При 1-ом подходе определение алгоритма соответствует ЧРФ. Во 2-ом случае, никакую программу нельзя назвать алгоритмом до тех пор, пока для нее не будет решена проблема остановки, а единого решения такой проблемы не существует. Все ЧРФ – это алгоритмы. Когда дело касается решения конкретной задачи, здесь так же будет требоваться и сходимость алгоритма. 4.7 Рекурсивные и рекурсивно-перечислимые множества (РМ и РПМ) Определение: Множество М называется РПМ, если элементы этого множества сгенерированы с помощью перечисляющей (порождающей) функции ах= φm(x), xN, axМ. Функция φm(x) – ОРФ. Определение: Множество М называется РМ, если существует алгоритм, который по любому объекту а дает ответ, принадлежит он как элемент множеству М или нет. То есть, если множество – М, то существует характеристическая функция типа ОРФ Xm(a). Xm(a)= Из определений следует, что любое конечное множество является РМ и РПМ. А также, если множество РМ, то оно и РПМ. С понятиями РМ и РПМ связаны понятия: множества, заданное эффективно, а таже конструктивное построение множества. Пример: 1. М={0, 1} - оно и РМ и РПМ. 2. Множество четных чисел М={0, 2, 4, .., n} – РПМ и РМ. 3. Рассмотрим десятичное разложение числа π π =3, 14159265… Выделим тройки, четверки или пятерки чисел. Если тройки: φm(0)=314 φm(1)=159 φm(x2)=265 Это РПМ, но не РМ. Функция, которая нумерует алгоритм – перечисляемая. Множество всех алгоритмов – РПМ. Так как, язык теории множеств является наиболее универсальным языком математики, то его язык в плане РМ и РПМ может быть использован для определения существования или отсутствия алгоритма решения задач. Множества пар (x, y) M, таких что Ах(y) – дает результат не РМ. Теорема: Множество всех ОРФ не РМ, но оно РПМ. Множество М является РМ тогда и только тогда, когда оно само (М) и его дополнение () - РПМ. Если на выходе некоторого аппарата появляется числовая последовательность, которая не является РПМ и тем более не РМ, то это говорит о том, что процесс работы этого аппарата не может быть алгоритмизован (не является алгоритмическим). 4.8 Теорема Райса Теорема Райса: Никакое нетривиальное свойство вычислимых функций не является разрешимой. Определение: Пусть С – некоторый нетривиальный класс вычислимых функций одной переменной. Например: класс постоянных функций, периодических, ограниченных, функций содержащий среди своих значений конкретного числа. Теорема: Не существует алгоритма, который по номеру х, функции fx, определил бы принадлежитfxC или нет. Или множество М={x| fxC } – не РМ. Теорема Райса показывает, что по номеру вычислимой функции нельзя узнать, является ли она постоянной, периодической и т.д. По номеру алгоритма, который реализует функцию fx однозначно определяется его описание. Разным номерам соответствуют разные алгоритмы. Но для функции в классическом математическом смысле слова – это не так. При ху fxи fy могут вычислять одну и туже математическую зависимость. В теореме Райса участвуют функции – алгоритмы и математические функции как зависимости. Когда мы говорим fx- это алгоритм, а класс функции – в математическом смысле слова. Таким образом, смысл теоремы Райса состоит в том, что по описанию алгоритма нельзя узнать о его свойствах. По синтаксису алгоритма ничего нельзя сказать о его семантике. Примеры неразрешимости задач: 1) Черч F1,…,Fn F0 Исчисление предикатов 1-го порядка неразрешимо. Все множество ППФ является РПМ множеством, но это не РМ множество. Исчисление предикатов высших порядков и не РПМ и не РМ. 2) Не существует алгоритма решения диафантово уравнения. 3) Множество всех теорем обычной арифметики – РПМ, но не РМ. Теорема Геделя гласит, что каждая тривиальная арифметическая логика не полна. Т.е. существует суждение о числах, которые нельзя доказать в этой логике. 4) Не существует алгоритма, позволяющего для любого многочлена с целыми коэффициентами, определить, представляет ли многочлен числа из натурального ряда или нет. Если рассмотреть х у (τ(х,у)=0), где функция τ – это ПРФ. Не существует алгоритма, выявляющего тождественную истинность этого предиката. у(τ(х*,у)=0) уР(у) Для них не существует алгоритма определения их тождественной истинности. С теоретической точки зрения неразрешимость – это не удача, а научный факт. Знание алгоритмически неразрешимых проблем необходимо для специалиста в области криптографии. Чтобы иметь дело с наверняка разрешимыми задачами, надо учитывать, что: 1) Отсутствие общего алгоритма решения проблемы не означает отсутствие успеха в каждом частном случае. 2) Наличие неразрешимости – признак чрезмерно общей постановки задачи. 5 СЛОЖНОСТЬ АЛГОРИТМОВ Сложность функций и сложность алгоритмов За сложность самой функции принимают минимальную алгоритмическую сложность. Если сложность алгоритма можно легко определить, то для получения сложности функции надо доказать, что имеющийся алгоритм – оптимальный. Сложность алгоритма на разных алгоритмических моделях. Сложность алгоритмов сильно зависит от того, какая алгоритмическая модель используется: 1) НАМ 2) МТ 3) РФ 4) ЭВМ – модели Например, задача копирования числа: Исходное (входное) слово 10111 Результат 10111•10111 ВНАМ и на МТ, используя «табличный» способ реализации (с большим числом подстановок в системе и большим числом состояний соответственно) преобразование может быть выполнено за небольшое число шагов. При сравнении алгоритмических моделей возникает вопрос: инвариантна ли сложность в этих моделях? Положительный ответ на вопрос об инвариантности основана на том, что задачи моделирования одних алгоритмов другими – P-сложная задача. Между сложностью решения задачи на МТ и ЭВМ существует следующее соотношение: ОMT(n)18 (OЭВМ(n))2 При использовании в ЭВМ адресной арифметики: ОMT(n) (OЭВМ(n))3 Следствие. Проблему поиска лучшего ранее известного алгоритма можно разделить на 2 класс: 1) Полиномиальная оптимизация 2) Принципиальная оптимизация (перевели задачу из экспоненциальной сложности в полиномиальную). Как только достигнута сложность вида O(nm), т.е. найден не переборный, а целенаправленный алгоритм решения задачи, то очень скоро (значительно более легко) удается его оптимизировать в плане уменьшения m. Классы сложности алгоритмов. Задача принадлежит классу Р, если она решается на МТ с полиномиальной сложностью. Рассмотрим недетерминированную МТ (НДМТ). НДМТ является математической абстракцией, реально ее создать невозможно. Для этого нужны бесконечные ресурсы. Рассмотрим одну команду НДМТ: qiaj→ l- максимальное число вариантов действий на каждом шаге. При выполнении первой команды возникает l параллельно работающих МТ. До выполнения данной команды записи на лентах одинаковы, после выполнения – они расходятся. Для больших ДМТ: K1→K2→K3→… Для НДМТ: → + результаты НДМТ – одновременно решает задачу разными способами. Каждой машине соответствует вариант ветви вычислений. Определение. Задача принадлежит классу NP, если она выполняется на НДМТ с полиномиальной сложностью. Т.к. обычная ДМТ – частный случай НДМТ при l=1, то это означает, что все задачи класса P являются задачами класса NP. NP –полные задачи и P – задачи. Некоторая задача, называемая NР – complete , если все остальные задачи с временной сложностью Р преобразуются в эту задачу. Стратегии решения NP – полных задач 1) Приближенный алгоритм с некоторой погрешностью ε. 2) Вероятные алгоритмы (метод Монте-Карло). 3) Частный случай NP – полных задач может оказаться Р – задачей. 4) Экспоненциальный алгоритм. 5) Локальный поиск. 6) Использование эвристик (в любом сочетании первые 5 подходов) без гарантии получения результатов.