КАЗАХСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ АЛЬ-ФАРАБИ
МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ
Образовательная программа по специальности «5В060100—математика»
Утверждено
на заседании Ученого Совета факультета
протокол № ____ от «____» сентября 2015 г.
декан механико-математического
факультета .
СИЛЛАБУС
Профессиональный элективный модуль №
«Математическая логика“
2 курс, р/о, осенний семестр 2015/2016 учебного года, количество кредитов 3.
Лектор: к. ф.-м. н., доцент
тел. сот. 8-771-416-88-97 , *****@***ru
Преподаватель практики: к. ф.-м. н., доцент
тел. сот. 8-771-416-88-97 , *****@***ru
Пререквизиты: Курс алгебры
Постреквизиты: Предмет необходим в компьютерных курсах механико-математического факультета.
Начало занятий с 1 сентября 2015 г.
Цель курса | Изучение студентами основ математической логики, теории предикатов, машин Тьюринга. Приобретение знаний и умений студентами в фундаментальной области, навыков в математической логике. Изучение курса поддерживается расширенным практикумом. |
Содержание дисциплины
Алгебра высказываний.
Формулы алгебры высказываний. Таблицы истинности. Дизъюнктивные и конъюнктивные нормальные формы. Полные системы логических связок. Релейно-контактные схемы. Восстановление формулы по её таблице истинности.
Исчисление высказываний
Аксиомы и правила вывода в исчислении высказываний. Теорема дедукции. Леммы о выводимости. Лемма Кальмара. Теорема о полноте исчисления высказываний. Следствия из теоремы о полноте исчисления высказываний.
Исчисление предикатов Алгебраические системы. Отношения и термы. Алгебры и модели. Определение формулы. Равносильность и выполнимость формул. Формулы в алгебре. Формальная система исчисления предикатов. Аксиомы и правила вывода в исчислении предикатов. Общезначимость аксиом и сохранение общезначимости доказуемых формул. Перестановочность универсальных кванторов. Выполнимость формулы в модели. Теории. Модели и математические теории. Эквивалентность формул. Нормальные формы.
Модели арифметики. орецом арифметических структур. Определимо сложнейшие арифметические структуры. Иерархия арифметических структур.
Машины Тьюринга. Построение машины Тьюринга для операций сложения и перестановки переменных. Построение машины Тьюринга для операций суперпозиции и минимизации. Построение машины Тьюринга для операции примитивной рекурсии.
Модуль №1 | Алгебра высказываний | Часы | Баллы |
1 неделя | |||
Лекционное занятие № | Формулы алгебры высказываний. Таблицы истинности. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Формулы алгебры высказываний. Таблицы истинности. | 1 | 5 |
СРСП | Формулы алгебры высказываний. Таблицы истинности. | 3 | 1 |
Всего часов | 6 | ||
2 неделя | |||
Лекционное занятие № | Дизъюнктивные и конъюнктивные нормальные формы. Полные системы логических связок. | 2 | 6 |
Лабораторное занятие № | |||
Семинарское занятие № | Релейно-контактные схемы. Восстановление формулы по её таблице истинности. | 1 | 5 |
СРСП | Релейно-контактные схемы. Восстановление формулы по её таблице истинности | 3 | 2 |
Всего часов | 6 | ||
Итого по модулю №1 | 12 | ||
Модуль № 2 | Исчисление высказываний | ||
3 неделя | |||
Лекционное занятие № | Аксиомы и правила вывода в исчислении высказываний. Теорема дедукции. | 2 | 6 |
Лабораторное занятие № | |||
Семинарское занятие № | Леммы о выводимости | 1 | 5 |
СРСП | Леммы о выводимости | 3 | 2 |
Всего часов | 6 | ||
4 неделя | |||
Лекционное занятие № | Лемма Кальмара. Теорема о полноте исчисления высказываний. | 2 | 6 |
Лабораторное занятие № | |||
Семинарское занятие № | Следствия из теоремы о полноте исчисления высказываний. | 1 | 5 |
СРСП | Следствия из теоремы о полноте исчисления высказываний. | 3 | 2 |
Всего часов | 6 | ||
Итого по модулю № 2 | 12 | ||
Модуль 3 | Исчисление предикатов | ||
5 неделя | |||
Лекционное занятие № | Алгебраические системы. Отношения и термы. | 2 | 6 |
Лабораторное занятие № | |||
Семинарское занятие № | Алгебры и модели. | 1 | 5 |
СРСП | Алгебры и модели. | 3 | 2 |
Всего часов | 6 | ||
6 неделя | |||
Лекционное занятие № | Определение формулы. Равносильность и выполнимость формул. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Формулы в алгебре. | 1 | 5 |
СРСП | Формулы в алгебре. | 3 | 2 |
Всего часов | 6 | ||
7 неделя | |||
Лекционное занятие № | Формальная система исчисления предикатов. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Контрольная работа № 1 | 1 | 20 |
СРСП | Формальная система исчисления предикатов. | 3 | |
Всего часов | 6 | 100 | |
8 неделя | |||
Лекционное занятие № | Общезначимость аксиом и сохранение общезначимости доказуемых формул. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Перестановочность универсальных кванторов | 1 | 4 |
СРСП | Перестановочность универсальных кванторов | 3 | 1 |
Всего часов | 6 | ||
9 неделя | |||
Лекционное занятие № | Выполнимость формулы в модели. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Теории | 1 | 4 |
СРСП | Теории | 3 | 1 |
Всего часов | |||
10 неделя | |||
Лекционное занятие № | Модели и математические теории. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Модели и математические теории | 1 | 4 |
СРСП | Модели и математические теории | 3 | 1 |
Всего часов | 6 | ||
11 неделя | |||
Лекционное занятие № | Эквивалентность формул | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Нормальные формы | 1 | 4 |
СРСП | Нормальные формы | 3 | 1 |
Всего часов | 6 | ||
Итого по модулю № 3 | 42 | ||
Модуль 4 | Модели арифметики | ||
12 неделя | |||
Лекционное занятие № | Построение Корецом фрагментов арифметики | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Фрагменты арифметики | 1 | 4 |
СРСП | Фрагменты арифметики | 3 | 1 |
Всего часов | 6 | ||
13 неделя | |||
Лекционное занятие № | Определимо сложнейшие фрагменты арифметики. | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Фрагменты арифметики. | 1 | 4 |
СРСП | Фрагменты арифметики | 3 | 1 |
Всего часов | 6 | ||
Итого по модулю 4 | 12 | ||
Модуль 5 | Машины Тьюринга | ||
14 неделя | |||
Лекционное занятие № | Построение машин Тьюринга | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие №14 | Машины Тьюринга. | 1 | 4 |
СРСП | Машины Тьюринга. | 3 | 1 |
Всего часов | 6 | ||
15 неделя | |||
Лекционное занятие № | Программы вычисления арифметических функций | 2 | 5 |
Лабораторное занятие № | |||
Семинарское занятие № | Программы для вычисления арифметических функций | 1 | 4 |
СРСП | Программы для вычисления арифметических функций | 3 | 1 |
Всего часов | 6 | ||
Итого по модулю № 6 | 12 | ||
Итого в семестре | 90 | 100 | |
Программа курса
СРС студентам выдает лектор
Список рекомендуемой литературы
I. Korec, A list of arithmetical structures strongest with respect to the first order definability, Preprint 33/1996
Math. Inst. Slovak Academy of sciences, Bratislava
, , Сборник задач по дискретной математике, М., Наука, 1977 г. Э. Мендельсон, Введение в математическую логику, М., Мир, 1976.Академическая политика курса
Все виды работ необходимо выполнять и защищать в указанные сроки. Студенты, не выполнившие все виды работ, к экзамену не допускаются.
При оценке работы студента в течение семестра учитывается следующее:
- посещаемость занятий активное и продуктивное участие в практических занятиях изучение основной и дополнительной литературы выполнение домашних заданий (СРС) своевременная сдача всех заданий
Политика академического поведения и этики
Будьте толерантны, уважайте чужое мнение. Возражения формулируйте в корректной форме. Плагиат и другие формы нечестной работы недопустимы. Недопустимы подсказывание и списывание во время сдачи СРС, промежуточного контроля и финального экзамена, копирование решенных задач другими лицами, сдача экзамена за другого студента. Студент, уличенный в фальсификации любой информации курса, несанкционированном доступе в Интранет, пользовании шпаргалками, получит итоговую оценку F.
Помощь. За консультациями по выполнению самостоятельных работ (СРС), их сдачей и защитой, а также за дополнительной информацией по пройденному материалу и всеми другими возникающими вопросами по читаемому курсу обращайтесь к преподавателю в период его оффис-часов.
Рассмотрено на заседании кафедры фундаментальной математики
Протокол №----от «____» __сентября__ 2015 г.
Лектор доцент ______________________
Зав. кафедрой
профессор ______________________
