Математическая логика: Рабочая учебная программа дисциплины

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Уральский государственный педагогический университет» Факультет ____математический___ Кафедра __алгебры и теории чисел УТВЕРЖДАЮ: Проректор по учебной работе УрГПУ ____________________ Т.Н. Шамало «____» _____________________2007 г.

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

по дисциплине ___« Математическая логика» для специальности 032100 «Математика» по циклу___«Дисциплины предметной подготовки» Очная форма обучения

Заочная форма обучения

Курс – 4 Семестр – 8 Объѐм в часах всего – 126 в т. ч.: лекции – 30 практические занятия – 30 лабораторные занятия – 0 самостоятельная работа – 66 Зачет – 8 семестр

Курс – 6 Семестр – 11 Объѐм в часах всего – 126 в т. ч.: лекции – 10 практические занятия – 10 лабораторные занятия – 0 самостоятельная работа –106 Зачет – 11 семестр

Екатеринбург 2007

Рабочая учебная программа по дисциплине «Математическая логика» ГОУ ВПО «Уральский государственный педагогический университет» Екатеринбург, 2007, 8 с. Составитель: Ильиных А.П., зав. кафедрой алгебры и теории чисел, д.ф.-м.н., доцент Рабочая программа обсуждена на заседании кафедры алгебры и теории чисел УрГПУ Протокол от_7 апреля 2006_ г. № _8_ . Зав. кафедрой А.П. Ильиных Отделом нормативного обеспечения образовательного процесса УрГПУ выдан сертификат № ____ от ________ г. Начальник отдела ______________Р.Ю. Шебалов

2

1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Современная математика может быть представлена как наука об абстрактных объектах таких, как вещественные числа, функции, поверхности, алгебраические системы и т.д. Математическая логика рассматривает новое направление в этой науке, сосредоточивая внимание на языке, используемом в математике, на способах определения абстрактных объектов и на законах логики, которыми мы руководствуемся, когда рассуждаем об этих объектах. Логики предприняли это изучение с надеждой понять природу математического опыта и в конечном счете внести вклад в математику как важными результатами, возникающими в самой логике (теорема Гѐделя о неполноте является наиболее известным примером), так и их приложениями к другим разделам математики. Курс математической логики для студентов математических специальностей педагогических вузов имеет своей целью изложить основы этой науки, познакомить студентов с формализованным аксиоматическим методом построения математических теорий, охватывающим также и логические средства; его основными составными частями: языком, аксиомами, правилами вывода; проблемами непротиворечивости, полноты, разрешимости теорий. Изучение математической логики безусловно будет способствовать более ясному представлению об общей структуре математических теорий, о математике в целом, а значит, и о школьной математике. Курс математической логики имеет разнообразные межпредметные связи с алгеброй и теорией чисел, геометрией, математическим анализом. Настоящая программа предусматривает также существенную связь его с курсом информатики. Это касается изучения языка первого порядка и формализованного построения математических теорий. Исчисление высказываний может быть изложено на основе книги Д. Шенфилда “Математическая логика”. Раздел «Алгоритмы» изучается в том объеме, который необходим для формулировки теоремы К.Геделя о неполноте аксиоматических теорий. На практических занятиях студенты решают задачи по разделам «логика высказываний», «исчисление высказываний», «логика предикатов», «теории 1-го порядка», «модели теорий». Они должны овладеть техникой логических преобразований, особенно обращению с кванторами, научиться доказывать выводимость формулы исчисления высказываний с использованием правил вывода. По курсу математической логики предусматривается проведение двух контрольных работ.

2. УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ 2.1. Учебно-тематический план очной формы обучения

№ п/п

Наименование раздела, темы

1 2

Аксиоматический метод Алгебра высказываний. Нормальные формы Исчисление высказываний.

3

Аудиторные Всего занятия труПрадоем- Все- Лек- ктикость го ции ческие 8 4 2 2 32 16 8 8 24

12 3

6

6

Лабораторные

Самостоятельная работа 4 16 12

4 5 6 7 8

Предикаты и кванторы. Теории 1-го порядка. Модель теории 1-го порядка. Теорема полноты К. Геделя. Теорема Геделя о неполноте. Итого

16 16 10 10 10 126

8 8 4 4 4 60

4 4 2 2 2 30

4 4 2 2 2 30

8 8 6 6 6 66

Учебно-тематический план заочной формы обучения

№ п/п

Наименование раздела, темы

1 2

