Определение нормального алгоритма и его выполнение

В середине прошлого века выдающийся русский математик А.А. Марков ввел понятие нормального алгоритма (алгорифма) с целью уточнения понятия " алгоритм ", что позволяет решать задачи по определению алгоритмически неразрешимых проблем. Позже это понятие получило название нормального алгоритма Маркова (НАМ). Язык НАМ, с одной стороны, намеренно беден, что необходимо для цели введения понятия " алгоритм ". Однако, с другой стороны, идеи НАМ положены в основу большой группы языков программирования, получивших название языки логического программирования, которые являются темой данного пособия.

Для определения НАМ вводится произвольный алфавит - конечное непустое множество символов, при помощи которых описывается алгоритм и данные. В алфавит также включается пустой символ, который мы будем обозначать греческой буквой .Под словом понимается любая последовательность непустых символов алфавита либо пустой символ, который обозначает пустое слово.

Всякий НАМ определяется конечным упорядоченным множеством пар слов алфавита, называемых подстановками. В паре слов подстановки левое (первое) слово непустое, а правое (второе) слово может быть пустым символом. Для наглядности левое и правое слово разделяются стрелкой. Например,

1.

2.

3.

4.

В качестве данных алгоритма берется любая непустая строка символов. Работа НАМ состоит из последовательности совершенно однотипных шагов. Шаг работы алгоритма может быть описан следующим образом:

1. В упорядоченной последовательности подстановок ищем самую первую подстановку, левое слово которой входит в строку данных.

2. В строке данных ищем самое первое (левое) вхождение левого слова найденной подстановки.

3. Это вхождение в строке данных заменяем на правое слово найденной подстановки (преобразование данных).

Шаг работы алгоритма повторяется до тех пор, пока

· либо не возникнет ситуация, когда шаг не сможет быть выполнен из-за того, что ни одна подстановка не подходит (левое слово любой подстановки уже не входит в строку данных) - правило остановки;

· либо не будет установлено, что процесс подстановок не может остановиться.

В первом случае строка данных, получившаяся при остановке алгоритма, является выходной (результатом) и алгоритм применим к входным данным, а во втором случае алгоритм не применим к входным данным.

Так, определенный выше в примере нормальный алгоритм Маркова преобразует слово в слово следующим образом (над стрелкой преобразования мы пишем номер применяемой подстановки, а в преобразуемой строке подчеркиваем левое слово применяемой подстановки):

а при преобразовании слова abbc этот же алгоритм будет неограниченно работать, так как имеет место цикличное повторение данных:

Таким образом, всякий нормальный алгоритм Маркова определяет функцию, которую мы назовем нормальной (или вычислимой по Маркову), которая может быть частичной и которая в области определения входному слову ставит в соответствие выходное слово.

21 Основная идея метода резолюций состоит в том, чтобы проверить, содержит ли множество дизъюнктов пустой дизъюнкт. Если множество содержит пустой дизъюнкт, то оно противоречиво (невыполнимо). Если множество не содержит пустой дизъюнкт, то проверяется следующий факт: может ли пустой дизъюнкт быть получен из данного множества. Множество содержит пустой дизъюнкт, тогда и только тогда, когда оно пустое. Если множество можно свести к пустому, то тем самым можно доказать его противоречивость. В этом и состоит метод резолюций, который часто рассматривают как специальное правило вывода, используемое для порождения новых дизъюнктов из данного множества.

Отметим, что дизъюнкт есть тавтология, если он содержит контрарную пару.

Определение 25: Правило резолюций состоит в следующем:

Для любых двух дизъюнктов C₁ и C₂, если существует литерал L₁ в C₁, который контрарен литералу L₂ в C₂, то вычеркнув L₁ и L₂ из C₁ и C₂ соответственно и построив дизъюнкцию оставшихся дизъюнктов, получим резолюцию (резольвенту) C₁ и C₂.

Пример 9: рассмотрим следующие дизъюнкты:

C₁: PЪ R,

C₂: ШPЪ Q.

Дизъюнкт C₁ имеет литерал P, который контрарен литералу ШP в C₂. Следовательно, вычеркивая P и ШP из C₁ и C₂ соответственно, построим дизъюнкцию оставшихся дизъюнктов R и Q и получим резольвенту RЪ Q.

Важным своством резольвенты является то, что любая резольвента двух дизъюнктов C₁ и C₂ есть логическое следствие C₁ и C₂. Это устанавлисвается в следующей теореме.

Теорема 4. Пусть даны два дизъюнкта C₁ и C₂. Тогда резольвента C дизъюнктов C₁ и C₂ есть логическое следствие C₁ и C₂.

Если есть два единичных дизъюнкта, то их резольвента, если она существует, есть пустой дизъюнкт я. Более существенно, что для невыполнимого множества дизъюнктов многократным применением правила резолюций можно породить я.

Определение 26: Пусть S – множество дизъюнктов. Резолютивный вывод C из S есть такая конечная последовательность С₁, C₂,…, C_k дизъюнктов, что каждый C_i или принадлежит S или является резольвентой дизъюнктов, предшествующих C_i, и C_k=C. Вывод я из S называется опровержением (или доказательством невыполнимости) S.

Пример 11. Рассмотрим множество S:

1. ШPЪ Q,

2. Ш Q,

3. P.

Из 1 и 2 получим резольвенту

4. ШP.

Из 4 и 3 получим резольвенту

5. я.

Так как я получается из S применениями правила резолюций, то согласно теореме 4 я есть логическое следствие S, следовательно S невыполнимо.

Метод резолюций является наиболее эффективным в случае применения его к множеству Хорновских дизъюнктов.

Определение 27:Фразой называется дизъюнкт, у которого негативные литералы размещаются после позитивных литералов в конце дизъюнкта.

22 Алфавит языка логики предикатов

1) Константы (индивидные символы). Обычно это имена объектов, наименования свойств, характеристик, значения свойств или характеристик;

2) Символы предметных переменных. Обычно, это малые буквы x, y,z, возможно с индексами. Предметная переменная подразумевает наличие области её определения, т.е. конечного множества значений данной переменной;

3) Функциональные символы. Обычно, это малые буквы f,q,h или осмысленные слова из строчных букв, например, плюс, минус, умножить, отец, мать, дочь;

4) предикатные символы. Обычно, это прописные (большие) буквы P,Q,R, или осмысленные слова из прописных букв, такие как БОЛЬШЕ, МЕНЬШЕ, ЛЮБИТ, СОДЕРЖИТ, СМЕРТЕН,ЧЕЛОВЕК.

5) связки исчисления высказываний.

6) кванторы общности (для всех) и существования (существует).

В языке предикатов содержится язык высказываний, так как предикат становится высказыванием после замены его предметных переменных их конкретными значениями.

Дата добавления: 2015-07-14