close

Вход

Забыли?

вход по аккаунту

?

1642.Лекции по математической логике и теории алгоритмов Белов Ю А

код для вставкиСкачать
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
Ю. А. Белов
В. А. Соколов
Лекции по математической логике
и теории алгоритмов
Учебное пособие
Рекомендовано
Научно-методическим советом университета
для студентов, обучающихся по направлению
Фундаментальная информатика
и информационные технологии
Ярославль
ЯрГУ
2013
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
УДК 510.23:510.6(075.8)
ББК В12я73
Б43
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2013 года
Рецензенты:
Д. О. Бытев, доктор технических наук, профессор;
кафедра алгебры ЯГПУ им. К. Д. Ушинского
Белов, Ю. А. Лекции по математической логике
Б43
алгоритмов: учебное пособие / Ю. А. Белов,
В. А. Соколов; Яросл. гос. ун-т им. П. Г. Демидова.
Ярославль : ЯрГУ, 2013. 140 с.
и
теории
ISBN 978-5-8397-0908-9
Пособие посвящено основам математической логики и
теории алгоритмов. При этом исчисление высказываний
представлено достаточно полно, для исчисления предикатов
рассмотрены вопросы интерпретации, непротиворечивости
и неразрешимости, теория алгоритмов представлена материалами по вычислимым функциям, разрешимым и перечислимым множествам, рассмотрены неразрешимые алгоритмические проблемы. Раздел формальной арифметики
включает теорему Гјделя о неполноте.
Предназначено для студентов, обучающихся по направлению 010300.62 Фундаментальная информатика и информационные технологии (дисциплина ѕМатематическая логика и теория алгоритмовї, блок ЕН), очной формы обучения.
УДК 510.23:510.6(075.8)
ББК В12я73
ISBN 978-5-8397-0908-9
c ЯрГУ, 2013
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ОГЛАВЛЕНИЕ
Введение
1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Элементы математической логики
7
. . . . . . . . . . . . . .
8
. . . . . . . . . .
13
. . . . .
16
. . . .
24
. . . . . . . . . . . . . . . . . . . . . . . . .
26
. . . .
31
. . . . . . . . . . . . . . . . . . .
34
Глава
1.
Формальные теории
Глава
2.
Исчисление высказываний
Глава
3.
Выводимость. Теорема дедукции
Глава
4.
Доказуемость, истинность, полнота
Глава
5.
Непротиворечивость исчисления
высказываний
Глава
6.
Полнота исчисления высказываний
Задачи и упражнения I
Глава
7.
Логика предикатов. Аксиомы
и правила вывода
Глава
8.
. . . . . . . . . . . . . . . . . . . . . . .
9.
Глава
10.
. . . . . . . . . . . . . . . . . . . . . .
43
Логическое следование и равносильность
54
предикатов
Глава
38
Интерпретация формул
логики предикатов
Глава
5
11.
предикатов
Непротиворечивость исчисления
. . . . . . . . . . . . . . . . . . . . . . . . . . .
59
Неразрешимость и полнота исчисления
. . . . . . . . . . . . . . . . . . . . . . . . . . .
64
. . . . . . . . . . . . . . . . . .
69
. . . . . . . . . . . . . . . .
71
Задачи и упражнения II
Решения, указания, ответы
3
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
4
2.
ОГЛАВЛЕНИЕ
Элементы теории алгоритмов
79
.
80
. . . . . . . . . . . . . .
84
. . . . .
88
Глава
12.
Основные понятия теории алгоритмов
Глава
13.
Машина Тьюринга
Глава
14.
Частично-рекурсивные функции
Глава
15.
Машина с неограниченными регистрами
Глава
16.
MНР-вычислимость
. .
16.1. Соединение программ . . . . . . .
16.2. Реализация подстановки на МНР
16.3. Реализация рекурсии на МНР . .
16.4. Реализация минимизации на МНР
16.5. Основной результат . . . . . . . .
частично-рекурсивных функций
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
104
.
106
. . . . . . . . . . . . . . . . . . . . . . . . . . .
108
Глава
18.
Теорема о параметризации
Глава
19.
Универсальная вычислимая функция
Глава
20.
Разрешимые и перечислимые
21.
Глава
Неразрешимые алгоритмические
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.
23.
. . . . . . . . . . . . . .
формул.
120
Язык формальной арифметики.
Арифметические множества и функции
Глава
117
Теорема Райса.
Теорема о неподвижной точке
Глава
95
97
97
98
99
. . . . . . . . .
Нумерация вычислимых функций
проблемы
95
101
17.
Глава
.
.
.
.
.
.
. . . .
Глава
множества
.
.
.
.
.
.
92
24.
Геделева
нумерация
Теорема Тарского.
. . . . . . . .
125
арифметических
Первая теорема Геделя
. . . . . . . . . . . . . . . . . . . . . . . . . . 133
Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
о неполноте
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ВВЕДЕНИЕ
Пособие посвящено изложению начал математической логики и теории алгоритмов, между которыми имеются глубокие
связи.
Математическая логика и опирающийся на неј аксиоматический метод оказали большое влияние на развитие всех разделов
математики, в частности, и потому, что классическое исчисление
предикатов является той логической системой, на базе которой
можно, в принципе, формализовать всю математику.
Наличие формализованной системы какой-либо математической теории позволяет, в свою очередь, строго формулировать
алгоритмические проблемы разрешимости, относящиеся к данной теории.
Для логики предикатов А. Чјрч установил алгоритмическую
неразрешимость проблемы разрешения для множества всех истинных предложений, указав тем самым некоторые ограничения данного подхода. Это, наряду с другими результатами,
стимулировало исследования в данной области по преодолению
отмеченных ограничений и рассмотрению ситуаций в других
формальных аксиоматических теориях.
К настоящему времени существенные приложения теории
алгоритмов имеются фактически во всех областях математики,
где встречаются алгоритмические проблемы. Для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно
множества всех еј предложений. Все теории подразделяются на
разрешимые и неразрешимые в зависимости от разрешимости или неразрешимости указанной проблемы. Кроме того, для
каждой формальной теории имеются, и часто ещј до сих пор
ждут своего решения, другие алгоритмические проблемы.
Неразрешимые алгоритмические проблемы встречаются в
алгебре (проблема тождества слов для полугрупп и групп), в
теории чисел (проблема разрешимости диофантовых уравнений), в топологии и других математических теориях.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
6
Введение
Наоборот, разрешимой формальной теорией является, например, исчисление высказываний. Конечно, этот пример скорее
исключение, чем правило.
Для адекватных формулировок и тем более решений отмеченных проблем уже требуются понятия, результаты и методы
теории алгоритмов. При этом на понятие алгоритма опирается и
центральная категория математической логики формального
аксиоматического исчисления.
Кроме того, теория алгоритмов является основанием для
вычислительной математики и тесно связана с информатикой,
в которой важное место занимает изучение алгоритмов управления и обработки информации.
Данное пособие охватывает материал, включающий теорему
Гјделя о неполноте формальных систем, которая, в определјнном смысле, является следствием теории алгоритмов. Из теоремы Гјделя следует, что в любой непротиворечивой формальной
системе, содержащей некоторые минимальные арифметические
аксиомы, обязательно найдјтся формально неразрешимое суждение, то есть такая формула A, что ни A, ни ¬A не являются
выводимыми в системе.
Упомянутые вопросы являются фундаментальными для становления всей математической культуры и объективно непросты, поэтому авторы пособия стремились при изложении материала, по возможности, учитывать взаимно противоположные
факторы: желательную доступность и необходимую строгость
изложения на ограниченном пространстве учебного издания.
При отборе материала существенно использовались (с небольшими изменениями и дополнениями) соответствующие разделы
из учебного пособия [9] и конспекта лекций [7].
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Часть 1
ЭЛЕМЕНТЫ
МАТЕМАТИЧЕСКОЙ ЛОГИКИ
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
1
ФОРМАЛЬНЫЕ ТЕОРИИ
Очевидные соображения показывают важность уточнения
тех способов рассуждений, которые используются в математике.
Это важно для того, чтобы избежать противоречивых математических заключений, то есть важно для корректного построения
математических теорий.
Кроме этого, внутреннего, стимула изучения логики имеются
сильные внешние причины для ее изучения, одна из основных
проблема автоматизации логического вывода грубо говоря,
проблема построения программной системы автоматического
доказательства теорем математики. Автоматизированное получение правильных выводов из имеющихся условий (посылок)
важно также для различных диагностических систем в медицине, технике и вообще для систем искусственного интеллекта,
когда живого эксперта рядом нет, а действовать надо быстро:
например, время какой-либо аварии, несчастного случая и т. п.
В подобных ситуациях экспертная система может дать хотя бы
какие-то предупреждения или рекомендации.
Другими словами, эти разные доводы подталкивают к одной
мысли необходим формальный однозначный механизм получения правильных выводов из имеющихся посылок (условий).
При этом желательно, чтобы способы получения этих выводов
можно было легко реализовать программно. Во всяком случае,
необходима формальная модель логики. Математика занимается построением различных формальных моделей, то есть таких
описаний объекта исследований, в которых отсутствует недосказанность, возможность различных толкований получаемых
результатов и вообще вопросы истолкования не рассматриваются. Все математические теории строятся в принципе как аксиоматические системы, в которых точно описываются начальные (неопределяемые) понятия и начальные (не доказываемые)
утверждения аксиомы, остальные понятия строятся на основе
первоначальных, все утверждения соответственно выводятся из
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 1. Формальные теории
9
аксиом, хотя явно такая структура может быть иногда описана
не до конца.
Математическая логика логика, изучаемая математическими методами, другими словами, логика здесь излагается в
виде аксиоматической теории. Более того, будет дано изложение
логики в виде
аксиоматической теории, то есть
для изложения будет использован искусственный ограниченный
язык. Это облегчит программную реализацию логики и даст
(редкую) возможность показать пример аксиоматической системы в полном объеме, хотя бы для такой простой теории,
как исчисление высказываний. Мы начнем изучение логики с
рассмотрения
или
, то есть предложений, которым можно сопоставить одно из двух возможных
истину или ложь. Предполагаем,
что истинностных значений всего два, то есть рассматриваем
классическую бинарную логику, хотя имеются теории k -значных
логик при k > 2, а также причинные, временные и другие
типы неклассических логик, имеющие большое значение для
приложений.
Итак, высказывание это предложение, которому можно
приписать одно из двух возможных истинностных значений
истину или ложь. Примером высказываний могут служить
утверждения: ѕшесть делится на триї, ѕшесть делится на четыреї, первое истинное, второе ложное. Конечно, далеко
не каждое предложение языка является высказыванием, даже
если отбросить предложения вида ѕсегодня хорошая погодаї
и т. п., истинность или ложность которых оценивается субъективно. Всевозможные вопросы, инструкции или распоряжения типа ѕследующая лекция начнјтся в четырнадцать часовї
дают примеры осмысленных предложений, не являющихся высказываниями. Это просто распоряжение, не имеющее истинностного значения. Конечно, для нас в первую очередь интересны высказывания математического содержания, для них
истинность или ложность обычно абсолютна в силу формальноаксиоматического характера математических знаний. Еще и потому логика называется математической, что она ориентирована
на анализ математических теорий.
Мы будем рассматривать некоторый набор начальных (элементарных) высказываний, из которых будем строить более
формальной
высказываний
истинностных значений
суждений
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
10
Гл. 1. Формальные теории
сложные высказывания, используя для этого логические связки,
например которые были определены ранее (или другие подобные):
? если A, то B , или из A следует B ;
¬ не A, неверно, что A;
? или A или B (или оба);
? и A и B.
Иногда используется более компактная запись отрицания:
¬A = A. Ранее эти знаки могли считаться просто стенографическими знаками для сокращения записей, теперь они станут
элементами специального формализованного языка изложения
логики, поэтому их словесная формулировка не имеет особого
значения.
Несколько замечаний о языках. Примерами формальных
языков являются языки программирования, сетевые протоколы,
языки запросов и т. п., используемые в информатике, язык
арифметических выражений в математике и другие. Имеется
большая теория формальных языков, которой мы касаться не
будем, дадим только два первоначальных определения.
A назовем конечное непустое множество символов. Словом в данном алфавите называется конечная последовательность букв алфавита.
Языком над алфавитом A называется определенное множество слов в данном алфавите.
Например, над латинским алфавитом имеются два языка
французский и английский. В искусственных языках обычно
имеются точно определенные правила построения слов языка. Отметим еще, что здесь говорится о словах, а
не о предложениях языка, что кажется необычным, но в действительности это не очень существенно предложение тоже
можно считать словом, если в алфавит добавить знак пробела
и другие синтаксические знаки. А в иероглифических языках
последовательность нескольких иероглифов без всяких знаков
пробела и других разделителей часто является предложением.
Дадим определение
Формальной аксиоматической теорией F называется алфавит A, над которым построено некоторое множество
ѕправильныхї слов формул языка; среди формул выделено
некоторое подмножество формул, называемых аксиомами, и на
Алфавитом
матика
Определение.
грам-
формальной аксиоматической теории.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 1. Формальные теории
11
множестве формул задано некоторое конечное множество отношений, называемых
Отметим, что, по данному определению, формальная аксиоматическая теория есть язык, в котором определены аксиомы и
правила вывода.
В рамках нашего курса будут определены две формальные
аксиоматические теории, описывающие логику.
Пусть f1 , f2 , . . . fn , fn+1 формулы теории F и среди правил
вывода есть такое отношение G, что (f1 , f2 , . . . fn , fn+1 ) ? G.
Тогда говорят, что fn+1 является
набора формул f1 , f2 , . . . fn по правилу вывода G. Формулы
f1 , f2 , . . . fn называют
, или
, формулу fn+1
.
Последовательность формул g1 , g2 , . . . gn называется
, если каждая формула в
этой последовательности является или аксиомой, или непосредственным следствием некоторых предыдущих формул.
Формула g называется
, или
, если существует формальное доказательство, заканчивающееся этой формулой.
Обозначается это так: ` g и читается ѕформула g доказуемаї.
В любой математической теории теоремы обычно не выводятся непосредственно из аксиом, так как это очень громоздко.
Теоремы выводятся из некоторых условий, которые, в свою
очередь, могут выводиться из предыдущих утверждений, те аналогично и так далее. Такое последовательное развитие теории наиболее естественно. Аналогично при изучении формальной теории определим понятие
обобщающее
понятие формального доказательства.
Пусть имеется произвольный набор формул
G = {g1 , g2 , . . . gm }, называемый посылками, или условиями, и
формула h. Говорят, что формула h выводится из набора условий G, и это обозначается так: G ` h, если существует конечная
последовательность формул h1 , h2 , . . . hn , такая, что каждая hk
является или аксиомой, или одним из условий из набора G, или
непосредственным следствием предыдущих формул по одному
из правил вывода и hn = h.
правилами вывода.
непосредственным следствием
условиями посылками
заключением
Определение.
формальным доказательством
мой
доказуемой
формальной теоре-
вывода из условий,
Определение.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
12
Гл. 1. Формальные теории
Конечно, приведенное определение совпадает с понятием
формального доказательства при G = ?; понятие непосредственного следствия тоже является простейшим частным случаем
вывода из условий.
Цель изучения конкретной формальной аксиоматической
теории описание класса доказуемых формул теории, разработка (по возможности) алгоритмов построения формальных
доказательств.
Изучение будет проходить в обычной неформальной манере,
как и в других математических теориях, с помощью обычных
неформализованных рассуждений будут устанавливаться какието утверждения о формальной теории. Например, вполне может
быть доказана (неформальная) теорема о том, что какая-то
формула является формальной теоремой. Эта ѕтеорема о теоремеї не должна удивлять. По сути эта теорема утверждает, что
в нашей формальной теории можно построить последовательность формул определенного вида. Надо только ясно различать
объект изучения формальную теорию и те обыкновенные
доводы, которые используются при этом изучении. Примером
простейшей (неформальной) теоремы, справедливой для любой
формальной теории, может быть теорема о транзитивности выводимости.
Пусть G = {g , g , . . . gm} набор условий, из
которого выводятся формулы h , h , . . . hl : G ` h , G ` h , . . .
... G ` hl , а из набора H = {h , h , . . . hl } выводится формула
s: H ` s. Тогда из набора G выводится формула s: G ` s.
Т е о р е м а 1.1.
1
2
1
1
2
1
2
2
Д о к а з а т е л ь с т в о. Надо доказать, что существует последовательность формул, каждая из которых является или аксиомой,
или одним из условий из G, или непосредственным следствием
предыдущих формул, заканчивающаяся на формуле s. Для построения такой последовательности выпишем подряд все выводы формул h1 , h2 , . . . hl из G, существующие по условиям теоремы, и припишем затем к получившейся последовательности
вывод s из H . Получим последовательность, заканчивающуюся
на формуле s, использующую наряду с аксиомами условия G
для выводов hi и в последней части условия из H . Однако
в этой объединенной последовательности условия из H уже
выведены из набора G, и потому теорема доказана.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
2
ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
В предыдущей главе было дано общее определение формальной аксиоматической теории. Сейчас будет дано определение
конкретной формальной теории исчисления высказываний (ИВ). Определим для этого необходимые элементы определения
формальной теории: алфавит, формулы, аксиомы, правила вывода.
Алфавит: прописные буквы латинского алфавита A, B , . . .
. . . Z или буквы с индексами A, A1 , Bk , C . . . (чтобы иметь
неограниченный набор символов), называемые
; логические связки ?, ?, ¬, ?, скобки (,).
Формулы:
1. Все пропозициональные буквы есть формулы.
2. Если A и B формулы, то следующие слова также являются формулами: (A ? B), (A ? B), (¬A), (A ? B).
Аксиомы:
ными буквами
Введение логических связок
1. A ? (B ? A)
? (A ? C))
3. A ? (B ? A ? B)
5. A ? B ? B
6. A ? A ? B 7. B ? A ? B
9. (A ? B) ? ((A ? B) ? A)
пропозициональ-
Удаление логических связок
2. (A ? B)
? ((A ? (B ? C))
4. A ? B ? A
8. (A ? C) ? ((B ? C)
? (A ? B ? C))
10. A ? A
Правило вывода:
Для любых формул X и Y тройка формул вида X , X ? Y , Y
находится в отношении непосредственной выводимости, Y называется непосредственным следствием двух предыдущих формул
согласно данному правилу вывода.
Само правило вывода называется MP (Modus Ponens ѕправило удаленияї). Теперь все элементы определения ИВ изложены и необходимо сделать несколько поясняющих замечаний.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
14
Гл. 2. Исчисление высказываний
Во-первых, данная теория называется исчислением высказываний потому, что при ее применении каждой пропозициональной букве сопоставляется определенное
высказывание из какой-то области математики, а логические связки
позволяют строить из этих элементарных высказываний другие
высказывания. Пусть, например, имеется два элементарных высказывания арифметического характера: ѕ57462916286 делится
на 49ї и ѕ57462916286 делится на 7ї; первое высказывание
обозначим через A, второе через B . Используя связку ?,
можно получить два новых высказывания: A ? B и B ? A,
первое из которых, видимо, истинно, а второе не так очевидно,
хотя тоже истинно. Вообще вопросы истинности формул тоже
требуют своего точного определения, что будет обсуждаться
позднее. Читать же приведенные формулы можно, например,
так: ѕиз A следует B ї или ѕесли A, то B ї; условимся только не
использовать термин ѕвыводитсяї, для которого есть строгое
определение в теории. Для развития формальной теории форма
чтения вообще не важна, важны лишь правила действия с формулами.
Логические связки ИВ имеют свои формальные названия:
? импликация,
? конъюнкция,
? дизъюнкция,
¬ отрицание.
Скобки в алфавите ИВ нужны для определения области
действия каждой связки в формуле. Условимся не выписывать
все скобки, требующиеся по построению формулы, что фактически мы уже и делали, когда давали список аксиом и примеры.
Считаем при этом, что отрицание имеет наименьшую область
действия, дизъюнкция и конъюнкция одного ранга и потому
всегда требуют поясняющих скобок, импликация имеет наибольший ранг. Например, A?¬B ? C в полной записи выглядит так:
((A ? (¬B)) ? C).
Отметим еще, что в определении формул, аксиом и правила вывода использовались буквы в каллиграфическом (закругленном) шрифте условимся, что элементы алфавита ИВ пропозициональные буквы прямые латинские, а каллиграфическими буквами обозначаются произвольные формулы ИВ.
Заметим еще, что индексы при буквах, строго говоря, в алфавит
элементарное
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 2. Исчисление высказываний
15
не входят, но у нас используются. Можно было бы включить в
алфавит еще и десятичные цифры и использовать индексы ѕна
законных основанияхї. Тогда пришлось бы точно определить,
что пропозициональный символ это буква или буква с индексом, а индекс есть последовательность цифр.
Это означает, что, строго говоря, аксиом бесконечное множество, а в данном списке приведены лишь
аксиом их
всего десять. Конкретные аксиомы получаются из схем подстановкой вместо каллиграфических букв произвольных формул
теории: например, C ? D ? (A ? C ? D) частный случай
первой аксиомы, получающийся, если в качестве A взять C ? D,
в качестве B взять A.
Все аксиомы (схемы) разбиты на два класса так называемые аксиомы введения и удаления связок. Две первые введение и удаление импликации, третья, четвертая и пятая
введение и две аксиомы удаления конъюнкции, шестая и
седьмая аксиомы введение дизъюнкции, восьмая удаление
дизъюнкции, девятая и десятая введение и удаление отрицания. Эти названия аксиом мы будем использовать при ссылках.
В аксиомах данная связка вводится или удаляется из заключения; напомним, что в импликации тоже есть условие и
заключение.
схемы
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
3
ВЫВОДИМОСТЬ. ТЕОРЕМА ДЕДУКЦИИ
Дадим несколько примеров формальных доказательств и
выводов из условий в теории ИВ. По определению это некоторые
последовательности формул. Пример:
1. A ? (A ? A)
; введение импликации
2. (A ? (A ? A)) ?
; удал. импл.
((A ? ((A ? A) ? A)) ? (A ? A))
3. ((A ? ((A ? A) ? A)) ? (A ? A)) ; МР 1, 2
4. A ? ((A ? A) ? A)
; введ. имп.
5. A ? A
; МР 4, 3.
Здесь дан простейший пример формального доказательства
или вывода из аксиом. Все формулы последовательности являются или частными случаями аксиом, или следствиями предыдущих формул по правилу МР, о чем говорят
,
расположенные в строке после точки с запятой. Комментарии
являются необходимым элементом обоснования того, что данная
последовательность является доказательством.
Отметим, что вместо формул в доказательстве можно было
бы иметь в виду аналогичные схемы формул, получилась бы
схема доказательства, пригодная для подстановки в нее вместо
символов определенных формул и получения конкретного доказательства, например доказательства формулы C ? D ? C ? D.
Доказанная формула A ? A весьма примитивна, но это первая формула, доказанная в данной формальной теории; первые
теоремы в геометрии тоже кажутся вначале совершенно тривиальными, хотя впоследствии видно, что они используются (явно
или неявно) очень часто. Приведенное доказательство также
будет использовано в дальнейшем в важной теореме.
Покажем, что A?B ` B ?A, то есть покажем, что из условия
A?B
формула B ? A.
комментарии
выводится
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 3. Выводимость. Теорема дедукции
1.
2.
3.
4.
5.
6.
7.
8.
A?B
A?B ?A
A?B ?B
A
B
B ? (A ? B ? A)
A?B?A
B?A
;
;
;
;
;
;
;
;
17
условие
?-удаление
?-удаление
МР 1, 2
МР 1, 3
?-введение
МР 5, 6
МР 4, 7
Решение этого примера аналогично предыдущему: вторая,
третья и шестая строки аксиомы, первая условие, остальные
являются следствиями предыдущих формул по правилу МР.
Отметим, что формальный вывод может строиться неоднозначно: например, можно поменять первые три строчки местами
или сто раз внести в вывод запись одной и той же аксиомы снова получим правильный вывод. Другими словами, существует актуальная проблема получения кратчайшего вывода или
доказательства. При этом длина вывода, например, количество
строчек в нем или другой разумный параметр.
Здесь ярко проявляется достоинство формальной теории возможность точно определить понятие сложности доказательства, описать которое без подходящей формализации весьма
трудно.
Еще пример вывода.
Л е м м а 3.1 (о транзитивности импликации).
A ? B , B ? C ` A ? C.
Д о к а з а т е л ь с т в о.
1. (B ? C) ? (A ? (B ? C))
2. B ? C
3. A ? (B ? C)
4. A ? B
5. (A ? B) ? ((A ? (B ? C)) ? (A ? C))
6. (A ? (B ? C)) ? (A ? C)
7. A ? C
;
;
;
;
;
;
;
?-введение
условие 2
МР 2, 1
условие 1
?-удаление
МР 4, 5
МР 3, 6
Из этих примеров видно, что непосредственное построение формальных выводов весьма громоздко и вообще бесперспективно,
так как ясно, что существуют формулы, кратчайшее доказательство которых может быть как угодно длинно. Это означает, что
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
18
Гл. 3. Выводимость. Теорема дедукции
надо разработать методы доказательства существования вывода
данной формулы из условий (или только из аксиом), которые не
приводили бы к необходимости выписывания всего формального
доказательства в явном виде только на этом пути можно получить какой-либо критерий, позволяющий для любой формулы
ответить на вопрос доказуема она или нет.
Далее начнјтся разработка таких методов.
Первой теоремой, помогающей установить выводимость
какой-либо формулы без явного выписывания полного вывода,
является теорема о дедукции. С ее помощью в дальнейшем
будут получены другие способы установления выводимости.
Т е о р е м а 3.1 (о дедукции). Пусть G произвольный набор
формул ИВ, A, B две формулы.
Тогда если G , A ` B, то G ` A ? B.
Д о к а з а т е л ь с т в о. Требуется доказать, что если существует
вывод B из соответствующих условий, то можно построить и
другой вывод формулы A ? B. В теореме будет дан способ
преобразования первого вывода во второй. Сначала ко всем
формулам имеющегося вывода припишем слева символы A ?:
B
C1
A ? C1
C2
A ? C2
..
..
.
.
вывод
преобразованная последовательность
Cn
A ? Cn
B
A?B
Преобразованная последовательность формул не является
выводом, но заканчивается той формулой, которая требуется в
теореме. Перед каждой формулой в полученной последовательности будем вписывать несколько формул так, что после этих
вставок получится требуемый вывод. Рассмотрим k-ю формулу
в последовательности: A ? Ck . По определению вывода B могут
быть такие случаи: Ck аксиома , Ck ? G , Ck = A, Ck следствие по правилу МР двух предыдущих формул Ci и Cj .
Рассмотрим последовательно все случаи.
Пусть Ck аксиома.
Тогда перед формулой A ? Ck впишем две формулы:
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 3. Выводимость. Теорема дедукции
19
..
..
.
.
Ck
; аксиома
Ck ? (A ? Ck ) ; ?-введение
Тогда следующая за ними формула A ? Ck является непосредственным выводом из двух предыдущих формул:
..
..
.
.
; аксиома
; ?-введение
; МР s, s + 1,
где s номер Ck в строящемся выводе.
Пусть Ck некоторое условие из G . Впишем перед разбираемой формулой те же две формулы, что и в предыдущем случае,
только изменим комментарий к формуле Ck . Снова получим,
что текущая формула A ? Ck выведена из G .
Если Ck = A, впишем перед ней доказательство формулы
A ? A, полученное в предыдущей главе.
Последний случай Ck следствие предыдущих формул
Ci и Cj по правилу МР. Тогда эти формулы имеют вид:
Ci = X , Cj = X ? Y , Ck = Y , и в преобразованной
последовательности имеются следующие формулы:
..
.
Ck
Ck ? (A ? Ck )
A ? Ck
p.
A?X
..
.
q.
A ? (X ? Y )
..
.
r.
A?Y
Впишем две строки перед рассматриваемой формулой A ? Y :
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
20
Гл. 3. Выводимость. Теорема дедукции
..
.
..
.
..
p. A ? X
.
..
..
.
.
..
q. A ? (X ? Y )
.
..
..
.
.
r. (A ? X) ? ((A ? (X ? Y )) ? (A ? Y )) ; ?-удаление
r+1. (A ? (X ? Y )) ? (A ? Y )
; МР p, r
r+2. A ? Y
; МР q, r+1.
Таким образом, получаем окончательную последовательность, являющуюся требуемым выводом формулы A ? B .
Отметим, что вывод формулы A ? B , строящийся в теореме, примерно в три раза длиннее исходного вывода формулы B . В этом проявляется смысл теоремы: имея короткий вывод,
можно утверждать, что существует более длинный и сложный
вывод. При этом теорема дает даже алгоритм построения нового
вывода его построение вполне может быть автоматизировано,
хотя, конечно, вывод, построенный при помощи теоремы, не
всегда оптимальный. Отметим, что теорема, обратная теореме
о дедукции, справедлива и тривиальна:
если G ` A ? B , то G , A ` B.
Для доказательства к имеющемуся выводу импликации
A ? B надо приписать A и B : A как новое условие и B как
следствие этого условия и импликации.
Приведем пример использования теоремы о дедукции. Сначала отметим, что теорема о транзитивности выводимости, доказанная для любой формальной теории, справедлива и для ИВ.
Укажем еще два простейших замечания о выводимости: F ` F
для любой формулы F и если H ` F и H ? G , то G ` F.
Докажем снова лемму о транзитивности импликации:
A ? B , B ? C ` A ? C.
1. A, A ? B , B ? C ` B
; МР усл. 1, 2
2. A, A ? B , B ? C ` B ? C ; тождест.
3. B , B ? C ` C
; МР
4. A, A ? B , B ? C ` C
; т.транз. 1, 2, 3
5. A ? B , B ? C ` A ? C
; т.дедук. 4.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 3. Выводимость. Теорема дедукции
21
Отметим, что здесь имеется не последовательность формул,
а последовательность утверждений о существовании каких-то
выводов, комментарии обосновывают эти утверждения. Например, в четвертой строке используется теорема о транзитивности
выводимости, так как в первой и второй строках из одного и
того же набора условий выводятся две формулы, а в третьей
строке из полученных двух формул выводится еще одна, это
соответствует условиям теоремы.
В подобном стиле будут оформляться утверждения о существовании выводимостей и в дальнейшем.
Предыдущий пример применения теоремы о дедукции совсем простой и не соответствует сложности теоремы. Сейчас
будет дано более важное применение теоремы о дедукции.
Т е о р е м а 3.2 (о введении и удалении логических связок).
G
A, B , C
Пусть произвольный список условий,
формулы.
Тогда справедливы следующие утверждения:
Введения
Удаления
1. Если G , A ` B, то G ` A ? B 2. A, A ? B ` B
3. A, B ` A ? B
4. A ? B ` A, 5. A ? B ` B
6. A ` A ? B, 7. B ` A ? B 8. Если G , A ` C и G , B ` C ,
то G , A ? B ` C
9. Если G , A ` B
10. ¬¬A ` A.
и G , A ` ¬B, то G ` ¬A
Д о к а з а т е л ь с т в о. 1 теорема о дедукции, 2 МР, 37 очевидные следствия соответствующих аксиом. Вот, к примеру,
доказательство пункта 3.
1. A
; 1 условие
2. B
; 2 условие
3. A ? (B ? A ? B) ; ?-введение
4. B ? A ? B
; МР 1, 3
5 A?B
; МР 2, 4.
Аналогично тривиально доказываются пункты 47 и 10.
Докажем утверждение 8. Применяя теорему дедукции к
условиям, получаем: G ` A ? C , G ` B ? C . Тогда тем более:
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
22
Гл. 3. Выводимость. Теорема дедукции
1. G , A ? B ` A ? C
; Т. Д. усл. 1
2. G , A ? B ` B ? C
; Т. Д. усл. 2
3. G , A ? B ` A ? B
; тождеств.
4. A ? C , B ? C , A ? B ` C ; ?-введение и три раза МР
5. G , A ? B ` C
; Т. Тр. 1, 2, 3, 4.
Строго говоря, четвертая строка требует своего доказательства,
но оно очевидно и потому пропущено. Таким же образом
доказывается пункт 9:
1. G ` A ? B
; Т. Д. 1-условие
2. G ` A ? ¬B
; Т. Д. 2-условие
3. A ? B , A ? ¬B ` ¬A ; ¬-введение и дважды МР
4. G ` ¬A
; Т. Т. 1, 2, 3
Фактически доказанная теорема переводит аксиомы на более
привычный язык выводимости. Девятое правило схема рассуждения ѕот противногої, восьмое способ доказательства
разбором случаев, другие правила тоже не противоречат интуитивным представлениям, но теперь это строго доказанные
свойства формальной теории.
Дадим примеры применения полученных правил.
Л е м м а 3.2 (о противоречии).
A, ¬A ` B.
Д о к а з а т е л ь с т в о.
1.
2.
3.
4.
5.
A, ¬A, ¬B ` A
A, ¬A, ¬B ` ¬A
A, ¬A, ` ¬¬B
¬¬B ` B
A, ¬A ` B
;
;
;
;
;
тожд.
тожд.
¬-введение 1, 2
¬-удаление
Т. Т. 3, 4
Отметим, что третья строка прокомментирована как введение
отрицания, это название соответствующей аксиомы, но теперь
это и название одного из правил последней теоремы правила
9, ссылка была на это правило. Аналогичное замечание для
следующей строки. Вообще теперь оборот ѕвведение/удаление
логических связокї является как названием аксиомы, так и
названием соответствующего этой аксиоме правила вывода; это
не очень удобно, но не должно приводить к непониманию.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 3. Выводимость. Теорема дедукции
Л е м м а 3.3 (о противоположной теореме).
G
A, B
G, A ` B
G , ¬B ` ¬A.
Пусть произвольный список условий,
Тогда если
, то
23
формулы.
Д о к а з а т е л ь с т в о.
1.
2.
3.
4.
5.
6.
7.
A ? B , A, ¬B ` B
A ? B , A, ¬B ` ¬B
A ? B , ¬B ` ¬A
A ? B ` ¬B ? ¬A
G`A?B
G ` ¬B ? ¬A
G , ¬B ` ¬A
;
;
;
;
;
;
;
МР 2, 1 условия
тожд.
¬-введение 1, 2
Т. Д. 3
Т. Д. условие леммы
Т. Т. 5, 4
ѕобратная Т. Д.ї 6.
Теперь основные свойства выводимости установлены. Отметим,
что получить явный вывод, дающийся, например, в лемме о
противоречии, уже довольно трудно.
Напомним, основная задача изучения ИВ, как и любой математической теории, описание класса формальных теорем.
В связи с этим подумаем, что утверждается в лемме о противоречии. Лемма утверждает, что если получено противоречие,
то доказуема любая формула и вопрос описания класса выводимых формул решается тривиально все формулы выводимы,
но, конечно, рассмотрение противоречивых теорий неинтересно.
Таким образом, возникает проблема доказательства непротиворечивости нашей теории.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
4
ДОКАЗУЕМОСТЬ, ИСТИННОСТЬ, ПОЛНОТА
Как отмечалось ранее, для содержательного изучения теории необходимо убедиться в ее непротиворечивости.
Формальная аксиоматическая теория будет называется
если ни для какой формулы F не может быть одновременно доказуема F и ¬F . Это
свойство теории называют еще непротиворечивостью в узком
смысле.
Другими словами, для любой формулы F хотя бы одно из
следующих утверждений неверно: ` F или ` ¬F .
Если рассматривать формальную аксиоматическую теорию,
в которой отсутствует символ отрицания (а такие теории изучаются), то теорию следует назвать непротиворечивой, если в
теории существуют недоказуемые формулы; по крайней мере,
для ИВ это определение совпадает с предыдущим, как следует
из леммы о противоречии.
План доказательства непротиворечивости ИВ таков: зададим некоторый способ, сопоставляющий каждой формуле определенную функцию. При этом доказуемым формулам окажутся
сопоставленными функции-константы; уже отсюда будет ясно,
что не все формулы доказуемы, и, значит, в силу леммы о
противоречии, теория непротиворечива.
Пусть F2 = {0, 1} множество из двух элементов, F2n декартова степень, F2 множество соответствующих
(0,1)-векторов, содержащее 2n элементов.
фукцией от n неизвестных называется
отображение f : F2n ? F2 .
Попросту сказать, функция y = f (x1 , x2 , . . . xn ) называется
булевой (логической), если переменные xi и сама функция y
принимают только два значения 0 и 1. Всякая логическая
функция может быть задана конечной таблицей значений (таблицей истинности), содержащей 2n строк.
Теперь сопоставим каждой логической связке следующие
булевы функции:
Определение.
внутренне непротиворечивой,
Определение.
Логической (булевой)
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 4. Доказуемость, истинность, полнота
x
0
0
1
1
y
0
1
0
1
x?y
0
0
0
1
x
0
0
1
1
y
0
1
0
1
x?y
0
1
1
1
x
0
0
1
1
y
0
1
0
1
x?y
1
1
0
1
25
x
0
1
¬x
1
0
Пусть теперь A произвольная формула ИВ. Всем пропозициональным буквам, входящим в A, сопоставим булевы переменные из F2 . Тогда формуле A однозначно соответствует булева
функция, значение которой на произвольном наборе значений
переменных вычисляется согласно определению формулы. Если,
например, A = B?C , то можно считать (индукция по количеству
логических связок), что значения формул B и C уже вычислены,
и для вычисления значения A используем таблицу для конъюнкции; для других логических связок вычисления аналогичны.
Отметим, что функции, сопоставленные логическим связкам, соответствуют интуитивным представлениям об истинности и ложности связок, если считать, что 0 соответствует лжи,
1 истине.
. Формула A исчисления высказываний называется
, или тождественно истинной, если соответствующая ей булева функция тождественно равна 1. Это
обозначается так: |= A.
Другими словами, при любом наборе значений входящих
в формулу пропозициональных букв значение самой формулы
равно 1.
Определение
тавтологией
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
5
НЕПРОТИВОРЕЧИВОСТЬ ИСЧИСЛЕНИЯ
ВЫСКАЗЫВАНИЙ
Непротиворечивость ИВ следует из теоремы:
Т е о р е м а 5.1. Если формула F исчисления высказываний доказуема, то она тождественно истинна. С использованием
сокращенных обозначений: если ` F , то |= F .
Д о к а з а т е л ь с т в о. Можно проверить, что все аксиомы тождественно истинны. Отметим при этом, что если схема аксиом
задает тождественно истинную функцию от входящих в нее
букв, то и частный случай аксиомы, получающийся подстановкой вместо букв произвольных формул, также будет тождественно истинной формулой.
Второй факт непосредственное следствие по правилу МР
двух тождественно истинных формул тождественно истинно,
то есть если |= A и |= A ? B , то и |= B . Действительно,
согласно таблице для импликации, если истинны условие и сама
импликация, это соответствует четвертой строке, в которой и
заключение истинно.
Очевидно, что из этих двух фактов и определения формального доказательства следует, что все формулы любого формального доказательства являются тавтологиями.
Говорят, что теорема 5.1 устанавливает свойство непротиворечивости относительно тождественной истинности.
Отсюда легко следует непротиворечивость теории.
Т е о р е м а 5.2.
Теория ИВ внутренне непротиворечива.
Д о к а з а т е л ь с т в о. По определению непротиворечивости надо доказать, что для всякой формулы F хотя бы одно утверждение не выполнено: ` F или ` ¬F . Действительно, если F не
является доказуемой все в порядке; пусть F доказуема. Тогда
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 5. Непротиворечивость исчисления высказываний
27
F тавтология в силу теоремы 5.1. Тогда ¬F тождественно
ложна и потому не доказуема
Сопоставление формулам булевых функций позволило сформулировать отличительное свойство доказуемых формул они
все являются тавтологиями, на этом основывалось доказательство непротиворечивости. Как отмечалось, непротиворечивость
ИВ означет, что не все формулы выводимы из аксиом. В связи с
этим имеет смысл рассмотреть следующий вопрос: нельзя ли
расширить систему аксиом так, чтобы расширенная система
оставалась непротиворечивой? Другими словами, если взять
какую-либо невыводимую схему и добавить ее к списку аксиом,
будет ли полученная теория противоречивой? В связи с этим
Непротиворечивая формальная аксиоматическая теория называется
, если добавление к
ее системе аксиом любой недоказуемой схемы нарушает внутреннюю непротиворечивость теории. Это свойство называется
еще полнотой в узком смысле.
Можно понять, что в применении к ИВ это определение
тесно связано с вопросом, все ли тавтологии доказуемы.
Дальнейшие рассмотрения направлены на установление полноты ИВ; попутно будет получено описание класса формальных
теорем ИВ.
Определение.
внутренне полной
Л е м м а 5.1 (о связи таблиц истинности и выводимости).
?, ?, ?, ¬
Для четырех основных логических связок
с каждой
строкой соответствующей таблицы истинности связано
отношение выводимости по следующему правилу: из букв или
их отрицаний выводима формула или ее отрицание; при этом
берется отрицание буквы, если она входит в данную строку
со значением 0, берется сама буква, если ее значение в строке
1, берется отрицание формулы, если ее значение в данной
строке 0, сама формула, если значение 1. Например, для
конъюнкции:
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
28
Гл. 5. Непротиворечивость исчисления высказываний
X
Y
X ?Y
0 0 0
¬X , ¬Y ` ¬(X ? Y )
0 1 0
¬X , Y ` ¬(X ? Y )
1 0 0
X , ¬Y ` ¬(X ? Y )
1 1 1
X, Y ` X ? Y
Подобные соотношения выводимости имеются для каждой
строки каждой связки всего 14 утверждений выводимости.
Д о к а з а т е л ь с т в о. Рассмотрим выписанные соотношения
для конъюнкции. Очевидно, что
1. X ? Y ` X
; удаление конъюнкции
2. ¬X ` ¬(X ? Y ) ; л. противопол. теор. 1,
откуда следует первая строка таблицы. Вторая и третья
то же самое, четвертая введение конъюнкции. Большинство других утверждений тоже доказывается просто, поэтому
докажем только соотношение, соответствующее первой строке
таблицы дизъюнкции, то есть докажем, что ¬X , ¬Y ` ¬(X ? Y ).
1. ¬X , ¬Y , X ` ¬(X ? Y )
; л. о противор.
2. ¬X , ¬Y , Y ` ¬(X ? Y )
; л. о противор.
3. ¬X , ¬Y , X ? Y ` ¬(X ? Y ) ; удаление дизъюнкции 1, 2
4. ¬X , ¬Y , X ? Y ` X ? Y
; тождеств.
5. ¬X , ¬Y ` ¬(X ? Y )
; введение отрицания 3, 4
Т е о р е м а 5.3 (о связи таблиц истинности и выводимости).
F
F = F(X? , X? , . . . Xn )
2n
Пусть
произвольная формула ИВ, включающая n
пропозициональных символов:
. Тогда
существует отношений выводимости, соответствующих
каждой строке таблицы значений данной формулы по
правилам, описанным в предыдущей лемме.
Д о к а з а т е л ь с т в о. Проведем индукцию по количеству k логических связок, использованных в формуле. При k = 1 все
следует из леммы; пусть k > 1. Тогда по правилам построения
формулы можно считать, что, например, F = G ? H, где ? последняя логическая связка, использованная в F . Для других
связок рассуждения аналогичны. Тогда G и H имеют меньше
k логических связок. Рассмотрим теперь произвольную строку
значений из таблицы F . По этой строке строится набор букв
Xi или их отрицаний. Формулы G и H можно без ограничения
общности считать зависящими от того же набора переменных,
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 5. Непротиворечивость исчисления высказываний
29
что и сама формула F , и по предположению индукции они
или их отрицания выводятся из описанного набора букв Xi или
отрицаний. Но значение F на выбранной строке определяется
значениями G и H, и в силу леммы F или отрицание F выводится из букв G и H или отрицаний. Тогда в силу теоремы
транзитивности F или отрицание F выводится из описанного
набора Xi или их отрицаний.
Следствие 5.1 Тавтология F = F(X? , X? , . . . Xn ) выводится
из набора букв Xi или их отрицаний, построенного по произвольному (0,1)-вектору длины n.
Если бы удалось исключить эти наборы условий, получилась
бы теорема о доказуемости любой тавтологии. Это действительно можно сделать.
Л е м м а 5.2 (о законе исключенного третьего).
` A ? ¬A
.
Д о к а з а т е л ь с т в о.
1.
2.
3.
4.
5.
6.
X ` ¬X ? X
¬(¬X ? X) ` ¬X
¬X ` ¬X ? X
¬(¬X ? X) ` ¬¬X
` ¬¬(¬X ? X)
` ¬X ? X
;
;
;
;
;
;
?-введение
лемма о против. т. 5.1
?-введение
Л. П. т. 5.3
¬-введение 2, 4
¬-удаление 5
Т е о р е м а 5.4 (о полноте относительно тавтологий).
F
|= F
` F.
Для любой формулы ИВ если
, то
Д о к а з а т е л ь с т в о. Пусть F содержит только два пропозициональных символа: F = F(X , Y ). Рассуждения в общем случае
аналогичны. В силу следствия 1 справедливы следующие отношения выводимости:
1. ¬X , ¬Y ` F
2. ¬X , Y ` F
3. X , ¬Y ` F
4. X , Y ` F .
Из первых двух строк заключаем по правилу удаления дизъюнкции:
5. ¬X , Y ? ¬Y ` F .
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
30
Гл. 5. Непротиворечивость исчисления высказываний
Из третьей и четвертой строки аналогично:
6. X , Y ? ¬Y ` F .
Теперь из строк 5 и 6 снова применяем правило удаления
дизъюнкции:
7. X ? ¬X , Y ? ¬Y ` F .
По лемме о законе исключенного третьего ` A?¬A . Тогда по
теореме транзитивности выводимости получаем окончательно:
8. ` F .
Суть этой теоремы совершенно очевидна: если какая-то формула доказывается и при выполнении условия X и при его
невыполнении, а остальные условия при этом неизменны, то
условие X не играет никакой роли и его можно исключить.
В общем случае n переменных происходит такое же попарное
взаимное уничтожение условий.
Отметим, что теорема о дедукции, о десяти правилах и все
последующие доказаны
, то есть в этих теоремах
не просто доказывалось существование выводов, но и давались
алгоритмы их построения. Например, можно написать программу (и это сделано), которая по любой тавтологии построит ее
вывод из аксиом.
Отметим одно следствие теоремы 5.4. Можно дать критерий
выводимости формулы из набора условий:
Следствие 5.2
F
G 1 , . . . Gn
(G1 ? (G2 ? (G3 . . . (Gn ? F ))...)
конструктивно
вий
Формула выводится из набора услотогда и только тогда, когда формула
тождественно истинна.
Д о к а з а т е л ь с т в о. Согласно теореме о дедукции: G1 , G2 , . . .
. . . Gn ` F тогда и только тогда, когда ` (G1 ? (G2 ? (G3 . . .
. . . (Gn ? F ))...), после чего применима теорема 5.4.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
6
ПОЛНОТА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
Теперь получено полное описание класса формальных теорем ИВ.
Т е о р е м а 6.1. Произвольная формула F исчисления высказываний доказуема тогда и только тогда, когда она тождественно истинна.
Д о к а з а т е л ь с т в о. Следствие теорем 5.1 и 5.4.
Таким образом, в исчислении высказываний имеется алгоритм
распознавания выводимости данной формулы очень простой:
надо построить таблицу значений формулы и посмотреть, все
значения равны 1 или нет. Такие теории называются
. Но в исчислении высказываний имеется, как отмечалось
ранее, даже алгоритм построения самого доказательства, хотя
и весьма сложный. Отметим, что не для всякой разрешимой
теории имеется алгоритм построения вывода, другими словами,
про формулу можно знать, что она выводима, но как построить
вывод неизвестно. Но для ИВ такое невозможно, для нее
выполнены все ѕхорошиеї свойства. Одно из важных свойств
еще не доказано.
мыми
Т е о р е м а 6.2.
разреши-
Исчисление высказываний внутренне полно.
Д о к а з а т е л ь с т в о. Требуется доказать, что добавление
любой недоказуемой формулы в качестве схемы к системе
аксиом нарушает непротиворечивость. Пусть F(X? , X? , . . . Xn )
некоторая недоказуемая формула, добавленная к списку аксиом.
В силу недоказуемости формула F не тавтология. Согласно т.
5.4. на некотором наборе значений (X1 , . . . Xn ) значение F равно
0. Зададим следующие формулы: Zi = (Y ? Y ), если значение
Xi на выбранной строке равно 1, и Zi = ¬(Y ? Y ), если
значение Xi равно 0, и рассмотрим формулу: F(Z? , Z? , . . .
. . . Zn ). Эта формула содержит один пропозициональный
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
32
Гл. 6. Полнота исчисления высказываний
символ Y и тожественно ложна. Действительно, напомним, что
формула Y ? Y тождественно истинна, и потому значения
Zi независимо от значений Y всегда будут совпадать со
значениями сооветствующих Xi на выбранной строке. Формула
F(Z? , Z? , . . . Zn ) является частным случаем аксиомы и по
определению доказуема. Но ее отрицание тождественно истинно
и потому выводится даже из первоначального списка аксиом
согласно т. 5.4, а значит, и из расширенного. Таким образом
получаем, что из нового списка аксиом выводится как частный
случай новой аксиомы, так и ее отрицание, то есть нарушена
непротиворечивость теории.
Рассмотренная формальная теория оказалась непротиворечивой, полной и даже разрешимой есть алгоритм распознавания выводимости формулы из аксиом; есть даже алгоритм
построения этого вывода. Надо отметить, что это практически
единственный случай в математике из всех изучавшихся формальных систем, когда выполнено такое количество свойств.
Связано это, видимо, с исключительной простотой предмета
изучения высказываний.
Отметим еще одно свойство системы аксиом независимость. Аксиоматика формальной теории называется независимой, если ни одна из аксиом не выводится из остальных.
Естественно, эта проблема не столь принципиальна, как
непротиворечивость или полнота, но все же если какая-то аксиома выводится из остальных, то это не аксиома, а теорема, и
можно обойтись меньшим количеством аксиом, ничего не потеряв в классе выводимых формул.
Аксиоматика, предолженная здесь для ИВ, является независимой. Для доказательства того, что одна аксиома не выводится из остальных, надо найти свойство, которым обладают все
остальные аксиомы и следствия из них, а изучаемая аксиома
данного свойства не имеет. Провести такое исследование для
каждой из десяти аксиом на достигнутом уровне изучения ИВ
не слишком сложно, но здесь оно не приводится, частично из-за
следующего замечания.
Можно было бы выбрать другую систему аксиом, равносильную исходной в том смысле, что класс доказуемых формул был бы тот же самый. Действительно, возможны другие
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 6. Полнота исчисления высказываний
33
аксиоматизации с меньшим количеством первичных связок и
аксиом. При этом происходит выигрыш в количестве аксиом, но
сложность аксиом возрастает. Возможна даже аксиоматизация
с единственной схемой аксиом и с первичными связками ¬ и ?.
При этом дизъюнкция является просто сокращенной записью
следующей формулы: (X ? Y ) = (¬X ? Y ), конъюнкция (X ? Y ) = ¬(X ? ¬Y ). Единственная схема аксиом оказывается
при этом, естественно, весьма громоздкой. Некоторые из отмеченных утверждений изложены в конце данного раздела в виде
ряда задач.
Приведенная же система аксиом наиболее близка шаблонам
рассуждений человека. Кроме того, из этой системы аксиом
минимальным перестроением можно получить
исчисление высказываний, весьма важное для анализа
алгоритмов. Система аксиом ИИВ получается, если формулу
A ? (¬A ? B) взять в качестве схемы вместо десятой аксиомы
удаления отрицания, остальные аксиомы оставить такими
же, и вообще все остальные элементы определения формальный
теории оставить неизменными. Получится один из примеров
логики в ней неверен закон исключенного
третьего, неверен закон удаления отрицания, который был исключен из списка аксиом, и вообще многое непривычно.
Геометрия Лобачевского тоже отличается от классической
евклидовой только одной аксиомой и тоже вначале кажется
непривычной: как это через точку вне прямой проходит более
одной прямой, не пересекающей данную? Просто эта геометрия
описывает другой мир и логика ИИВ тоже.
Начала ИИВ также даны в виде нескольких задач в конце
раздела.
Для других аксиоматических теорий доказать такие свойства, какие имеются для ИВ, удается редко. Для арифметики,
более того, доказано (К. Гедель), что если аксиоматика арифметики непротиворечива, то она не полна и даже не пополняема, то есть, добавляя в систему аксиом любые формулы,
полную систему не получить. Все это, видимо, указывает на
содержательность математических теорий и принципиальную
невозможность их полного формального описания.
ское
неклассической
2 Ю. А. Белов, В. А. Соколов
интуиционист-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ЗАДАЧИ И УПРАЖНЕНИЯ I
Используя теорему о десяти выводимых правилах, леммы
о противоположной теореме и о противоречии, доказать, что
имеются следующие отношения выводимости:
1. A ? B ` (B ? C) ? (A ? C)
2. A ? B ` (C ? A) ? (C ? B)
3. A ? B ` (A ? C) ? (B ? C)
4. A ? B ` (A ? C) ? (B ? C)
5. A ? ¬B ` B ? ¬A
6. A ? B ` ¬B ? ¬A
7. ` A ? ¬¬A
8. ` (A ? B) ? ((A ? C) ? (A ? B ? C))
9. ` ¬A ? A
10. ` (A ? B) ? (B ? A)
Будем говорить, что формула F не слабее G, если F ` G. Две
формулы F и G исчисления высказываний называются равносильными, если каждая не слабее другой, то есть существует
вывод F из G: G ` F и вывод G из F : F ` G. Равносильность
двух формул F и G будем обозначать так: F ? G.
11. Доказать, что отношение ѕне слабееї на множестве M всех
формул ИВ является отношением квазипорядка, а отношение
равносильности ассоциированным отношением эквивалентности. При этом фактор-множество M/ ? становится частично
упорядоченным относительно индуцированного отношения выводимости, указанного в отмеченной теореме. Указать классы
формул, являющихся в этом частично упорядоченном множестве наименьшим и наибольшим элементом.
Доказать следующие равносильности:
12.
14.
16.
17.
A ? B ? ¬A ? B
13. ¬(A ? B) ? ¬A ? ¬B
¬(A ? B) ? ¬A ? ¬B 15. A ? (B ? C) ? (A ? B) ? (A ? C)
A ? (B ? C) ? (A ? B) ? (A ? C)
A ? (B ? C) ? (A ? B) ? C
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Задачи и упражнения I
35
Пусть имеется формула F , содержащая пропозициональную
букву X . Это будем обозначать так: F(X ). Пусть G произвольная формула ИВ. Через F(G) будем обозначать формулу,
полученную из F заменой всех вхождений X на G .
Будем говорить, что формула F(X ) монотонно возрастает
по переменной X , если из того, что G1 не слабее G2 , следует,
что F(G1 ) не слабее F(G2 ). Другими словами, F(X ) монотонно
возрастает по X тогда и только тогда, когда справедливо следующее отношение выводимости:
G1 ? G2 ` F(G1 ) ? F(G2 ).
Аналогично, формула F(X ) монотонно убывает по переменной
X , если справедливо обратное отношение:
G1 ? G2 ` F(G2 ) ? F(G1 ).
18. Доказать, что X ? Y и X ? Y монотонно возрастают по
X и по Y , ¬X монотонно убывает по X , X ? Y монотонно
возрастает по Y и монотонно убывает по X .
19. Доказать, что если формулы G и H равносильны, а формула F(X ) содержит вхождения X , то формулы F(G) и F(H)
равносильны. При этом утверждение остајтся справедливым,
если в формуле F только одно вхождение X заменяется на G
или H соответственно.
Дадим определение подформулы данной формулы F ИВ.
Оно состоит из трјх пунктов.
Если F является пропозициональной буквой, то подформула
сама буква.
Если формула F имеет вид (A ? B), (A ? B) или (A ? B),
то A и B подформулы F . Если F имеет вид (¬A), то A подформула F .
Если G подформула F , H подформула G , то H подформула F .
20. Пусть G подформула F и H равносильна G . Тогда
формула F1 , полученная из формулы F заменой подформулы
G на H, равносильна F . Доказать.
Как отмечалось ранее, приведенная аксиоматика исчисления высказываний не является единственной, то есть можно
привести другие аксиоматические системы, в некотором смысле
эквивалентные ИВ. Имеет смысл исследовать и некоторые формальные аксиоматические системы, не эквивалентные исходной
2*
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
36
Задачи и упражнения I
системе ИВ. Все они отличаются от изученной системы ИВ только составом аксиом, остальные элементы определения: алфавит,
определение формул и правила вывода остаются неизменными.
Определим формальную аксиоматическую систему ИВ2, определяющуюся так же, как исходная система ИВ, за исключением
одного фрагмента: из списка аксиом ИВ исключается схема 3 введение конъюнкции, вместо которой вводится схема
(A ? B) ? ((A ? C) ? (A ? B ? C)).
Систему ИВ3 определим так: из исходного списка аксиом
ИВ исключим аксиому 9 введение отрицания и добавим две
аксиомы:
(A ? B) ? (¬B ? ¬A)
A ? ¬¬A.
Система ИВ4 получается из ИВ изменениями списка аксиом,
указанными для получения ИВ2 и ИВ3 одновременно. Другими
словами, из списка аксиом ИВ удаляются две аксиомы 3 и 9 и добавляются три указанные схемы.
Приведјм пример еще одной системы, упоминавшейся ранее,
интуиционистского исчисления высказываний (ИИВ). Система
ИИВ получается из ИВ, если в списке аксиом аксиому 10 удаление отрицания заменить на следующую аксиому:
A ? (¬A ? B).
21. Доказать, что множество формул, доказуемых в ИВ2,
совпадает с множеством формул, доказуемых в ИВ.
22. Доказать, что множество формул, доказуемых в ИВ3,
совпадает с множеством формул, доказуемых в ИВ.
23. Доказать, что множество формул, доказуемых в ИВ4,
совпадает с множеством формул, доказуемых в ИВ.
Задачи 2123 показывают, что в определјнных пределах
можно варьировать список аксиом, сохраняя множество доказуемых формул. При этом в данных примерах всегда вместо одной
исключаемой аксиомы добавлялась одна или две другие. Естественный вопрос: если исключить одну из аксиом ИВ, ничего
не добавив в список аксиом взамен, уменьшится ли множество
доказуемых формул?
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Задачи и упражнения I
37
Точное определение следующее. Рассмотрим формальную
аксиоматическую систему ИВ?10 (ИВ минус десять), получающуюся из ИВ, если из списка аксиом исключить аксиому 10:
¬¬A ? A. Будем говорить, что в ИВ аксиома 10 независима,
если ¬¬A ? A не доказуема в ИВ?10. Это условие означает,
что аксиома 10 не выводится из остальных девяти аксиом, то
есть множество формул, выводимых в системе ИВ?10, есть собственное подмножество формул, выводимых в ИВ. Аналогичное
определение независимости дается и для любой другой аксиомы.
24. Доказать, что аксиома 10 ИВ независима.
25. Доказать, что аксиомы 39 ИВ независимы.
26. Доказать, что в ИИВ справедлива теорема о дедукции:
пусть ? = {A1 , A2 , . . . , Ak } произвольный набор формул, k >
> 0, A, B еще две формулы ИИВ. Тогда если ?, A `иив B , то
? `иив A ? B .
27. A ? B , B ? C `иив A ? C .
28. `иив A ? ¬¬A.
29. A ? B `иив ¬B ? ¬A.
30. Доказать, что формула ¬¬A ? A не доказуема в ИИВ.
31. Доказать, что формула A ? ¬A не доказуема в ИИВ.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
7
ЛОГИКА ПРЕДИКАТОВ.
АКСИОМЫ И ПРАВИЛА ВЫВОДА
Мы познакомимся с еще одной формальной аксиоматической
теорией, посвященной логике, исчислением предикатов. Исчисление предикатов гораздо сложнее, чем ИВ, поэтому изложение не будет полным. Как и исчисление высказываний, исчисление предикатов (ИП) разрабатывалось как средство формализации математических рассуждений. Можно сказать, что
ИП является детализацией исчисления высказываний и его возможности, в отличие от средств ИВ, в принципе достаточны для
адекватного описания любых математических рассуждений.
В основе ИВ лежало понятие высказывания, то есть предложения, которому можно приписать одно из двух возможных
истинностных значений. Предполагалось, что все высказывания
относятся к одной и той же математической теории и поэтому
их можно соединять логическими связками и получать при этом
новые осмысленные высказывания. Совершенно такой же подход будет проводиться и сейчас, только теперь в основе дальнейших построений лежат
предложения.
Предикатное предложение предложение, зависящее от
нескольких
переменых. Переменные могут принимать значения из некоторой
, и при каждом
конкретном наборе значений предикатное предложение становится высказыванием, истинным или ложным.
Например, предложение x < y предикатное предложение.
Считаем, что переменные x и y принадлежат множеству натуральных чисел N . Пример чисто математический, даже написан
на языке математических обозначений, но это не принципиально. Действительно, для любой конкретной пары значений x и
y , например 7, 4, получается высказывание, в данном случае
ложное: 7 < 4. Если бы были выбраны числа 1 и 2, получилось бы высказывание 1 < 2, истинное. Таким образом, говоря
математическим языком, предикат это функция, в данном
предикатные
предметных
предметной области
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 7. Логика предикатов. Аксиомы и правила вывода
39
примере от двух переменных x и y . Поэтому ИП ещј называют
функциональным исчислением.
Должно быть понятно, что практически любая математическая формулировка содержит предикаты от разного количества
переменных.
Предикатные предложения от одного переменного еще называют свойствами. Пусть снова x принадлежит множеству натуральных чисел N , тогда примерами свойств будут предложения
типа: x делится на 3, x больше 1. Допустимым вырожденным
случаем предикатного предложения будет предложение, не зависящее вообще от предметных переменных, это высказывание.
Таким образом, предикатное предложение задает функцию
от n предметных переменных, значениями которой являются
высказывания.
В связи с этим
Пусть G произвольное непустое множество, называемое
. Предикатом P от n переменных на области G называется функция P : Gn ? F2 , принимающая
значения 0 или 1.
Каждому предикату P соответствует некоторая
подмножество множества Gn , для элементов которого x1 , x2 , . . . xn
определение:
предметной областью
область ис-
тинности
P (x1 , x2 , . . . xn ) = 1.
Область истинности задает на G соответствующее n-арное
отношение, которым предикат однозначно определяется.
Понятно, что каждому предикатному предложению соответствует предикат. Как высказывания в ИВ обозначались пропозициональными символами, так и в исчислении предикатов
предикаты будут обозначаться предикатными символами, затем
из них при помощи связок и кванторов будут строиться новые
предикаты.
Дадим соответствующие точные определения.
Напомним, что для определения формальной аксиоматической теории требуются четыре элемента: алфавит, формулы,
аксиомы, правила вывода. Определим эти элементы для ИП,
сначала алфавит и формулы.
Алфавит состоит из следующих символов: прямые прописные буквы латинского алфавита A, B , . . . Z или буквы с индек-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
40
Гл. 7. Логика предикатов. Аксиомы и правила вывода
сами, например A1 , Bk , . . . (чтобы иметь неограниченный набор
символов), называемые
; символы предметных переменных строчные латинские буквы a, b, . . . x, y , z
или буквы с индексами xi , a1 , . . .; логические связки ?, ?, ¬, ?;
кванторы ?, ?; скобки (,).
Отличие алфавита ИП от алфавита исчисления высказываний в наличии предметных переменных и кванторов.
Замечание об индексах такое же, как для ИВ.
Формулы. Элементарная предикатная формула это предикатная буква с приданными переменными: например, A(x, y),
A(t, t), B(x1 , x2 , x3 ), A(z) и т. п.
1. Элементарная предикатная формула есть формула.
2. Если A и B формулы, x произвольная предметная
переменная, то следующие слова также являются формулами:
(A ? B), (A ? B), (¬A), (A ? B), (?xA), (?xA).
Часть формулы, заключенная в скобки при использовании
квантора, называется
.
В дальнейшем при написании формулы будем изображать
лишь необходимое количество скобок, позволяющее однозначно
восстановить формулу. При этом сохраняем те соглашения об
областях действия логических связок, которые имелись в ИВ.
Области действия кванторов считаем наименьшими возможными, например формула ?xA(x, y) ? B(x) есть сокращенная
запись для формулы ((?xA(x, y)) ? B(x)). Если же требуется, чтобы область действия квантора по x охватывала всю
импликацию, в сокращјнной записи надо написать соответствующие скобки: ?x(A(x, y) ? B(x)), в полной соответственно
(?x(A(x, y) ? B(x))).
Прежде чем давать список аксиом, необходимы предварительные определения.
Напомним, что любая формула есть просто слово в данном алфавите, построеннное по определенным правилам. То
есть формула представляет собой некоторую последовательность символов алфавита.
предметной переменной x в формулу есть
элемент последовательности, равный x. Например, в слове
?xA(x, y) ? B(x) имеются три вхождения x.
Некоторое вхожение переменной x в формулу
называется
, если оно находится в области действия
предикатными буквами
областью действия квантора
Вхождение
Определение.
связанным
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 7. Логика предикатов. Аксиомы и правила вывода
41
квантора по x. Вхождение, не являющееся связанным, называется
.
В последней приведенной формуле первое и второе вхождения x являются связанными, третье свободным. Вхождение y
в данную формулу является свободным, так как это вхождение
не находится в области действия квантора по y в формуле
вообще нет кванторов по y , хотя y и лежит в области действия
квантора по x. Если формула не содержит свободных вхождений
данной переменной x, то говорят короче: формула не зависит от
x. Например, ?x(A(x, y) ? B(x)) не зависит от x.
Если формула F содержит свободные вхождения переменной
x, то можно произвести
новой неизвестной t вместо
x. Подстановка есть замена всех свободных вхождений x на t.
Чтобы указать замену t вместо x в формуле F , будем использовать следующие обозначения: вместо F обозначим исходную
формулу через F (x), формулу, получившуюся в результате замены, через F (t). Отметим, что если F не содержит свободных
вхождений x, то F = F (x) = F (t), так как t никуда не будет
подставлено.
Но вообще может быть два случая: либо все вхождения
переменной t, возникшие в результате подстановки, являются
свободными, либо не все. В первом случае подстановка t вместо
x называется свободной, во втором нет. Другими словами,
подстановка t вместо x называется свободной, если все свободные вхождения x не находятся в области действия квантора по t.
Например, подстановка в формулу ?x(A(x, y) ? B(x)) t вместо
y свободна, подстановка же x вместо y не свободна. Результат
подстановки в первом случае: ?x(A(x, t) ? B(x)), во втором
?x(A(x, x) ? B(x)). Разница между формулами в том, что
в формуле, возникшей после первой подстановки, вхождение t
свободно, а третье вхождение x во второй формуле, возникшее
в результате подстановки, связанное. Ещј пример. Подстановка
t вместо x в формулу A(t) ? ?y(B(x) ? ?tC(t, y)) приводит к
результату A(t) ? ?y(B(t) ? ?tC(t, y)). Эта подстановка свободна, так как второе вхожение t, получающееся в результате
подстановки, свободно.
Теперь получены необходимые технические понятия, требующиеся в дальнейших определениях, и можно определить два
свободным
подстановку
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
42
Гл. 7. Логика предикатов. Аксиомы и правила вывода
оставшихся элемента новой формальной теории аксиомы и
правила вывода.
Аксиомы. Список содержит 12 схем аксиом, первые 10
текстуально те же, что и для исчисления высказываний:
Введение логических связок
1. A ? (B ? A)
3. A ? (B ? A ? B)
6. A ? A ? B 7. B ? A ? B
9. (A ? B) ? ((A ? B) ? A)
Удаление логичеких связок
2. (A ? B)
? ((A ? (B ? C)) ? (A ? C))
4. A ? B ? A 5. A ? B ? B
8. (A ? C)
? ((B ? C) ? (A ? B ? C))
10. A ? A
Отличие от ИВ в том, что теперь вместо букв в схемы
можно вписывать любые формулы исчисления предикатов.
Кроме того, имеются две аксиомы, использующие кванторы:
11. ?xA(x) ? A(t) ,
где A(x) любая такая формула, что подстановка t вместо
x свободна; это ?-схема, или аксиома всеобщности.
12. A(t) ? ?xA(x) ,
где A(x) любая такая формула, что подстановка t вместо
x свободна; это ?-схема, или аксиома существования.
Правила вывода:
1. Правило MP такое же, как в ИВ: из X , X ? Y непосредственно выводится Y ; оно теперь применяется для формул ИП.
2. ?-правило: из формулы C ? A(x) непосредственно выводится формула C ? ?xA(x), если C не содержит свободных
вхождений x (не зависит от x).
3. ?-правило: из формулы A(x) ? C непосредственно выводится формула ?xA(x) ? C , если C не содержит свободных
вхождений x (не зависит от x).
Теперь определение исчисления предикатов завершено.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
8
ИНТЕРПРЕТАЦИЯ ФОРМУЛ ЛОГИКИ ПРЕДИКАТОВ
Мы не будем рассматривать теорию доказательств для
ИП, которая содержит аналог теоремы о дедукции, теоремы
о различных выводимых правилах и т. п., так как всј это
выходит за рамки данного пособия. Мы дадим лишь простейшие
примеры формальных доказательств и выводов из условий в
исчислении предикатов. Напомним, что определения этих
понятий были даны в общем виде в применении к любой
аксиоматической теории. В частности, будет использоваться
обозначение G ` F , если формула F выводится из набора
условий G , может быть пустого.
Правило переименования свободных переменных
Пусть подстановка y вместо x в формуле F (x) свободна,
тогда если F (x) доказуема, то и F (y) доказуема.
Д о к а з а т е л ь с т в о. Докажем, что F (x) ` F (y).
1. F (x) ; условие
2. F (x) ? (G ? F (x)) ; схема аксиом 1. ?-введение, в
качестве G выберем любую доказуемую формулу, не зависящую
от x.
3. G ? F (x) ; МР 1., 2.
4. G ? ?xF (x) ; ?-правило, примененное к 3.
5. G ; доказуемо по выбору.
6. ?xF (x) ; МР 5., 4.
7. ?xF (x) ? F (y) ; ?-аксиома.
8. F (y) ; МР 6., 7.
Построенная последовательность является выводом формулы F (y) из формулы F (x): F (x) ` F (y). По условию ` F (x), а
тогда по теореме транзитивности выводимости ` F (y)
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
44
Гл. 8. Интерпретация формул логики предикатов
Первое правило переименования
связанных переменных
Пусть 1) подстановка y вместо x в формуле F (x) свободна
и 2) F (x) не зависит от y. Тогда если ?xF (x) доказуема, то
?yF (y) доказуема.
Д о к а з а т е л ь с т в о. Докажем, что ?xF (x) ` ?yF (y).
1. ?xF (x) ; условие.
2. ?xF (x) ? F (y) ; ?-схема акс. 11, усл. 1).
3. ?xF (x) ? ?yF (y) ; ?-правило, примененное к 2. Отметим,
что в силу условия 2) ?yF (y) не зависит от y .
4. ?yF (y) ; МР 1, 3.
Второе правило переименования
связанных переменных
Пусть 1) подстановка y вместо x в формуле F (x) свободна
и 2) F (x) не зависит от y. Тогда если ?xF (x) доказуема, то
?yF (y) доказуема.
Д о к а з а т е л ь с т в о. Докажем, что ?xF (x) ` ?yF (y). Сначала
докажем, что при условиях 1) и 2) подстановка x вместо y в
формулу F (y) свободна. Действительно, все свободные вхождения y в F (y) появились в результате подстановки y вместо x в
силу 2). В силу 1) все свободные вхождения x были заменены
на свободные вхождения y . Поэтому подстановка x в F (y) произойдет на места всех исходных свободных вхождений x в F (x).
Это значит, что подстановка x в F (y) свободна и результат ее исходная формула F (x).
1. ?xF (x) ; условие.
2. F (x) ? ?yF (y) ; ?-схема акс. 12; замечание о свободе
подстановки x вместо y .
3. ?xF (x) ? ?yF (y) ; ?-правило вывода, примененное к 2.
Правило применимо, так как ?yF (y) не зависит от x.
4. ?yF (y) ; МР 1, 3.
Полное длинное определение исчисления предикатов было
приведено для того, чтобы можно было доказать хотя бы одну
содержательную теорему для исчисления. Это будет теорема о
непротиворечивости ИП и один пример, показывающий принципиальную разницу между исчислением высказываний и исчислением предикатов.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 8. Интерпретация формул логики предикатов
45
Вспомним, что для доказательства непротиворечивости ИВ
каждой формуле была сопоставлена определенная булева функция. При этом оказалось, что всем доказуемым формулам соответствуют тождественно истинные функции, и потому ИВ
оказалась непротиворечивой.
Конечно, смысл рассмотрения булевых функций не только в
том, что с их помощью можно доказать непротиворечивость.
Булевы функции дают точное определение понятия истинности, с их помощью возможно истолковать,
аксиомы как основные истины, из которых остальные истины
выводятся.
Можно всю теорию высказываний изложить на основе понятия истинности и соответствующих таблиц значений, только это
уже была бы не формальная аксиоматическая теория, это было
бы действительно ѕисчислениеї.
Для доказательства непротиворечивости ИП тоже можно идти путјм
, то есть определить некую процедуру
сопоставления каждой формуле ИП предиката аналогично
подходу, проведенному в ИВ. Снова можно отметить, что это
сопоставление даст строгое формальное определение истинности предикатных формул, снова аксиомы будут выступать как
основные истины, только, в отличие от ИВ, исчисление предикатов не сводится к вычислениям по конечным таблицам.
Опишем процедуру, называемую
: сопоставление каждой формуле ИП предиката от всех свободных
переменных, входящих в формулу.
интерпретировать
интерпретации
интерпретацией
Для задания интерпретации требуются следующие элементы:
1. Предметная область непустое множество D. Предполагается, что в данной интерпретации все предметные переменные
будут принимать значения из этого множества.
2. Каждой элементарной предикатной формуле F (предикатной букве с приданными переменными) ставится в соответствие
какой-то предикат p(F ) от соответствующего количества переменных на предметной области (множестве D). В вырожденном
случае, когда элементарная предикатная формула имеет 0 приданных переменных, ей сопоставляется один из символов 0
или 1.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
46
Гл. 8. Интерпретация формул логики предикатов
Тем самым каждой элементарной предикатной формуле уже
поставлен в соответствие предикат от свободных переменных
этой формулы (а других переменных в таких формулах нет).
Для остальных формул ИП соответствующий предикат уже
однозначно определяется по следующим правилам.
Каждая формула F ИП имеет один из следующих видов:
(A?B), (A?B), (¬A), (A ? B), (?xA), (?xA), где формулы A
и B имеют меньшее количество логических связок и кванторов.
Проводим индукцию по общему количеству k связок и кванторов в формуле. При k = 0 формула явлется элементарной
и еј интерпретация имеется. Пусть формула имеет вид C =
= (A ? B). Тогда формулы A и B имеют меньшее количество
связок и у каждой из них свой набор свободных переменных
{x1 , x2 , . . . xn } в формуле A и {y1 , y2 , . . . ym } в формуле B .
По построению формулы C еј набор свободных переменных есть
объединение наборов xi и yj , и пусть задан произвольный фиксированный набор значений всех этих переменных. Заданием
этих значений определяются наборы значений переменных xi
и yj . По предположению индукции, однозначно определяются
булевские значения формул A и B , точнее, значения тех предикатов p(A) и p(B), которые соответствуют этим формулам.
Тогда по определению значение предиката p(C) вычисляется
как соответствующее табличное значение конъюнкции: p(C) =
= p(A) ? p(B).
В действительности все это описание сводится просто к естественному вычислению по структуре формулы. Точное различение формулы C и соответствующего ей предиката p(C) будет
отмечаться явно, когда, например, рассматриваются две интерпретации: p1 (C) и p2 (C) и в других необходимых случаях.
Когда же это не приведјт к непониманию, будем ради краткости
допускать вольность речи и говорить про значения формулы
C на заданном наборе значений переменных, имея в виду, что
формуле C соответствует предикат с тем же обозначением.
Для других логических связок вычисление значений определяется аналогично.
Рассмотрим кванторы.
Пусть формула C имеет вид: C = (?xA) или C = (?xA).
Пусть формула A зависит от n свободных перменных: {x1 , x2 , . . .
. . . xn }. Если среди них нет переменной x, то C = (?xA) =
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 8. Интерпретация формул логики предикатов
47
= A. Это описание вырожденного случая, когда квантор взят
по переменной, свободных вхождений которой в формуле нет.
Пусть x = xn ; номер переменной, конечно, не имеет значения
в последующих построениях. Тогда формула C = (?xA), по
определению свободного вхождения переменной, имеет свободные вхождения только n ? 1 переменного: {x1 , x2 , . . . xn?1 }, и
ей будет соответствовать предикат от этих переменных. Пусть
взят некоторый набор значений указанных переменных из предметной области: {d1 , d2 , . . . dn?1 }, где все di ? D. Значение C =
= (?xA) на данном наборе равно 1 тогда и только тогда, когда
значение A равно 1 на любом наборе значений вида: {d1 , d2 , . . .
. . . dn?1 , d} для любого d ? D. Другими словами, C равно 1
на выбранном наборе значений тогда и только тогда, когда на
любом расширении этого набора значений произвольным значением последней переменной исходная формула A равна 1.
В действительности определение вполне естественно: формула (?xA) равна 1 тогда и только тогда, когда формула A
равна 1 при всех значениях x, остальные переменные при этом
фиксированы.
Для формулы C = (?xA) всј аналогично: она равна 1 на
некотором наборе значений {d1 , d2 , . . . dn?1 }, ?i di ? D тогда
и только тогда, когда формула A равна 1 на некотором расширении этого набора, полученном присоединением значения
последней переменной xn .
Как условились ранее, в приведјнных определениях допущены выражения вида ѕзначение формулы Aї вместо более
точного p(A) и т. п., кроме того, в дальнейшем внешние скобки
в формулах будем (как и в ИВ) для краткости опускать.
Теперь процедура интерпретации определена полностью.
Для построения интерпретации требуется задать предметную область D и каждой предикатной букве сопоставить
предикат на D от соответствующего количества переменных.
Пусть предметная область D = {a, b, c} состоит из трех
произвольных символов. Для краткости будем рассматривать
только предикатные буквы, имеющиеся в формуле F =
= ?y(A(x) ? ?xB(x, y)), и построим предикат p(F ).
Сначала, по определению интерпретации, надо элементарным формулам B(x, y) и A(x) сопоставить некоторые предикаты
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
48
Гл. 8. Интерпретация формул логики предикатов
на области D от двух или одного переменного соответственно:
x
a
a
a
b
b
b
c
c
c
y
a
b
c
a
b
c
a
b
c
p(B(x, y))
1
1
1
0
1
1
1
0
1
x
a
b
c
p(A(x))
1
1
0
Теперь можно начать вычисление подформул формулы F :
y
a
b
c
p(?xB(x, y))
0
0
1
Как получено, например, значение 0 в первой строке?
По определению интерпретации квантора всеобщности, были
рассмотрены первая, четвертая и седьмая строки в таблице для
p(B(x, y)), в которых значение y равно a. Оказалось, что не во
всех указанных строчках значение p(B(x, y)) равно 1. Поэтому
значение формулы с квантором считаем равным 0. Аналогично
получены остальные две строки значений.
Теперь построим таблицу значений для формулы
p(A(x) ? ?xB(x, y)).
Эта формула задает предикат от двух переменных x
и y (объединение свободных переменных составляющих
подформул):
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 8. Интерпретация формул логики предикатов
x
a
a
a
b
b
b
c
c
c
y
a
b
c
a
b
c
a
b
c
49
A(x) ? ?xB(x, y)
0
0
1
0
0
1
1
1
1
Эта таблица получена как таблица импликации из A в B ,
что и было еще раз указано перед еј построением. Построим
таблицу значений всей формулы F = ?y(A(x) ? ?xB(x, y)):
x
a
b
c
p(?y(A(x) ? ?xB(x, y)))
1
1
1
Формула оказалась тождественно истинной в данной интерпретации. Если изменить таблицы для p(A(x)) и/или p(B(x, y)),
получили бы на той же предметной области D, вообще говоря,
другую интерпретацию формулы F , она получила бы другую
таблицу значений.
Ясно, что количество различных интерпретаций данной формулы на данном конечном множестве конечно. Действительно,
например, для задания интерпретации формулы F необходимо
определить два предиката на D: одноместный для буквы A
и двуместный для буквы B . Очевидно, количество различных
одноместных предикатов на D равно 23 , двуместных 29 , количество пар 212 .
Кроме того, ясно, что количество различных интерпретаций
данной формулы на конечном множестве определяется только
количеством элементов |D| в данном множестве и количеством
переменных формулы и не зависит от того, из каких элементов
состоит D.
Иногда формула может оказаться тождественно истинной
при любой интерпретации на данном множестве D. Простейший
пример: формула ?xA(x) ? ?xA(x) тождественно истинна на
любой области из одного элемента. Грубо ѕпо смыслуї форму-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
50
Гл. 8. Интерпретация формул логики предикатов
лы: если существует значение x, для которого A(x) истинно,
то A(x) будет истинно и для всех x, потому что возможных
значений x в нашей интерпретации всего одно.
Можно придумать формулу, которая будет тождественно
истинной при любой интерпретации на двухэлементном множестве, например достаточно в формулу X ? X вместо X вписать
любую формулу ИП. В силу того, что схема, в которую подставляются формулы, тождественно истинна, полученная формула
тоже будет тождественно истинной. Ясно, что такая формула
будет тождественно истинной при любой интерпретации на любом множестве вообще.
Формула F исчисления предикатов называется
, если она тождественно истинна при любой интерпретации на любой предметной области. Обозначение: |= F .
В связи с данным определением интересен такой вопрос:
можно ли придумать не общезначимую формулу, которая была
бы все же тождественно истинна при любой интерпретации на
любом двухэлементном множестве?
Назовем формулу k -общезначимой, если она тождественно
истинна при любой интерпретации на любом множестве, имеющем не более k элементов. Тогда возникают следующие вопросы:
существуют ли k -общезначимые, но не (k + 1)-общезначимые
формулы? Существуют ли формулы, k -общезначимые для любого k , но не общезначимые?
Второй вопрос фактически о том, нужно ли для проверки
истинности формул ИП ѕуходить в бесконечностьї, то есть рассматривать бесконечные предметные области, весьма важен;
в дальнейшем он будет решен.
Рассмотрим пример с бесконечной предметной областью D.
Первое затруднение при этом определение предикатов для
элементарных формул. Так как прямое построение бесконечных
таблиц невозможно, необходимо дать какие-то правила построения истинностных значений предиката для произвольных наборов значений переменных.
Построение предикатов для составных формул в этом случае
также не сводится к просмотру таблиц, которые теперь бесконечны, а должно быть как-то обосновано рассуждениями.
Пусть D = N , где N = {0, 1, 2, . . . n, . . .} множество натуральных чисел. Рассмотрим две элементарные предикатные форму-
Определение.
общезначимой
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 8. Интерпретация формул логики предикатов
51
лы S(x, y , z) и P (x, y , z) от трех переменных. С их помощью построим ряд формул, которые при интерпретации будут означать
вполне осмысленные арифметические утверждения. Определим
предикаты, соответствующие выбранным буквам: p(S(x, y , z)) =
= 1 тогда и только тогда, когда x + y = z , p(P (x, y , z)) =
= 1 тогда и только тогда, когда x ? y = z . Таким образом,
бесконечные таблицы заменены арифметическими формулами.
Можно считать неважным, как именно задан предикат, главное,
что можно вычислить его значение на произвольном наборе
значений пременных (хотя это и не совсем так).
Рассмотрим теперь простые примеры формул ИП, построенных на этих двух буквах, интерпретированных как сумма и
произведение.
?x?yS(x, y , y). Это так называемая замкнутая формула она не имеет свободных переменных и должна представлять
ѕпредикат от 0 переменныхї, то есть высказывание. При данной
интерпретации это высказывание истинно оно означает, что
в N существует элемент, нейтральный относительно сложения:
x + y = y для всех y из N . Действительно, такой элемент
существует это 0. Если бы интерпретация проводилась только
на множестве положительных чисел, высказывание было бы
ложным. Аналогично ?x?yP (x, y , y) истинное высказывание,
означающее существование 1 в N .
Конечно, вторую (и первую) формулу можно разбирать ѕв
строгом табличном стилеї, как в примере с конечной областью D.
p(P (x, y , z)) определено, теперь рассмотрим фрагмент
?yP (x, y , y). Эта подформула зависит от одного свободного
неизвестного x. Построим таблицу (бесконечную) значений этой
формулы. При данной интерпретации она означает: ?y (x ? y =
= y). Это предикат от x. Вычисляем его для каждого значения
x ? N . Пусть сначала x = 0. Верно ли, что ?y (0 ? y = y)?
Нет, неверно. Значит, при x = 0 подформула равна 0. Затем
x = 1. Верно ли, что ?y (1 ? y = y)? Да. Значит, при x = 1
подформула равна 1. И так далее до бесконечности. Но уже
из двух вычисленных значений одно равно 1, и потому вся
исходная формула истинна.
Это нарочитый пример, но понимание интерпретации формулы должно быть именно таковым. В книге [10] об этом го-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
52
Гл. 8. Интерпретация формул логики предикатов
ворится так: ѕКонечно, при больших конечных |D| или очень
сложных формулах вычисление может оказаться невероятно
длинным. Если же область D бесконечна, истинностная таблица
перестает быть конечным объектом, который теоретически можно вычислить, хотя сама идея этой таблицы остается совершенно
ясной, и о ней можно рассуждатьї.
Еще примеры. ?yS(y , y , x) задает, очевидно, предикат от одного неизвестного x, истинный тогда и только тогда, когда x
четно, ?zS(x, z , y) определяет неравенство x 6 y , ¬(?yS(y , y , x))
является истинным тогда и только тогда, когда x нечетно. Таким
образом, имея две основные предикатные буквы, можно строить
множество новых осмысленных арифметических предикатов,
определяющих простоту числа, делимость одного числа на другое и т. п., формулировать теоремы арифметики другими словами, ИП может служить основой формального языка описания
математических теорий.
Для упрощения таких описаний, то есть для усиления выразительных возможностей исчисления предикатов, можно рассматривать варианты ИП, в которых, кроме предметных переменных, имеются еще предметные константы, которые тоже
можно подставлять в предикатные буквы, однако константы
нельзя использовать с кванторами. Каждой константе при интерпретации надо сопоставить фиксированный элемент предметной области. Рассматривая последний пример для такого исчисления, можно было бы каким-то символам констант присвоить значение 0, 2, 2002 ..., если именно эти константы позволят
упростить формулировки.
Можно, кроме того, в определение ИП вводить символы
операций или функциональные буквы. Функциональные буквы
зависят от нескольких предметных переменных и могут подставляться вместо предметных переменных в предикатные буквы.
Функциональные буквы можно подставлять вместо переменых
в другие функциональные буквы. При интерпретации каждой
функциональной букве сопоставляется операция на D от соответствующего количества переменных. В нашем примере при
таком подходе можно, скажем, рассмотреть на области N выражение x ? y + x + y , считая его сопоставленным некоторому
функциональному символу f (x, y), вообще возникает возможность непосредственно строить арифметические выражения.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 8. Интерпретация формул логики предикатов
чистом
53
В нашем же
исчислении предикатов даже основные
константы вроде нуля или единицы определялись косвенно при
помощи формул. Однако все варианты определения исчисления
предикатов идейно одинаковы, зато чистое исчисление имеет
самое простое описание.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
9
ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ И РАВНОСИЛЬНОСТЬ
Как отмечалось ранее, теория доказуемости для исчисления
предикатов использует для своего построения многие факты, относящиеся к теории алгоритмов. На данном этапе можно только
использовать процедуру интерпретации формул как некоторую
возможность изучения выводимости и доказуемости на основе
следующего определения.
Пусть имеются две формулы ИП A и B . Говорим, что формула B является
формулы
A, если при любой интерпретации на любой предметной области D область истинности формулы A является подмножеством
области истинности формулы B .
Обозначается это так: A |= B , что согласуется с предыдущим
использованием этого знака, в частности если A общезначима,
то и B общезначима.
Раскроем это определение.
Пусть {x1 , x2 , . . . xn } объединение всех свободных переменных формул A и B . Теперь можно считать, что A и B зависят от
одного и того же набора свободных переменных. Пусть задана
предметная область D и некоторый набор значений {d1 , d2 , . . .
. . . dn }, где все dk ? D. В определении требуется, чтобы B на
данном наборе значений было истинным, если на нем истинна
формула A; и нужно, чтобы это выполнялось при любой интерпретации на любой предметной области.
Легко видеть, что A |= B тогда и только тогда, когда
|= A ? B . Этим частично объясняется термин ѕлогическое следствиеї, хотя фактически это следствие получено в результате
ѕпроверки на моделиї.
Можно обобщить приведенное определение и говорить, что
формула B логически следует из набора формул:
Определение.
логическим следствием
A1 , A2 , . . . , Am |= B ,
если при любой интерпретации пересечение областей истинности
Ak содержится в области истинности формулы B .
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 9. Логическое следование и равносильность
55
Справедлива теорема о транзитивности отношения логического следования, аналогичная теореме о транзитивности выводимости.
Отношение логического следования обладает
свойствами рефлексивности и транзитивности: 1) A |= A,
2)если A |= B и B |= C , то A |= C . Более того: если A , A , . . .
... Am |= Bk , k = 1, 2, . . . l и B , B , . . . Bl |= C , то A , A , . . .
... Am |= C .
Т е о р е м а 9.1.
1
2
1
2
1
2
Д о к а з а т е л ь с т в о. Свойства 1) и 2) очевидны. Докажем обобщение свойства 2) для нескольких формул. Если Bk логически
следует из набора формул A1 , A2 , . . . Am , это по определению
означает, что для любой интерпретации пересечение областей
истинности Ai является подмножеством области истинности
Bk , k = 1, 2, . . . l. Тогда пересечение областей истинности Ai
содержится в пересечениии областей истинности Bk и, значит, в
области истинности C .
Напомним, что бинарные отношения со свойствами рефлексивности и транзитивности называются отношениями квазипорядка. Отношение логического следования также, в силу теоремы 9.1, является квазипорядком на множестве всех формул ИП.
Понятие логического следования позволяет определить следующее отношение между формулами:
Две формулы A и B исчисления предикатов
называются равносильными, если A |= B и B |= A. Обозначается
равносильность следующим знаком: A ? B .
Таким образом, две формулы ИП являются равносильными
тогда и только тогда, когда при любой интерпретации они определяют один и тот же предикат.
Определение.
Отношение равносильности есть отношение
эквивалентности на множестве всех формул ИП.
Т е о р е м а 9.2.
Д о к а з а т е л ь с т в о. Лјгкая проверка по определению.
Отношение равносильности разбивает множество всех формул ИП на непересекающиеся классы равносильных формул. На
эти классы можно перенести отношение логического следования: класс A |= B тогда и только тогда, когда A |= B .
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
56
Гл. 9. Логическое следование и равносильность
Словесная формулировка этого определения: один класс равносильных формул является логическим следствием другого,
если хотя бы одна формула первого класса является логическим
следствием некоторой формулы второго класса. Тогда, конечно,
и любая формула первого класса является логическим следствием любой формулы второго класса.
Понятие логического следствия, как отмечалось, позволяет
выявить некоторые соотношения между формулами.
о переносе квантора через отрицание ).
Т е о р е м а 9.3 (
¬(?xA) ? ?x(¬A).
¬(?xA) ? ?x(¬A).
Д о к а з а т е л ь с т в о. Пусть, как обычно, D предметная
область, на которой задана интерпретация формулы A,
{x, y1 , y2 , . . . yn } набор всех свободных переменных A.
Докажем первое утверждение. Заметим, что обе формулы в
нем зависят от переменных {y1 , y2 , . . . yn }. Пусть {d1 , d2 , . . .
. . . dn }, dk ? D произвольный набор значений yi . Требуется
доказать, что формула ¬(?xA) истинна тогда и только тогда,
когда ?x(¬A) истинна.
Может быть два случая: либо формула A истинна на всех
наборах значений вида {d, d1 , d2 , . . . dn }, d, dk ? D, полученных
расширениями набора значений для yi , либо не на всех.
В первом случае формула ?xA, по определению интерпретации квантора всеобщности истинна на наборе {d1 , d2 , . . . dn }, ее
отрицание ложно. Формула ¬A в этом случае на всех наборах
{d, d1 , d2 , . . . dn } ложна и, по определению интерпретации квантора существования, формула ?x(¬A) ложна на наборе значений
{d1 , d2 , . . . dn }, то есть левая и правая формулы принимают одинаковые значения.
Пусть теперь формула A истинна не на всех наборах значений вида {d, d1 , d2 , . . . dn }. Другими словами, существует такое
значение d = d0 , что A ложна на наборе значений {d0 , d1 , d2 , . . .
. . . dn }, а ¬A истинна. Тогда ?xA ложна на наборе {d1 , d2 , . . . dn },
значит, ее отрицание истинно и формула ?x(¬A) истинна.
Доказательство второго утверждения теоремы аналогично.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 9. Логическое следование и равносильность
57
Т е о р е м а 9.4 (о равносильном переносе кванторов).
?x(A ? B) ? ?xA ? ?xB.
?x(A ? B) ? ?xA ? ?xB.
Д о к а з а т е л ь с т в о. Пусть D предметная область, задана
интерпретация формул A и B , {x, y1 , y2 , . . . yn } объединение
свободных переменных A и B .
Докажем первое утверждение. Формулы ?x(A ? B) и
?xA ? ?xB зависят от переменных {y1 , y2 , . . . yn }. Требуется
доказать, что при любом наборе значений этих переменных
формулы принимают одинаковые значения.
Пусть {d1 , d2 , . . . dn } произвольный набор значений yi .
Снова два случая: либо формула A ? B истинна на всех
наборах значений вида {d, d1 , d2 , . . . dn }, d, dk ? D, полученных
расширениями набора значений для yi , либо не на всех.
В первом случае и A и B истинны на всех таких расширениях. Тогда формулы ?x(A ? B), ?xA и ?xB истинны на {d1 , d2 , . . .
. . . dn } и, значит, формулы ?x(A ? B) и ?xA ? ?xB истинны на
этом наборе.
Второй случай: формула A ? B , зависящая от d, истинна не
на всех наборах {d, d1 , d2 , . . . dn }. Значит, существует значение
d = d0 такое, что A ? B ложна на наборе значений {d0 , d1 , d2 , . . .
. . . dn }. Тогда ?x(A ? B) ложна на {d1 , d2 , . . . dn }, кроме того,
или формула A, или B ложна на наборе {d0 , d1 , d2 , . . . dn }. Последнее означает, что или ?xA, или ?xB соответственно ложна
на наборе значений {d1 , d2 , . . . dn } и конъюнкция этих формул
ложна. Значит, формулы ?x(A?B) и ?xA??xB ложны и первое
утверждение теоремы доказано.
Второе утверждения теоремы доказывается аналогично.
В доказанной теореме не указано, как ѕвзаимодействуетї
квантор всеобщности с дизъюнкцией и квантор существования
с конъюнкцией. Об этом следующие утверждения.
Т е о р е м а 9.5 (о неравносильном переносе кванторов).
?xA ? ?xB |= ?x(A ? B).
?x(A ? B) |= ?xA ? ?xB.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
58
Гл. 9. Логическое следование и равносильность
Д о к а з а т е л ь с т в о. Пусть D предметная область, задана
интерпретация формул A и B , {x, y1 , y2 , . . . yn } объединение
свободных переменных A и B .
Тогда формулы ?xA??xB и ?x(A?B) зависят от переменных
{y1 , y2 , . . . yn }. Требуется доказать, что если на некотором наборе
значений этих переменных первая формула истинна, то и вторая
тоже истинна. Пусть {d1 , d2 , . . . dn } набор значений yi , на
котором формула ?xA ? ?xB истинна. Тогда на этом наборе
истинна формула ?xA или ?xB . Это означает, что формула
A или формула B истинна на всех наборах вида {d, d1 , d2 , . . .
. . . dn }, d, dk ? D, полученных расширениями набора значений
для yi . Тогда формула A ? B истинна на всех таких расширениях. По определению интерпретации квантора всеобщности, это
означает, что формула ?x(A ? B) истинна на наборе значений
{d1 , d2 , . . . dn }.
Второе утверждение теоремы доказывается аналогично.
Можно дополнить полученные результаты очевидными соотношениями о перестановке одноименных кванторов:
?x(?yA) ? ?y(?xA);
?x(?yA) ? ?y(?xA).
Все эти свойства, в сочетании с правилами переименования
свободных и связанных переменных, сформулированными раньше для отношения выводимости, но верными и для отношения
логического следования, являются основой для приведения любой формулы ИП к некоторому равносильному
виду, в котором все кванторы вынесены перед формулой.
Приведение формул к нормальному виду проводится как
предварительное преобразование при доказательстве полноты
ИП, что оправдывает рассмотрение отмеченных свойств.
Однако у любого подхода, опирающегося на общезначимость, имеется принципиальное ограничение отсутствие для
формул ИП алгоритма проверки общезначимости. Этот факт не
доказан, но далее он будет обсуждаться.
нормальному
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
10
НЕПРОТИВОРЕЧИВОСТЬ ИСЧИСЛЕНИЯ
ПРЕДИКАТОВ
После того как было введено понятие интерпретации, можно
проводить доказательство непротиворечивости ИП по той же
схеме, которая использовалась для исчисления высказываний.
Т е о р е м а 10.1. Аксиомы исчисления предикатов являются общезначимыми формулами.
Д о к а з а т е л ь с т в о. Сначала разберем первые десять схем
аксиом. Рассмотрим произвольную интерпретацию аксиом на
некоторой области D. Каждая аксиома построена при помощи
подстановки в схему формул ИП. Формулам при интерпретации
сопоставлены по известным правилам предикаты от имеющихся
свободных переменных. Набор свободных переменных аксиомы
является объединением наборов свободных переменных
подформул, из которых аксиома построена. Любому набору
значений переменных соответствуют определенные значения
подформул. Значение самой аксиомы получается из значений
подформул при помощи булевых таблиц истинности. Как
отмечалось ранее, все схемы аксиом ИВ тождественно истинны.
Десять схем ИП перенесены из ИВ без изменений. Поэтому
значение аксиомы на любом наборе значений переменных будет
равно 1.
Расссмотрим ?-схему ?xA(x) ? A(t) аксиому 11. По определению подстановка t вместо x свободна. Здесь A(x) произвольная формула ИП, у которой ни одно свободное вхождение x не
находится в области действия квантора по t. Надо доказать, что
такая формула тождественно истинна при любой интерпретации
в любой области D.
Сначала тривиальный случай: A(x) вообще не зависит от x,
то есть не имеет свободных вхождений x. Тогда подстановка t
вместо x никуда не будет произведена и A(t) просто совпадает
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
60
Гл. 10. Непротиворечивость исчисления предикатов
с A(x); соответственно совпадут и их значения при интерпретации. Кроме того, по правилам интерпретации значения ?xA(x) и
A(x) в таком случае также совпадают. Значит, условие и заключение в ?-схеме при интерпретации будут принимать одинаковые
значения и схема будет тождественно истинна.
Пусть A(x) = A(x, y1 , y2 , . . . yn ) формула A с явно выписанным списком всех имеющихся свободных переменных. Может
быть два случая: либо среди yk есть переменная t, либо нет. Рассуждения почти одинаковы в обоих случаях, проведем их поэтому, когда свободной переменной t в формуле A(x) нет. Отметим,
что тогда подформула ?xA(x) зависит только от {y1 , y2 , . . . yn }, а
подформула A(t) от {t, y1 , y2 , . . . yn }. Вхождения t, появившиеся в A(t) в результате подстановки, являются свободными в силу
свободы подстановки, и притом это все свободные вхождения t
вообще других свободных вхождений не было. Вся аксиома
тоже зависит от этого набора: {t, y1 , y2 , . . . yn }. Пусть теперь
задана область D и дано распределение значений всех этих
переменных: {d0 , d1 , d2 , . . . dn }, при этом ?k dk ? D.
Возможны два случая: либо A(t) на этом наборе истинна,
либо ложна. В первом случае вся импликация тоже истинна, так
как заключение истинно. Во втором случае докажем, что значение формулы ?xA(x) на наборе {d1 , d2 , . . . dn } ложно. Действительно, значение формулы A(x) = A(x, y1 , y2 , . . . yn ) на наборе
значений переменных {d0 , d1 , d2 , . . . dn } получается при подстановке dk вместо yk при k > 0 и d0 вместо свободных вхождений x.
По условию свободные вхождения x в формуле A(x) заменены на
вхожения t, которые тоже остались свободными в силу свободы
подстановки. Значит, d0 в формуле A(x) будет подставлено на
те же места, что и в формуле A(t). Так как A(t) на этом наборе
ложно, A(x) тоже. Это означает, что ?xA(x) на наборе {d1 , d2 , . . .
. . . dn } ложно. Если условие ложно, импликация истинна.
Рассуждения для ?-схемы совершенно аналогичны. При тех
же обозначениях и предположениях имеются два содержательных случая: либо A(t) на наборе {d0 , d1 , d2 , . . . dn } истинна, либо
ложна. Если посылка импликации ложна, импликация истинна.
Если A(t) при данных значениях истинна, то, в силу свободы
подстановки, A(x) тоже будет истинна при x = d0 . Рассуждения при этом аналогичны предыдущему случаю. Если A(x)
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 10. Непротиворечивость исчисления предикатов
61
при некотором d0 ? D истинно, то ?xA(x) истинно на наборе
значений {d1 , d2 , . . . dn }, а тогда импликация тоже истинна.
Простейший пример показывает, что, если в аксиомах 11
и 12 не выполнены условия свободы подстановки t вместо x,
общезначимая формула может не получиться.
Пусть A(x) = ?tB(x, t). Для этой формулы подстановка t вместо x не свободна. Проверим, что формула
?x?tB(x, t) ? ?tB(t, t) не общезначима.
В качестве предметной области D рассмотрим двухэлементное множество: D = {a, b}. Таблицу значений для B(x, t)
определим так:
x
a
a
b
b
t
a
b
a
b
p(B(x, t))
0
1
1
0
Тогда, очевидно, A(x) = ?tB(x, t) в этой интерпретации
истинна и при x = a, и при x = b, значит, ?x?tB(x, t) истинное
высказывание. Но A(t) = ?tB(t, t) ложно, и вся импликация
ложна.
Т е о р е м а 10.2. Формулы ИП, полученные как непосредственные следствия общезначимых формул, тоже являются общезначимыми.
Д о к а з а т е л ь с т в о. В исчислении предикатов имеются три
правила вывода, которые и надо проверить. Насчет правила МР
известно, что из тавтологий выводятся тавтологии. Из этого
следует, что из общезначимых формул по правилу МР снова
получаются общезначимые формулы.
Рассмотрим ?-правило: из формулы C ? A(x) непосредственно выводится формула C ? ?xA(x); если C не содержит
свободных вхождений x (не зависит от x).
Пусть D произвольная предметная область, на ней задана некоторая интерпретация, и {x, y1 , y2 , . . . yn } список всех
свободных переменных формулы C ? A(x). Тогда формула
C ? ?xA(x) зависит от {y1 , y2 , . . . yn }. Подформула C тоже за-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
62
Гл. 10. Непротиворечивость исчисления предикатов
висит только от {y1 , y2 , . . . yn }. Пусть {d1 , d2 , . . . dn } некоторый
набор значений из области D.
Может быть два случая: либо формула ?xA(x) на этом наборе истинна, либо ложна. Если формула истинна, вся импликация
тоже истинна на наборе значений {d1 , d2 , . . . dn }.
Пусть формула ?xA(x) на указанном наборе ложна. По
определению интерпретации квантора всеобщности, это значит,
что существует такое d0 ? D, что формула A(x) на наборе
значений {d0 , d1 , d2 , . . . dn } ложна. Значение формулы C ? A(x)
на этом наборе истинно в силу общезначимости формулы. Но
если заключение импликации ложно, а вся импликация истинна, то условие тоже ложно, другими словами, C на наборе
{d0 , d1 , d2 , . . . dn } ложна. В силу того что C не зависит от x,
фактический набор значений для C {d1 , d2 , . . . dn }. Так как
C на этом наборе ложна, вся импликация C ? ?xA(x) истинна.
Рассуждения для ?-правила совершенно аналогичны.
Замечание. Пусть имеется набор формул T , T , . . . Tn, тож1
2
дественно истинных на одной фиксированной предметной области D. Тогда всякая формула F ИП, выводимая из этого набора,
также будет тождественно истинна на D.
Действительно, все аксиомы и формулы Ti , участвующие в
выводе F , тождественно истинны на D. Тогда и следствия из них
будут тождественно истинны на D. Этот факт устанавливается
такими же рассуждениями, как и в теореме 10.2.
Если формула F исчисления предикатов доказуема, то она общезначима. В стандартных обозначениях:
если ` F , то |= F .
Т е о р е м а 10.3.
Д о к а з а т е л ь с т в о. По теореме 10.1 все аксиомы ИП общезначимы. По теореме 10.2 следствия общезначимых формул общезначимы. Если формула F доказуема, существует ее формальное доказательство, то есть последовательность формул
из аксиом и непосредственных следствий предыдущих формул,
заканчивающаяся формулой F . В силу предыдущих замечаний
заключаем, что все формулы в формальном доказательстве общезначимы.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 10. Непротиворечивость исчисления предикатов
63
Свойство теории ИП, выраженное в теореме 3, называется
непротиворечивостью относительно общезначимости.
Отсюда следует внутренняя непротиворечивость теории.
Исчисление предикатов является внутренне
непротиворечивой теорией.
Т е о р е м а 10.4.
Д о к а з а т е л ь с т в о. По определению непротиворечивости, надо доказать, что для всякой формулы F хотя бы одно утверждение не выполнено: ` F или ` ¬F . Действительно, если F не
является доказуемой тогда все доказано; пусть F доказуема. Тогда F общезначима в силу теоремы 10.3. Тогда ¬F тождественно
ложна и потому не доказуема.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
11
НЕРАЗРЕШИМОСТЬ И ПОЛНОТА ИСЧИСЛЕНИЯ
ПРЕДИКАТОВ
Все заключения, полученные в предыдущей главе, совершенно аналогичны результатам о непротиворечивости для исчисления высказываний. Содержательная основа интерпретация
формул ИП до некоторой степени аналогична таблицам значений для формул ИВ.
Полной аналогии, однако, между исчислением высказываний
и исчислением предикатов нет, как, в частности, показывает следующая теорема, фактически сформулированная в предыдущей
главе.
Не существует алгоритма распознавания общезначимости формул исчисления предикатов.
Т е о р е м а 11.1 (А. Чјрч).
Доказательство теоремы на элементарном уровне изложить
невозможно. Действительно, доказать существование алгоритма
можно просто, предъявив какой-либо алгоритм. Для доказательства отсутствия алгоритма надо хотя бы иметь какое-то
ѕопределение алгоритмаї, чтобы знать, отсутствие чего требуется доказать. А вопрос определения порождает целую теорию
теорию алгоритмов, так как алгоритм первичное понятие.
Другими словами, даже вопрос корректного понимания формулировки отмеченной теоремы далеко не прост. Частично этот
факт дајт мотивировку дальнейшего изложения теории алгоритмов.
Во всяком случае, теорема Чјрча показывает, что не существует простого описания класса общезначимых формул, вроде
того критерия тождественной истинности, что был получен для
исчисления высказываний.
Напомним, теорию называют разрешимой, если существует алгоритм распознавания выводимости формулы из аксиом.
Конечно, это близко к теореме Чјрча, только там говорится о
распознавании общезначимости. Для исчисления высказываний
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 11. Неразрешимость и полнота исчисления предикатов
65
общезначимость (тавтологичность) и выводимость одно и то
же, в силу теоремы о полноте. Оказывается, что исчисление
предикатов тоже полно относительно общезначимости.
Если формула исчисления предикатов общезначима, то она доказуема. В принятых обозначениях: если |= F , то ` F .
Т е о р е м а 11.2 (К. Гјдель).
Доказательство зтой теоремы весьма сложно. В качестве первого шага использует приведение формулы к равносильной нормальной форме.
Следствие 11.1.
Для исчисления предикатов класс доказуемых формул и класс общезначимых формул совпадают.
Д о к а з а т е л ь с т в о. Применение теорем 10.3 и 11.2.
Замечание.
Как отмечалось, теорема Гјделя о полноте устанавливает полноту ИП относительно класса общезначимых формул. Этот результат аналогичен факту полноты исчисления
высказываний относительно тавтологий. Но для исчисления высказываний имеется и свойство внутренней полноты, согласно
которому добавление к системе аксиом любой недоказуемой схемы нарушает внутреннюю непротиворечивость теории.
Для исчисления предикатов свойства внутренней полноты
нет.
Действительно,
дополним
систему
аксиом
схемой
?xA ? ?xA. Эта схема недоказуема. Ранее отмечалось, что
она тождественно истинна на предметной области из одного
элемента, но, очевидно, не общезначима. В то же время
присоединение этой схемы к списку аксиом не приводит к
внутренней противоречивости: все аксиомы и эта формула
тождественно истинны на предметной области D из одного
элемента, и потому все следствия из них тоже тождественно
истинны на D в силу замечания к теореме 10.2.
Исчисление предикатов является неразрешимой теорией, теперь это следует из теоремы Чјрча и совпадения классов доказуемых и общезначимых формул. Поэтому теорему Чјрча
называют теоремой о неразрешимости ИП.
Как отмечалось, доказательство теоремы о неразрешимости
далеко выходит за рамки материала, изложенного к данному
3 Ю. А. Белов, В. А. Соколов
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
66
Гл. 11. Неразрешимость и полнота исчисления предикатов
моменту. Однако уже сейчас можно привести пример, показывающий, что для распознавания общезначимости недостаточно
конечных предметных областей. Этот пример до некоторой степени поясняет отсутствие алгоритма распознавания.
Существует формула ИП, являющаяся kобщезначимой для любого k, но не общезначимой.
Т е о р е м а 11.3.
Д о к а з а т е л ь с т в о. Рассмотрим формулу:
G = (?x¬P (x, x)) ? ?x?y?z(P (x, y) ? P (y , z) ?
P (x, z)) ? ?x?yP (x, y).
Формула G не содержит свободных переменных и при любой
интерпретации является высказыванием, истинным или ложным. Докажем, что при любой интерпретации на конечной области формуле G соответствует ложное высказывание.
Предположим противное: нашлась конечная предметная
область D и такая интерпретация, при которой G истинна.
Без ограничения общности будем считать, что D состоит
из трех элементов: D = {a, b, c}. Формула G использует
только одну предикатную букву P (x, y). Будем строить
таблицу значений P (x, y) (см. ниже), учитывая, что G
истинно. G состоит из трех конъюнктивных сомножителей:
?x¬P (x, x), ?x?y?z(P (x, y) ? P (y , z) ? P (x, z) и ?x?yP (x, y).
В силу истинности всей формулы каждый сомножитель тоже
истинный. Так как истинна формула ?x¬P (x, x), в первой, пятой
и девятой строках таблицы значений P (x, y) должно быть равно
0. Впишем эти значения в таблицу. В силу истинности формулы
?x?yP (x, y) и при x = a, и при x = b, и при x = c должно
быть хотя бы одно значение y , при котором P (x, y) равно 1.
Другими словами, в первых трех строках должна быть хотя бы
одна единица; в следующих трјх строчках (четвертой, пятой
и шестой) также хотя бы одна единица, в седьмой, восьмой,
девятой строках аналогично.
Так как в первой строке должен быть 0, имеются две возможности: или во второй, или в третьей строке значение P (x, y)
должно быть равно 1. Эти случаи совершенно одинаковы, считаем потому, что во второй строке значение P (x, y) равно 1.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 11. Неразрешимость и полнота исчисления предикатов
67
Впишем и его в таблицу. Теперь рассмотрим вторую формулу:
?x?y?z(P (x, y) ? P (y , z) ? P (x, z).
В силу ее истинности можно заключить, что, например,
в четвертой строке значение P (x, y) должно быть равно 0.
Действительно, предположим, что P (b, a) = 1. Тогда, в силу
P (a, b) = 1, P (b, a) = 1 и истинности импликации для любой
тройки значений, должно быть истинно заключение: P (a, a) = 1
противоречие. Значит, P (b, a) = 0. Впишем и этот результат
в таблицу. Теперь можно утверждать, что P (b, c) = 1, так как
хотя бы одна единица при x = b должна быть. Тогда аналогично
предыдущим рассуждениям P (c, b) = 0. Записав его в таблицу,
видим, что должно быть: P (c, a) = 1.
Теперь заметим, что в силу P (a, b) = 1 и P (b, c) = 1 из-за
истинности импликации можно заключить, что P (a, c) = 1.
Но тогда P (a, c) = 1 и P (c, a) = 1, откуда P (a, a) = 1 противоречие. Таким образом, предположение истинности G
противоречиво.
x
a
a
a
b
b
b
c
c
c
y
a
b
c
a
b
c
a
b
c
P (x, y)
0
1
?
0
0
1
1
0
0
Теоретически можно было бы проверить все возможные интерпретации P (x, y) на данном множестве D. Различных интерпретаций, то есть различных таблиц значений для P (x, y),
имеется 29 многовато для вычислений ѕвручнуюї. Кроме того,
оставался бы вопрос что делать с областями из четырех и
более элементов?
Сейчас этот вопрос тоже актуален но проведенные рассуждения можно строго оформить в виде математической индукции
по количеству элементов предметной области D.
Итак, при любой интерпретации в любой конечной предметной области формула G ложна.
3*
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
68
Гл. 11. Неразрешимость и полнота исчисления предикатов
Рассмотрим теперь интерпретацию G на множестве
натуральных чисел N = {0, 1, 2, . . . n, . . .}. Значения P (x, y)
определим таким образом: P (x, y) = 1 тогда и только
тогда, когда x < y . Тогда получаем, что ?x¬P (x, x) =
= 1 есть свойство иррефлексивности строгого неравенства.
Попросту сказать, для всякого x верно, что x не меньше
x. ?x?y?z(P (x, y) ? P (y , z) ? P (x, z) = 1) на N это в
точности свойство транзитивности, которое справедливо для
строгого неравенства натуральных чисел. Снова словесная
формулировка: для любых x, y , z если x < y и y < z , то x < z .
Последняя формула: ?x?yP (x, y) в данной интерпретации
утверждает, что для всякого x существует y , больший, чем x.
Это, если угодно, утверждение о бесконечности предметной
области. Во всяком случае, очевидно, что ?x?yP (x, y) = 1.
Тогда и вся формула G истинна на N .
Рассмотрим теперь формулу F = ¬G. В силу полученных
результатов F будет истинна при любой интерпретации на любой конечной предметной области, но она будет ложна при
указанной интерпретации на N .
Таким образом, для проверки формулы ИП на общезначимость недостаточно рассматривать только конечные предметные области, нужно еще рассматривать интерпретации формулы на бесконечных множествах D. В качестве маленького
ѕутешенияї можно отметить, что среди бесконечных областей
D достаточно рассмотреть только счјтное множество.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ЗАДАЧИ И УПРАЖНЕНИЯ II
32. Пусть задана предметная область D = {a, b, c} из трјх
предметов и формула ?y(?xA(x, y , z) ? ?tB(y , t)). Перечислить
интерпретации данной формулы на данной области, не являющиеся тождественно ложными.
33. Доказать, что формула
?x?y(A(x, y) ? (A(x, x) ? A(y , y)))
истинна в любой предметной области, имеющей не более трјх
элементов.
34. Построить 2-общезначимую, но не общезначимую формулу ИП.
35. Пусть задана предметная область D = N , где N =
= {0, 1, . . .} множество натуральных чисел, и на ней определены два предиката S(x, y , z) и P (x, y , z). S(x, y , z) = 1 тогда и
только тогда, когда x+y = z , P (x, y , z) = 1 тогда и только тогда,
когда xy = z .
Используя связки ИП, записать формулы с одной свободной
переменной x, истинные в D тогда и только тогда, когда x = 0;
когда x чјтно; когда x простое число.
Записать формулы с двумя свободными переменными x и y ,
истинные тогда и только тогда, когда x 6 y ; когда x < y ; когда
x является делителем y .
Записать формулы с тремя свободными переменными x, y , z ,
истинные в D тогда и только тогда, когда z наибольший общий
делитель x и y ; когда z наименьшее общее кратное x и y .
Записать замкнутые (т. е. не содержащие свободных переменных) формулы, утверждающие коммутативность сложения
в области D; ассоциативность умножения в области D; бесконечность множества простых чисел в D.
Построить замкнутую формулу, утверждающую дистрибутивность умножения относительно сложения.
Построить замкнутую формулу, утверждающую,что каждое
число из D является суммой четырјх квадратов.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
70
Задачи и упражнения II
Построить замкнутую формулу, утверждающую,что каждое
число из D является суммой двух квадратов.
Построить замкнутую формулу, утверждающую,что в D
множество простых чисел конечно.
Построить замкнутую формулу, утверждающую,что в D существует наибольшее число.
Построить замкнутую формулу, утверждающую,что в D не
существует наименьшего числа.
Построить замкнутую формулу, утверждающую,что в D всякое чјтное число, большее двух, является суммой двух простых.
Построить замкнутую формулу, утверждающую,что в D существует бесконечное множество простых чисел-близнецов.
Что можно сказать об истинности данных утверждений в D?
36. Пусть задана предметная область D = B(M ), где M
некоторое непустое множество, B(M ) его булеан. Пусть
на D задан предикат Q(x, y), равный 1 тогда и только тогда,
когда x ? y . Записать формулы ИП с использованием Q и трјх
свободных переменных x, y , z , которые будут истинны тогда и
только тогда, когда x = y ? z ; когда x = y ? z .
Записать формулу от двух свободных переменнных x и y ,
истинную тогда и только тогда, когда x = y? .
Построить формулу от одного свободного переменного x,
истинную тогда и только тогда, когда x = ?.
37. Построить выводы следующих формул:
?x?yA(x, y) ? ?y?xA(x, y)
?x?yA(x, y) ? ?y?xA(x, y)
?x?yA(x, y) ? ?y?xA(x, y)
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
РЕШЕНИЯ, УКАЗАНИЯ, ОТВЕТЫ
1. Указание. Два раза применить МР и теорему о дедукции
к следующему набору условий:
A ? B, B ? C , A
3. Решение.
1.
2.
3.
4.
5.
6.
7.
8.
A ? B, A ` B
B ` B?C
A ? B, A ` B ? C
A ? B, C ` C
C ` B?C
A ? B, C ` B ? C
A ? B, A ? C ` B ? C
A ? B ` (A ? C) ? (B ? C)
;
;
;
;
;
;
;
;
МП
введение дизъюнкции
т. о транз. выводимости 1, 2
тождественно
введение дизъюнкции
т. о транзитивности 4, 5
удаление дизъюнкции 3, 6
MP 7
Замечание. Решение задачи 3 дано в виде последовательности некоторых утверждений о выводимости, каждое из которых снабжено комментарием обоснованием. Эта форма соответствует ранее указанным требованиям. Предполагается, что
решения других задач о выводимости должны оформляться в
таком же виде.
5. Решение.
1.
2.
3.
4.
A ? ¬B , B , A ` B
A ? ¬B , B , A ` ¬B
A ? ¬B , B ` ¬A
A ? ¬B ` B ? ¬A
;
;
;
;
тождественно
MP
введение отрицания 1, 2
т. о дедукции 3
7. Решение.
1. A, ¬A ` A
2. A, ¬A ` ¬A
3. A ` ¬¬A
; тождественно
; тождественно
; введение отрицания 1, 2
9. Указание. Смотрите лемму 5.2 (о законе исключјнного
третьего).
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
72
Решения, указания, ответы
10. Решение.
1.
2.
3.
4.
5.
6.
7.
8.
B`A?B
A ? B ` (A ? B) ? (B ? A)
B ` (A ? B) ? (B ? A)
¬B ` B ? A
B ? A ` (A ? B) ? (B ? A)
¬B ` (A ? B) ? (B ? A)
B ? ¬B ` (A ? B) ? (B ? A)
` (A ? B) ? (B ? A)
;
;
;
;
;
;
;
;
введение импликации
введение дизъюнкции
т. о транзитивности 1. 2
лемма о противоречии
введение дизъюнкции
т. о транзитивности 4, 5
удаление дизъюнкции 3, 6
т. о транз., задача 9, 7
12. Указание. Докажем следующее утверждение:
¬A ? B ` A ? B
1. ¬A, A ` B
; лемма о противоречии
2. B , A ` B
; тождественно
3. ¬A ? B , A ` B
; удаление дизъюнкции 1, 2
4. ¬A ? B ` A ? B ; т. о дедукции 3
Для полного решения задачи требуется еще установить выводимость в обратном направлении, что предлагается для самостоятельного решения.
14. Указание. ѕНабросокї вывода в одном направлении:
1. A ? B ` A, A ? B ` B
2. ¬A ` ¬(A ? B), ¬B ` ¬(A ? B)
3. ¬A ? ¬B ` ¬(A ? B)
; ?-удаление
; л. о противополож. теор.
; ?-удаление
18. Указание. Рассмотрим для примера монотоннность дизъюнкции. Для этого требуется доказать, что если A ` B , то
X ? A ` X ? B . Это утверждение легко следует из утверждения задачи 3. К аналогичным простым задачам о выводимости
сводятся и остальные утверждения о монотонности.
19. Указание. Индукция по количеству связок в формуле F .
20. Указание. Пусть G подформула F и H равносильна G .
Можно провести индукцию относительно количества k логических связок формулы F , расположенных вне G .
Если k равно 0, то F = G , F1 = H, и всј доказано. Если k >
> 0, то F имеет вид F = (A ? B) или аналогичный с конъюнкцией, импликацией или отрицанием в качестве последней связки.
Тогда подформула G является также подформулой A или B .
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Решения, указания, ответы
73
Для определјнности можно считать, что G подформула A.
По предположению индукции можно считать, что A ? A1 , где
A1 получена из A заменой G на H. При этом, конечно, F1 =
= (A1 ? B). Теперь для доказательства равносильности F и F1
достаточно сослаться на результат задачи 18 монотонность
дизъюнкции.
21. Решение. Легко проверить, что все аксиомы системы ИВ2
являются тождественно истинными. Поэтому все доказуемые в
ИВ2 формулы также являются тождественно истинными, что
доказывается так же, как и для системы ИВ. Напомним, что
в системе ИВ доказуемы тождественно истинные формулы и
только они. Это значит, что все формулы, доказуемые в ИВ2,
доказуемы и в исходной системе ИВ. Остајтся доказать обратное
включение, что все тождественно истинные формулы доказуемы
в системе ИВ2. Для этого достаточно доказать, что формула
A ? (B ? A ? B), исключјнная из списка аксиом, доказуема в
системе ИВ2. Действительно, если выводимость из аксиом ИВ2
этой формулы будет доказана, то формулой можно будет пользоваться при построении любых выводов наряду с остальными
аксиомами. Для доказательства указанной формулы сначала
отметим, что в системе ИВ2 справедлива теорема о дедукции,
так как еј доказательство использует только две первые аксиомы, одинаковые для систем ИВ и ИВ2. Установим для ИВ2
следующее отношение выводимости:
A, B ` A ? B.
В системе ИВ2 не доказаны теорема о десяти правилах и
лемма о противоположной теореме, и потому нет возможности
оформить вывод, как в задаче 3. Строим непосредственный
вывод согласно определению.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
74
1.
2.
3.
4.
5.
Решения, указания, ответы
; условие 1
; условие 2
; аксиома 1
; МР 2, 3
; доказательство
сохраняется и
для ИВ2
6. (A ? A) ? ((A ? B) ? (A ? A ? B)) ; частный случай
новой аксиомы 3
7. (A ? B) ? (A ? A ? B)
; МР 5, 6
8. A ? A ? B
; МР 4, 7
9. A ? B
; МР 1, 8
Теперь к полученному отношению выводимости дважды применяем теорему о дедукции и получаем, что в ИВ2 доказуема
формула A ? (B ? A ? B), что, как отмечалось, достаточно
для решения задачи.
22. Решение. Рассуждая так же, как в предыдущей задаче,
получаем, что достаточно доказать в системе ИВ3 исключјнную
аксиому:
(A ? B) ? ((A ? ¬B) ? ¬A).
A
B
B ? (A ? B)
A?B
A?A
Для системы ИВ3 справедлива теорема о дедукции, ¬¬X ? X
и верна лемма о противоположной теореме (л. п. т.).
Действительно, теорема о дедукции доказывается одинаково
для ИВ и для ИВ3, равносильность X и двойного отрицания
X следует из аксиомы удаления отрицания и второй новой аксиомы, л. п. т. легко следует из теоремы о дедукции и первой
введјнной аксиомы.
Имея эти инструменты, докажем в ИВ3 следующее отношение выводимости:
A ? B , A ? ¬B ` ¬B.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Решения, указания, ответы
75
1. A, A ? ¬B ` ¬B
; МР
2. A, ¬¬B ` ¬(A ? ¬B)
; л. п. т. 1
3. A, B ` ¬(A ? ¬B)
; снятие двойного отрицания 2
4. A, A ? B ` ¬(A ? ¬B)
; МР и т. транзитивности
5. A ? B , ¬¬(A ? ¬B) ` ¬A ; л. п. т. 4
6. A ? B , A ? ¬B ` ¬A
; снятие двойного отрицания 5
Теперь, дважды применив теорему о дедукции к полученному
отношению, получаем, что в ИВ3 доказуема аксиома, исключјнная из списка.
23. Указание. Как и в предыдущих двух задачах, достаточно доказать, что исключјнные аксиомы доказуемы в ИВ4.
Для этого достаточно доказать, что исключјнная аксиома введения конъюнкции доказуема в ИВ4. Это доказывается точно
так же, как в задаче 21. После этого можно утверждать, что все
аксиомы ИВ3 доказуемы в системе ИВ4, а это значит, что все
тождественно истинные формулы доказуемы в системе ИВ4.
24. Решение. Для доказательства независимости аксиомы
удаления отрицания применим ту же идею идею инварианта,
что и для доказательства непротиворечивости ИВ. Сопоставим
каждой логической связке некоторую булеву функцию. Тогда
и каждой формуле исчисления будет соответствовать некоторая функция. Сопоставление построим так, чтобы все аксиомы,
кроме последней, были тождественно истинны и чтобы формула, выводимая из тождественно истинных формул, также была
тождественно истинна. При этом ясно, что последняя аксиома,
не будучи тождественно истинной, не может быть выведена из
остальных (тождественно истинных) аксиом. Сопоставим всем
логическим связкам, кроме отрицания, их стандартные булевы
функции. Отрицанию сопоставим тождественную единицу, то
есть считаем, что отрицание 0 есть 1 и отрицание 1 есть 1.
Ясно, что все аксиомы, кроме двух последних, будут при этом
тождественно истинными, так как они не содержат отрицания.
Аксиома 9 введение отрицания тоже, как легко проверить,
тождественно истинна, а последняя аксиома нет.
25. Указание. Доказательство независимости каждой из указанных аксиом проводится по той же схеме, как в предыдущей
задаче. Все логические связки, кроме одной, определяются как
в булевой алгебре, одна связка определяется по-другому. Дадим
таблицу, в первом столбце которой указана аксиома, чья незави-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
76
Решения, указания, ответы
симость доказывается, во втором определяется исключительная связка, в третьем столбце указаны значения переменных,
при которых проверяемая аксиома принимает значение 0:
Аксиома
A?B ?A
A?B ?B
A ? (B ? A ? B)
A?A?B
B ?A?B
(A ? C) ?
((B ? C) ? (A ? B ? C))
(A ? B) ? ((A ? B) ? A)
A?A
Искл.
A?B
A?B
A?B
A?B
A?B
A?B
A=0
A=1
операция
=B
=A
=B
=A
=1
Значения
A = 0, B = 1
A = 1, B = 0
A = 1, B = 1
A = 1, B = 0
A = 0, B = 1
A = 0, B = 0
C=0
A = 0, B = 1
A=0
Замечание. Две первые аксиомы также независимы, однако
при доказательстве их независимости каждой логической связке
сопоставляется функция, принимающая четыре значения, а не
только 0 и 1. Отметим, что для решения задач 30 и 31 также
требуется сопоставлять логическим связкам функции, принимающие больше двух значений.
26. Указание. Проверить, что доказательство теоремы о дедукции, имеющееся для ИВ, сохраняется и для ИИВ.
Действительно, доказательсто использует только две первые
аксиомы, совпадающие для формальных теорий ИВ и ИИВ.
27. Указание. Доказательсто леммы о транзитивности импликации без изменений сохраняется для ИИВ.
28. Решение. С учетом справедливости для ИИВ теоремы о
дедукции (задача 26) достаточно доказать в ИИВ следующее
отношение выводимости:
A ` ¬¬A.
Излагаем требуемый вывод:
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Решения, указания, ответы
77
1. A
2. A ? (¬A ? A)
3. ¬A ? A
4. ¬A ? ¬A
5. (¬A ? A) ? ((¬A ? ¬A) ? ¬¬A)
6. (¬A ? ¬A) ? ¬¬A
7. ¬¬A
; условие
; аксиома ИИВ введение импликации
;
; МР 1, 2
; аксиома ИИВ введение отрицания
; МР 3, 5
; МР 4, 6
29. Решение. С учетом справедливости для ИИВ теоремы о
дедукции (задача 26) достаточно доказать в ИИВ следующее
отношение выводимости: A ? B , ¬B ` ¬A. Строим вывод:
1.
2.
3.
4.
5.
6.
7.
A?B
¬B
¬B ? (A ? ¬B)
A ? ¬B
(A ? B) ? ((A ? ¬B) ? ¬A)
(A ? ¬B) ? ¬A
¬A
;
;
;
;
;
;
;
условие 1
условие 2
аксиома ИИВ
МР 2, 3
аксиома ИИВ
МР 1, 5
МР 4, 6
Замечание. В приведјнном выводе не использована новая
аксиома ИИВ, поэтому он является выводом и в ИВ.
30. Решение. Сопоставим каждой логической связке функцию, принимающую три значения 0, 1, 2:
X
0
0
0
1
1
1
2
2
2
Y
0
1
2
0
1
2
0
1
2
X ?Y
0
0
0
0
1
1
0
1
2
X ?Y
0
1
2
1
1
2
2
2
2
X?Y
2
2
2
0
2
2
0
1
2
Для отрицания считаем, что отрицание нуля есть два, а отрицание единицы и двух равны нулю. Теперь и любой формуле
ИИВ можно сопоставить функцию, принимающую три значе-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
78
Решения, указания, ответы
ния. Просто проверить, что все аксиомы ИИВ тождественно
равны двум, а формула ¬¬A ? A при A = 1 равна 1. Кроме
того, также легко увидеть из приведјнной таблицы, что из двух
формул, равных двум, по правилу вывода МР также получится
формула, равная двум. Другими словами, сохранение двойки
наследуется при выводе из аксиом.
Замечание. В задаче попутно дано другое доказательство
независимости последней аксиомы ИВ, то есть другое решение
задачи 24, так как здесь доказано, что десятая аксиома не выводится не только из девяти остальных, но даже из девяти и ещј
одной новой.
Из приведјнной таблицы следует также внутренняя непротиворечивость ИИВ. Свойством внутренней полноты ИИВ не
обладает, что также следует из результата задачи.
31. Указание. Полностью используется решение предыдущей
задачи.
32. Указание. Перебор.
33. Решение. Например:
?x(A(x) ? ¬B(x)) ? ?x(B(x) ? ¬A(x)) ? ?y(A(y) ? B(y)).
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Часть 2
ЭЛЕМЕНТЫ ТЕОРИИ
АЛГОРИТМОВ
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
12
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
алгоритмов
Первые примеры
встречаются уже в средней
школе: алгоритм сложения натуральных чисел столбиком, алгоритм умножения двух натуральных чисел, алгоритм деления
с остатком, процесс нахождения наибольшего общего делителя
двух целых чисел, известный под названием
. Из других алгоритмов можно указать алгоритм разложения натурального числа на простые множители, извлечения
квадратного корня из натурального числа, решения системы
линейных уравнений методом Гаусса и т. д. Каждый из этих алгоритмов представляет собой некоторую вычислительную процедуру, выполнение которой не требует изобретательности или
сообразительности, а состоит лишь в строгом следовании инструкциям.
Общие черты алгоритмов:
клида
алгоритма Ев-
1.
Дискретность. Алгоритм это процесс последователь-
2.
Детерминированность.
3.
Элементарность шагов. Закон получения последующего
ного построения объектов, идущий в дискретном времени
так, что в начальный момент задается исходный набор
объектов, а в каждый следующий момент из набора объектов, имевшихся в предыдущий момент, по определенному
закону (программе) получается новый набор объектов. Выполнение всякого алгоритма состоит из отдельных шагов.
Каждый шаг обязательно завершается. Если выполнение
алгоритма никогда не закончится, это означает, что алгоритм совершает бесконечное число шагов.
Набор объектов, получаемых в
какой-то момент, однозначно определяется набором объектов, полученных в предшествующие моменты.
набора объектов из предшествующего должен быть простым и локальным.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 12. Основные понятия теории алгоритмов
4.
5.
81
Направленность. Должно быть указано, что надо считать
результатом алгоритма.
Массовость. Начальный набор объектов может выбираться из потенциально бесконечного множества множества
возможных исходных данных этого алгоритма. При этом
исходными данными для алгоритма могут быть лишь так
называемые конструктивные объекты. Интуитивно, кон-
структивный объект это такой объект, который построен
(сконструирован) из некоторых исходных элементарных
неделимых элементов фиксированного точно очерченного
конечного множества по фиксированным правилам, так
что строение этого объекта может быть полностью описано некоторым текстом на подходящем языке. Если фиксированы набор исходных элементов и правила конструирования объектов из них, говорят, что задан
.
ансамбль
конструктивных объектов
Типичным примером ансамбля конструктивных объектов является множество слов в данном конечном
. При этом
исходными элементами являются
алфавита, а способ конструирования состоит в построении конечных цепочек букв,
т. е.
. В частности, множество натуральных чисел N =
= {0, 1, 2, ...} может рассматриваться как ансамбль конструктивных объектов, ибо натуральные числа можно изображать,
например, словами в однобуквенном алфавите {|}: 0 пустое
слово; 1 слово |; 2 слово || и т. д. Множества целых и рациональных чисел также могут рассматриваться как ансамбли
конструтивных объектов.
Всякий ансамбль конструктивных объектов счетен. Более того, его всегда можно эффективно занумеровать, т. е. установить
такое взаимно однозначное соответствие между ансамблем конструктивных объектов и множеством натуральных чисел, что
по любому объекту можно вычислить его номер, а по любому
натуральному числу n можно эффективно построить объект с
номером . Свойство эффективной нумеруемости мы примем
за основной признак ансамбля конструктивных объектов. Итак,
множество возможных исходных данных любого алгоритма это некоторый ансамбль конструктивных объектов.
буквы
слов
n
алфавите
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
82
Гл. 12. Основные понятия теории алгоритмов
Понятие алгоритма, определяемое требованиями 15, не
строгое. Это нестрогое понятие алгоритма обычно называется
понятием алгоритма.
При применении данного алгоритма к исходному данному
возможны следующие три варианта. 1. Применение алгоритма
к исходному данному завершится через конечное число шагов, и
алгоритм выдаст результат. В этом случае говорят, что алгоритм
применим к исходному данному. 2. Применение алгоритма к
исходному данному завершится через конечное число шагов,
но алгоритм не выдаст никакого результата. 3. Применение
алгоритма к исходному данному никогда не закончится, т. е.
алгоритм совершает бесконечное число шагов. В случаях 2 и
3 говорят, что алгоритм не применим к исходному данному.
Множество возможных исходных данных, к которым алгоритм
применим, называется
алгоритма.
Пусть X множество возможных исходных данных алгоритма A, а его результаты принадлежат ансамблю конструктивных объектов Y . Пусть D ? X область применимости алгоритма A. Будем говорить, что алгоритм A
f : D ?? Y , которая каждому x ? D сопоставляет результат
применения алгоритма A к x.
будем называть любую функцию f : D ?? Y , где D ? X .
Таким образом, каждый алгоритм с множеством возможных исходных данных X , результаты которого принадлежат ансамблю
конструктивных объектов Y , вычисляет некоторую частичную
функцию из X в Y.
В дальнейшем мы будем иметь дело с выражениями (частичными именными формами), в которых встречаются обозначения
для частичных функций и которые, следовательно, определены
не при всех значениях свободных переменных. В связи с эти
мы будем употреблять символ условного равенства ' и будем
считать, что предложение s ' t истинно при тех значениях
свободных переменных, при которых оба выражения s и t определены и имеют одинаковые значения или же оба не определены.
Интуитивное понятие алгоритма удовлетворяло математиков до тех пор, пока возникающие в математике проблемы,
требующие нахождения алгоритма для решения некоторой совокупности родственных задач (или алгоритмические проблемы), удавалось решить путем указания конкретных алгоритмов.
интуитивным
областью применимости
вычисляет функцию
Частичной функцией из X в Y
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 12. Основные понятия теории алгоритмов
83
Но в XX в. положение изменилось на первый план выдвинулись алгоритмические проблемы, положительное решение которых было сомнительным. Среди них так называемая 10-я
проблема Гильберта о разрешимости алгебраических уравнений
в целых числах. Чтобы доказать несуществование алгоритма,
надо иметь точное определение понятия алгоритма. Математические уточнения понятия алгоритма были получены в середине
тридцатых годов XX в. в работах Д. Гильберта, К. Геделя,
А. Черча, С. Клини и Э. Поста.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
13
МАШИНА ТЬЮРИНГА
Э. Пост (1936) и А. Тьюринг (1937) независимо друг от
друга предложили уточнение понятия алгоритма как процесса,
который может совершаться подходяще устроенной ѕмашинойї.
Машины, введенные Постом и Тьюрингом, отличались не очень
существенно и в дальнейшем стали называться машинами Тьюринга. Мы рассмотрим вариант машин Тьюринга, близкий к
тому, который был предложен Постом.
Машина Тьюринга содержит следующие части:
1.
Конечная лента, разбитая на конечное число клеток (или
ячеек). В процессе работы машины к ленте могут пристраиваться новые ячейки, так что лента может считаться потенциально бесконечной. В каждой ячейке ленты записан
(или содержится) один из конечного числа символов, составляющих
A = {a0 , a1 , ..., am }. Клетки, в которых записан символ a0 , обычно обозначаемый 0,
называются пустыми. Все вновь пристраиваемые ячейки
являются пустыми.
внешний алфавит
2.
Внутренняя память
некоторое устройство, которое в
каждый момент находится в одном из конечного числа ѕсостоянийї, составляющих внутренний алфавит Q =
= {q0 , q1 , ..., qn }. Состояние q0 называется
состоянием.
ным
3. Управляющая головка
заключитель-
некоторое устройство, которое
может перемещаться вдоль ленты так, что в каждый момент находится в определенной ячейке или ѕобозреваетї
эту ячейку.
4.
Механическое устройство, которое в зависимости от содержимого обозреваемой ячейки и состояния внутренней
памяти может изменить состояние внутренней памяти и
при этом либо изменить содержимое обозреваемой ячейки,
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 13. Машина Тьюринга
85
либо сдвинуть управляющую головку в соседнюю ячейку
слева или в соседнюю ячейку справа. Если управляющая
головка находится в крайней ячейке и должна сдвинуться
в отсутствующую соседнюю ячейку, то машина пристраивает недостающую пустую ячейку.
Машинным словом машины Тьюринга (или конфигурацией )
называется слово
aj1 aj2 ...qi ajk ...ajr ,
содержащее совокупность всех данных о состоянии машины
в данный момент: aj1 aj2 ...ajk ...ajr последовательность букв,
записанных в ячейках ленты, qi внутреннее состояние, номер обозреваемой ячейки.
Работа машины состоит в последовательном переходе от одной конфигурации к другой в результате выполнения одного из
следующих действий:
k
1. Имея внутреннее состояние qi и обозревая ячейку, в которой записан символ aj , машина переводит внутреннюю
память в состояние qs и одновременно заменяет символ
в обозреваемой ячейке на ar . Это действие выражается
командой
qi aj ?? qs ar .
2. Имея внутреннее состояние qi и обозревая ячейку, в которой записан символ aj , машина переводит внутреннюю
память в состояние qs и одновременно передвигает управляющую головку в соседнюю ячейку справа. Это действие
выражается командой
qi aj ?? qs R.
3. Имея внутреннее состояние qi и обозревая ячейку, в которой записан символ aj , машина переводит внутреннюю
память в состояние qs и одновременно передвигает управляющую головку в соседнюю ячейку слева. Это действие
выражается командой
qi aj ?? qs L.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
86
Гл. 13. Машина Тьюринга
Совокупность всех команд, которые может выполнять машина,
называется ее
. Для каждого незаключительного
внутреннего состояния qi и каждого символа aj из внешнего
алфавита программа должна содержать ровно одну команду,
начинающуюся с qi aj .
Выполнение каждой из команд может быть описано как процесс построения конфигурации m0 по заданной конфигурации m.
Пусть ?,? некоторые алфавиты, не содержащие символ
a0 , F частичная -местная функция, определенная на некотором подмножестве множества ?? всех слов в алфавите ? и
со значениями в множестве ?? . Будем говорить, что данная
машина Тьюринга
, если ее внешний алфавит включает алфавиты ?,?, и каковы бы ни были слова
?1 , ..., ?n в алфавите ?, если значение F (?1 , ..., ?n ) определено,
то эта машина перерабатывает конфигурацию q1 0?1 0...0?n в
конфигурацию 0...0q0 0?0...0, причем F (?1 , ..., ?n ) = ?, а если
значение F (?1 , ..., ?n ) не определено, то в процессе переработки
конфигурации q1 0?1 0...0?n машина никогда не придет в заключительное состояние. Функция F называется
, если существует машина Тьюринга, которая вычисляет функцию F .
Натуральные числа изображаются как слова в однобуквенном алфавите {|}, так что можно считать определенным понятие
вычислимой по Тьюрингу частичной числовой функции.
программой
n
вычисляет функцию F
вычислимой по
Тьюрингу
Задачи
Построить машины Тьюринга, вычисляющие следующие
функции:
1. s(x) = x + 1;
2. o(x) = 0;
n (x , ..., x ) = x
3. Im
1
n
m
(1 6 m 6 n);
4. x + y ;
(
x ? 1, если x > 0;
5. p(x) =
0,
если x = 0;
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 13. Машина Тьюринга
(
1, если
6. sg(x) =
0, если
(
0, если
7. sg(x) =
1, если
(
x ? y,
8. d(x, y) =
0,
9. x ? y ;
10. x/2;
11. [x/2] .
x > 0;
x = 0;
x > 0;
x = 0;
если x > y ;
если x < y;
87
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
14
ЧАСТИЧНО-РЕКУРСИВНЫЕ ФУНКЦИИ
С помощью машин Тьюринга мы получили некоторое уточнение понятия вычислимой частичной функции из множества
?? в множество ?? для произвольных алфавитов ? и ?. В
частности, мы имеем понятие вычислимой по Тьюрингу числовой функции, т. е. частичной многоместной функции из N в
N . Посредством C (n) будем обозначать класс всех вычислимых
по Тьюрингу частичных функций из N n в N . Вместо C (1) будем
писать просто C .
Насколько хорошо понятие функции, вычислимой по Тьюрингу, соответствует интуитивному понятию вычислимой функции? В настоящее время известно много других формальных
описаний вычислимых функций. Оказалось, что все они задают
один и тот же класс -местных вычислимых частичных числовых функций, совпадающий с C (n) . Кроме того, до сих пор никому не удалось привести пример вычислимой функции, которая
не была бы вычислима по Тьюрингу. Это, а также многие другие наблюдения позволили сформулировать следующий тезис,
обычно называемый
: для любой вычислимой
частичной функции из ?? в ?? существует машина Тьюринга, которая вычисляет эту функцию. В частности, интуитивно
понимаемый класс -местных вычислимых частичных числовых
функций совпадает с C (n) . Заметим, что тезис Чјрча невозможно
ни доказать, ни опровергнуть, так как понятие вычислимой
функции не имеет строгого математического определения. Таким образом, тезис Чјрча это своего рода естественно-научная
гипотеза, подтверждаемая математическим опытом.
Классы C (n) ( = 1, 2, . . .) допускают и другое, внутреннее
описание, которое полезно знать всякому, кто изучает теорию
алгоритмов.
Следующие тотальные (т. е. всюду определенные) числовые
функции будем называть простейшими, или
: s(x) =
n (x , ..., x ) = x (1 6 m 6 n). Очевидно, что
= x + 1; o(x) = 0; Im
1
n
m
n
тезисом Чјрча
n
n
базисными
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 14. Частично-рекурсивные функции
89
все базисные функции вычислимы. Более того, решив задачи
1)3) из главы 13, мы доказали, что все они вычислимы по
Тьюрингу.
Будем говорить, что -местная (n > 1) частичная функция
получается с помощью
из -местной
функции f и -местных функций g1 , ..., gk , если для любых
x1 , ..., xn ? N имеет место условное равенство
n
h
n
операции подстановки
k
h(x1 , ..., xn ) ' f (g1 (x1 , ..., xn ), ..., gk (x1 , ..., xn )).
Например, функция f (x) = 1 получается операцией подстановки
из функций s(x) и o(x). Функция
f (x, y , z) = z + 1
получается подстановкой из функций s(x) и I33 (x, y , z). Очевидно, что если функции f , g1 , ..., gk всюду определены, то h
тотальная функция. Кроме того, если функции f , g1 , ..., gk
вычислимы, то и функция h вычислима.
Скажем, что (n + 1)-местная (n > 1) частичная функция
h получается с помощью
из -местной
функции f и (n+2)-местной функции g , если для любых
x1 , ..., xn , y ? N выполняются следующие условные равенства:
операции рекурсии
n
h(x1 , ..., xn , 0) ' f (x1 , ..., xn );
n
h(x1 , ..., xn , y + 1) ' g(x1 , ..., xn , y , h(x1 , ..., xn , y)).
Для = 0 операция рекурсии определяется следующим образом. Одноместная частичная функция получается операцией
рекурсии из двуместной частичной функции и натурального
числа a, если для любого натурального y выполняются условные
равенства:
h(0) = a;
h
g
h(y + 1) ' g(y , h(y)).
Например, функция h(x, y) = x + y получается рекурсией из
функций I11 (x) и g(x, y , z) = z + 1. Очевидно, что если функция
h получается рекурсией из вычислимых функций f и g , то и
функция h вычислима. Кроме того, если функции f и g всюду
определены, то h тотальная функция.
Функция называется
, если она может быть получена из базисных функций с помощью конечного
примитивно-рекурсивной
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
90
Гл. 14. Частично-рекурсивные функции
числа применений операций подстановки и рекурсии. Иными
словами, функция f является примитивно-рекурсивной, если
существует конечная последовательность функций f0 , ..., fn , в
которой каждая функция fi (i 6 n) либо является базисной,
либо получается из каких-нибудь предшествующих функций с
помощью подстановки или рекурсии, и при этом fn есть функция f . Как показывают приведенные выше примеры, функции
f (x) = 1, g(x, y) = x + y являются примитивно-рекурсивными.
Из отмеченных выше свойств операций подстановки и рекурсии
немедленно следует, что всякая примитивно-рекурсивная функция вычислима и является тотальной.
Будем говорить, что -местная (n > 1) частичная функция получается с помощью
(или µоператора) из (n + 1)-местной частичной функции , если для
любых x1 , ..., xn , y ? N значение g(x1 , ..., xn ) определено и равно
y тогда и только тогда, когда для любого z < y значение
f (x1 , ..., xn , z) определено и не равно 0, а f (x1 , ..., xn , y) = 0. В
этом случае пишут
n
g
операции минимизации
f
g(x1 , ..., xn ) ' µy[f (x1 , ..., xn , y) = 0].
Заметим, что если функция g получается операцией минимизации из вычислимой функции f , то g также вычислима, однако
она может оказаться не тотальной, даже если функция f всюду
определена.
Функция называется
, если она может
быть получена из базисных функций с помощью конечного числа применений операций подстановки, рекурсии и минимизации.
Иными словами, функция f является частично-рекурсивной,
если существует конечная последовательность функций, заканчивающаяся функцией f , в которой каждая функция либо является базисной, либо получается из предыдущих функций с
помощью операций подстановки, рекурсии или минимизации.
Тотальные частично-рекурсивные функции называются общерекурсивными.
частично-рекурсивной
Класс всех n-местных частично-рекурсивных
функций совпадает с классом C (n) функций, вычислимых по
Тьюрингу.
Т е о р е м а 14.1.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 14. Частично-рекурсивные функции
91
Эта теорема доказывается довольно рутинным способом. Мы
этого делать не будем. Заметим лишь, что в силу тезиса Чјрча
понятие частично-рекурсивной функции может рассматриваться как еще одно уточнение понятия вычислимой числовой функции.
Задачи
1. Доказать, что если функция f (x1 , ..., xn ) примитивнорекурсивна, то примитивно-рекурсивна также функция
g(x1 , ..., xn ) = f (x?(1) , ..., x?(n) ), где ? произвольная тотальная
функция из {1, ..., n} в {1, ..., n}.
2. Доказать, что если функцияf (x1 , ..., xn ) примитивнорекурсивна, то примитивно-рекурсивна также функция
h(x1 , ..., xn , xn+1 ) = f (x1 , ..., xn ).
3. Доказать, что следующие функции примитивно-рекурсивны:
1. f (x, y) = x · y ;
2. f (x, y) = xy (здесь 00 = 1);
3. f (x) = x! (здесь 0! = 1);
(
1, если x > 0;
4. sg(x) =
0, если x = 0;
(
0, если x > 0;
5. sg(x) =
1, если x = 0;
(
x ? 1, если x > 0;
6. p(x) =
0, если x = 0;
(
x ? y , если x > y ;
7. d(x, y) =
0, если x < y ;
8. |x ? y|;
9. max(x, y);
10. min(x, y).
4. Доказать, что следующие
функции частично-рекурсивны:
?
y
а) x ? y ; б) x/y ; в) x; г) x/2; д)[x/2].
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
15
МАШИНА С НЕОГРАНИЧЕННЫМИ РЕГИСТРАМИ
Рассмотрим еще одно уточнение интуитивного понятия алгоритма, работающего с натуральными числами.
(МНР) это своего рода идеализированный компьютер. МНР имеет бесконечно
много регистров R1 , R2 , R3 , ..., в каждом из которых в любой
момент времени записано некоторое натуральное число. Число,
содержащееся в регистре Rn , мы будем обозначать rn . Содержимое регистров может меняться при выполнении некоторой
команды. Конечный список команд образует программу. Команды бывают следующих четырех типов:
Машина с неограниченными регистрами
1.
Команда обнуления имеет вид Z(n)(n ? {1, 2, 3, ...}).
Выполнение такой команды заменяет содержимое регистра Rn на 0, не затрагивая другие регистры.
Команда прибавления единицы
2.
имеет вид S(n), где
n ? {1, 2, 3, ...}.
Выполнение такой команды увеличивает содержимое
регистра Rn на 1, не затрагивая другие регистры.
3.
имеет вид T (m, n) (здесь
m, n ? {1, 2, 3, ...}.)
Выполнение такой команды заменяет содержимое
регистра Rn числом rm , содержащимся в регистре Rm , не
затрагивая другие регистры (включая Rm ).
4.
имеет вид J(m, n, q)
(m, n, q ? {1, 2, 3, ...}).
Выполнение такой команды состоит в следующем. Сравнивается содержимое регистров Rm и Rn . Если rm = rn ,
то машина переходит к выполнению q -й команды выполняемой программы; если rm 6= rn , то машина переходит к
Команда переадресации
Команда условного перехода
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 15. Машина с неограниченными регистрами
93
выполнению следующей команды. Если требуется выполнение команды с номером, превосходящим число команд в
программе, машина прекращает работу.
Команды обнуления, прибавления единицы и переадресации называются
.
Пусть n ? {1, 2, 3, ...}. Каждую программу можно рассматривать как алгоритм с множеством возможных исходных
данных N n . Применение такого алгоритма к исходному данному
hx1 , ..., xn i состоит в следующем. В начальный момент числа
x1 , ..., xn помещаются соответственно в регистры R1 , ..., Rn ,
при этом во всех остальных регистрах содержится 0. Затем
выполняются команды данной программы, начиная с первой.
Один шаг работы алгоритма состоит в выполнении одной
команды. Последовательность шагов работы алгоритма
называется вычислением. Вычисление завершается, когда в
программе нет команды, которую можно было бы выполнить.
Это может произойти, если
1) выполнена последняя команда программы и эта команда
была арифметической;
2) при выполнении команды J(m, n, q) оказалось, что rm = rn ,
но q превосходит число команд в программе;
3) при выполнении команды J(m, n, q) оказалось, что rm 6= rn ,
но это была последняя команда программы.
арифметическими
Завершение работы алгоритма всегда считается результативным. Результатом работы алгоритма является натуральное
число, записанное в регистре R1 в момент завершения
вычисления. Таким образом, каково бы ни было n ? {1, 2, 3, ...},
каждая программа вычисляет частичную n-местную числовую
функцию. Частичная функция из N n в N называется
, если существует программа для МНР, которая
вычисляет эту функцию.
Примеры.
1. Функция f (x, y) = x + y вычисляется следующей программой:
вычислимой
1. J(3, 2, 5);
2. S(1);
МНР-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
94
Гл. 15. Машина с неограниченными регистрами
3. S(3);
4. J(1, 1, 1).
2. Каково бы ни было n ? {1, 2, 3, ...}, нигде не определенная
функция из N n в N вычисляется, например, следующей
программой:
1. J(1, 1, 1).
Задачи
1. Доказать, что следующие функции МНР-вычислимы:
(а) sg(x);
(б) f (x) = 5;
(
0,
(в) f (x, y) =
1,
(
0,
(г) f (x, y) =
1,
если x = y ;
если x =
6 y;
если x 6 y ;
если x > y ;
(д) f (x) = x3 ;
(е) f (x) = [ 23x ] ([z] обозначает целую часть числа z).
2. Доказать, что если функция f вычисляется программой
без команд условного перехода, то найдется такое число
m, что либо (?x)f (x) = m, либо (?x)f (x) = x + m.
3. Доказать, что для любой МНР-вычислимой функции существует программа без команд переадресации, вычисляющая эту функцию.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
16
MНР-ВЫЧИСЛИМОСТЬ
ЧАСТИЧНО-РЕКУРСИВНЫХ ФУНКЦИЙ
Мы докажем, что всякая частично-рекурсивная функция
вычислима на машине с неограниченными регистрами.
16.1. Соединение программ
В дальнейшем нам придется рассматривать программы, которые содержат другие программы в качестве
. Рассмотрим некоторые технические средства, позволяющие строить
сложные программы из более простых. Для этого нам понадобится некоторая стандартизация программ. Пусть программа
P состоит из команд I1 , ..., Is . Будем говорить, что программа
P имеет
, если во всякой команде условного
перехода J(m, n, q) из P выполняется неравенство q 6 s + 1.
Очевидно, что каждая программа P может быть приведена к
стандартному виду путем замены в ней всякой команды вида
J(m, n, q), где q > s + 1, на J(m, n, s + 1), выполняющую точно
такое же действие, а именно остановку выполнения программы
P . Пусть теперь P = I1 , ..., Is и Q = I10 , ..., It0 программы
стандартного вида.
программ P и Q называется
программа
подпрограмм
стандартный вид
Соединением
P Q = I1 , ..., Is , Is+1 , ..., Is+t ,
где Is+1 , ..., Is+t команды, полученные из команд программы
Q заменой каждой команды условного перехода J(m, n, q) на
J(m, n, s + q). Очевидно, что результат выполнения программы
P Q таков же, как и результат последовательного выполнения
программ P и Q. Можно говорить также о соединении трех
и более программ, понимая, например, программу P QR как
(P Q)R.
В том случае, когда одна программа используется как подпрограмма в другой программе, важно позаботиться о том,
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
96
Гл. 16. MНР-вычислимость частично-рекурсивных функций
чтобы в ходе выполнения подпрограммы не изменилось содержимое регистров, используемых основной программой. Этого
нетрудно добиться следующим образом. Пусть мы собираемся
использовать программу P как подпрограмму при составлении
новой программы Q. Поскольку программа P конечна, в ней
используется конечное число регистров, так что найдется такое
наименьшее число u (обозначим его ?(P )), что регистры Rv при
v > u не используются в этой программе. Тогда при составлении
программы Q, использующей P в качестве своей части, т. е.
подпрограммы, нужно использовать в качестве рабочих только
регистры Rv при v > u.
Если программа P предназначена для вычисления некоторой
функции f (x1 , ..., xn ), то, в соответствии с общими соглашениями, исходные данные записываются в регистры R1 , ..., Rn , а
результат в регистр R1 . В то же время при использовании
программы P в качестве подпрограммы в другой программе
исходные данные для P могут быть записаны в каких-то других
регистрах Rl1 , ..., Rln , а результат требуется поместить в регистр
Rl . Чтобы обеспечить возможность такого использования программы P , мы можем преобразовать ее в следующую программу,
? являющуюся соединением трех программ:
?
T (l1 , 1);
?
?
?
?
...
?
?
?
?T (l , n);
n
?
Z(n
+ 1);
?
?
?
?
...
?
?
?
?Z(?(P ));
P
n
T (1, l).
Модифицированную таким образом программу будем обозначать
P [l1 , ..., ln ? l].
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
16.3. Реализация рекурсии на МНР
97
16.2. Реализация подстановки на МНР
Сейчас мы докажем, что класс всех МНР-вычислимых функций замкнут относительно операции подстановки.
Пусть функция h(x), где x = (x , ..., xn), получена подстановкой из МНР-вычислимых функций f (y , ..., yk ) и
g (x), ..., gk (x). Тогда и функция h(x) МНР-вычислима.
Т е о р е м а 16.1.
1
1
1
Д о к а з а т е л ь с т в о. Пусть программы F , G1 , ..., Gk , имеющие стандартный вид, вычисляют соответственно функции
f , g1 , ..., gk . Напишем программу H для вычисления функции h.
Пусть
m = max(n, k , ?(F ), ?(G1 ), ..., ?(Gk )).
Тогда программа H будет выглядеть как следующее соединение
нескольких программ:
?
?
?T (1, m + 1);
...
?
?T (n, m + n);
G1 [m + 1, m + 2, ..., m + n ?? m + n + 1]
...
Gk [m + 1, m + 2, ..., m + n ?? m + n + k]
F [m + n + 1, ..., m + n + k ?? 1]
Вспомнив только что введенные обозначения для модифицированных программ, читатель без труда убедится, что программа H действительно вычисляет функцию h. Теорема доказана.
16.3. Реализация рекурсии на МНР
Сейчас мы докажем, что класс всех МНР-вычислимых функций
замкнут относительно операции рекурсии.
Пусть функция h(x, y), где x = (x , ..., xn),
получена рекурсией из МНР-вычислимых функций f (x) и
g(x, y , z). Тогда и функция h(x, y) МНР-вычислима.
Т е о р е м а 16.2.
1
Д о к а з а т е л ь с т в о. Пусть программы F и G, имеющие
стандартный вид, вычисляют соответственно функции f (x)
4 Ю. А. Белов, В. А. Соколов
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
98
Гл. 16. MНР-вычислимость частично-рекурсивных функций
и g(x, y , z). Напишем программу H для вычисления функции
h(x, y). Пусть
m = max(n + 2, ?(F ), ?(G)).
Обозначим сумму m + n через t. Тогда программа H будет
выглядеть
как следующее соединение нескольких программ:
?
?
T
(
1,
m
+
1);
?
...
?
?T (n + 1, m + n + 1);
F [1, 2, ..., n ?? t + 3]
{Iq : J(t + 2, t + 1, p)
G[m
? + 1, m + 2, ..., m + n, t + 2, t + 3 ?? t + 3]
?
?S(t + 2);
J(1, 1, q);
?
?Ip : T (t + 3, 1)
Вспомнив введенные выше обозначения для модифицированных программ, читатель без труда убедится, что программа H
действительно вычисляет функцию h. Теорема доказана.
16.4. Реализация минимизации на МНР
Сейчас мы докажем, что класс всех МНР-вычислимых функций
замкнут относительно операции минимизации.
Пусть g(x) = µy[f (x, y) = 0], где x =
,а
есть МНР-вычислимая функция. Тогда
также МНР-вычислима.
Т е о р е м а 16.3.
= (x1 , ..., xn )
f (x, y)
g(x)
функция
Д о к а з а т е л ь с т в о. Пусть программа F , имеющая стандартный вид, вычисляет функцию f (x, y). Напишем программу G
для вычисления функции g(x). Пусть m = max(n + 1, ?(F )).
Тогда программа G будет выглядеть как следующее соединение
нескольких
программ:
?
?
T
(
1,
m
+
1
);
?
...
?
?T (n, m + n);
Ip : F [m + 1, m + 2, ..., m + n + 1 ? 1]
(т. е. Ip является номером первой команды)
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
16.5. Основной результат
99
?
J(1, m + n + 2, q);
?
?
?
?S(m + n + 1);
?
J(1, 1, p);
?
?
?
Iq : T (m + n + 1, 1)
Согласно введенным выше обозначениям для модифицированных программ, программа G действительно вычисляет
функцию g . Теорема доказана.
16.5. Основной результат
Т е о р е м а 16.4. Всякая частично-рекурсивная функция является МНР-вычислимой.
Д о к а з а т е л ь с т в о. По
определению
любая
частичнорекурсивная функция может быть получена из базисных
функций
n
o(x), s(x), Im
(x1 , ..., xn )(n = 1, 2, ...; 1 6 m 6 n)
с помощью операций подстановки, рекурсии и минимизации.
Базисные функции, очевидно, МНР-вычислимы. Так, функция
o(x) вычисляется программмой, состоящей из одной команды
Z(1),
функция s(x) вычисляется программмой, состоящей из одной
команды
S(1),
n (x , ..., x )
Im
1
n
а функция
из одной команды
вычисляется программмой, состоящей
T (m, 1).
Отсюда и из теорем 16.116.3 немедленно следует, что всякая
частично-рекурсивная функция МНР-вычислима. Теорема доказана.
Всякая МНР-вычислимая функция является
частично-рекурсивной.
Т е о р е м а 16.5.
4*
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
100
Гл. 16. MНР-вычислимость частично-рекурсивных функций
Д о к а з а т е л ь с т в о. Эта теорема доказывается более сложно с
помощью такого рассуждения. Пусть функция f (x), где x =
= (x1 , ..., xn ), вычисляется программой P . Обозначим через
c(x, t) содержимое регистра R1 после t шагов работы программы
P на исходных данных x, если она не завершилась раньше, и заключительное содержимое регистра R1 , если работа программы
завершилась за k < t шагов. Через j(x, t) обозначим номер следующей команды, после того как сделано ровно t шагов работы
программы P на исходных данных x, если она не завершилось
раньше, и 0, если работа программы завершилась за l 6 t шагов.
Тогда, очевидно,
f (x) ' c(x, µt[j(x, t) = 0]).
Затем доказывается, что функции c и j частично-рекурсивны.
Это дает частичную рекурсивность функции f .
Таким образом, классы числовых функций, вычислимых на
машинах Тьюринга и на машинах с неограниченными регистрами, совпадают с классом всех частично-рекурсивных функций.
Этот факт может рассматриваться как еще один довод в пользу
тезиса Чјрча, в силу которого мы теперь имеем, что числовые
функции, вычислимые в интуитивном смысле, это в точности
МНР-вычислимые функции.
Задачи
Составить программы для МНР, вычисляющие следующие
числовые функции:
1) f (x, y , z) = x + y + z ; 2)f (x) = x! (факториал);
3) f (x, y) = x · y ;
4) f (x, y) = xy ;
5) f (x, y) = |x ? y|;
6) f (x, y) = max(x, y);
x
7) f (x, y) = min(x, y);
8) f (x, y) = .
y
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
17
НУМЕРАЦИЯ ВЫЧИСЛИМЫХ ФУНКЦИЙ
Напомним, что N = {0, 1, 2, ...}. Пусть N + = {1, 2, ...}.
Нетрудно убедиться, что функция
?(m, n) = 2m · (2n + 1) ? 1
задает вычислимое взимно-однозначное соответствие между
множествами N Ч N и N . Аналогично функция
?(m, n, q) = ?(?(m ? 1, n ? 1), q ? 1)
задает вычислимое взимно-однозначное соответствие между
множествами N + Ч N + Ч N + и N . Наконец, рассмотрим
функцию
? (ha1 , ..., ak i) = 2a1 + 2a1 +a2 +1 + 2a1 +a2 +a3 +2 + ...
... + 2a1 +a2 +...+ak +k?1 ? 1
(в дальнейшем вместо ? (ha1 , ..., ak i) мы будем писать просто ? (a1 , ..., ak )). Функция ? задает вычислимое взаимнооднозначное соответствие между множеством всех кортежей
натуральных чисел и множеством N . Реально это соответствие
устанавливается так. Для данного кортежа ha1 , ..., ak i будем
строить конечную последовательность нулей и единиц справа
налево следующим образом. Первую единицу поставим на
(a1 + 1)-м месте справа, т. е пишем a1 нулей, а за ними одну
единицу. Вторую единицу поставим на (a2 + 1)-м месте влево от
первой единицы, и так далее. Наконец, последнюю, k -ю единицу
поставим на (ak + 1)-м месте слева от (k ? 1)-й единицы.
Полученная последовательность нулей и единиц является
двоичной записью некоторого положительного натурального
числа a. Тогда a ? 1 как раз и есть ? (a1 , ..., ak ). Пусть, например,
дан кортеж h3, 7, 1i. Тогда по определению ? (3, 7, 1) = 23 + 211 +
+ 213 ? 1. Построим последовательность нулей и единиц, как
сказано выше. Получим двоичное число 10100000001000, равное
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
102
Гл. 17. Нумерация вычислимых функций
числу 23 + 211 + 213 . Вычитая из него 1, как раз и получаем
? (3, 7, 1).
Используя функции ? и ? , каждой команде I для МНР
поставим в соответствие число ?(I) по следующему правилу:
?(Z(n)) = 4(n ? 1);
?(S(n)) = 4(n ? 1) + 1;
?(T (m, n)) = 4?(m ? 1, n ? 1) + 2;
?(J(m, n, q)) = 4?(m, n, q) + 3.
Не трудно понять, что функция задает вычислимое взаимнооднозначное соответствие между командами для МНР и натуральными числами. Число ?(I) будем называть
команды I . Наконец, для любой программы P = I1 , I2 , ..., Is
положим
гјделевым номе-
ром
?(P ) = ? (?(I1 ), ..., ?(Is )).
Функция ? задает вычислимое взаимно-однозначное соответствие между программами для МНР и натуральными числами.
Число ?(P ) будем называть
программы P
или просто ее
. Программу с номером n будем обозначать Pn .
Как известно, при любом n > 1 всякая программа для
МНР вычисляет некоторую частичную n-местную числовую
функцию. n-местную функцию, вычисляемую программой Pa ,
(n)
будем обозначать ?a . Одноместную функцию, вычисляемую
программой Pa , будем обозначать просто ?a .
Заметим, что вычислимые числовые функции образуют
счетное множество. Поскольку множество всех числовых
функций имеет мощность континуума, очевидно существование
невычислимых числовых функций. Теперь мы можем привести
конкретный пример такой функции. Пусть
(
?n (n) + 1, если значение ?n (n) определено;
f (n) =
0, если значение ?n (n) не определено.
номером
гјделевым номером
Допустим, что эта функция вычислима. Тогда она МНРвычислима. Пусть f вычисляется программой Pm , т. е. f есть
?m . Очевидно, что значение ?m (m) определено, так что имеем:
f (m) = ?m (m) + 1 = f (m) + 1.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 17. Нумерация вычислимых функций
103
Это явный абсурд. Полученное противоречие доказывает, что
на самом деле функция f невычислима.
Задачи
1. Найти геделев номер команды J(3, 4, 2).
2. Найти команду с номером 503.
3. Найти номер следующей программы:
(а) T (3, 4);
(б) S(3);
(в) Z(1).
4. Найти программу P100 .
5. Доказать,
( что невычислима функция
?n (n) + 27n , если ?n (n) определено;
f (n) =
n2 , если ?n (n) не определено.
6. Пусть f (x, y) тотальная вычислимая функция. Каждому
m сопоставим такую функцию gm , что (?y)gm (y) = f (m, y).
Построить такую тотальную вычислимую функцию h, что
(?m)h 6= gm .
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
18
ТЕОРЕМА О ПАРАМЕТРИЗАЦИИ
Условимся о некоторых терминах и обозначениях, связанных
с функциями. В этой и следующих главах мы будем рассматривать только числовые функции, т. е. многоместные частичные
функции из N в N . Всюду определенные функции будем называть
.
Иногда функция задается путем выражения ее значений через значения аргументов в виде числовой формы. Например,
говорят о функции x2 . Чтобы выражаться более точно и различать числовые (и вообще именные) формы и задаваемые ими
функции, обычно используют так называемые ?-обозначения.
Например, упомянутую функцию x2 можно обозначить так:
?x.x2 . Вообще, если дана именная форма f (x) с единственным
параметром x, то выражение ?x.f (x) считается именем (т. е.
обозначением) функции, которая каждому значению a переменной x сопоставляет значение f (a) формы f (x) при этом
значении переменной x. В выражении ?x.f (x) переменная x
оказывается связанной. Если именная форма f (x, y) наряду
с x содержит другие параметры из списка y , то выражение
?x.f (x, y) является функциональной формой с параметрами y ,
значением которой при данных значениях a параметров y является функция ?x.f (x, a). Аналогично вводятся обозначения для
многоместных функций. Пусть дана именная форма f (x1 , ..., xn )
с параметрами x1 , ..., xn . Тогда выражение ?x1 ...xn .f (x1 , ..., xn )
считается обозначением n-местной функции, которая каждому
набору a1 , ..., an значений переменных x1 , ..., xn сопоставляет
объект, именем которого является выражение f (a1 , ..., an ). Если
именная форма f (x1 , ..., xn , y) наряду с x1 , ..., xn содержит другие параметры из списка y , то выражение ?x1 ...xn .f (x1 , ..., xn , y)
является функциональной формой с параметрами y , значением
которой при данных значениях a параметров y есть функция
тотальными функциями
?x1 ...xn .f (x1 , ..., xn , a).
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 18. Теорема о параметризации
105
Пусть f двуместная вычислимая функция. Существует одноместная тотальная вычислимая функция k такая, что f (x, y) ' ?k(x)(y).
Т е о р е м а 18.1 (теорема о параметризации).
Д о к а з а т е л ь с т в о. Пусть программа F вычисляет функцию
f . Для каждого x построим программу Qx , являющуюся соединением
двух программ:
?
T
(
1,
2
)
;
?
?
?
?
?
?Z(1);
S(1);
?
?
?
...
?
?
?
S(1)
F,
где команда S(1) написана x раз. Пусть k(x) гјделев номер
программы Qx . Очевидно, что функция k вычислима. Нетрудно
видеть, что программа Qx вычисляет функцию ?y.f (x, y), т.
е. имеет место f (x, y) ' ?k(x) (y), что и требовалось доказать.
Теорема 18.1 доказана.
Только что доказанная теорема имеет следующее естественное обобщение.
Для любых m, n > 1 суще-m
ствует тотальная вычислимая (m + 1)-местная функция sn
такая, что для любых натуральных чисел e, x , ..., xm, y , ..., yn
имеет место
Т е о р е м а 18.2 (s-m-n-теорема).
1
1
?(m+n)
(x1 , ..., xm , y1 , ..., yn ) '
e
(n)
?sm (e,x1 ,...,xm ) (y1 , ..., yn ).
n
Эта теорема имеет прозрачный смысл: по программе с гјделе(m+n)
вым номером e, вычисляющей (m+n)-местную функцию ?e
,
и произвольному набору натуральных чисел x1 , ..., xm можно
найти (с помощью функции sm
n ) гјделев номер программы, вычисляющей функцию
?y1 ...yn ?e(m+n) (x1 , ..., xm , y1 , ..., yn ).
Теорема доказывается с помощью того же программистского
приема, что и теорема о параметризации.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
19
УНИВЕРСАЛЬНАЯ ВЫЧИСЛИМАЯ ФУНКЦИЯ
Пусть K некоторый класс n-местных (n > 1) функций.
Тогда (n + 1)-местная функция U называется
K, если выполнены следующие условия:
класса
универсальной для
? для каждого натурального e функция ?x1 ...xn .U (e, x1 , ..., xn )
принадлежит классу K;
? для любой функции f из класса K существует такое натуральное число e, что f = ?x1 ...xn .U (e, x1 , ..., xn ).
Очевидно, что универсальная функция для класса K существует в том и только в том случае, когда класс K не более чем
счетен. Более интересен вопрос о существовании вычислимых
универсальных функций для классов, состоящих только из вычислимых функций.
Для
любого натурального числа
существует ( )-местная
вычислимая функция, универсальная для класса
всех nместных вычислимых функций.
Т е о р е м а 19.1 (о вычислимой универсальной функции).
n>1
n+1
C (n)
Д о к а з а т е л ь с т в о. (n + 1)-местную функцию ?(n) определим
(n)
как ?ex1 ...xn ?e (x1 , ..., xn ). Функция ?(n) вычисляется следующим неформальным алгоритмом: ѕПусть даны натуральные
числа e, x1 , ..., xn . Найдите программу Pe с номером e. Затем
поместите в регистры R1 , ..., Rn соответственно числа x1 , ..., xn
и запустите выполнение программы Pe . Если вычисление заканчивается, требуемое значение ?(n) (e, x1 , ..., xn ) содержится в
регистре R1 ї.
Таким образом, функция ?(n) вычислима.
Докажем, что ?(n) универсальная функция для класса C (n) . Действительно, для любого натурального e функция
(n)
?x1 ...xn .?(n) (e, x1 , ..., xn ) совпадает с функцией ?e и, следо(n)
вательно, принадлежит классу C . С другой стороны, любая
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 19. Универсальная вычислимая функция
107
функция f из класса C (n) вычисляется некоторой программой
Pe и потому имеет вид ?e для некоторого e. Но тогда, очевидно,
f = ?x1 ...xn .?(n) (e, x1 , ..., xn ).
Теорема доказана.
Задачи
1. Доказать, что не существует вычислимой функции, универсальной для класса всех одноместных тотальных вычислимых функций.
2. Доказать, что существует вычислимая функция, универсальная для класса всех одноместных примитивнорекурсивных функций.
3. Доказать, что не существует примитивно-рекурсивной
функции, универсальной для класса всех одноместных
примитивно-рекурсивных функций.
4. Доказать, что существует общерекурсивная функция, не
являющаяся примитивно-рекурсивной.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
20
РАЗРЕШИМЫЕ И ПЕРЕЧИСЛИМЫЕ
МНОЖЕСТВА
Пусть X некоторый ансамбль конструктивных объектов,
A его подмножество.
A называется функция XA : X ? {0, 1}, определяемая
следующим образом:
(
1, если x ? A;
XA (x) =
0, если x ?
/ A.
Характеристической функцией множе-
ства
Множество A ? X называется разрешимым (или рекурсивным), если его характеристическая функция XA(x) вычислима.
О п р е д е л е н и е 20.1.
Иными словами, множество A разрешимо, если существует алгоритм, который для каждого x ? X вычисляет истинностное
значение высказывания x ? A. Очевидно, что множества X и ?
разрешимы.
Если множества A, B ? X разрешимы, то
,
разрешимы.
Т е о р е м а 20.1.
A ? B, A ? B A \ B
множества
Д о к а з а т е л ь с т в о. Доказываемое утверждение совершенно
очевидно. Действительно, так как множества A, B ? X
разрешимы, то их характеристические функции XA и XB
вычислимы. Тогда функция XA?B вычисляется следующим
алгоритмом: ѕесли XA (x) = 1 или XB (x) = 1, то XA?B (x) =
= 1; в противном случае XA?B (x) = 0ї. Аналогично находятся
значения XA?B (x) и XA\B (x), если найдены значения XA и XB .
Теорема доказана.
Из теоремы 20.1, в частности, получается, что дополнение
X \ A разрешимого множества A разрешимо.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 20. Разрешимые и перечислимые множества
109
Полухарактеристической функцией множества A называет-
ся частичная функция ?A из X в {1}, определяемая следующим
образом:
(
1, если x ? A;
?A (x) =
не определено, если x ?
/ A.
О п р е д е л е н и е 20.2. Множество A ? X называется полуразрешимым, если его полухарактеристическая функция ?A вычислима.
Т е о р е м а 20.2. Всякое разрешимое множество является полуразрешимым.
Д о к а з а т е л ь с т в о. Пусть множество A ? X разрешимо. Тогда его характеристическая функция XA вычислима. Полухарактеристическая функция ?A множества A вычисляется следующим неформальным алгоритмом: ѕПусть дан элемент x ? X .
Вычислить XA (x). Если XA (x) = 1, то положить ?A (x) = 1;
в противном случае значение ?A (x) не определеної. Теорема
доказана.
Множество A ? X разрешимо тогда и только тогда, когда оба множества A и X \ A
полуразрешимы.
Т е о р е м а 20.3 (теорема Поста).
Д о к а з а т е л ь с т в о. Если множество A разрешимо, то множество X \ A также разрешимо и, по теореме 20.2, оба они
полуразрешимы. Обратно, пусть оба множества A и X \ A полуразрешимы. Тогда их полухарактеристические функции ?A и
?X\A вычислимы. Характеристическая функция XA множества
A вычисляется следующим неформальным алгоритмом: ѕПусть
дан элемент x ? X . Запустить параллельное выполнение программ для вычисления значений ?A (x) и ?X\A (x). Если первая
программа выдала результат, то XA (x) = 1. Если вторая программа выдала результат, то XA (x) = 0 ї. Теорема доказана.
Последовательностью
называется любая функция, область
определения которой множество всех натуральных чисел N .
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
110
Гл. 20. Разрешимые и перечислимые множества
Следующее понятие в некотором смысле является алгоритмическим аналогом понятия не более чем счетного множества.
Пусть X некоторый ансамбль конструктивных объектов.
Множество A ? X называется
(или
), если A = ? или A является множеством значений некоторой вычислимой последовательности.
перечислимым
Т е о р е м а 20.4.
луразрешимым.
перечислимым
рекурсивно
Всякое перечислимое множество является по-
Д о к а з а т е л ь с т в о. Пусть множество A ? X перечислимо.
Если A = ?, то A разрешимо и, следовательно, полуразрешимо.
Пусть A 6= ?. Тогда A является множеством значений некоторой
вычислимой последовательности f : N ?? X. Полухарактеристическая функция ?A множества A вычисляется следующим
неформальным алгоритмом: ѕПусть дан элемент x ? X . Для каждого натурального n, начиная с 0, вычислять f (n) и проверять
условие f (n) = x. Если нашлось такое n, что f (n) = x, то
?A (x) = 1ї. Теорема доказана.
Пусть X и Y некоторые ансамбли конструктивных объектов,
f частичная функция из X в Y .
f называется множество ?f ? X Ч Y , определяемое следующим образом:
Графиком функции
?f = {hx, yi|y = f (x)}.
Частичная функция f из
в вычислима тогда и только тогда, когда ее график ?f
перечислим.
Т е о р е м а 20.5 (теорема о графике).
X Y
Д о к а з а т е л ь с т в о. Пусть f частичная вычислимая функция из X в Y . Если функция f нигде не определена, то ее график
пуст и, следовательно, перечислим по определению. Рассмотрим
случай, когда f определена хотя бы в одной точке. Пусть f
определена в точке a ? X . Тогда пара ha, f (a)i принадлежит
графику ?f . Будем считать, что фиксировано некоторое кодирование ансамбля конструктивных объектов X натуральными числами, т. е. фиксирована некоторая вычислимая биекция
? : X ?? N . Для каждого натурального числа i положим
xi = ??1 (i). Последовательность g : N ?? X Ч Y определим
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 20. Разрешимые и перечислимые множества
111
следующим образом. Пусть дано натуральное число n. Оно является номером некоторой пары натуральных чисел hl, ri при
рассмотренной нами нумерации всех пар натуральных чисел
? , т. е. ?(l, r) = n, причем числа l и r можно эффективно
вычислить по n. Запустим алгоритм вычисления функции f
на исходном данном xl и дождемся выполнения r + 1 шагов
работы этого алгоритма. Если за r+1 шагов или раньше получен
результат f (xl ), полагаем g(n) = hxl , f (xl )i. Если же за r + 1
шагов работа алгоритма еще не завершилась или же произошла
безрезультатная остановка, полагаем g(n) = ha, f (a)i. Очевидно,
что последовательность g вычислима. Очевидно также, что множество ее значений Ran(g) является подмножеством графика
?f . Докажем, что ?f ? Ran(g). Пусть пара hx, yi принадлежит
графику функции f . Это означает, что алгоритм вычисления
функции f на исходном данном x заканчивает работу, скажем,
за r > 0 шагов и выдает результат y . Пусть ?(x) = l. Положим
n = ?(l, r ? 1).
Из определения функции g видно, что g(n) = hx, yi, т. е.
hx, yi ? Ran(g).
Таким образом, график функции f является множеством значений вычислимой последовательности g , следовательно, он перечислим по определению.
Пусть график ?f функции f перечислим. Если он пуст, то
функция f нигде не определена и, следовательно, вычислима.
Если же график не пуст и перечислим, то он является множеством значений некоторой вычислимой последовательности
g : N ?? X Ч Y . Функция f вычисляется следующим алгоритмом. Пусть дано натуральное число n. Последовательно
для каждого натурального i, начиная с 0, вычисляем значение
g(i) = ha, f (a)i и проверяем условие a = n. Если это условие
выполнено, то f (n) = f (a) и вычисление закончено. Теорема
доказана.
Пусть частичная вычислимая функция из
в . Тогда ее область определения Dom(f ) ? X и множество значений
суть перечислимые множества.
Т е о р е м а 20.6.
f
X Y
Ran(f ) ? Y
Д о к а з а т е л ь с т в о. Пусть функция f вычислима. По теореме
20.5, ее график перечислим. Если f нигде не определена, то
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
112
Гл. 20. Разрешимые и перечислимые множества
Dom(f ) и Ran(f ) пусты и, следовательно, перечислимы. В противном случае ?f является множеством значений некоторой
вычислимой последовательности g : N ?? X Ч Y . Последовательности l : N ?? X и r : N ?? Y определим следующим
образом. Пусть дано натуральное число n. Вычисляем
g(n) = ha, bi
и полагаем l(n) = a, r(n) = b. Очевидно, что последовательности
l и r обе вычислимы, причем Ran(l) есть в точности множество
первых компонент пар из ?f , т. е. область определения фунции
f , а Ran(r) это в точности множество вторых компонент пар
из ?f , т. е. множество значений функции f . Таким образом, множество Dom(f ) является множеством значений вычислимой последовательности l и перечислимо по определению. Множество
Ran(f ) является множеством значений вычислимой последовательности r и потому также перечислимо. Теорема доказана.
Множество A ? X перечислимо тогда и
только тогда, когда оно является множеством значений некоторой вычислимой функции.
Т е о р е м а 20.7.
Д о к а з а т е л ь с т в о. Пусть множество A перечислимо. Докажем, что A является множеством значений некоторой вычислимой функции. Если оно пусто, то является множеством значений
нигде не определенной функции. Если же A не пусто, то по
определению оно является множеством значений вычислимой
последовательности и утверждение доказано.
Обратно, если A является множеством значений некоторой
вычислимой функции, то, по теореме 20.6, оно перечислимо.
Теорема доказана.
Множество A ? X перечислимо тогда и
только тогда, когда оно является областью определения некоторой вычислимой функции.
Т е о р е м а 20.8.
Д о к а з а т е л ь с т в о. Пусть множество A перечислимо. Тогда,
по теореме 20.4, оно полуразрешимо. Следовательно, его полухарактеристическая функция ?A вычислима. Но всякое множество является областью определения своей полухарактеристиче-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 20. Разрешимые и перечислимые множества
113
ской функции. Таким образом, A является областью определения вычислимой функции ?A .
Обратно, если множество A является областью определения
некоторой вычислимой функции, то, по теореме 20.6, оно перечислимо. Теорема доказана.
Т е о р е м а 20.9.
перечислимым.
Всякое полуразрешимое множество является
Д о к а з а т е л ь с т в о. Полуразрешимое множество A является
областью определения вычислимой функции ?A и, по теореме
20.6, перечислимо. Теорема доказана.
Пусть X произвольный ансамбль конструктивных объектов, A произвольное его подмножество.
Тогда следующие условия эквивалентны:
1) множество A перечислимо;
2) множество A полуразрешимо;
3) множество A является областью определения некоторой вычислимой функции;
4) множество A является множеством значений некоторой вычислимой функции.
Т е о р е м а 20.10.
Д о к а з а т е л ь с т в о. Эквивалентность условий 1) и 2) вытекает
из теорем 20.4 и 20.9. В силу теорем 20.8 и 20.7 каждое из
условий 3), 4) эквивалентно условию 1). Теорема доказана.
Пусть X произвольный ансамбль конструктивных объектов, A, B ? X перечислимые множества. Тогда множества A ? B и A ? B перечислимы.
Т е о р е м а 20.11.
Д о к а з а т е л ь с т в о. Пусть A, B ? X перечислимые множества. Докажем перечислимость множества A ? B . Если хотя
бы одно из множеств A, B пусто, то A ? B совпадает с другим
множеством и потому перечислимо. Рассмотрим случай, когда
оба множества A, B непусты. Тогда A является множеством
значений некоторой вычислимой последовательности f , а B множеством значений некоторой вычислимой последовательности g . Определим последовательность h следующим образом:
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
114
Гл. 20. Разрешимые и перечислимые множества
для любого натурального числа n положим
(
f ( n2 ), если четно;
h(n) =
1
g( n?
), если нечетно.
2
n
n
Очевидно, что последовательность h вычислима, а множество
ее значений есть в точности множество A ? B .
Докажем, что множество A ? B перечислимо. Для этого достаточно доказать, что оно полуразрешимо. Множества A, B полуразрешимы, следовательно их полухарактеристичекие функции ?A и ?B вычислимы. Полухарактеристическая функция
?A?B множества A ? B вычисляется следующим алгоритмом.
Пусть дан элемент x ? X . Вычислять ?A (x). Если вычисление
завершилось результативно, вычислять ?B (x). Если и это вычисление завершилось результативно, то ?A?B (x) = 1. Теорема
доказана.
Функция f : N ? N называется
неубывающей, если
(?x, y)[x < y ? f (x) 6 f (y)].
перечислимо в порядке
Будем говорить, что множество A ? N
, если существует такая неубывающая вычислимая
функция f : N ? N , что A = Ran(f ).
неубывания
Т е о р е м а 20.12. Пусть A ? N . Множество A разрешимо и
непусто тогда и только тогда, когда оно перечислимо в порядке
неубывания.
Д о к а з а т е л ь с т в о. Пусть множество A ? N разрешимо и
непусто. Пользуясь разрешимостью множества A, найдем его
наименьший элемент n0 . Теперь определим функцию f : N ?
? N следующим образом:
f (0) = n0 ;
(
x + 1, если x + 1 ? A,
f (x + 1) =
f (x), в противном случае.
Нетрудно убедиться, что f неубывающая вычислимая функция, и
A = Ran(f ).
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 20. Разрешимые и перечислимые множества
115
Обратно, пусть существует такая неубывающая вычислимая
функция f : N ? N , что A = Ran(f ). Очевидно, что в этом
случае A непусто. Если множество A конечно, то оно, очевидно,
разрешимо. Если же A бесконечно, то для выяснения вопроса,
принадлежит ли произвольное данное число x множеству A,
будем вычислять последовательные значения f (0), f (1), f (2), ...
функции f , пока среди них не появится число, большее, чем x.
Если к этому моменту число x уже появилось среди значений
функции f , то x ? A; в противном случае x ?
/ A. Итак, мы
располагаем алгоритмом для распознавания принадлежности
произвольного числа множеству A, т. е. A разрешимо. Теорема
20.12 доказана.
Функция f : N ? N называется
возрастающей, если
(?x, y)[x < y ? f (x) < f (y)].
Будем говорить, что множество A ? N перечислимо в порядке
возрастания, если существует такая возрастающая вычислимая
функция f : N ? N , что A = Ran(f ).
Т е о р е м а 20.13. Пусть A ? N. Множество A разрешимо и
бесконечно тогда и только тогда, когда оно перечислимо в
порядке возрастания.
Д о к а з а т е л ь с т в о. Пусть множество A ? N разрешимо и
бесконечно. Пользуясь разрешимостью множества A, найдем его
наименьший элемент n0 . Теперь определим функцию f : N ? N
следующим образом:
f (0) = n0 ;
f (x + 1) = µy[y ? A&f (x) < y].
Нетрудно убедиться, что f тотальная возрастающая вычислимая функция и A = Ran(f ).
Обратно, пусть существует такая возрастающая вычислимая
функция f : N ? N , что A = Ran(f ). Очевидно. что в
этом случае множество A бесконечно. Для выяснения вопроса,
принадлежит ли произвольное данное число x множеству A,
будем вычислять последовательные значения f (0), f (1), f (2), ...
функции f , пока среди них не появится число, большее, чем x.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
116
Гл. 20. Разрешимые и перечислимые множества
Если к этому моменту число x уже появилось среди значений
функции f , то x ? A; в противном случае x ?
/ A. Итак, мы
располагаем алгоритмом для распознавания принадлежности
произвольного числа множеству A, т. е. A разрешимо. Теорема
20.13 доказана.
Всякое бесконечное перечислимое множество
содержит бесконечное разрешимое подмножество.
Т е о р е м а 20.14.
Д о к а з а т е л ь с т в о. Пусть множество A ? N перечислимо и
бесконечно. Тогда по определению A является множеством значений некоторой вычислимой последовательности f . Определим
функцию g следующим образом:
g(0) = f (0);
g(x + 1) = f (µy[f (y) > g(x)]).
Нетрудно убедиться, что g тотальная возрастающая вычислимая функция. Положим B = Ran(g). По теореме 20.13 множество B разрешимо. Так как при этом, очевидно, B ? A, то
теорема 20.14 доказана.
Задачи
1. Доказать, что существует множество натуральных чисел, не
являющееся перечислимым.
2. Доказать, что бесконечное множество A ? N разрешимо тогда
и только тогда, когда A является множеством значений строго
возрастающей тотальной вычислимой функции.
3. Доказать, что непустое множество A ? N разрешимо тогда и
только тогда, когда A является множеством значений монотонно
(не обязательно строго) возрастающей тотальной вычислимой
функции.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
21
НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ
ПРОБЛЕМЫ
Как было доказано в главе 20, каждое перечислимое множество является областью определения некоторой вычислимой
функции. Это позволяет задать следующую нумерацию всех
перечислимых подмножеств N . Пусть Wx = Dom(?x ). Число x
будем называть
множества Wx . Очевидно,
что всякое перечислимое множество имеет бесконечно много
гјделевых номеров.
В главе 20 было также установлено, что каждое перечислимое множество является множеством значений некоторой вычислимой функции. Используя нумерацию перечислимых множеств, этот факт можно выразить в следующей более сильной
форме.
гјделевым номером
Существует одноместная тотальная вычислимая функция f такая, что для любого x Wx = Dom(?x) =
= Ran(?f (x) ).
Т е о р е м а 21.1.
Д о к а з а т е л ь с т в о. Будем считать, что запись !f (x) означает,
что функция f определена в точке x. Пусть двуместная функция
h определена следующим образом:
(
y , если !?x (y);
h(x, y) =
не определено в противном случае.
Очевидно, что функция h вычислима. По теореме о параметризации (глава 18), существует такая одноместная тотальная
вычислимая функция f , что h(x, y) ' ?f (x) (y) для любых x, y .
Из этого условного равенства и определения функции h следует,
что y ? Ran(?f (x) ) ?!?x (y) ? y ? Dom(?x ). Это как раз и
означает, что f искомая функция. Теорема 21.1 доказана.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
118
Гл. 21. Неразрешимые алгоритмические проблемы
про-
Пусть f частичная функция. Функция g называется
функции f , если Dom(f ) ? Dom(g) и g(x) = f (x)
для любого x ? Dom(f ).
должением
Т е о р е м а 21.2. Существует частичная вычислимая функция,
не имеющая тотального вычислимого продолжения.
Д о к а з а т е л ь с т в о. Рассмотрим
следующую
частичную
функцию f из N в N :
(
?n (n) + 1, если значение ?n (n) определено;
f (n) =
не определено, если значение ?n (n) не определено.
Очевидно, функция f вычислима. Докажем, что никакая тотальная вычислимая функция не является продолжением функции f . Пусть дана произвольная тотальная вычислимая функция g : N ? N , и пусть m гјделев номер программы,
вычисляющей функцию g . Тогда g = ?m и
g(m) = ?m (m)
(21.1)
Так как значение ?m (m) определено, то
f (m) = ?m (m) + 1
(21.2)
Равенства (1) и (2) показывают, что функция g не является
продолжением функции f .
Т е о р е м а 21.3.
жество.
Существует неразрешимое перечислимое мно-
Д о к а з а т е л ь с т в о. В силу теоремы 21.2 существует частичная вычислимая функция f , не имеющая тотального вычислимого продолжения. Область определения этой функции Dom(f )
перечислимое множество. Докажем, что оно неразрешимо.
Это вытекает из следующего довольно очевидного общего факта: если область определения частичной вычислимой функции
разрешима, то эта функция имеет тотальное вычислимое продолжение. Действительно, пусть g вычислимая частичная
функция из X в Y , причем множество Dom(g) ? X разрешимо.
Рассмотрим тотальную функцию h : X ? Y , определенную
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 21. Неразрешимые алгоритмические проблемы
следующим образом: для любого x ? X
(
g(x), если x ? Dom(g);
h(x) =
0, если x ?
/ Dom(g).
119
(21.3)
Очевидно, что функция h вычислима и является продолжением
функции g .
Множество
числимо, но не разрешимо.
Т е о р е м а 21.4.
K = {n|?n (n)
определено} пере-
Д о к а з а т е л ь с т в о. Множество K является областью определения функции f , построенной при доказательстве теоремы
21.2. Его неразрешимость была установлена при доказательстве
теоремы 21.3.
Теорема 21.4 означает алгоритмическую неразрешимость так
называемой проблемы самоприменимости программ: не существует алгоритм, который по любой программе для МНР давал
бы правильный ответ на вопрос, завершается ли работа этой
программы, когда исходным данным является гјделев номер
этой программы. Очевидно, это явление характерно не только
для МНР, но и для любого другого способа программирования.
Т е о р е м а 21.5 (неразрешимость проблемы остановки).
Не существует алгоритм, который по любой программе P для
МНР и любому исходному данному x дајт правильный ответ
на вопрос, завершается ли работа программы P на данном x.
Д о к а з а т е л ь с т в о. Если бы существовал алгоритм, о котором
идет речь в формулировке теоремы, то, очевидно, была бы
разрешима проблема самоприменимости программ, что, как мы
видели, невозможно.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
22
ТЕОРЕМА РАЙСА.
ТЕОРЕМА О НЕПОДВИЖНОЙ ТОЧКЕ
Проблема самоприменимости и проблема остановки это
лишь два примера неразрешимых алгоритмических проблем в
теории алгоритмов. На самом деле оказывается неразрешимой
любая нетривиальная алгоримическая проблема, связанная с
распознаванием свойств вычислимых функций по программам,
вычисляющим эти функции.
Пусть F произвольное семейство одноместных частичных
вычислимых числовых функций, т. е. F ? C .
семейства F называется множество IF = {n|?n ? F}.
Иными словами, индексное множество семейства F состоит в
точности из всех номеров программ, вычисляющих функции
из семейства F . Семейство F ? C называется
,
если F 6= ? и F 6= C.
жеством
Индексным мнонетривиальным
Индексное множество IF любого нетривиального семейства функций F ? C неразрешимо.
Т е о р е м а 22.1 (теорема Райса).
Д о к а з а т е л ь с т в о. Пусть ? нигде не определенная функция. Допустим, что ? ? F. Так как семейство F нетривиальное,
существует функция g ? C\F . Двуместную частичную функцию
f определим следующим образом: для произвольных натуральных чисел n и x положим
(
g(x), если ?n (n) определено;
f (n, x) '
не определено, если ?n (n) не определено.
Функция f вычисляется неформальным алгоритмом описываемым следующими инструкциями:
ѕВычислять ?n (n). Если будет получен результат, перейти к
вычислению g(x). Если вычисление завершится результативно,
положить f (n, x) = g(x)ї.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 22. Теорема Райса. Теорема о неподвижной точке
121
В силу теоремы о параметризации существует одноместная
тотальная вычислимая функция k такая, что f (n, x) ' ?k(n) (x).
Как и раньше, пусть K = n|?n (n) определено. Очевидно, что
если n ? K , т. е. значение ?n (n) определено, то ?k(n) = g , и
k(n) ?
/ IF . Если же n ?
/ K , т. е. значение ?n (n) не определено,
то ?k(n) = ? , и k(n) ? IF . Таким образом,
n ? K ? k(n) ?
/ IF .
(22.1)
Из условия (22.1) непосредственно вытекает, что если бы множество IF было разрешимым, то разрешимо было бы и множество
K , что невозможно в силу теоремы 21.4.
Мы доказали неразрешимость множества IF при условии,
что ? ? F . Если же ? ?
/ F , то из доказанного вытекает неразрешимость множества IC\F = N \ IF , откуда уже следует неразрешимость множества IF , так как дополнение неразрешимого
множества неразрешимо.
Мы видим, что в теории алгоритмов имеется очень много
неразрешимых алгоритмических проблем. Используя результаты о неразрешимости некоторых проблем в теории алгоритмов,
удалось доказать алгоритмическую неразрешимость некоторых
проблем, имеющих общематематическое значение.
В 1900 году на Международном математическом конгрессе в
Париже знаменитый немецкий математик Д. Гильберт сформулировал ряд математических проблем, решение которых, по его
мнению, наиболее актуально для математики XX-го века. Одна
из них, под номером 10, касалась так называемых диофантовых
уравнений, т. е. уравнений вида
p(x1 , x2 , ..., xn ) = 0,
где p(x1 , x2 , ..., xn ) диофантов многочлен, т. е. многочлен
от переменных x1 , x2 , ..., xn с целыми коэффициентами, причем
ищутся только целые решения такого уравнения. Десятая проблема Гильберта состояла в том, чтобы установить, существует
ли алгоритм, с помощью которого можно определить, имеет ли
решение произвольное наперед заданное диофантово уравнение.
В 1970 году советский математик Ю. В. Матиясевич доказал,
что такого алгоритма не существует. Суть его доказательства
состоит в том, что для любого перечислимого множества A ? N
можно написать такой диофантов многочлен p(a, x1 , x2 , ..., xn )
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
122
Гл. 22. Теорема Райса. Теорема о неподвижной точке
от переменных a, x1 , x2 , ..., xn , что для любого натурального a
уравнение p(a, x1 , x2 , ..., xn ) = 0 как уравнение относительно
неизвестных x1 , x2 , ..., xn имеет целые решения тогда и только
тогда, когда a ? A. Теперь решение десятой проблемы Гильберта непосредственно вытекает из существования неразрешимого
перечислимого множества.
Представляет интерес следующая теорема, имеющая важные
приложения.
Т е о р е м а 22.2 (теорема о неподвижной точке). Каковы бы ни
были натуральное число m > 1 и тотальная одноместная(m)вычислимая функция f , существует число n такое, что ?f (n) =
(m)
= ?n .
Д о к а з а т е л ь с т в о. Рассмотрим следующую (m+1) -местную
функцию:
(m)
?(u, x1 , ..., xm ) ' ??u (u) (x1 , ..., xm ).
(22.2)
(m)
s-
Пусть e гјделев номер функции ? , т. е. ? = ?e . В силу
-теоремы (теорема 18.2) существует тотальная вычислимая
двуместная функция s (функция s1m в обозначениях упомянутой
теоремы) такая, что для любых u, x1 , ..., xm , имеет место услов(m+1)
(m)
ное равенство ?e
(u, x1 , ..., xm ) ' ?s(e,u) (x1 , ..., xm ). В нашем
случае, при фиксированном e, положим g(u) = s(e, u). Тогда
m-n
(m)
(m)
?g(u) (x1 , ..., xm ) ' ??u (u) (x1 , ..., xm ).
Пусть v гјделев номер композиции функций f и g , т. е. ?v (x) =
= f (g(x)) для любого x. Тогда для любых x1 , ..., xm имеем:
(m)
(m)
(m)
?g(v) (x1 , ..., xm ) ' ??v (v) (x1 , ..., xm ) ' ?f (g(v)) (x1 , ..., xm )
и теорема доказана, если взять n = g(v).
При m = 1 получаем, что для любой тотальной одноместной
вычислимой функции f существует ѕнеподвижная точкаї,
т. е. такое число n, что ?f (n) = ?n . Эта теорема имеет
многочисленные применения в теории алгоритмов.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 22. Теорема Райса. Теорема о неподвижной точке
123
Примеры
1. Вот как, например, с помощью теоремы о неподвижной
точке доказывается теорема Райса. Допустим, что индексное множество IF нетривиального семейства одноместных вычислимых функций F разрешимо. Пусть ?a ?
? F , ?b ?
/ F . Если множество IF разрешимо, то вычислима
функция
(
b, если x ? IF ;
f (x) =
a, если x ?
/ IF .
По теореме о неподвижной точке, существует число n такое, что ?f (n) = ?n . Пусть n ? IF , т. е. ?n ? F . Тогда
f (n) = b, что невозможно, так как в этом случае ?n =
= ?f (n) = ?b ?
/ F . Аналогично, если n ?
/ IF , т. е. ?n ?
/ F,
то f (n) = a, что также невозможно, ибо в этом случае ?n =
= ?f (n) = ?a ? F . Значит, неверно ни одно из утверждений
n ? IF и n ?
/ IF . Полученное противоречие доказывает, что
на самом деле множество IF неразрешимо.
2. Если f тотальная одноместная вычислимая функция, то
существует такое число n, что Wf (n) = Wn . Действительно, по теореме о неподвижной точке, существует число n
такое, что ?f (n) = ?n . Тогда
Wf (n) = Dom(?f (n) ) = Dom(?n ) = Wn .
3. Существует такое число n, что (?x)?n (x) = xn . Для доказательства этого факта рассмотрим двуместную вычислимую функцию f (m, x) = xm . По теореме о параметризации, существует тотальная одноместная вычислимая
функция k такая, что f (m, x) = ?k(m) (x) для любых m, x.
По теореме о неподвижной точке, существует такое число
n, что ?k(n) = ?n . Тогда для любого x имеем: ?n (x) =
= ?k(n) (x) = f (n, x) = xn , что и требовалось.
Задачи
1. Пусть тотальная одноместная вычислимая функция
f : N ? N удовлетворяет условию (?x)f (x) > x. Доказать,
что множество значений Ran(f ) функции f разрешимо.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
124
Гл. 22. Теорема Райса. Теорема о неподвижной точке
2. Доказать, что каждое бесконечное перечислимое множество A ? N является множеством значений некоторой
взаимно-однозначной тотальной вычислимой функции
f : N ? N.
3. Доказать, что график тотальной вычислимой функции является разрешимым.
4. Доказать, что полный прообраз f ?1 (A) разрешимого множества A относительно тотальной вычислимой функции f
разрешим.
5. Пусть A ? N разрешимое множество, f : N ? N тотальная вычислимая функция, причем Ran(f ) = N , f (A)?
? f (N \ A) = ?. Доказать, что множество f (A) разрешимо.
6. Пусть A, B перечислимые множества, C разрешимое
множество, причем A ? B = ?, A ? C ? A ? B . Доказать,
что множество A разрешимо.
7. Пусть A произвольное семейство перечислимых множеств натуральных чисел. Индексным множеством семейства A называется множество IA = {n|Wn ? A}. Семейство A называется нетривиальным, если оно не пусто и
содержит не все перечислимые множества натуральных
чисел. Доказать следующий вариант теоремы Райса для
перечислимых множеств: индексное множество IA всякого нетривиального семейства перечислимых множеств A
неразрешимо.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
23
ЯЗЫК ФОРМАЛЬНОЙ АРИФМЕТИКИ.
АРИФМЕТИЧЕСКИЕ МНОЖЕСТВА И ФУНКЦИИ
Сейчас мы рассмотрим некоторые применения теории алгоритмов в математической логике. Как известно, математическая логика математическими методами изучает математические рассуждения. Всякое рассуждение есть в некотором смысле
логически правильная последовательность утверждений. Чтобы
сделать математические утверждения точными математическими объектами, для их записи в математической логике разработаны искусственные, формализованные языки. Мы рассмотрим
один из таких языков , предназначенный для записи утверждений о натуральных числах.
Как и всякий формализованный язык, язык формальной арифметики использует фиксированный
. Алфавит языка
формальной арифметики содержит следующие символы:
0 и 1,
сложения + и умножения ·,
равенства =, а также символы
для логических операций ¬ (отрицание), & (конъюнкция), ?
(дизъюнкция), ? (импликация) и кванторов всеобщности ? и
существования ?. Кроме того, в языке формальной арифметики
имеются счетное множество переменных V = {v0 , v1 , v2 , ...} и
скобки (, ).
Среди всех слов в описанном алфавите различаются два
типа осмысленных выражений термы и формулы. Терм это формальный аналог числовой формы. Термы строятся по
следующим правилам:
язык формальной арифметики
алфавит
станты
символы для операций
символ для отношения
кон-
? константы 0 и 1 являются термами;
? всякая переменная является термом;
? если t1 и t2 термы, то выражения (t1 + t2 ) и (t1 · t2 )
являются термами.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
126
Гл. 23. Язык формальной арифметики
Например, термами являются выражения 0, 1, (1+1),
((1+1)+1) и т. д. Очевидно, что эти термы являются записями
чисел 0, 1, 2, 3 и т. д. В дальнейшем мы будем через n обозначать
терм, являющийся записью натурального числа n. Например, 7
есть ((((((1+1)+1)+1)+1)+1)+1).
является формальным аналогом высказывания или
высказывательной формы. Формулы строятся по следующим
правилам:
Формула
? если t1 и t2 термы, то выражение t1 = t2 является
формулой;
? если ? формула, то выражение ¬? является формулой;
? если ? и ? формулы, то выражения (?&?), (? ? ?),
(? ? ?) являются формулами;
? если ? формула, x переменная, то выражения ?x? и
?x? являются формулами.
Например, формулой является выражение ?v1 ((v1 · (1 + 1)) =
= v0 ). Очевидно, что эта формула является записью высказывательной формы ѕv0 четное числої. Формула ?v1 ((v1 · 2) =
= 5) выражает ложное высказывание, а формула ?v1 ((v1 · 2) = 4)
выражает истинное высказывание.
Выражает ли данная формула высказывание или высказывательную форму, зависит от присутствия в ней свободных вхождений переменных. Свободные и связанные вхождения переменных в формулу различаются следующим образом. В формуле
вида ?x? или ?x? ее часть ?x или ?x называется
, а ? еј областью действия. Вхождение переменной x называется
, если оно находится в кванторной
приставке ?x или ?x или в ее области действия. Вхождение переменной называется
, если оно не является связанным.
Формула, не содержащая свободных вхождений переменных,
называется
, или высказыванием. Очевидно, что всякое высказывание оказывается истинным или ложным при естественном понимании всех входящих в него символов. Обозначим через T множество всех истинных высказываний, а через F множество всех ложных высказываний.
Если формула ?(x1 , ..., xn ) не содержит свободных вхождений переменных, отличных от x1 , ..., xn , то она превращается в
приставкой
кванторной
связанным
свободным
замкнутой формулой
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 23. Язык формальной арифметики
127
высказывание ?(k1 , ..., kn ), если вместо этих свободных вхождений подставить соответственно термы k1 , ..., kn , изображающие
натуральные числа k1 , ..., kn . Поэтому такая формула может
рассматриваться как высказывательная форма. Например, отношение x < y выражается формулой
?v0 (¬(v0 = 0)&((x + v0 ) = y)).
Поэтому в дальнейшем вместо такой формулы мы иногда
будем писать просто x < y .
Пусть n > 1 натуральное число. Множество A ? N n называется арифметическим, если существует арифметическая формула ?A (v1 , ..., vn ) со свободными переменными только из списка
v1 , ..., vn такая, что для любых натуральных чисел k1 , ..., kn выполняется следующее условие:
hk1 , ..., kn i ? A ? ?(k1 , ..., kn ) ? T .
В этом случае будем говорить, что формула ?A (v1 , ..., vn ) определяет множество A.
Если множества nA, B ? N n являются арифметическими, то множества N \ A, A ? B, A ? B также
являются арифметическими.
Т е о р е м а 23.1.
Д о к а з а т е л ь с т в о. Пусть множества A и B определяются
соответственно формулами ?A (v1 , ..., vn ) и ?B (v1 , ..., vn ).
Тогда, очевидно, множество N n \ A определяется формулой
¬?A (v1 , ..., vn ), множество A ? B определяется формулой
?A (v1 , ..., vn ) ? ?B (v1 , ..., vn ), а множество A ? B определяется
формулой ?A (v1 , ..., vn )&?B (v1 , ..., vn ). Теорема 23.1 доказана.
Частичная функция f из множества N n в множество N называется арифметической, если ее график ?f является арифметическим множеством. Формулу, определяющую график арифметической функции f , будем обозначать ?f (v1 , ..., vn , vn+1 ).
Всякая вычислимая числовая функция является арифметической.
Т е о р е м а 23.2.
Д о к а з а т е л ь с т в о. В силу тезиса Черча всякая вычислимая
числовая функция является частично-рекурсивной. Поэтому достаточно доказать, что всякая частично-рекурсивная функция
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
128
Гл. 23. Язык формальной арифметики
является арифметической. Сначала докажем арифметичность
базисных функций. Очевидно, что функция s(x) = x + 1 определяется формулой v2 = (v1 + 1); функция o(x) = 0 определяется
n (x , ..., x ) = x
формулой v2 = 0; функция Im
1
n
m определяется
формулой vn+1 = vm .
Докажем теперь, что если арифметичны k -местная функция
f и n-местные функции g1 , ..., gk , то n-местная функция h, получающаяся из них подстановкой, также арифметична. Пусть
?f (v1 , ..., vk , vk+1 ), ?gi (v1 , ..., vn , vn+1 )(i = 1, ..., k)
суть формулы, определяющие соответствующие функции. Тогда, очевидно, функция h определяется следующей формулой:
?u1 ...?uk (?g1 (v1 , ..., vn , u1 )&...
...&?gk (v1 , ..., vn , uk )&?f (u1 , ..., uk , vn+1 )).
Докажем, что если n-местная (n > 1) частичная функция g
получается с помощью минимизации из (n + 1)-местной частичной арифметической функции f , то функция g также арифметична. Пусть формула ?g (v1 , ..., vn , vn+1 , vn+2 ) определяет функцию g . Тогда, очевидно, функция f определяется следующей
формулой:
?v(v < vn+1 ? ?w(?g (v1 , ..., vn , v , w)&¬(w = 0)))&
?g (v1 , ..., vn , vn+1 , 0).
Случай, когда (n + 1)-местная (n > 1) частичная функция h
получается с помощью операции рекурсии из n-местной арифметической функции f и (n+ 2)-местной арифметической функции
g , требует некоторой изобретательности.
Пусть x, y , z натуральные числа. Говорят, что число z
y
x, и пишут z ? y(mod x),
если числа z и y дают одинаковые остатки при делении на x
или, что то же самое, если их разность z ? y делится на x.
Отметим следующий известный факт из алгебры: если числа
w и x взаимно просты, то существует такое число z , что wz ?
? 1(mod x).
сравнимо с числом по модулю
Каковы бы ни
и натуральные попарно
Л е м м а 23.1 (китайская теорема об остатках).
y1 , ..., yk
были натуральные числа
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 23. Язык формальной арифметики
129
взаимно простые числа x , ..., xk , существует натуральное
число z такое, что z ? y (mod x ), ..., z ? yk (mod xk ).
1
1
1
Д о к а з а т е л ь с т в о. Пусть x = x1 ...xk . Тогда x = w1 x1 =
= ...wk xk для подходящих чисел w1 , ..., wk . Для любого i =
= 1, ..., k числа wi и xi взаимно просты, следовательно существует такое число zi , что wi zi ? 1(mod xi ). Положим теперь
z = w1 z1 y1 + ... + wk zk yk . Тогда z ? y1 (mod xi ) для любого i =
= 1, ..., k . Лемма 23.1 доказана.
Пусть rm(x, y) обозначает остаток от деления числа y на число
x. Рассмотрим следующую функцию: ?(x, y , z) = rm(1 + (z + 1) ·
· y , x) (обычно еј называют ? ).
функцией Геделя
Л е м м а 23.2. Для любой конечной последовательности натуральных чисел k , k , ..., kn существуют такие натуральные числа b и c, что для любого i = 0, 1, ..., n имеет место равенство
?(b, c, i) = ki .
0
1
Д о к а з а т е л ь с т в о. Пусть j = max(n, k0 , k1 , ..., kn ) и c = j!.
Рассмотрим числа ui = 1 + (i + 1) · c (i = 0, 1, ..., n). Они попарно
взаимно просты. Действительно, если бы числа ul и um , где 1 6
6 l < m 6 n, имели простой общий делитель p, то p было бы
делителем их разности um ? ul = (m ? l) · c, а значит и делителем
хотя бы одного из чисел m?l и c. Но так как m?l 6 j , то в любом
случае c делится на p. Однако очевидно, что тогда ни ul , ни um
не могут делиться на p. Полученное противоречие показывает,
что на самом деле числа ul и um взаимно просты. Согласно
китайской теореме об остатках (лемма 23.1), существует число
b такое, что для любого i = 0, 1, ..., n имеет место равенство b ?
? ki (mod ui ), т. е. число b дает такой же остаток при делении
на ui , как и число ki . Заметим, что для любого i = 0, 1, ..., n
выполняются условия ki 6 j 6 j! = c < 1 + (i + 1) · c = ui , т. е.
ki < ui . Это означает, что rm(ui , ki ) = ki . Теперь имеем:
?(b, c, i) = rm(1 + (i + 1) · c, b) = rm(ui , b) = rm(ui , ki ) = ki ,
что и требовалось доказать. Лемма 23.2 доказана.
Заметим, что функция ? является арифметической: она определима формулой
5 Ю. А. Белов, В. А. Соколов
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
130
Гл. 23. Язык формальной арифметики
?v5 (v1 = (((1 + ((v3 + 1) · v2 )) · v5 ) + v4 )&
v4 < ((1 + ((v3 + 1) · v2 )))),
которая, естественно, обозначается ?? (v1 , v2 , v3 , v4 ).
Вернемся к доказательству теоремы 23.2. Пусть (n +
+ 1)-местная (n > 1) частичная функция h получается с
помощью рекурсии из n-местной арифметической функции
f и (n + 2)-местной арифметической функции g . Пусть
?f (v1 , ..., vn , vn+1 , vn+2 ), ?g (v1 , ..., vn+2 , vn+3 )
формулы,
определяющие соответствующие функции. Тогда, очевидно,
функция h определяется следующей формулой:
?u?v((?w(?? (u, v , 0, w)&?f (v1 , ..., vn , w)))&?? (u, v , vn+1 , vn+2 )&
&?w(w < vn+1 ? ?y?z(?? (u, v , w, y)&
&?? (u, v , (w + 1), z)&?g (v1 , ..., vn , w, y , z)))).
Отдельно рассмотрим случай, когда одноместная функция h
получается рекурсией из числа a и двуместной функции g .
Пусть ?g (v1 , v2 , v3 ) формула, определяющая функцию g . Тогда функция h определяется следующей формулой:
?u?v(?? (u, v , 0, a)&?? (u, v , v1 , v2 )&
?w(w < v1 ? ?y?z(?? (u, v , w, y)&
&?? (u, v , (w + 1), z)&?g (w, y , z)))).
Итак, мы доказали, что все базисные функции являются арифметическими, а с помощью операций подстановки, рекурсии и
минимизации из арифметических функций получаются только арифметические функции. Следовательно, всякая частичнорекурсивная функция арифметична. Теорема 23.2 доказана.
Т е о р е м а 23.3. Всякое перечислимое множество A ? N является арифметическим.
Д о к а з а т е л ь с т в о. Пусть множество A ? N перечислимо.
Тогда оно является областью определения некоторой вычислимой функции f . По теореме 23.2, функция f арифметична.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 23. Язык формальной арифметики
131
Пусть ?f (v1 , v2 ) формула, определяющая функцию f . Так
как A является областью определения функции f , то, очевидно,
формула ?v2 ?f (v1 , v2 ) определяет множество A. Теорема 23.3
доказана.
Т е о р е м а 23.4.
множество.
Существует неперечислимое арифметическое
Д о к а з а т е л ь с т в о. Пусть A какое-нибудь неразрешимое
перечислимое множество. По теореме 23.3 оно является арифметическим. По теореме 23.1 его дополнение также арифметично,
но оно, очевидно, неперечислимо. Теорема 23.4 доказана.
Задачи
1. Доказать, что множество всех простых чисел является
арифметическим.
2. Доказать, что если множества A, B ? N арифметичны, то
их разность A \ B также арифметична.
3. Для следующих функций написать определяющие их
арифметические формулы:
(
x2 , если x четно;
(а) f1 (x) =
x + 1, если x нечетно;
(б) f (x, y) = xy (здесь 00 = 1);
(в) f (x) = x! (здесь 0! = 1);
(
1, если x > 0;
(г) sg(x) =
0, если x = 0;
(
0, если x > 0;
(д) sg(x) =
1, если x = 0;
(
x ? 1, если x > 0;
(е) p(x) =
0, если x = 0;
(
x ? y , если x > y ;
(ж) d(x, y) =
0, если x < y ;
5*
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
132
Гл. 23. Язык формальной арифметики
(з) |x ? y|;
(и) max(x, y);
(к) min(x, y);
(л) x ? y ;
(м) x/y ;
?
(н) y x
(о) x/2;
(п) [ x2 ].
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
24
ГЕДЕЛЕВА НУМЕРАЦИЯ АРИФМЕТИЧЕСКИХ
ФОРМУЛ. ТЕОРЕМА ТАРСКОГО. ПЕРВАЯ ТЕОРЕМА
ГЕДЕЛЯ О НЕПОЛНОТЕ
Каждому символу ? из алфавита языка формальной арифметики сопоставим натуральное число g(?), называемое
символа ?: g(0) = 3, g(1) = 5, g(+) = 7, g(·) =
= 9, g(=) = 11, g(¬) = 13, g(&) = 15, g(?) = 17, g(?) = 19, g(?) =
= 21, g(?) = 23, g(() = 25, g()) = 27, g(vi ) = 29 + 2i(i = 0, 1, 2, ...).
Таким образом, различным символам поставлены в соответствие
различные нечетные натуральные числа.
Каждому слову w = ?0 ?1 ...?n в алфавите языка формальной
арифметики сопоставим натуральное число
гјделе-
вым номером
n)
g(w) = 2g(?0 ) · 3g(?1 ) · ... · pg(?
,
n
где pn есть n-е простое число, если считать p0 = 2. Число
g(w) будем называть гјделевым номером слова w. В частности,
каждый терм t имеет некоторый гјделев номер g(t) и каждая
формула ? имеет некоторый гјделев номер g(?). Например,
g(v0 = v1 ) = 229 · 311 · 531 . Заметим, что в силу единственности
разложения натуральных чисел в произведения степеней простых чисел различные выражения получают различные гјделевы номера. Кроме того, гјделевы номера выражений четны и
потому отличны от гјделевых номеров символов. Такая нумерация символов и выражений языка формальной арифметики
была впервые введена Геделем с целью замены высказываний о
математических утверждениях на высказывания о натуральных
числах.
Рассмотренный здесь способ построения гјделевых номеров
не является единственно возможным. Главной отличительной
особенностью этой и других гјделевых нумераций является существование алгоритма, позволяющего по любому выражению
найти его гјделев номер, и алгоритма, который для любого
натурального числа n позволяет определить, является ли n
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
134
Гл. 24. Геделева нумерация арифметических формул
гјделевым номером какого-нибудь выражения и, если является,
найти это выражение.
Если X некоторое множество выражений языка формальной арифметики, ему соответствует множество IX ? N , состоящее в точности из гјделевых номеров выражений, входящих
в X . Будем называть IX
множества
выражений X . Теперь все эпитеты, адресованные числовым
множествам, могут быть применены к множествам выражений
языка формальной арифметики, так что множество выражений
X будет называться разрешимым, перечислимым, арифметическим и т. д., если его индексное множество IX является соответственно разрешимым, перечислимым, арифметическим и т.
д. С чисто математической точки зрения наиболее интересен
вопрос о свойствах множества T всех истинных высказываний.
В некотором смысле окончательный ответ на этот вопрос дает
следующая теорема.
индексным множеством
Множество всех истинных высказываний языка формальной арифметики не является
арифметическим.
Т е о р е м а 24.1 (теорема Тарского).
Д о к а з а т е л ь с т в о. Допустим, что множество T всех истинных высказываний языка формальной арифметики арифметично и ?T (v1 ) формула, определяющая множество IT , т. е. множество гјделевых номеров всех истинных формул. Последнее
означает, что каково бы ни было натуральное число n, формула
?T (n) истинна тогда и только тогда, когда n является гјделевым
номером истинной замкнутой формулы.
Рассмотрим следующую двуместную частичную числовую
функцию:
(
g(?(y)), если x = g(?(v1 ));
sub(x, y) =
не определено в противном случае.
Очевидно, что эта функция вычислима. Она вычисляется следующим алгоритмом: ѕПусть даны натуральные числа
x и y . Определите, является ли x гјделевым номером какойлибо формулы ?(v1 ). Если это так, то вместо всех свободных
вхождений переменной v1 в формулу ?(v1 ) подставьте терм,
изображающий число y . Вычислите гјделев номер полученной
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 24. Геделева нумерация арифметических формул
135
формулы. Это и есть значение sub(x, y)ї. Поскольку функция
sub вычислима, то в силу теоремы 23.2 она арифметична. Пусть
?sub (v1 , v2 , v3 ) формула, определяющая функцию sub. Рассмотрим формулу ?v0 (?sub (v1 , v1 , v0 )&¬?T (v0 )), которую обозначим ?(v1 ). Эта формула имеет свободные вхождения только
переменной v1 и, очевидно, утверждает, что замкнутая формула,
полученная подстановкой терма v1 вместо свободных вхождений
переменной ѕv1 ї в формулу с гјделевым номером v1 , ложна.
Пусть m = g(?(v1 )). Тогда sub(m, m) = g(?(m)). Допустим,
что высказывание ?(m) истинно. Это высказывание имеет вид
?v0 (?sub (m, m, v0 )&¬?T (v0 )), и его истинность означает, что существует такое число a, для которого истинно высказывание
?sub (m, m, a)&¬?T (a). Следовательно, a = sub(m, m) и истинно высказывание ¬?T (sub(m, m)). Но это означает, что высказывание с номером sub(m, m), т. е. ?(m), ложно. Полученное
противоречие показывает, что высказывание ?(m) не может
быть истинным. Значит, оно ложно. Ложность высказывания
?v0 (sub(m, m, v0 )&¬?T (v0 )) означает, что каково бы ни было натуральное число a, если истинно высказывание ?sub (m, m, a), то
высказывание ¬?T (a) ложно. В частности, когда a = sub(m, m)
получаем, что ложно высказывание ¬?T (sub(m, m)). Но это
означает, что истинно высказывание ?T (sub(m, m)), а тогда
истинно и высказывание с гјделевым номером sub(m, m), т. е.
?(m). Опять получили противоречие. Значит, высказывание
?(m) не истинно и не ложно, чего не может быть. Итак, наше
предположение об арифметичности множества T и существовании формулы ?T (v1 ) неверно и на самом деле множество T
неарифметично. Теорема 24.1 доказана.
Множество T всех истинных высказываний
языка формальной арифметики не является перечислимым.
Т е о р е м а 24.2.
Д о к а з а т е л ь с т в о. По теореме 23.3, всякое перечислимое
множество является арифметическим. В силу теоремы Тарского
множество T неарифметично, значит оно и неперечислимо.
Теорема 24.2 доказана.
Теорема 24.2 имеет самое непосредственное отношение к проблеме задания формальной арифметики в виде аксиоматической
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
136
Гл. 24. Геделева нумерация арифметических формул
Аксиоматический метод
аксиомами
постулатами
системы.
построения математической
теории состоит в том, что некоторые исходные факты этой теории, называемые
или
, принимаются
ѕбез доказательстваї, а все другие утверждения этой теории
выводятся из них путем рассуждений. В 1891 году итальянский
математик Дж. Пеано предложил аксиоматику для натурального ряда. На языке формальной арифметики аксиомы Пеано
записываются следующим образом:
1. ?x?y((x + 1) = (y + 1) ? x = y);
2. ?x¬((x + 1) = 0);
3. ?x((x + 0) = x);
4. ?x?y((x + (y + 1)) = ((x + y) + 1));
5. ?x((x · 0) = 0);
6. ?x?y((x · (y + 1)) = ((x · y) + x));
7. ?(0)&?x(?(x) ? ?(x + 1)) ? ?x?(x).
При этом 7) представляет собой не отдельную аксиому, а схему аксиом : какова бы ни формула ?(x), выражение 7) является
аксиомой.
В математической логике разработаны средства формального логического вывода, позволяющие из данных аксиом по
определенным правилам получать новые высказывания, логически вытекающие из аксиом и называемые
. Одним
из таких средств является
, изучаемое
в курсе математической логики. В рамках этого исчисления
вводится понятие
как конечной последовательности формул, строящейся по определенным правилам вывода.
При этом, если множество всех аксиом разрешимо (как, например, в случае аксиом Пеано), то множество всех доказательств
также оказывается разрешимым. Формула ? считается доказуемой, если существует доказательство, оканчивающееся этой
формулой. Правила вывода исчисления предикатов позволяют
на основе истинных аксиом доказывать только истинные высказывания. Нетрудно убедиться, что множество всех доказуемых
высказываний является перечислимым. Следовательно, в силу
теоремами
исчисление предикатов
доказательства
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 24. Геделева нумерация арифметических формул
137
теоремы 24.2, оно не совпадает с множеством всех истинных
высказываний. Приведенное рассуждение представляет собой
доказательство
, которая в
упрощенном виде формулируется следующим образом.
первой теоремы Гјделя о неполноте
Пусть
задана аксиоматическая теория в языке формальной арифметики с разрешимым множеством аксиом, в которой все
доказуемые высказывания истинны. Тогда существует высказывание ?, которое является истинным, но не доказуемым.
Т е о р е м а 24.3 (Первая теорема Гјделя о неполноте).
Задачи
1. Найти гјделев номер терма 2.
2. Найти гјделев номер формулы (2 · 2) = 4.
3. Пусть F множество всех ложных высказываний языка
формальной арифметики.
Доказать, что множество F неарифметично.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Литература
1. Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд. М. : Мир, 1983.
2. Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров,
Л. Л. Максимова. М. : Физматлит, 1995.
3. Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс. М. : Мир, 1972.
4. Мендельсон, Э. Введение в математическую логику
/ Э. Мендельсон. М. : Наука, 1984.
5. Успенский, В. А. Лекции о вычислимых функциях
/ В. А. Успенский. М. : Физматлит, 1960.
6. Успенский, В. А. Вводный курс математической логики
/ В. А. Успенский, Н. К. Верещагин, В. Е. Плиско. М. :
Физматлит, 2002.
7. Плиско, В. Е. Теория алгоритмов / В. Е. Плиско. URL:
http://bookre.org/reader?le=638828
8. Мальцев, А. И. Алгоритмы и рекурсивные функции
/ А. И. Мальцев. М. : Наука, 1986.
9. Белова, Л. Ю. Элементы теории множеств и математической логики. Теория и задачи: учеб. пособие
/ Л. Ю. Белова, В. А. Башкин, Ю. А. Белов. Ярославль :
ЯрГУ, 2005.
10. Клини, С. К. Математическая логика
/ С. К. Клини. М. : Мир, 1973.
11. Новиков, П. С. Элементы математической логики
/ П. С. Новиков. М. : Наука, 1973.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Учебное издание
Белов
Соколов
Юрий Анатольевич
Валерий Анатольевич
Лекции по математической логике
и теории алгоритмов
Учебное пособие
Редактор, корректор М. Э. Левакова
Компьютерный набор и верстка А. Г. Седова
Подписано в печать 12.12.12. Формат 60Ч 84 1/16.
Усл. печ. л. 8,14. Уч.-изд. л. 8,0.
Тираж 40 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрГУ.
Ярославский государственный университет
им. П. Г. Демидова.
150000, Ярославль, ул. Советская, 14.
?
A = Ran(f ).
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 20. Разрешимые и перечислимые множества
115
Обратно, пусть существует такая неубывающая вычислимая
функция f : N ? N , что A = Ran(f ). Очевидно, что в этом
случае A непусто. Если множество A конечно, то оно, очевидно,
разрешимо. Если же A бесконечно, то для выяснения вопроса,
принадлежит ли произвольное данное число x множеству A,
будем вычислять последовательные значения f (0), f (1), f (2), ...
функции f , пока среди них не появится число, большее, чем x.
Если к этому моменту число x уже появилось среди значений
функции f , то x ? A; в противном случае x ?
/ A. Итак, мы
располагаем алгоритмом для распознавания принадлежности
произвольного числа множеству A, т. е. A разрешимо. Теорема
20.12 доказана.
Функция f : N ? N называется
возрастающей, если
(?x, y)[x < y ? f (x) < f (y)].
Будем говорить, что множество A ? N перечислимо в порядке
возрастания, если существует такая возрастающая вычислимая
функция f : N ? N , что A = Ran(f ).
Т е о р е м а 20.13. Пусть A ? N. Множество A разрешимо и
бесконечно тогда и только тогда, когда оно перечислимо в
порядке возрастания.
Д о к а з а т е л ь с т в о. Пусть множество A ? N разрешимо и
бесконечно. Пользуясь разрешимостью множества A, найдем его
наименьший элемент n0 . Теперь определим функцию f : N ? N
следующим образом:
f (0) = n0 ;
f (x + 1) = µy[y ? A&f (x) < y].
Нетрудно убедиться, что f тотальная возрастающая вычислимая функция и A = Ran(f ).
Обратно, пусть существует такая возрастающая вычислимая
функция f : N ? N , что A = Ran(f ). Очевидно. что в
этом случае множество A бесконечно. Для выяснения вопроса,
принадлежит ли произвольное данное число x множеству A,
будем вычислять последовательные значения f (0), f (1), f (2), ...
функции f , пока среди них не появится число, большее, чем x.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
116
Гл. 20. Разрешимые и перечислимые множества
Если к этому моменту число x уже появилось среди значений
функции f , то x ? A; в противном случае x ?
/ A. Итак, мы
располагаем алгоритмом для распознавания принадлежности
произвольного числа множеству A, т. е. A разрешимо. Теорема
20.13 доказана.
Всякое бесконечное перечислимое множество
содержит бесконечное разрешимое подмножество.
Т е о р е м а 20.14.
Д о к а з а т е л ь с т в о. Пусть множество A ? N перечислимо и
бесконечно. Тогда по определению A является множеством значений некоторой вычислимой последовательности f . Определим
функцию g следующим образом:
g(0) = f (0);
g(x + 1) = f (µy[f (y) > g(x)]).
Нетрудно убедиться, что g тотальная возрастающая вычислимая функция. Положим B = Ran(g). По теореме 20.13 множество B разрешимо. Так как при этом, очевидно, B ? A, то
теорема 20.14 доказана.
Задачи
1. Доказать, что существует множество натуральных чисел, не
являющееся перечислимым.
2. Доказать, что бесконечное множество A ? N разрешимо тогда
и только тогда, когда A является множеством значений строго
возрастающей тотальной вычислимой функции.
3. Доказать, что непустое множество A ? N разрешимо тогда и
только тогда, когда A является множеством значений монотонно
(не обязательно строго) возрастающей тотальной вычислимой
функции.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
21
НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ
ПРОБЛЕМЫ
Как было доказано в главе 20, каждое перечислимое множество является областью определения некоторой вычислимой
функции. Это позволяет задать следующую нумерацию всех
перечислимых подмножеств N . Пусть Wx = Dom(?x ). Число x
будем называть
множества Wx . Очевидно,
что всякое перечислимое множество имеет бесконечно много
гјделевых номеров.
В главе 20 было также установлено, что каждое перечислимое множество является множеством значений некоторой вычислимой функции. Используя нумерацию перечислимых множеств, этот факт можно выразить в следующей более сильной
форме.
гјделевым номером
Существует одноместная тотальная вычислимая функция f такая, что для любого x Wx = Dom(?x) =
= Ran(?f (x) ).
Т е о р е м а 21.1.
Д о к а з а т е л ь с т в о. Будем считать, что запись !f (x) означает,
что функция f определена в точке x. Пусть двуместная функция
h определена следующим образом:
(
y , если !?x (y);
h(x, y) =
не определено в противном случае.
Очевидно, что функция h вычислима. По теореме о параметризации (глава 18), существует такая одноместная тотальная
вычислимая функция f , что h(x, y) ' ?f (x) (y) для любых x, y .
Из этого условного равенства и определения функции h следует,
что y ? Ran(?f (x) ) ?!?x (y) ? y ? Dom(?x ). Это как раз и
означает, что f искомая функция. Теорема 21.1 доказана.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
118
Гл. 21. Неразрешимые алгоритмические проблемы
про-
Пусть f частичная функция. Функция g называется
функции f , если Dom(f ) ? Dom(g) и g(x) = f (x)
для любого x ? Dom(f ).
должением
Т е о р е м а 21.2. Существует частичная вычислимая функция,
не имеющая тотального вычислимого продолжения.
Д о к а з а т е л ь с т в о. Рассмотрим
следующую
частичную
функцию f из N в N :
(
?n (n) + 1, если значение ?n (n) определено;
f (n) =
не определено, если значение ?n (n) не определено.
Очевидно, функция f вычислима. Докажем, что никакая тотальная вычислимая функция не является продолжением функции f . Пусть дана произвольная тотальная вычислимая функция g : N ? N , и пусть m гјделев номер программы,
вычисляющей функцию g . Тогда g = ?m и
g(m) = ?m (m)
(21.1)
Так как значение ?m (m) определено, то
f (m) = ?m (m) + 1
(21.2)
Равенства (1) и (2) показывают, что функция g не является
продолжением функции f .
Т е о р е м а 21.3.
жество.
Существует неразрешимое перечислимое мно-
Д о к а з а т е л ь с т в о. В силу теоремы 21.2 существует частичная вычислимая функция f , не имеющая тотального вычислимого продолжения. Область определения этой функции Dom(f )
перечислимое множество. Докажем, что оно неразрешимо.
Это вытекает из следующего довольно очевидного общего факта: если область определения частичной вычислимой функции
разрешима, то эта функция имеет тотальное вычислимое продолжение. Действительно, пусть g вычислимая частичная
функция из X в Y , причем множество Dom(g) ? X разрешимо.
Рассмотрим тотальную функцию h : X ? Y , определенную
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Гл. 21. Неразрешимые алгоритмические проблемы
следующим образом: для любого x ? X
(
g(x), если x ? Dom(g);
h(x) =
0, если x ?
/ Dom(g).
119
(21.3)
Очевидно, что функция h вычислима и является продолжением
функции g .
Множество
числимо, но не разрешимо.
Т е о р е м а 21.4.
K = {n|?n (n)
определено} пере-
Д о к а з а т е л ь с т в о. Множество K является областью определения функции f , построенной при доказательстве теоремы
21.2. Его неразрешимость была установлена при доказательстве
теоремы 21.3.
Теорема 21.4 означает алгоритмическую неразрешимость так
называемой проблемы самоприменимости программ: не существует алгоритм, который по любой программе для МНР давал
бы правильный ответ на вопрос, завершается ли работа этой
программы, когда исходным данным является гјделев номер
этой программы. Очевидно, это явление характерно не только
для МНР, но и для любого другого способа программирования.
Т е о р е м а 21.5 (неразрешимость проблемы остановки).
Не существует алгоритм, который по любой программе P для
МНР и любому исходному данному x дајт правильный ответ
на вопрос, завершается ли работа программы P на данном x.
Д о к а з а т е л ь с т в о. Если бы существовал алгоритм, о котором
идет речь в формулировке теоремы, то, очевидно, была бы
разрешима проблема самоприменимости программ, что, как мы
видели, невозможно.
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Глава
22
ТЕОРЕМА РАЙСА.
ТЕОРЕМА О НЕПОДВИЖНОЙ ТОЧКЕ
Проблема самоприменимости и проблема остановки это
лишь два примера неразрешимых алгоритмических проблем в
теории алгоритмов. На самом деле оказывается неразрешимой
любая нетривиальная алгоримическая проблема, связанная с
распознаванием свойств вычислимых функций по программам,
вычисляющим эти функции.
Пусть F произвольное семейство одноместных частичных
вычислимых числовых функций, т. е. F ? C .
семейства F называется множество IF = {n|?n ? F}.
Иными словами, индексное множество семейства F состоит в
точности из всех номеров программ, вычисляющих функции
из семейства F . Семейство F ? C называется
,
если 
Документ
Категория
Без категории
Просмотров
218
Размер файла
19 673 Кб
Теги
логика, лекция, белое, алгоритм, математические, 1642, теория
1/--страниц
Пожаловаться на содержимое документа