Аксиоматический метод Алгебра высказываний. Нормальные формы Исчисление высказываний. Предикаты и кванторы. Теории 1-го порядка. Модель теории 1-го порядка. Теорема полноты К. Геделя. Теорема Геделя о неполноте. Итого

3 4 5 6 7 8

Аудиторные Всего занятия труПрадоем- Все- Лек- ктикость го ции ческие 8 4 2 2 32 2 2 24 16 16 10 10 10 126

2 2 4 2 2 2 20

2 2 2 2 10

Лабораторные

2 2 2

10

Самостоятельная работа 4 30 22 14 12 8 8 8 106

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 1. Аксиоматический метод в математике. Аксиоматический метод в математике. Математическая логика и формализация математических теорий. Применение математической логики в других областях знаний. 2. Алгебра высказываний. Алгебра высказываний. Операции над высказываниями и их свойства. Истинностные значения формул. Тавтологии - законы логики высказываний. Равносильность и преобразования формул. Нормальные формы. Представление истинностных функций формулами. Применение алгебры высказываний к переключательным схемам. 3. Исчисление высказываний. Понятие формальной системы: язык формальной системы, аксиомы, правила вывода, теоремы. Построение исчисления высказываний в виде формальной системы. Язык исчисления высказываний, формулы и правила вывода. Теоремы о выводимых формулах. Совпадение понятий выводимой формулы и тавтологии. 4. Предикаты и кванторы. Понятие предиката. Формулы логики предикатов. Истинностные значения формул. Равносильность. Общезначимость и выполнимость формул. Проблема разрешения для общезначимости и выполнимости. Применение языка логики предикатов для записи математических предложений, определений, построение отрицаний предложений. 4

5. Теории 1-го порядка. Языки 1-го порядка: переменные, логические и нелогические символы, термы и формулы. Однозначность построения термов и формул, часть формулы. Cвободные и связанные вхождения переменных. Операция подстановки терма в формулу и ее допустимость. Логические и нелогические аксиомы, правила вывода. Теоремы и доказательства в теории 1-го порядка. 6. Модели теории 1-го порядка. Структуры для языка 1-го порядка. Истинность формулы в структуре для языка 1-го порядка. Теорема истинности. Модель теории. 7. Теорема полноты К. Геделя. Истинность формулы в теории. Две формы теоремы полноты К. Геделя. Изоморфизм моделей. Категоричность теории. Формализация математических теорий. Примеры формализации математических теорий: теория групп, теория N, теория множеств. 8. Теорема Геделя о неполноте.

4. САМОСТОЯТЕЛЬНАЯ РАБОТА И ОРГАНИЗАЦИЯ КОНТРОЛЬНО-ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ Темы, вынесенные на самостоятельное обучение: 1. Формулы логики предикатов. Истинностные значения формул. Равносильность. 2. Общезначимость и выполнимость формул. Проблема разрешения для общезначимости и выполнимости. 3. Применение языка логики предикатов для записи математических предложений, определений, построение отрицаний предложений. Примерные темы курсовых работ: 1. 2. 3. 4. 5. 6.

Аксиоматический метод в математике. Решение логических задач. Математическая логика и формализация математических теорий. Некоторые применения математической логики. Теория формальных систем. Теории 1-го порядка. Формализация математических теорий. Теорема Геделя о неполноте.

Вопросы для экзамена: 1. Аксиоматический метод в математике и формализация математических теорий Алгебра высказываний. 2. Конъюнктивная и дизъюнктивная нормальные формы. 3. Построение исчисления высказываний в виде формальной системы. 4. Свойства выводимых формул. 5. Совпадение классов выводимых и тождественно истинных формул. 6. Функции и предикаты Формализация математических теорий на языке первого порядка. 7. Аксиомы и правила вывода теории первого порядка. 8. Модель теории первого порядка. 9. Теорема о полноте. 10. Алгоритмы и машина Тьюринга. 11. Теорема Геделя о неполноте.

5

5. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ Студент, изучивший дисциплину, должен знать: о применениях математической логики в вопросах обоснования математики; формализованный аксиоматический метод построения математических теорий, его основные составные части: язык, аксиомы, правила вывода; проблемы непротиворечивости, полноты, разрешимости теорий; алгебра высказываний и нормальные формы; применение алгебры высказываний; изложение исчисления высказываний в виде формальной теории; предикаты и кванторы, проблема разрешения для общезначимости и выполнимости; теории 1-го порядка, язык теории, теоремы и доказательства, модель теории, изоморфизм моделей, категоричность теории; теорема К. Геделя о полноте; алгоритмы, рекурсивные функции и их связь с аксиоматическим методом; теорема Геделя о неполноте. Студент, изучивший дисциплину, должен уметь: записывать математических утверждений с использованием логической символики; преобразовывать формулы, в частности, формулы с кванторами и предикатами; вычислять нормальные формы; применять алгебру высказываний; доказывать выводимость формулы исчисления высказываний; записывать математические утверждения на языке 1-го порядка; строить модели теории; проверять непротиворечивость, независимость системы аксиом.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ 6.1. Рекомендуемая литература Основная 1. Ершов Ю.Л. Математическая логика [Текст]: учеб. пособие для вузов / Ю.Л. Ершов, Е.А. Палютин. – 4-е изд. стер. – СПб.: Лань, 2005. – 336 с. 2. Игошин В.И. задачник-практикум по математической логике [Текст]: учеб. пособие для студентов-заочников физ.-мат. фак. пед. ин-тов / В.И. Игошин. – Подольск: Академия, 2005. – 156 с. 3. Ильиных А.П. Математическая логика [Текст]: учеб. пособие / Урал. гос. пед. ун-т. – Екатеринбург:[б.и.], 2002. – 76 с. 4. Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов [Текст] / И.А. Лавров, Л.Л. Максимова. – М.: Наука, 1995. – 240 с. 5. Мендельсон Э. Введение в математическую логику [Текст] / Э. Мендельсон. – М.: Наука, 1976. – 287 с. 6. Новиков П.С. Элементы математической логики [Текст] / П.С. Новиков. – М.: Наука, 1973. – 399 с. 7. Шенфилд Д.Р. Математическая логика [Текст] / Д.Р. Шенфилд. – М.: Наука, 1975. – 527 с.

Дополнительная 1. Гжегорчик А. Популярная логика [Текст] / А. Гжегорчик. – М.: Наука, 1979. – 2. Гладкий А.В. Математическая логика [Текст] / А.В. Гладкий. – М.: Рос. гос. гум. ун-т, 1998. – 479 с.

6

3. Градштейн И.С. Прямая и обратная теоремы. Элементы алгебры логики [Текст] / И.С. Градштейн. – М.: Наука, 1972. – 4. Клини С.К. Математическая логика [Текст] / С.К. Клини. – М.: Мир, 1973. 480 с. 5. Колмогоров А.Н. Математическая логика: Доп. гл. [Текст]: учеб. пособие для вузов по спец. «Математика» / А.Н. Колмогоров, А.Г. Драгалин. – М.: Изд-во Моск. унта, 1984. – 119 с. 6. Лихтарников Л.М. Математическая логика [Текст]: курс лекций, задачникпрактикум и решения / Л.М. Лихтарников, Т.Г. Сукачева. – СПб.: Лань, 1998. – 288 с. 7. Мадер В.В. Школьнику об алгебре логики [Текст]: книга для внеклассного чтения учащихся 10-11 кл. сред. школы / В.В. Мадер. – М.: Просвещение, 1993. – 8. Математическая логика: Для спец. «Математика» [Текст]: МГЗПИ; сост. отв. ред. Ф.Л. Варпаховский. – М.,1991. – 9. Математическая логика [Текст]: учеб. пособие для мат. спец. пед. ин-тов; под общ.ред. А.А.Столяра. – Минск.: Вышэйшая школа, 1991. – 269 с. 10. Основы математической логики [Текст]: метод. разраб. / В.Б. Репницкий; Свердл. гос. пед. ин-т. – Свердловск: [б.и.], 1987. – 122 с.

6.2. Информационное обеспечение дисциплины Локальная сеть математического факультета УрГПУ, сайт кафедры алгебры и теории чисел, «Информационная обучающая среда».

7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ И ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Компьютерные классы математического факультета.

8. СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ Ильиных Анатолий Петрович, д.ф.м.н., зав каф. алгебры и теории чисел УрГПУ Рабочий телефон: 371-12-61.

7

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

по дисциплине ___«Математическая логика » для специальности 032100 «Математика» по циклу___«Дисциплины предметной подготовки»

Подписано в печать

Формат 60х84/16

Бумага для множительных аппаратов. Усл. печ. л. Тираж

экз.

Заказ

Уральский государственный педагогический университет. 620017 Екатеринбург, пр. Космонавтов, 26.

8