Лихтарников Л. М., Сукачева Т.Г. Математическая логика. Курс лекций. 3адачник-практикум и решения ОНЛАЙН


СОДЕРЖАНИЕ
Предисловие…………………………………………………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



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


Теги:
сборник задач по математической логике, Лихтарников математическая логика, практикум по математической логике, решебник по математической логике

Коментарі до Лихтарников Л. М., Сукачева Т.Г. Математическая логика. Курс лекций. 3адачник-практикум и решения ОНЛАЙН