Содержание

1. Теория алгоритмов……………………………………………………….

   1. Нормальные алгоритмы Маркова…………………………………

   2. Машины Тьюринга…………………………………………………

   3. Рекурсивные функции……………………………………………..

   4. Алгоритмы и сложность……………………………………………

2. Формальные системы……………………………………………………..

   1. Понятие формальной системы…………………………………….

   2. Исчисление высказываний…………………………………………

      1. Предложения и высказывания………………………………….

      2. Исчисление высказываний как формальная система …………

   3. Исчисление предикатов первого порядка как формальная система

   4. Проблема разрешимости……………………………………………

3. Автоматическое доказательство теорем…………………………………

   1. Нормальные формы исчисления высказываний…………………

   2. Нормальные формы исчисления предикатов………………………

   3. Логические следствия……………………………………………….

   4. Процедура вывода Эрбрана…………………………………………

   5. Принцип резолюции для логики высказываний……………………..

   6. Принцип резолюции для логики предикатов……………………….

   7. Семантическая резолюция…………………………………………..

   8. Линейная резолюция………………………………………………….

Рекомендуемая литература…………………………………………..

1. Теория алгоритмов

1.1. Нормальные алгоритмы Маркова

Крупнейшим достижением науки ХХ века является теория алгоритмов. Предметом этой математической дисциплины являются алгоритмы. В двадцатых годах нашего века проблема точного определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине тридцатых годов в работах Гильберта, Гёделя, Чёрча, Клини, Поста, Тьюринга, и позднее Маркова. Чтобы сформулировать понятие алгоритма введем ряд понятий и определений.

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

Пусть Р и S - два слова в заданном алфавите А. Тогда R=PS - слово, полученное приписыванием справа к символам слова Р последовательно всех символов слова S. Слово Р входит в слово R, если R можно представить как S₁PS₂, где S₁, S₂ - слова, возможно пустые. При заданных R и Р может быть найдено несколько различных вхождений Р в R. Вхождение, при котором S₁ имеет наименьшую длину, назовем первым вхождением Р в S.

Пусть S₁PS₂ соответствует первому вхождению Р в R. Тогда слово, полученное заменой в слове R первого вхождения слова Р словом Q, имеет вид S₁QS₂. Назовем такое преобразование подстановкой вида P  Q. Применение подстановки к слову R сводится к замене какого-либо вхождения Р в R на слово Q. Если Р не входит в R, подстановка P  Q к слову R неприменима.

Преобразование слов в алфавите А может задаваться системой подстановок вида

P  Q,

называемых далее ориентированными подстановками. Если система подстановок включает в себя одновременно пару подстановок P  Q и Q P, такую ситуацию обозначим P  Q и будем говорить о неориентированной подстановке. Ассоциативным исчислением в А назовем множество всех слов в А вместе с конечной системой неориентированных подстановок.

Рассмотрим проблему эквивалентности слов в ассоциативном исчислении. Если слово S в ассоциативном исчислении может быть преобразовано в слово R путем однократного применения какой-либо подстановки, то R и S назовем смежными словами. Последовательность слов R₁, R₂, R₃, ... , R_n попарно- смежных, назовем дедуктивной цепочкой, ведущей от R₁ к R_n. Если можно построить цепочку, ведущую от слова R к слову S, то в силу симметричности подстановок можно построить и цепочку, ведущую от S к R. Слова R и S будут эквивалентными в данном ассоциативном исчислении (RS).

Лемма. Пусть PQ; тогда, если в каком-либо слове R имеется вхождение Р, то в результате подстановки вместо него Q получается слово, эквивалентное R.

Если для ассоциативного исчисления можно указать способ, с помощью которого для любой пары слов S₁ и S₂ можно определить, являются ли эти слова эквивалентными или нет, то говорят, что в этом ассоциативном исчислении разрешима проблема эквивалентности слов.

Пример 1.1. Дано исчисление: алфавит A={a, b, c} и система подстановок:

ba  ab

ca  ac

cb  bc

Доказать, что в подобном исчислении разрешима проблема эквивалентности слов.

Легко заметить, что приведенная система подстановок обладает одним свойством: каждая подстановка меняет порядок букв в слове, не изменяя количества этих букв. Алгоритм определения, являются ли два заданных слова S₁ и S₂ эквивалентными, состоит в подсчете количества букв a, b, c в данных словах: если число букв a, b, c в слове S₁ равно числу тех же букв в слове S₂, то вне зависимости от расположения этих букв в S₁ и S₂ слова будут эквивалентными.

