Математическая логика, курс лекций, задачник-практикум и решения, Лихтарников Л.М., Сукачева Т.Г., 2009

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

  Учебное пособие состоит из двух частей — курса лекций по математической логике, включающего теоретический материал по ряду разделов: алгебра логики, исчисление высказываний, логика предикатов, математические теории, алгоритмы, и задачника-практикума, содержащего упражнения по перечисленным разделам.
Учебное пособие предназначено для студентов университетов и педагогических вузов, изучающих математическую логику.




ПОНЯТИЕ ВЫСКАЗЫВАНИЯ.
Основным (неопределяемым) понятием математической логики является понятие «простого высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».

Приведем примеры высказываний.
1) Великий Новгород стоит на Волхове.
2) Париж — столица Англии.
3) Карась не рыба.
4) Число 6 делится на 2 и на 3.
5) Если юноша окончил среднюю школу, то он получает аттестат зрелости.
Высказывания 1), 4), 5) истинны, а высказывания 2) и 3) ложны.

Очевидно, предложение «Да здравствуют наши спортсмены!» не является высказыванием.
Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).

ОГЛАВЛЕНИЕ.
Предисловие.
Часть I. Курс лекций по математической логике.
Введение.
Глава 1. Алгебра логики.
§1. Понятие высказывания.
§2. Логические операции над высказываниями.
§3. Формулы алгебры логики.
§4. Равносильные формулы алгебры логики.
§5. Равносильные преобразования формул.
§6. Алгебра Буля.
§7. Функции алгебры логики.
§8. Представление произвольной функции алгебры логики в виде формулы алгебры логики.
§9. Закон двойственности.
§10.Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ).
§11. Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ).
§12.Проблема разрешимости.
§13.Некоторые приложения алгебры логики.
Глава 2. Исчисление высказываний.
§1. Понятие формулы исчисления высказываний.
§2. Определение доказуемой формулы.
§3. Производные правила вывода.
§4. Понятие выводимости формулы из совокупности формул.
§5. Понятие вывода.
§6. Правила выводимости.
§7. Доказательство некоторых законов логики.
§8. Связь между алгеброй высказываний и исчислением высказываний.
§9. Проблемы аксиоматического исчисления высказываний
Глава 3. Логика предикатов.
§1. Понятие предиката.
§2. Логические операции над предикатами.
§3. Кванторные операции.
§4. Понятие формулы логики предикатов.
§5. Значение формулы логики предикатов.
§6. Равносильные формулы логики предикатов.
§7. Предваренная нормаль ная форма.
§8. Общезначимость и выполнимость формул.
§9. Пример формулы, выполнимой в бесконечной области и невыполнимой ни в какой конечной области.
§10.Проблема разрешимости для общезначимости и выполнимости, неразрешимость ее в общем случае (без доказательства).
§11. Алгоритмы распознавания общезначимости формул в частных случаях.
§12.Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.
§13.Замечание об аксиоматическом исчислении предикатов.
Глава 4. Математические теории.
§1. Язык первого порядка.
§2. Термы и формулы.
§3. Логические и специальные аксиомы. Правила вывода.
§4. Примеры математических теорий из алгебры, анализа, геометрии.
§5. Доказательство в теории.
§6. Доказуемость частных случаев тавтологий.
§7. Теорема дедукции.
§8. Интерпретация языка теории.
§9. Истинностные значения формул в интерпретации. Модель теории.
§10.Изоморфизм интерпретаций. Категоричность теории.
§11. Проблемы непротиворечивости, полноты, разрешимости теории.
§12.Непротиворечивость и счисления предикатов (теории без специальных аксиом).
§13.Теория натуральных чисел.
§14.Теорема Геделя о неполноте.
Глава 5. Алгоритмы.
§1. Понятие алгоритма и его характерные черты.
§2. Разрешимые и перечислимые множества.
§3. Уточнение понятия алгоритма.
§4. Вычислимые функции. Частично рекурсивные и общерекурсивные функции.
§5. Машины Тьюринга.
§6. Нормальные алгоритмы Маркова.
§7. Неразрешимые алгоритмические проблемы (обзор).
Часть II. Задачник-практикум по математической логике.
Глава 1. Алгебра логики.
§1. Высказывания и логические операции над ними. Формулы алгебры логики.
§2. Равносиль ные формулы алгебры логики.
§3. Функции алгебры логики. Совершенные нормальные формы.
§4. Приложения алгебры логики.
Глава 2. Исчисление высказываний.
Глава 3. Логика предикатов.
§1. Понятие предиката. Логические и кванторные операции над предикатами.
§2. Понятие формулы логики предикатов. Равносильные формулы логики предикатов.
§3. Общезначимость и выполнимость формул. Предваренная нормаль ная форма (п.н.ф.).
§4. Применение логики предикатов в математике.
Глава 4. Алгоритмы.
§1. Частично рекурсивные и общерекурсивные функции.
§2. Машина Тьюринга.
Ответы, указания, решения.
Глава 1.
Глава 2.
Глава 3.
Глава 4.
Литература.

Купить .





Теги: учебник по математике :: математика :: Лихтарников :: Сукачева