Л. М. Лихтарников, Т.Г. Сукачева. Математическая Логика. Курс лекций. 3адачник-практикум и решения. Серия Учебники для вузов. - Санкт-Петербург, 1999. - 288 с.
Учебное пособие предназначено дли студентов университетов и педагогических институтов, изучающих курс математической логики. В файле представлен только курс лекций. Включает в себя разделы : Алгебра логики, исчисление высказываний, логика предикатов, математические теории, алгоритмы.
СОДЕРЖАНИЕ
Предисловие.........................................................3
Часть I. Курс лекций по математической логике
Введение.............................................................5
ГЛАВА I. АЛГЕБРА ЛОГИКИ
§ 1. Понятие высказывания..........................................9
§ 2. Логические операции над высказываниями......................10
§ 3. Формулы алгебры логики......................................14
§ 4. Равносильные формулы алгебры логики..........................16
§ 5. Равносильные преобразования формул...........................20
§ 6. Алгебра Буля...............................................21
§ 7. Функции алгебры логики....................................23
§ 8. Представление произвольной функции алгебры логики
в виде формулы алгебры логики........................................25
§ 9. Закон двойственности.........................................27
§ 10. Дизъюнктивная нормальная форма и совершенная
дизъюнктивная нормальная форма (ДНФ и СДНФ)......29
§ 11. Конъюнктивная нормальная форма и совершенная
конъюнктивная нормальная форма (КНФ и СКНФ)........31
§ 12. Проблема разрешимости.....................................34
§ 13. Некоторые приложения алгебры логики.......................37
ГЛАВА II. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
§ 1. Понятие формулы исчисления высказываний.................46
§ 2. Определение доказуемой формулы..........................48
§ 3. Производные правила вывода...............................53
§ 4. Понятие выводимости формулы из совокупности формул..........56
§ 5. Понятие вывода...........................................58
§ 6. Правила выводимости......................................59
§ 7. Доказательство некоторых законов логики.......................64
§ 8. Связь между алгеброй высказываний
и исчислением высказываний..........................................68
§ 9. Проблемы аксиоматического исчисления высказываний............. 76
ГЛАВА III. ЛОГИКА ПРЕДИКАТОВ
§ 1. Понятие предиката............................................. 83
§ 2. Логические операции над предикатами............................85
§ 3. Кванторные операции............................................87
§ 4. Понятие формулы логики предикатов...............................90
§ 5. Значение формулы логики предикатов.............................92
§ 6. Равносильные формулы логики предикатов....................93
§ 7. Предваренная нормальная форма....................................96
§ 8. Общезначимость и выполнимость формул.......................98
§ 9. Пример формулы, выполнимой в бесконечной области
и невыполнимой ни в какой конечной области.............101
§ 10. Проблема разрешимости для общезначимости и выполнимости, неразрешимость ее в общем случае (без доказательства).....................102
§ 11. Алгоритмы распознавания общезначимости формул в частных случаях..........103
§ 12. Применение языка логики предикатов для записи математических предложений, определений,
построения отрицания предложений.............................106
§ 13. Замечание об аксиоматическом исчислении предикатов..................113
ГЛАВА IV. МАТЕМАТИЧЕСКИЕ ТЕОРИИ
§ 1. Язык первого порядка......................................116
§ 2. Термы и формулы..........................................117
§ 3. Логические и специальные аксиомы. Правила вывода............118
§ 4. Примеры математических теорий из алгебры, анализа, геометрии..............120
§ 5. Доказательство в теории ..................................................123
§ 6. Доказуемость частных случаев тавтологий.................... 124
§ 7. Теорема дедукции ..........................................124
§ 8. Интерпретация языка теории..................................127
§ 9. Истинностные значения формул в интерпретации. Модель теории............128
§ 10. Изоморфизм интерпретаций. Категоричность теории.......................130
§ 11. Проблемы непротиворечивости, полноты, разрешимости теории...............132
§ 12. Непротиворечивость исчисления предикатов (теории без специальных аксиом)............135
§ 13. Теория натуральных чисел.............................................136
§ 14. Теорема Геделя о неполноте.........................................138
ГЛАВА V. АЛГОРИТМЫ
§ 1. Понятие алгоритма и его характерные черты.................139
§ 2. Разрешимые и перечислимые множества......................141
§ 3. Уточнение понятия алгоритма...................................143
§ 4. Вычислимые функции. Частично рекурсивные
и общерекурсивные функции.............................................146
§ 5. Машины Тьюринга................................................ 152
§ 6. Нормальные алгоритмы Маркова.................................... 163
§ 7. Неразрешимые алгоритмические проблемы (обзор).................. 166
Часть II. Задачник-практикум по математической логике
ГЛАВА I. АЛГЕБРА ЛОГИКИ
§ 1 Высказывания и логические операции над ними.
Формулы алгебры логики...............................................174
§ 2. Равносильные формулы алгебры логики........................181
§ 3. Функции алгебры логики. Совершенные нормальные формы...........186
§ 4. Приложения алгебры логики........................................ 194
ГЛАВА II. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ Исчисление высказываний..............204
ГЛАВА III. ЛОГИКА ПРЕДИКАТОВ
§ 1. Понятие предиката. Логические и кванторные операции над предикатами... 214
§ 2. Понятие формулы логики предикатов. Равносильные формулы логики предикатов......223
§ 3. Общезначимость и выполнимость формул. Предваренная нормальная форма (п.н.ф.)...230
§ 4. Применение логики предикатов в математике...............234
ГЛАВА IV. АЛГОРИТМЫ
§ 1. Частично рекурсивные и общерекурсивные функции.... 242
§ 2. Машина Тьюринга....................................................245
Ответы, указания, решения
Литература...................................................................282
