|
ОГЛАВЛЕНИЕ
Предисловие..............3 РАЗДЕЛ I. ПРОСТЕЙШИЕ ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ 9 Глава 1. Пропозициональные формулы как средство моделирования математических и других утверждений на естественном языке............ — § 1. Анализ сложных предложений..... 11 § 2. Метаязык для определения логических формул.. 13 § 3. Определение пропозициональной формулы.... 15 § 4. Булевы функции......... 18 § 5. Применение пропозициональных формул к контактным схемам.......... 22 Глава 2. Секвенциальный вариант исчисления предикатов. - 23 § 1. Формальный аппарат выводимости..... — § 2. Язык исчисления предикатов....... 27 § 3. Валентность постоянных формул исчисления предикатов. 30 § 4. Секвенциальное исчисление предикатов..... 32 Глава 3. Использование языка исчисления предикатов для построения математических теорий....... 36 § 1. Аксиоматическая элементарная теория чисел... 37 § 2. Построение основ теории множеств в системе Цермело— Френкеля........... 39 Глава 4. Простейшие свойства исчисления высказываний и исчисления предикатов......... 48 § 1. Теорема о семантическом обосновании исчисления высказываний § 2. Правила, допустимые в исчислениях высказываний и предикатов............ 51 § 3. Непротиворечивость и полнота исчисления высказываний. 58 § 4. Доказательство теоремы об эквивалентной замене.. 59 § 5. Теоремы о конъюнктивной и дизъюнктивной нормальной форме............ 63 § 6. Совершенная конъюнктивная и дизъюнктивная нормальная форма............ 66 § 7. Предваренная нормальная форма...... 70 Краткие комментарии........... 73 Указатель литературы.......... 75 РАЗДЕЛ П. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ В ТЕОРИИ ПРОГРАММИРОВАНИЯ...........76 Глава 1. Математически точное понятие алгоритма, основанное на некоторых простых средствах языков программирования. — § 1. Определение математически точного понятия алгоритма.
Примеры........... 33
§ 2. Универоальная программа....... 90
§ 3. Представление о трансляторах компилирующего и интерпретирующего типа. Метод раскрутки..... 91
§ 4. Невозможность построения алгоритмов, обладающих некоторыми заранее заданными свойствами.... 94
§ 5. О распознавании инвариантных свойств алгоритмов.. 99
Глава 2. Корректное аннотирование программ..... 103
§ 1. Простейшие примеры доказательств утверждений о корректности программ......... 104
§ 2. Эквивалентность нескольких правил для доказательства
корректности оператора цикла...... 108
§ 3. Правила корректного аннотирования обращений к рекурсивной процедуре......... 114
Краткие комментарии..........120
Указатель литературы........... 12!
РАЗДЕЛ III. ПРИЛОЖЕНИЯ К ТЕОРИИ СУБРЕКУРСИВНЫХ АЛГОРИТМОВ 123
Приложение 1
Некоторые классы субрекурсивных словарных предикатов.. — Глава 1. Предваренные представления и другие свойства некоторых
субрекурсивных словарных предикатов..... —
§ 1. Дизъюнкция уравнений в словах...... 124
§ 2. Об изословарных предикатах....... 130
§ 3. Свойства предикатов класса RJ...... 133
§ 4. Свойства предикатов класса R ...... 138
§ 5. Предваренное представление s-рудиментарных предикатов 143
§ 6. Предваренное представление рудиментарных предикатов. 144 Глава 2. О непринадлежности ряда предикатов некоторым классам
субрекурсивных словарных предикатов... -147
§ 1. Одно свойство множества решений словарного уравнения — § 2. О предикатах, не являющихся изословарными...149 § 3. Соотношения между классами рудиментарных, s-рудимен-
тарных предикатов и классами предикатов R ,R .. 154
Указатель литературы........... 1о6
Приложение 2
Об одной проблеме Гжегорчика....... —
Указатель литературы........... 109
Приложение 3
О непрерывности и аппроксимируемости операторов в конструктивных метрических пространствах
1. Непрерывность операторов в конструктивных метрических
пространствах.......... 160
2. Аппроксимируемость операторов в конструктивных метриче-
ских пространствах.........172
Указатель литературы........... 190
|