- •ВВЕДЕНИЕ
- •Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
- •§1. Высказывание. Логические операции
- •§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности
- •§ 3. Упрощения в записях пропозициональных форм
- •§ 4. Тавтологии (общезначимые формулы). Противоречия
- •§ 5. Равносильность пропозициональных форм
- •§ 6. Важнейшие пары равносильных пропозициональных форм
- •§ 7. Зависимости между пропозициональными связками
- •§ 8. Нормальные формы
- •§ 9. Совершенные нормальные формы
- •§ 10. Булева (переключательная) функция
- •§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
- •§ 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов
- •§ 13. Вопросы и темы для самопроверки
- •§ 14. Упражнения
- •Глава 2 ЛОГИКА ПРЕДИКАТОВ
- •§ 1. Понятие предиката
- •§ 2. Кванторы
- •§ 3. Формулы логики предикатов
- •§ 4. Интерпретация. Модель
- •§ 5. Свойства формул в данной интерпретации
- •§ 6. Логически общезначимые формулы. Выполнимые и равносильные формулы
- •§ 8. Правила перестановки кванторов
- •§ 9. Правила переименования связанных переменных
- •§ 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма
- •§ 11. Вопросы и темы для самопроверки
- •§ 12. Упражнения
- •Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
- •§ 1. Логическое следствие и проблема дедукции в логике высказываний
- •§ 2. Резольвента дизъюнктов логики высказываний
- •§ 3. Метод резолюций в логике высказываний
- •§ 4. Метод насыщения уровня
- •§ 5. Стратегия вычеркивания
- •§ 6. Лок-резолюция
- •§ 7. Метод резолюций для хорновских дизъюнктов
- •§ 8. Преобразование формул логики предикатов. Сколемовская стандартная форма
- •§ 9. Унификация
- •§ 10. Метод резолюций в логике предикатов
- •§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля.
- •§ 12. Использование метода резолюций в языке ПРОЛОГ
- •§ 13. Введение и использование правил в ПРОЛОГе
- •§ 14. Рекурсивное задание правил в ПРОЛОГе
- •§ 15. Особенности ПРОЛОГа
- •§ 16. Вопросы и темы для самопроверки
- •§ 17. Упражнения
- •Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
- •§ 1. Понятие об эффективных и полуэффективных процессах (методах)
- •§ 2. Дедуктивные теории
- •§ 3. Свойства дедуктивных теорий
- •§ 4. Пример полуформальной аксиоматической теории - геометрия
- •§ 5. Формальные аксиоматические теории
- •§ 6. Свойства выводимости
- •§ 7. Исчисление высказываний (теория L)
- •§ 8. Некоторые теоремы исчисления высказываний
- •§ 9. Эквивалентность двух определений непротиворечивости
- •§ 11. Свойства исчисления высказываний
- •§ 12. Другие аксиоматизации исчисления высказываний
- •§ 13. Теории первого порядка
- •§ 14. Формальная арифметика (теория S)
- •§ 15. Свойства теорий первого порядка
- •§ 16. Значение аксиоматического метода
- •§ 17. Теория естественного вывода
- •§ 18. Вопросы и темы для самопроверки
- •§ 19. Упражнения
- •Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
- •§ 1. Трехзначные логики
- •§ 2. Многозначные логики
- •§ 3. Понятие нечеткого множества
- •§ 4. Нечеткие высказывания и максиминные операции над ними
- •§ 5. Понятие о нечеткой лингвистической логике
- •§ 6. Модальные логики
- •§ 7. Временные (темпоральные) логики
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •Глава 6. ТЕОРИЯ АЛГОРИТМОВ
- •§1. Неформальное понятие алгоритма
- •§ 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы
- •§ 3. Нормальный алгоритм (алгоритм А. А. Маркова)
- •§ 4. Функции частично вычислимые и вычислимые по Маркову
- •§ 5. Замыкание, распространение нормального алгоритма
- •§ 6. Операции над нормальными алгоритмами
- •§ 7. Машина Тьюринга
- •§ 8. Задание машины Тьюринга
- •§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
- •§ 10. Связь между машинами Тьюринга и нормальными алгоритмами
- •§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)
- •§ 12. Проблема алгоритмической неразрешимости
- •§ 13. Примеры алгоритмически неразрешимых массовых проблем
- •§ 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
- •§ 15. Примитивно рекурсивные и общерекурсивные функции
- •§ 16. Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
- •§ 17. Ламбда-исчисление
- •§ 18. Основные результаты
- •§ 19. Вопросы и темы для самопроверки
- •§ 20. Упражнения
- •Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ
- •§ 1. Понятие о сложности
- •§ 2. Временная сложность вычислений (алгоритма)
- •§ 3. Полиномиальные алгоритмы и задачи. Класс Р
- •§ 4. NP класс
- •§ 5. NP-полные и NP-трудные задачи
- •§ 6. Класс Е
- •§ 7. Ёмкостная (ленточная) сложность алгоритма
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •ЛИТЕРАТУРА
- •ПРИЛОЖЕНИЯ
- •Варианты типового задания
- •Тесты для самоконтроля
- •Тест по логике высказываний (тест № 1)
- •Тест по логике предикатов (тест № 2)
- •Тест по логическому следствию и методу резолюций (тест № 3)
- •Тест по дедуктивным теориям (тест № 4)
- •Тест по теории алгоритмов (тест № 5)
- •Тест по неклассическим логикам и сложности вычислений (тест № 6)
- •Ответы к тестам самоконтроля
183
очевидно, тоже применим только к тем словам в алфавите М, которые суть цифры, и преобразует любое слово n в слово n +1, т.е. A1( n )= n +1 для любого натурального n. Алгоритм A1, как и A0, не применим к пустому слову.
Когда я рассмотрел то, что нужно людям при счёте, я нашёл , что всё это есть число.
Аль-Хорезми
§ 4. Функции частично вычислимые и вычислимые по Маркову
Напомним, что функция f(x) называется частично определенной на множестве M, если значения этой функции определены не для всех х из M.
Функция f называется арифметической, если ее значения и значения её аргументов являются целыми неотрицательными числами, т.е. область определения аргументов и область значений функции есть множество натуральных чисел.
Положим, как и раньше, алфавит М={1,*}.
Пусть ϕ частично определенная арифметическая функция от n аргументов. Положим, что существует некоторый алгоритм (не обязательно нормальный) Aϕ в алфавите М, позволяющий вычислять значения этой
функции всякий раз, когда |
значение функции существует, т.е. |
||||
Aϕ(( |
|
))= |
|
|
тогда и только тогда, когда хотя бы одна из |
k1,k2 ,...,kn |
ϕ( k1 ,k2 ,...,kn ) |
частей этого равенства определена. При этом считаем, что алгоритм Aϕ не применим к словам, отличным от слов вида ( k1,k2 ,...,kn ). Назовем функцию
ϕ частично вычислимой по Маркову функцией, если существует нормальный алгоритм B над М, вполне эквивалентный Aϕ относительно алфавита М.
Иными словами, n-аргументная функция ϕ частично вычислима по Маркову тогда и только тогда, когда существует нормальный алгоритм, позволяющий вычислить значение ϕ(k1,k2,...,kn) для любых совокупностей значений х1=k1, х2=k2,..., xn = kn, при которых ϕ(k1,k2,...,kn) существует.
Если функция определена всюду, т.е. определена для любой совокупности значений своих аргументов, и является частично вычислимой по Маркову, то назовем ее вычислимой по Маркову. Таким образом, n- аргументная функция ϕ вычислима по Маркову тогда и только тогда, когда существует нормальный алгоритм, позволяющий вычислить значение ϕ(x1,x2,...,xn) для любых совокупностей значений x1,x2,...,xn.
В предыдущем параграфе показано, что для всюду определенных арифметических функций
f(x)=0, x(x≥0), f(x)=x+1, x(x≥0),
существуют нормальные алгоритмы, вычисляющие их значения (примеры 4, 5). Следовательно, эти функции являются вычислимыми по Маркову.
184
Где начало того конца, которым оканчивается начало.
Козьма Прутков
§ 5. Замыкание, распространение нормального алгоритма
Пусть A - произвольный нормальный алгоритм в алфавите А: |
|
P |
→(•)Q |
1 |
1 |
P2 →(•)Q2 |
|
A = |
|
................. |
|
|
→(•)Q |
P |
|
n |
n |
Замыканием алгоритма A называется алгоритм А•, полученный из A добавлением формулы подстановки Λ→•Λ в качестве последней подстановки, т.е.
P1 → (•)Q1P2 → (•)Q2
А• = .................
Pn → (•)QnΛ→•Λ
Нам известно, что любой нормальный алгоритм заканчивает процесс переработки слова либо после применения заключительной подстановки, либо если все слова Р1,Р2,Р3,..., Рn не содержатся в слове, полученном при предыдущем шаге. Подстановка Λ→•Λ применима к любому слову. Следовательно, алгоритм А• заканчивает переработку слов всегда по заключительной подстановке, которая есть либо некоторая из подстановок
Pi→(•)Qi (1≤ i≤ n) либо Λ→•Λ.
Отметим, что подстановка Λ→•Λ, добавленная к A для получения А•, стоит последней. Поэтому эта подстановка будет применяться только тогда, когда не применимы все подстановки алгоритма A, причем применение Λ→•Λ к любому слову не изменяет этого слова. Следовательно, результаты применения алгоритмов A и А• к любому слову в А будут совпадать, т.е. алгоритмы A и А• вполне эквивалентны.
Пусть A - нормальный алгоритм в алфавите А1, а алфавит А2 является
расширением А1, т.е. А1 А2. Тогда можно рассмотреть нормальный алгоритм |
|||
A# в алфавите А2 с той же самой схемой, что и A . Очевидно, |
|
||
|
# |
(Р), |
(1) |
P в алфавите А1: А(Р) |
А |
|
т.е. A и A# вполне эквиваленты относительно А1. Нормальный алгоритм А#
будем называть естественным распространением A на алфавит А2.
В некоторых случаях удобнее, чтобы алгоритм A#, удовлетворяющий (1), был не применим к тем словам в А2, которые не являются словами в А1. Этого
185
легко достигнуть, приписав к схеме A сверху формулу вида x→x, где x - любая буква из А2\А1. Получившийся нормальный алгоритм называют формальным распространением A на алфавит А2. Очевидно, что формальное распространение алгоритма A вполне эквивалентно алгоритму A относительно А1 и не применимо к тем словам в А2, которые не являются
словами в А1.
Использование возможности распространения нормального алгоритма на более широкий алфавит позволяет во многих случаях опускать без особого ущерба точности упоминание об алфавитах, в которых строятся конкретные нормальные алгоритмы.
§ 6. Операции над нормальными алгоритмами
Композиция алгоритмов. Пусть A и B два алгоритма в алфавите А. Композицией алгоритмов A и B в алфавите А называют алгоритм C такой,
что P в А : C(P) B(A(P)).
Таким образом, композиция алгоритмов A и B представляет собой алгоритм, получающийся в результате последовательного применения алгоритмов к заданному слову Р, что можно продемонстрировать следующей блок-схемой (рис.6.1)
Р |
А(Р) |
В(А(Р)) |
А |
|
В |
Рис. 6.1.
Композиция алгоритмов A и B обозначается как: C=B°A
Пусть A1,A2,...,An - алгоритмы в алфавите А, тогда под An°An-1° ... °A1 будем понимать следующее:
An°(An-1°(...°(A3°(A2°A1))...)).
Теорема 6.1. Композиция нормальных алгоритмов A1,A2,...,An в алфавите А есть снова нормальный алгоритм (над алфавитом А).
Ясно, что достаточно провести доказательство для композиции двух алгоритмов.
Доказательство. Пусть A и B - нормальные алгоритмы в алфавите А. Сопоставим каждой букве а из А новую букву а, которую назовем двойником буквы а. При этом считаем, что для любой буквы а из А ее двойник не принадлежит А. Пусть А - алфавит, состоящий из всех двойников букв алфавита А. Выберем какие ни будь две буквы, например, α и β , не принадлежащие A A . Обозначим через Aα схему, полученную из схемы нормального алгоритма A• заменой в ней всюду "•" на "α".
186
Обозначим через B β схему, полученную из B• заменой "•" на "β", далее всех букв из А - их двойниками и затем заменой всех формул подстановок
вида Λ→Q формулами подстановок |
α→αQ. |
|||||||
Рассмотрим схему: |
|
|
||||||
aα |
→α a |
(a A) |
(1) |
|||||
|
→α a |
(a A) |
(2) |
|||||
α a |
||||||||
ab → a |
|
|
(a,b A) |
(3) |
||||
b |
||||||||
aβ → β a |
(a A) |
(4) |
||||||
C = βa → β a |
(a A) |
(5) |
||||||
ab |
→ ab |
(a,b A) |
(6) |
|||||
αβ |
→•Λ |
|
(7) |
|||||
|
|
β |
|
|
|
|
(8) |
|
|
B |
|
|
|
|
|||
Aα |
|
|
|
|
(9) |
Эта схема представляет собой сокращенную запись некоторого нормального алгоритма C (в алфавите A A {α, β}), причем в (1)-(6) буквы а и b означают произвольные буквы из А, а строки (8) и (9) означают, что нужно
записать все подстановки сначала алгоритма Вβ , затем алгоритма Aα. Покажем, что нормальный алгоритм C таков, что
P в А: C(Р) B(A(Р)),
т.е. C есть композиция A и B. Пусть задано произвольное слово Р, например, Р=ак1ак2...акm (акi A). Сначала подстановки (1)-(8) не применимы к Р, ибо
буквы α , β и буквы-двойники (алгоритм Вβ записан в двойниках) не содержатся в слове Р, а также в (8) нет подстановок вида Λ→Q, ибо они заменены на подстановки α→αQ. Если алгоритм A не применим к слову Р (перерабатывает его бесконечно), то по (9) и C будет не применимым к Р. Если A применим к Р, то в результате мы получили бы некоторое слово R=A(P), пусть, например, R=bn1bn2...bnk (bni A). Нам известно, что алгоритмы A и A• вполне эквивалентны, т.е. результаты их применения к любому слову из А совпадают. В предыдущем параграфе мы отметили, что алгоритм A• всегда заканчивает переработку слова заключительной подстановкой Pi →•Qi либо Λ→•Λ. Так как в Aα все "•" заменены на "α", то в результате
применения (9) получим, что в слове R где-то вклинится буква α, т.е. имеем:
bn1bn2...bnqαbn(q+1)…bnk (q ≤ k, bni A, 1 ≤ i ≤ k).
Применяя q раз подстановку (1) к последнему слову, получим
α bn1bn2...bnk (αA(P)).
После этого, применяя подстановку (2), и k-1 раз подстановку (3), придем к слову
αbn1 bn2 …bnk .
187
Если алгоритм В не применим к слову R=А(Р), то и алгоритм С будет не применим к Р вследствие того, что (8) будет бесконечно перерабатывать
слово bn1 bn2 …bnk
Если алгоритм B применим к слову R=A(Р), то в результате его применения мы получили бы слово B(A(Р)), пусть, например,
B(A(Р)) = cm1 cm2 ... cml ( cmi A, 1 ≤ i ≤ l ),
тогда, как легко видеть, что в результате применения (8) получим
αсm1 сm2 .. сms β сms+1... сml (s ≤ l; cmi A, 1 ≤ i ≤ l )
Теперь s-кратное применение (4) приводит к слову
αβ сm1 сm2 .. сml.
Далее применяя (5), а затем (l-1) раз (6), имеем
α β cm1 cm2 .. cm = α β B(A(P)).
Применяя заключительную подстановку (7), получим результат B(A(P)). Таким образом, C(P) B(A(P)), и так как слово Р было произвольным, то
теорема доказана.
Соединение алгоритмов.
Теорема 6.2. Пусть A1,A2,...,An-нормальные алгоритмы в алфавитах А1,А2,...,Аn соответственно и пусть А - объединение этих алфавитов. Тогда существует нормальный алгоритм B над А, называемый соединением алгоритмов A1,A2,...,An, такой, что
P в А : B(Р) A1# (Р)A2# (Р)...An# (Р) ,
где Ai# есть естественное распространение Ai на А.
Теорему примем без доказательства. Доказательство см., например, в работе [21].
Разветвление алгоритмов. Пусть заданы алгоритмы A и B в алфавите А и задано некоторое условие U. Тогда можно задать предписание следующего типа: для данного слова Р в алфавите А проверить, удовлетворяет ли оно условию U, если удовлетворяет, то к Р применить алгоритм A , в противном случае применить к Р алгоритм B, см. Рис 6.2.
Ясно, что условие U можно задавать самым различным образом, например, можно задать так: условие U выполнимо для заданного слова Р, если P≠NP (см. главу о сложности вычислений). Решить, выполнимо это условие U или нет, в настоящее время нельзя, ибо указанная проблема еще не решена, несмотря на настойчивые попытки. Поэтому такого рода (типа) условия не будем рассматривать. Будем считать, что условие U всегда задано с помощью какого-то алгоритма C в алфавите А в следующем виде:
условие U для слова Р выполнено, если C(Р)=Λ,
условие U для слова Р не выполнено, если C(Р)≠Λ.
|
U выполненo |
P |
A(P) |
A |
|
|
Проверка |
|
условия U |
B(P)
188
U не выполнено
При таком задании условия U описанное выше предписание будем считать разветвлением алгоритмов в алфавите А. Точнее, пусть A, B и C- алгоритмы в алфавите А. Разветвлением алгоритмов A и B называется алгоритм V в А, не применимый к Р, если не применим к Р алгоритм С и такой, что`
( ) A(P), если С(P)= Λ
P в А:V P ( ) ( ) .
B P , если С P ≠ Λ
Будем говорить, что это разветвление алгоритмов управляется алгоритмом C .
Теорема 6.3. Разветвление нормальных алгоритмов, управляемое нормальным алгоритмом, является нормальным алгоритмом.
Примем без доказательства. Доказательство см., например, в работе [21]. Повторение алгоритмов. Во многих случаях требуется повторить одну и ту же процедуру многократно, каждый раз применяя ее к результату,
полученному на предыдущем шаге. Процедуру повторяем до выполнения некоторого условия U. Будем считать, что условие U задается с помощью алгоритма, как и выше. Такая процедура будет задавать повторение алгоритма. Более точно: пусть A и C - алгоритмы в алфавите А и пусть Ро - произвольное слово в А. Применим к Ро алгоритм A. Получим некоторое слово Р1=A(Ро), если С(Р1)=Λ, то процесс заканчивается. Если C(Р1)≠Λ, то к Р1 применяем A, получаем Р2=A(Р1)=A(A(Ро)). Если C(Р2)=Λ, то процесс заканчиваем. Если C(Р2)≠Λ, то к Р2 применяем A, и т.д. Определенный таким образом алгоритм называется повторением алгоритма A, управляемым алгоритмом C.
Повторение алгоритма можно представить следующей блок схемой, см.
Рис. 6.3.
P0 |
|
Pi=A(Pi-1) |
U выполнено |
|
A |
Проверка |
|||
|
|
|||
|
|
|
условия U |
|
|
|
U не выполнено |
|