Проблема эквивалентности слов для ассоциативных исчислений была впервые сформулирована ещё в 1914 году норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой алгоритм, который для любого ассоциативного исчисления и для любой пары слов в нем позволил бы установить, эквивалентны эти слова, или нет.

В 1946 и 1947 годах русский математик А.А.Марков и американский матема­тик Э.Пост независимо один от другого построили конкретные примеры ассоциатив­ных исчислений, для каждого из которых проблема эквивалентности слов алгорит­ми­ч­ески неразрешима. Тем более не существует алгоритма для распознавания экви­ва­­лентности слов в любом исчислении. Первые примеры, построенные для алгоритмической неразрешимости ассоци­а­тив­ных исчислений, оказались весьма громоздкими и насчитывали сотни доп­усти­мых подстановок. Была поставлена задача построения по возможности более про­с­тых примеров. В этом направлении впечатляет успех математика Г.С.Цейтина, по­строившего пример ассоциативного исчисления, насчитывающего всего семь допус­тимых подстановок, в котором проблема эквивалентности слов также алгоритмичес­ки неразрешима.

Пример 1.2 (Г.С.Цейтин). Дано ассоциативное исчисление, включающее алфавит A={ a, b, c, d, e} и систему подстановок:

1. ac  ca, 5. abac  abace,

2. ad  da, 6. eca  ae,

3. bc  cb, 7. edb  be.

4. bd  db,

В данном исчислении неразрешима проблема эквивалентности слов.

Как с помощью системы подстановок можно построить алгоритм? Поскольку алгоритм требует однозначного решения, что делать на каждом шаге, введем следую­щие требования:

1. Используем только ориентированные подстановки.

2. Систему подстановок упорядочиваем:

1) P₁  Q₁

2) P₂ Q₂

. . .

k) P_k  Q_k

3. В применении к какому-либо слову R алгоритм работает следующим образом. Берется первая по порядку подстановка из списка, которая применима к слову R. При наличии нескольких вхождений ее левой части в слово, подстановку применяют к самому левому (первому) вхождению. К полученному новому слову опять применяется самая первая подстановка и т.д. Если после конечного числа таких шагов получено слово S, к которому неприменима ни одна из подстановок, будем говорить, что алгоритм применим к слову R и перерабатывает его в слово S.

Алгоритм для переработки слов в алфавите А, заданный какой-либо упоря­до­ченной конечной системой ориентированных подстановок в совокупности с правилами применения подстановок называется нормальным алгоритмом Маркова.

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

1) P  Q.

2) P  .

3)  *

где символ . играет роль команды STOP, то есть после замены Р на Q в случае 1) или после стирания Р в случае 2) прекращается дальнейшее применение подстановок. Подстановка 3) приписывает символ * слева к слову.

Прекращение применения подстановок возможно в следующих случаях:

- в слово не входит ни одна из левых частей подстановок;

- слово таково, что к нему на предшествующем шаге была применена подстановка Р Q. или Р  . . В этих случаях мы получим результирующее слово.

Рассмотрим примеры работы алгоритма Маркова.

Пример 1.3

Алфавит А содержит символ { | }. Построить нормальный алгоритм Маркова, удваивающий число в унарной системе счисления. Вспомним, что в унарной системе счисления любое натуральное число представляется соответствующим количеством палочек. Так, запись | | | | | соответствует числу 5, а запись | | | - числу 3.

Решение. Для удвоения исходного числа, представленного набором палочек, необходимо ввести основную подстановку вида:

|  | |

Однако попытка применить такую подстановку к любому исходному слову приведет к тому, что удваиваться будет всегда самая первая (левая) палочка в слове (в соответствии с правилом применения подстановок) и алгоритм никогда не остано­вится. Возникает проблема, как отличить уже удвоенные палочки от палочек исход­ного слова? Используем дополнительный символ *, чтобы отличать уже удвоенные палочки от палочек исходного слова. Тогда подстановка примет вид: *| | | *, и при каждом удвоении звездочка будет перемещаться вправо. Но в исходном слове нет символа *. Чтобы приписать звездочку слева от основного слова введем подста­нов­ку: * и разместим ее самой последней в системе подстановок. Что­бы избежать многократного приписывания звездочек к исходному слову выше этой подстановки поместим подстановку, содержащую символ окончания алгоритма (точ­ку). Алгоритм должен заканчиваться, когда справа от * не останется ни одной па­лоч­ки, нуждающейся в удвоении. Поэтому окончательно система подстановок при­мет вид:

