Учебное пособие предназначено для студентов университетов и педагогических вузов, изучающих математическую логику. Предисловие
| Вид материала | Учебное пособие |
- Учебное пособие М.: Педагогическое общество России. 1999 442, 5623.86kb.
- В. Ф. Пономарев математическая логика, 2676.48kb.
- Лесников Анатолий Ильич, старший преподаватель Уфимского Государственного института, 1383.27kb.
- В. И. Ульянова ленина кафедра региональной геологии и полезных ископаемых региональная, 650.15kb.
- Л. Н. Шиян Свойства и химия воды. Водоподготовка Учебное пособие, 1119.56kb.
- Пособие предназначено для студентов и преподавателей биологических и психологических, 4623.82kb.
- В. М. Агеев экономическая теория учебное пособие, 1438.84kb.
- Учебное пособие для вузов / Г. Р. Колоколов. М.: Издательство «Экзамен», 2006. 256, 66.37kb.
- Предлагаемое учебное пособие предназначено для студентов, аспирантов и преподавателей, 2052.38kb.
- Учебное пособие предназначено для студентов вузов естественнонаучных, технических, 4646.64kb.
Лихтарников Л. М., Сукачева Т. Г.Математическая логика. Курс лекций.
Задачник-практикум и решения:
Учебное пособие. 3-е изд.
ISBN 978-5-8114-0082-9
Год выпуска 2008
Тираж 2000 экз.
Формат 12,8 20 см
Переплет: твердый
Страниц 288
Учебное пособие состоит из двух частей — курса лекций по математической логике, включающего теоретический материал по ряду разделов: алгебра логики, исчисление высказываний, логика предикатов, математические теории, алгоритмы, и задачника-практикума, содержащего упражнения по перечисленным разделам.
Учебное пособие предназначено для студентов университетов и педагогических вузов, изучающих математическую логику.
Предисловие
Настоящее учебное пособие «Математическая логика. Курс лекций и задачник-практикум» предназначено для студентов университетов и педагогических институтов, изучающих математическую логику.
Оно состоит из двух частей. Часть первая «Курс лекций по математической логике» включает в себя теоретический материал по разделам: 1. Алгебра логики. 2. Исчисление высказываний. 3. Логика предикатов. 4. Математические теории. 5. Алгоритмы.
Часть вторая «Задачник-практикум по математической логике» содержит набор упражнений почти по всем перечисленным разделам.
В зависимости от содержания программ курса математической логики на конкретных специальностях, отдельные разделы пособия могут быть исключены из рассмотрения (например, исчисление высказываний, математические теории), а из других разделов использована лишь часть материала.
Учитывая, что в отдельных случаях студентам требуется лишь «Задачник-практикум», в каждом его разделе приводится минимум теоретических сведений, необходимых для решения предлагаемых задач. Студенты математических специальностей университетов и педагогических институтов материалы разделов 1, 3 и 5 могут впоследствии использовать в подготовке школьного факультативного курса «Элементы математической логики».
Оглавление
Предисловие .......... 3
Часть I. Курс лекций по математической логике
Введение .......... 7
Глава 1. Алгебра логики .......... 11
§ 1. Понятие высказывания .......... 11
§ 2. Логические операции над высказываниями .......... 12
§ 3. Формулы алгебры логики .......... 16
§ 4. Равносильные формулы алгебры логики .......... 18
§ 5. Равносильные преобразования формул .......... 21
§ 6. Алгебра Буля .......... 22
§ 7. Функции алгебры логики .......... 24
§ 8. Представление произвольной функции алгебры логики в виде формулы алгебры логики .......... 26
§ 9. Закон двойственности .......... 28
§ 10. Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ) .......... 30
§ 11. Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ) .......... 32
§ 12. Проблема разрешимости .......... 34
§ 13. Некоторые приложения алгебры логики .......... 37
Глава 2. Исчисление высказываний .......... 46
§ 1. Понятие формулы исчисления высказываний .......... 46
§ 2. Определение доказуемой формулы .......... 48
§ 3. Производные правила вывода .......... 52
§ 4. Понятие выводимости формулы из совокупности формул .......... 56
§ 5. Понятие вывода .......... 57
§ 6. Правила выводимости .......... 59
§ 7. Доказательство некоторых законов логики .......... 64
§ 8. Связь между алгеброй высказываний и исчислением высказываний .......... 67
§ 9. Проблемы аксиоматического исчисления высказываний 76
Глава 3. Логика предикатов .......... 82
§ 1. Понятие предиката .......... 82
§ 2. Логические операции над предикатами .......... 84
§ 3. Кванторные операции .......... 85
§ 4. Понятие формулы логики предикатов .......... 88
§ 5. Значение формулы логики предикатов .......... 89
§ 6. Равносильные формулы логики предикатов .......... 90
§ 7. Предваренная нормальная форма .......... 92
§ 8. Общезначимость и выполнимость формул .......... 95
§ 9. Пример формулы, выполнимой в бесконечной области и невыполнимой ни в какой конечной области .......... 97
§ 10. Проблема разрешимости для общезначимости и выполнимости, неразрешимость ее в общем случае (без доказательства) .......... 99
§ 11. Алгоритмы распознавания общезначимости формул в частных случаях .......... 100
§ 12. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений .......... 103
§ 13. Замечание об аксиоматическом исчислении предикатов 109
Глава 4. Математические теории .......... 111
§ 1. Язык первого порядка .......... 112
§ 2. Термы и формулы .......... 113
§ 3. Логические и специальные аксиомы. Правила вывода 114
§ 4. Примеры математических теорий из алгебры, анализа, геометрии .......... 116
§ 5. Доказательство в теории .......... 118
§ 6. Доказуемость частных случаев тавтологий .......... 119
§ 7. Теорема дедукции .......... 120
§ 8. Интерпретация языка теории .......... 123
§ 9. Истинностные значения формул в интерпретации. Модель теории .......... 124
§ 10. Изоморфизм интерпретаций. Категоричность теории. 126
§ 11. Проблемы непротиворечивости, полноты, разрешимости теории .......... 127
§ 12. Непротиворечивость исчисления предикатов (теории без специальных аксиом) .......... 130
§ 13. Теория натуральных чисел .......... 131
§ 14. Теорема Геделя о неполноте .......... 133
Глава 5. Алгоритмы .......... 134
§ 1. Понятие алгоритма и его характерные черты .......... 134
§ 2. Разрешимые и перечислимые множества .......... 136
§ 3. Уточнение понятия алгоритма .......... 138
§ 4. Вычислимые функции. Частично рекурсивные и общерекурсивные функции .......... 141
§ 5. Машины Тьюринга .......... 146
§ 6. Нормальные алгоритмы Маркова .......... 156
§ 7. Неразрешимые алгоритмические проблемы (обзор) .......... 160
Часть II. Задачник-практикум по математической логике
Глава 1. Алгебра логики .......... 169
§ 1. Высказывания и логические операции над ними. Формулы алгебры логики .......... 169
§ 2. Равносильные формулы алгебры логики .......... 175
§ 3. Функции алгебры логики. Совершенные нормальные формы .......... 179
§ 4. Приложения алгебры логики .......... 187
Глава 2. Исчисление высказываний .......... 197
Глава 3. Логика предикатов .......... 206
§ 1. Понятие предиката. Логические и кванторные операции над предикатами .......... 206
§ 2. Понятие формулы логики предикатов. Равносильные формулы логики предикатов .......... 214
§ 3. Общезначимость и выполнимость формул. Предваренная нормальная форма (п.н.ф.) .......... 221
§ 4. Применение логики предикатов в математике .......... 225
Глава 4. Алгоритмы .......... 233
§ 1. Частично рекурсивные и общерекурсивные функции. 234
§ 2. Машина Тьюринга .......... 238
Ответы, указания, решения .......... 244
Глава 1 .......... 244
Глава 2 .......... 251
Глава 3 .......... 260
Глава 4 .......... 265