Дисциплина: Математическая логика.
Цель дисциплины. Обучение студентов знаниям, умениям и навыкам, позволяющим овладеть методологическими основами языка современной математики, усвоить основные идеи построения систем математических знаний посредством формальных аксиоматических теорий; сформулировать точное математическое понятие алгоритма; использовать идеи и методы математической логики при изучении других математических дисциплин.
Задачи дисциплины.
1.Изучение языка алгебры высказываний и алгебры предикатов, их выразительных возможностей и алгоритмических свойств.
2. Построение исчисления высказываний в виде формальной аксиоматической теории.
3. Построение и изучение класса машин Тьюринга, как формального аналога класса интуитивных алгоритмов.
4. Изучение теории натуральных чисел, как формальной аксиоматической теории.
Содержание курса
Тема 1. Алгебра множеств.
Предмет и методы математической логики. Краткие исторические сведения о возникновении и развитии этой области математики, её связи с другими математическими дисциплинами. Дедуктивный характер математики и роль математической логики в обосновании математики и в приложениях в теоретическом программировании.
Тема 2. Алгебра высказываний.
Логические операции над высказываниями. Формулы. Истинные значения формул. Восстановление формулы по её таблице истинности. Равносильные преобразования формул. Тавтологии – законы логики высказываний. Законы де-Моргана, контрапозиции, двойного отрицания. Дизъюнктивная и конъюнктивная нормальные формы. Полные системы логических связок.
Тема 3. Исчисление высказываний.
Формальные системы. Аксиомы и правило вывода ИВ. Доказуемость формул. Выводимость формул из гипотез. Теорема дедукции. Лемма о выводимости. Лемма Кальмара. Полнота исчисления высказываний. Непротиворечивость исчисления высказываний.
Тема 4. логика предикатов.
Понятие предиката и операции на множестве. Модели. Термы фиксированной сигнатуры. Атомные формулы логики предикатов, свободные и связанные переменные, кванторы. Формулы логики предикатов. Выполнимость формулы в моделях. Равносильность формул логики предикатов и основные равносильные преобразования. Пренексная нормальная форма. Общезначимость и выполнимость формул.
Тема 5. Исчисление предикатов.
Аксиоматический метод в математике. Содержательные и формальные аксиоматические теории. Теории первого порядка, общелогические и специальные аксиомы. Понятие модели. Отношение изоморфизма; автоморфизмы модели. Модели арифметики; определимость отношений в фрагментах модели арифметики. Метод Падоа доказательства неопределимости некоторых арифметических отношений. Формальная система исчисления предикатов. Правила вывода. Доказуемые формулы и формулы, выводимые из множества гипотез. Доказуемость частных случаев тавтологий. Теорема дедукции для исчисления предикатов.
Тема 6. Метод формальных аксиоматических теорий. Формальная арифметика.
Аксиоматическое построение теорий. (Векторные пространства, евклидова геометрия). Аксиоматическое построение арифметики Пеано. Аксиомы и правила вывода. Роль аксиомы индукции в обосновании законов арифметических операций. Примеры формальных выводов законов арифметики Пеано. Система аксиом формальной арифметики. Аксиома индукции. Примеры построения выводов в формальной арифметике. Теорема Геделя о неполноте арифметики.
Литература
Основная
1. , Сукачева логика. М., Наука, 2008.
2. . Математическая логика. М., 2002.
3. . Математическая логика и теория алгоритмов. Изд-во Саратовского университета, 2001.
4. Введение в математическую логику. Пер. с англ. М., 2000.
5. , . Сборник задач по теории множеств, математической логике и теории алгоритмов. М., 2002.
6. . Задачник-практикум по математической логике. М., 2004.
Дополнительная
7. математическая логика. Пер. с англ. М., 2000.
8. Гиндикин. логики в задачах. М., 2002.
9. , . Математическая логика. – М.: Наука, 2004.
10. , . Вводный курс математики. – Павлодар, НИЦ ПГУ им. С. Торайгырова, 2004
