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


Для студентов, аспирантов и преподавателей технических вузов.
Оглавление
ЧАСТЬ 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



Читать онлайн
скачать бесплатно


Теги:
Математическая логика, курс лекций по математической логике, Шапорев математическая логика

Коментарі до Шапорев С. Д. Математическая логика. Курс лекций и практических занятий ОНЛАЙН