Шапорев С. Д. Математическая логика. Курс лекций и практических занятий

Шапорев С. Д. Математическая логика. Курс лекций и практических занятий. — СПб., 2005. - 416 с: ил.
В учебном пособии представлены разделы, традиционно изучаемые в курсе математической логики: алгебра логики и исчисление высказываний, логика и исчисление предикатов, рассмотрены вопросы содержательного и формального определения логики высказываний и логики предикатов. Дается введение в теорию алгоритмов и вычислимых функций. Содержание разделов книги взаимно связано друг с другом и снабжено большим количеством примеров и решенных задач, помогающих усвоить и закрепить излагаемый материал.
Для студентов, аспирантов и преподавателей технических вузов.
Оглавление
ЧАСТЬ I. МАТЕМАТИЧЕСКАЯ ЛОГИКА............................................1
Глава 1. Алгебра логики (алгебра высказываний).............................3
1.1. Введение......................................3
1.2. Операции над высказываниями................................5
1.3. Формулы алгебры логики..........................9
1.4. Равносильные группы формул и равносильные преобразования............11
1.5. Практическое занятие № 1. Алгебра высказываний.....................16
1.6. Алгебра Буля.........................................20
1.7. Функции алгебры логики.............................................23
1.8. Разложение булевых функций по переменным...........................25
1.9. Дизъюнктивная и конъюнктивная нормальные формы..................28
1.10. Закон двойственности................................32
1.1 К Практическое занятие № 2. Функции алгебры логики. Закон двойственности.........34
1.12. Минимизация булевых функций в классе ДНФ............................37
Карты Карно.........................................................37
1.13. Проблема разрешимости.......................................42
1.14. Полиномы Жегалкина...................................45
1.15. Полнота и замкнутость функций алгебры логики...........................48
1.16. Производные от булевых функций....................................53
1.17. k-значные логики..........................................59
1.18. Практическое занятие N° 3. Минимизация в классе дизъюнктивных нормальных форм. Замкнутые классы и полнота систем функций алгебры логики. k-значные логики..........................68
1.19. Схемы из функциональных элементов. Релейно-контактные схемы, оценка сложности схем....................................71
1.20. Решение логических задач..............................83
1.21. Практическое занятие № 4, Реализация булевых функций схемами и формулами. Решение логических задач........................87
Глава 2. Исчисление высказываний........................................... 93
2.1. Язык, система аксиом и правила вывода исчисления высказываний..............93
2.2. Некоторые дополнительные производные правила вывода......................98
2.3. Теорема дедукции и другие законы исчисления высказываний............106
Теорема дедукции................................106
Обобщение теоремы дедукции.......................................10S
Закон перестановки посылок..........................................108
Закон соединения посылок...........................................109
Закон разъединения посылок .......................................110
2.4. Практическое занятие № 5. Исчисление высказываний: правила вывода и доказуемость формул..............117
2.5. Монотонность и эквивалентность формул исчисления высказываний...............120
2.6. Связь между формулами алгебры высказываний и исчисления высказываний........122
2.7. Некоторые алгоритмы проверки выводимости формул в исчислении высказываний............128
Алгоритм Квайна ......................................129
Алгоритм метода редукций...............................131
Метод резолюций.....................................131
2.8. Проблемы аксиоматического исчисления высказываний.......................134
2.9. Практическое занятие № 6. Эквивалентность формул исчисления высказываний и теорема о выводимости. Алгоритмы Квайна, редукций и резолюций.....................................137
Глава 3. Логика предикатов.........................................141
3.1. Определение предикатов и логические операции над ними..................141
3.2. Кванторные операции..........................................146
3.3. Формулы логики предикатов.....................................149
3.4. Практическое занятие № 7. Логические и кванторные операции над предикатами............153
3.5. Равносильные формулы логики предикатов.............................................156
3.6. Предваренная нормальная форма. Общезначимость и выполнимость формул логики предикатов...............159
Случай конечных областей.............................................163
Проблема разрешимости для формул, содержащих в предваренной нормальной форме кванторы одного типа.............164
3.7. Практическое занятие № 8. Выполнимость формул логики предикатов..............166
3.8. Применение языка логики предикатов для записи математических предложений.........168
Запись математических определений............................................................168
формулировка математических теорем.........................................................170
Построение противоположных утверждений и доказательство методом от противного...............171
формулировка обратных и противоположных теорем................................173
Формулировка необходимых и достаточных условий.................................175
3.9. Практическое занятие № 9. Применение языка логики предикатов в математике.............176
Глава 4. Исчисление предикатов................................................................181
4.1. Синтаксис языка исчисления предикатов.................................................181
4.2. Аксиомы и основные правила вывода....................................................183
4.3. Производные правила вывода в исчислении предикатов........................187
4.4. Некоторые теоремы исчисления предикатов............................................188
4.5. Эквивалентные формулы...................................193
4.6. Дедуктивная эквивалентность..........................................196
4.7. Получение V-формул. Скулемовские функции......................................197
4.8. Унификация формул исчисления предикатов..........................................200
4.9. Метод резолюций в исчислении предикатов............................................204
4.10. Практическое занятие № 10. Унификация формул. Метод резолюций в исчислении предикатов...210
4.11. Некоторые проблемы аксиоматического исчисления предикатов.......212
Разрешимость.........................................................212
Непротиворечивость и независимость.......................................212
Полнота в узком смысле...................................................213
Полнота в широком смысле........................................................214
Глава 5. Теория алгоритмов.,...................................................215
5.1. Характерные черты алгоритма........................................215
5.2. Вычислимые, частично рекурсивные и общерекурсивные функции.......................218
Примитивная рекурсия...............................................219
Операция минимизации.........................................................229
5.3. Примитивная рекурсивность некоторых арифметических функций........................232
5.4. Практическое занятие № 11. Рекурсивность функций............................236
5.5. Словарные множества и функции............................................239
5.6. Машины Тьюринга..................................................244
5.7. Неразрешимые алгоритмические проблемы..........................................257
5.8. Практическое занятие № 12. Словарные функции. Построение программ для машин Тьюринга.....259
ЧАСТЬ II. ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ.......................................261
Глава б. Алгебра высказываний...............................................263
6.1. Ответы и решения задач практического занятия N° 1.....................................263
6.2. Ответы и решения практического занятия №2........................................273
6.3. Ответы и решения практического занятия №3........................................284
6.4. Ответы и решения практического занятия №4........................................307
Глава 7. Исчисление высказывании.......................................................319
7.1. Ответы и решения практического занятия № 5.......................................319
7.2. Ответы и решения практического занятия №6........................................329
Глава 8. Логика предикатов..........................................................345
8.1. Ответы и решения практического занятия № 7.......................................345
8.2. Ответы и решения практического занятия № 8.......................................351
8.3. Ответы и решения практического занятия № 9.......................................357
Глава 9. Исчисление предикатов.......................................................367
9.1. Ответы и решения практического занятия № 10.....................................367
Глава 10. Теория алгоритмов..........................................................383
10.1. Ответы и решения практического занятия № 11...................................383
10.2. Ответы и решения практического занятия № 12...................................395
Список литературы...................................................................405
Предметный указатель.........................................................................406