1) *| | | *

2) *.

3) *

Рассмотрим пример работы алгоритма. Исходное слово S = | | | что соответствует числу 3.

| | | _подст.3* | | | _подст.1| | * | | _подст.1| | | | * | _подст.1| | | | | | * _подст.2 | | | | | |.

Пример 1.4

Построить алгоритм Маркова для перевода чисел из двоичной системы счисления в унарную.

Решение. Двоичная система счисления является позиционной, то есть «вес» каждой цифры (единицы) зависит от ее положения в двоичном числе. Поскольку веса разрядов являются степенями двойки, положим в основу алгоритма принцип удвоения палочки при переходе через каждый разряд. В соответствии с этим введем подстановки:

|1 1 | |

и |0 0| |.

Исходное слово (двоичное число) содержит только нули и единицы, поэтому потребуется подстановка, заменяющая самую старшую (левую) единицу двоичного числа на палочку: 1 |. Если самым левым символом слова будет ноль, его можно просто стереть: 0 . Наконец, признаком завершения работы алгоритма будет получение слова, состоящего только из палочек (подстанов­ка ||.). Расположим введенные подстановки в следующем порядке:

1. |1 1| |

2. |0 0| |

3. 0

4. 1 |

5. | |.

Применим данный алгоритм к слову 101 (число 5 в двоичной системе).

101 _подст.4  | 01_подст.2  0 | | 1 _подст.1 0 | 1 | | _подст.1 01 | | | | _подст.3  1 | | | | _подст.4 | | | | | _подст.5 | | | | | .

Результатом является слово из пяти палочек, то есть число 5 в унарной системе. Чтобы проверить, как влияет порядок подстановок на работу алгоритма, поменяйте местами подстановки 3 и 4. Примените новый алгоритм к слову 100 (число 4). Что изменится? Самостоятельно проверьте, как будет работать алгоритм, если самой первой сделать подстановку номер 4 ( 1| ). Будет ли такой алгоритм решать поставленную задачу? Обоснуйте ответ.

Тезис А.А.Маркова. Всякий алгоритм в алфавите А эквивалентен некоторому нормальному алгоритму в этом же алфавите.

Этот тезис не может быть строго доказан, так как, с одной стороны, здесь имеет место интуитивное понятие «всякий алгоритм», а с другой стороны - точное понятие «нормальный алгоритм».

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

aa a

bb b

cc  c

можно ввести обобщенную подстановку  , где А={ a, b, c}.

При применении системы подстановок L к некоторому исходному слову S возможны два случая:

1. если процесс преобразования слова заканчивается после конечного числа применения подстановок, в результате чего получается результирующее слово R, то говорят, что нормальный алгоритм применим к слову S и перерабатывает его в слово R;

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

В приведенных примерах были даны готовые системы подстановок и не были указаны правила построения этих систем. К сожалению, нет общих правил получения систем подстановок. Так, один и тот же алгоритм можно реализовать, используя совершенно разные принципы. Рассмотрим следующую задачу.

Пример 1.5. Требуется построить нормальный алгоритм Маркова, переводящий число, представленное в унарной системе счисления, в систему счисления по основанию 2.

Для перевода слова, представляющего собой набор палочек, в запись в двоичном коде воспользуемся следующим методом. Первоначально припишем к исходному слову ноль. Далее, стирая по одной палочке, будем каждый раз прибавлять 1 к формируемому двоичному числу. При отсутствии палочек алгоритм завершит работу. Важной частью задачи является организация двоичного переноса при прибавлении 1 к двоичному числу. Введем для этого новый символ . Система подстановок примет вид:

1) 1  0

2) 0  1

3) 0  10

4) 0|  1

5) 1|  0

6) 1  .1

7)  0

Рассмотрим работу алгоритма на примере слова из пяти палочек.

| | | | | _подст.7  0| | | | | _подст.4  1| | | | _подст.5  0| | | _подст.3  10| | | _подст.4  11| | _подст.5  10| _подст.1  00| _подст.3  100| _подст.4  101 _подст.6  101.

Ту же задачу можно решить, основываясь на другом принципе. Известный алгоритм перевода произвольного числа в двоичную систему счисления заключается в последовательном делении исходного числа и затем получаемых частных на основание 2. Цифрами двоичного числа при этом будут остатки от деления, причем младшей цифре числа соответствует первый полученный остаток, старший разряд числа соответствует последнему частному:

 6 2 Код 110 соответствует числу 6.

