Учебное пособие посвящено изложению элементов математической логики на основе секвенциального аппарата выводимости,, успешно используемого в современных метаматематических исследованиях, и на основе предлагаемого автором точного понятия алгоритма, ориентированного на приложения в теории программирования. Формулируются аксиомы элементарной теории чисел, строятся основы теории множеств в аксиоматической системе Цермело — Френкеля. В последнем разделе книги — приложения к теории субрекурсивных алгоритмов в специализированных направлениях. Настоящее издание рассчитано на студентов, инженеров, аспирантов и научных сотрудников, интересующихся математической логикой, современной теорией алгоритмов, а также математическими основами теории программирования.
Author(s): Косовский Н. К.
Publisher: Изд-во Ленингр. ун-та
Year: 1981
Language: Russian
Pages: 193
City: Ленинград
Титул ......Page 2
Аннотация ......Page 3
Предисловие ......Page 4
Глава 1. Пропозициональные формулы как средство моделирования математических и других утверждений на естественном языке ......Page 10
§ 1. Анализ сложных предложений ......Page 12
§ 2. Метаязык для определения логических формул ......Page 14
§ 3. Определение пропозициональной формулы ......Page 16
§ 4. Булевы функции ......Page 19
§ 5. Применение пропозициональных формул к контактным схемам ......Page 23
§ 1. Формальный аппарат выводимости ......Page 24
§ 2. Язык исчисления предикатов ......Page 28
§ 3. Валентность постоянных формул исчисления предикатов ......Page 31
§ 4. Секвенциальное исчисление предикатов ......Page 33
§ 1. Аксиоматическая элементарная теория чисел ......Page 37
§ 2. Построение основ теории множеств в системе Цермело—Френкеля ......Page 40
§ 1. Теорема о семантическом обосновании исчисления высказываний ......Page 49
§ 2. Правила, допустимые в исчислениях высказываний и предикатов ......Page 52
§ 3. Непротиворечивость и полнота исчисления высказываний ......Page 59
§ 4. Доказательство теоремы об эквивалентной замене ......Page 60
§ 5. Теоремы о конъюнктивной и дизъюнктивной нормальной форме ......Page 64
§ 6. Совершенная конъюнктивная и дизъюнктивная нормальная форма ......Page 67
§ 7. Предваренная нормальная форма ......Page 71
Краткие комментарии ......Page 74
Указатель литературы ......Page 76
Глава 1. Математически точное понятие алгоритма, основанное на некоторых простых средствах языков программирования ......Page 77
§ 1. Определение математически точного понятия алгоритма. Примеры ......Page 84
§ 2. Универоальная программа ......Page 91
§ 3. Представление о трансляторах компилирующего и интерпретирующего типа. Метод раскрутки ......Page 92
§ 4. Невозможность построения алгоритмов, обладающих некоторыми заранее заданными свойствами ......Page 95
§ 5. О распознавании инвариантных свойств алгоритмов ......Page 100
Глава 2. Корректное аннотирование программ ......Page 104
§ 1. Простейшие примеры доказательств утверждений о корректности программ ......Page 105
§ 2. Эквивалентность нескольких правил для доказательства корректности оператора цикла ......Page 109
§ 3. Правила корректного аннотирования обращений к рекурсивной процедуре ......Page 115
Краткие комментарии ......Page 121
Указатель литературы ......Page 122
Глава 1. Предваренные представления и другие свойства некоторых субрекурсивных словарных предикатов ......Page 124
§ 1. Дизъюнкция уравнений в словах ......Page 125
§ 2. Об изословарных предикатах ......Page 131
§ 3. Свойства предикатов класса R~ ......Page 134
§ 4. Свойства предикатов класса R~ ......Page 139
§ 5. Предваренное представление s-рудиментарных предикатов ......Page 144
§ 6. Предваренное представление рудиментарных предикатов ......Page 145
§ 1. Одно свойство множества решений словарного уравнения ......Page 148
§ 2. О предикатах, не являющихся изословарными ......Page 150
§ 3. Соотношения между классами рудиментарных, s-рудиментарных предикатов и классами предикатов RS-,R- ......Page 155
Указатель литературы ......Page 157
Указатель литературы ......Page 160
1. Непрерывность операторов в конструктивных метрических пространствах ......Page 161
2. Аппроксимируемость операторов в конструктивных метрических пространствах ......Page 173
Указатель литературы ......Page 191
Оглавление ......Page 192