6 3 2

0 2 1

1

Система подстановок для реализации такого алгоритма может быть записана следующим образом.

1) *| |  |*

2) *|  1

3) |* | 0

4) *1 .1

5) *0  .0

6)  *

Самостоятельно рассмотрите процесс перевода любого числа из палочек в двоичный код на примере данной системы подстановок.

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

Задачи

1.	Ассоциативное исчисление включает алфавит А={a, b, c, d, e} и систему подстановок: ac  ca, bc  cb, bd  db, eca ae, edb  be, abac  abacc, ad  da. Эквивалентны ли в этом исчислении пары слов aad и cbbc, abcde и cadedb?
2.	Доказать, что в ассоциативном исчислении, включающем алфавит А={a, b} и систему подстановок aaa  bb, bbbb  разрешима проблема эквивалентности слов.
3.	Нормальный алгоритм Маркова определен в алфавите А={a, b} системой подстановок: ba  a aa  a bb  a aaaa  В какое слово этот алгоритм переработает 1) слово abab, 2) слово bbbb, 3) слово abba?
4.	Доказать, что нормальный алгоритм, определенный в алфавите А={a, b, c} системой подстановок ba  ab cb  bc ca  ac a  b  cc  c любое слово в А перерабатывает либо в пустое слово, либо в однобуквенное слово с.
5.	Построить нормальный алгоритм , прибавляющий единицу к числу, представленному в двоичной системе счисления.
6.	Построить нормальный алгоритм, преобразующий всякое унарное число в запись этого числа в троичной системе счисления.
7.	Написать нормальный алгоритм, преобразующий всякое унарное число в запись этого числа в восьмеричной системе счисления.
8.	Написать нормальный алгоритм, преобразующий всякое унарное число в запись этого числа в десятичной системе счисления.
9.	Написать нормальный алгоритм, который всякое натуральное число, записанное в троичной системе счисления, преобразует в унарное число.
10.	Написать нормальный алгоритм, который всякое натуральное число, записанное в восьмеричной системе счисления, преобразует в унарное число.
11.	Написать нормальный алгоритм, который всякое натуральное число, записанное в десятичной системе счисления, преобразует в унарное число.
12.	Написать нормальный алгоритм, который преобразует любое унарное число N в целую часть числа (3N : 2).
13.	Написать нормальный алгоритм, который находит наибольший общий делитель двух чисел, записанных в унарной системе счисления.
14.	Написать нормальный алгоритм, который преобразует любое унарное число N в целую часть числа ((2N+1):3).
15.	Написать нормальный алгоритм, который преобразует любое унарное число в остаток от деления этого числа на 5.
16.	Написать нормальный алгоритм, который преобразует любое унарное число M*N в целую часть числа ((M+N):3).
17.	Написать нормальный алгоритм, который преобразует унарное число M*N (где М>N) в целую часть числа ((M-N):2).
18.	Написать нормальный алгоритм, преобразующий унарное число M*N (M>N) в остаток от деления М на N.
19.	Написать нормальный алгоритм для умножения унарных чисел M*N.
20.	Написать нормальный алгоритм, преобразующий унарное число N в число (3N-2).
21.	Написать нормальный алгоритм, преобразующий унарное число M*N в число 3(M+N).
22.	Написать нормальный алгоритм, преобразующий унарное число M*N (M>N) в число 2(M-N).
23.	Написать нормальный алгоритм, преобразующий число N в число 2N, если оно нечетно, и в число 3N, если N- четно.
24.	Написать нормальный алгоритм сложения натуральных чисел, записанных в двоичной системе счисления.
25.	Написать нормальный алгоритм, переводящий любое натуральное число из восьмеричной системы счисления в двоичную.
26.	Написать нормальный алгоритм, выполняющий умножение двух чисел в унарной системе счисления.
27.	Построить нормальный алгоритм, проверяющий, состоит ли произвольное слово Р в алфавите { a, b, c} из одинаковых букв (только a, только b, только с) .
28.	Написать нормальный алгоритм, переводящий любое натуральное число из двоичной системы счисления в восьмеричную систему счисления.
29.	Написать нормальный алгоритм, переводящий любое натуральное число из двоичной системы счисления в десятичную систему счисления.
30.	Построить нормальный алгоритм, преобразующий слово P, в алфавите { a, b, c} в слово РP.
31.	Построить в алфавите { a, b, c} алгоритм, который переворачивает любое слово в данном алфавите.