МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Чеченский государственный педагогический институт
Кафедра информатики
«УТВЕРЖДАЮ»
Декан факультета
____________
2011г.
Рабочая программа дисциплины
«МАТЕМАТИЧЕСКАЯ ЛОГИКА»
Специальность: Математика и информатика
Факультет: физико-математический
Форма обучения: очная
г. Грозный
2011 г.
Рецензент:___________________________________________________________
Рабочая программа дисциплины «Математическая логика»
Рабочая программа предназначена для преподавания дисциплины очной формы обучения специальности «Математика и информатика» в 5-ом семестре.
Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированных специалистов специальности «Математика и информатика», утвержденного 14.04.2000г. Министерством образования РФ.
Составитель ______________
28.08.11г.
Лист
Согласования рабочей программы
Специальность: «Математика и информатика»____________________________
Дисциплина: Математическая логика_____________________________________________
Форма обучения: __________очная _____________________________________
Учебный год: г. г.
Рекомендовано заседанием кафедры информатики
Протокол от «__»_________________2011г.
Ответственный исполнитель зав. каф. информатики _____________09.2011г.
Исполнитель: ст. преподаватель каф. информатики_________ 09.2011г.
СОГЛАСОВАНО:
зав. кафедрой информатики________________________ 09.2011г.
председатель методической комиссии по специальности
Математика и информатика_____________________________________________________
Личная подпись Расшифровка подписи Дата
Заведующий отделом комплектования научной библиотеки
__________________________________________________________________________
Личная подпись Расшифровка подписи Дата
Начальник УМО __________________________________________________________
Личная подпись Расшифровка подписи Дата
I. Цели и задачи дисциплины
Цель курса – формирование представлений о понятиях и методах в области формализованных логических исчислений.
Использование в логике формальных языков привело к созданию логических исчислений, возникших из потребности разрешения известных логических парадоксов.
Поэтому долгое время математическая логика развивалась как средство решения задач обоснования математики. Было получено множество результатов, имеющих общекультурное значение. Поэтому данный курс имеет все основания находиться среди дисциплин, читаемых будущим учителям информатики. Одним из наиболее известных проектов создания компьютеров 5 поколения предполагается использование логических исчислений в качестве основной системы программирования.
Для достижения целей курса необходимо решить следующие задачи:
· формирование знаний и умений в записи математических утверждений на язык исчисления предикатов, навыков выполнения равносильных преобразований формул исчисления предикатов и построения простейших выводов;
· формирование представлений об основных методах поиска вывода и их использования в логическом программировании и наиболее актуальных задачах в математической логике и их значении для информатики.
II. Требования к уровню освоения содержания дисциплины
После изучения дисциплины студент должен:
- уметь записывать математические утверждения на языке узкого исчисления предикатов;
- уметь выполнять основные равносильные преобразования формул узкого исчисления предикатов и строить в этом исчислении простейшие выводы;
- понимать принципиальную ограниченность аксиоматического вывода;
- приобрести навыки в применении основных методов поиска вывода и их использовании в логическом программировании.
III. Объем дисциплины и виды учебной работы
Вид учебной работы | Всего часов | Семестры |
Общая трудоемкость | 130 | 5 |
Аудиторные занятия | 72 | |
Лекции | 36 | |
Практические занятия | 36 | |
Контрольные работы | 4 | |
Самостоятельная работа | 54 | |
Контроль | экзамен |
IV. Содержание дисциплины
1) Разделы дисциплины и виды занятий.
№ п/п | Разделы дисциплины | Лекции | Практические занятия |
1 | Введение | 2 | 2 |
2 | Исчисление высказываний | 14 | 14 |
3 | Исчисление предикатов | 10 | 10 |
4 | Аксиоматические системы | 8 | 8 |
5 | Теории первого порядка | 2 | 2 |
Семестр 5
Лекций - 36 часов, практических – 36 часов
№№ п/п | Тема | Лекции | Практические занятия |
Введение. | 2 | 2 | |
1 | Правильные рассуждения. Предложения и высказывания. Понятие высказывания. Истинные и ложные высказывания. | 2 | 2 |
Исчисление высказываний. | 14 | 14 | |
2 | Понятие формального языка, синтаксис и семантика. Частные, единичные и общие высказывания. | 2 | 2 |
3 | Язык исчисления высказываний. Семантика исчисления высказываний. Основные логические операции. | 2 | 2 |
4 | Выполнимые и общезначимые формулы. Логическое следование. Таблицы истинности. | 2 | 2 |
5 | Элементарные конъюнкции и дизъюнкции. Законы алгебры логики. | 2 | 2 |
6 | Нормальные формы формул. Совершенные формулы. | 2 | 2 |
7 | Принцип двойственности. Метод резолюций. | 2 | 2 |
8 | Проблемы в исчислении высказываний. | 2 | 2 |
Исчисление предикатов. | 10 | 10 | |
9 | Понятие предиката. Язык исчисления предикатов. | 2 | 2 |
10 | Семантика исчисления предикатов. | 2 | 2 |
11 | Нормальные формы в исчислении предикатов. | 2 | 2 |
12 | Метод резолюций в исчислении предикатов. Принцип двойственности. | 2 | 2 |
13 | Принцип логического программирования. Некоторые сведения о языке ПРОЛОГ. | 2 | 2 |
Аксиоматические системы. | 8 | 8 | |
14 | Аксиоматические системы их свойства (непротиворечивость, полнота). | 2 | 2 |
15 | Аксиоматическая система исчисления высказываний. Полнота и непротиворечивость исчисления высказываний. | 2 | 2 |
16 | Натуральный вывод в исчислении высказываний. | 2 | 2 |
17 | Аксиоматическая система исчисления предикатов. Равенство в исчислении предикатов. | 2 | 2 |
Теории первого порядка. | 2 | 2 | |
18 | Теории первого порядка, их свойства. Интерпретации. Модели. Существований модели для непротиворечивой теории. | 2 | 2 |
итого | 36 | 36 |
V. Учебно-методическое обеспечение дисциплины
1). Рекомендуемая литература
1. , Языки и исчисления. – М.: МЦНМО, 2000.
2. , Математическая логика и теория алгоритмов.
3. Искусство программирования на языке ПРОЛОГ.
4. Грей. Логика, алгебра и базы данных. – М.: Машиностроение, 1989.
5. Гладкий языки и грамматики. – М.: Наука, Главная редакция физ.-мат. Литературы, 1973.
6. , Максимова по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 2002.
2). Средства обеспечения освоения дисциплины
Учебные и методические пособия (учебники, учебно-методические пособия, пособия для самостоятельной работы, сборники упражнений и др.)
VI. Материально-техническое обеспечение дисциплины
Специально оборудованные аудитории, компьютерные классы, технические средства обучения.
VII. Методические рекомендации по организации изучения дисциплины
1) Перечень примерных контрольных вопросов и заданий для самостоятельной работы
1. Таблицы истинности для основных операций алгебры логики.
2. Теоремы булевой алгебры.
3. Законы де Моргана.
4. Теорема дедукции для исчисления высказываний.
5. Эквивалентность различных формул исчисления высказываний.
6. Предикаты и отображения.
7. Теорема дедукции для исчисления предикатов.
8. Эквивалентность различных формул исчисления предикатов.
9. Некоторые теоремы формальной арифметики.
10. Формальные грамматики.
2) Примерная тематика рефератов
1. Принципы построения систем автоматизации доказательств.
2. Доказательные вычисления на ЭВМ.
3. Машинно-ориентированная логика, основанная на принципе резолюций.
4. Алгоритмы машинного поиска логического вывода в исчислении высказываний.
5. Алгоритмы машинного поиска логического вывода в исчислении предикатов.
6. Сравнение мощности логических систем.
7. Логические уравнения и методы их решения.
VIII. Примерный перечень вопросов к экзамену
1. Понятие высказывания. Пропозициональные переменные.
2. Логика высказываний. Истинные и ложные высказывания.
3. Алгебра высказываний.
4. Логические операции. Унарные и бинарные операции.
5. Правила записи сложных формул. Примеры.
6. Составление сложных высказываний. Примеры.
7. Правила записи сложных суждений. Примеры.
8. Удаление и расстановка скобок. Примеры.
9. Равносильные формулы. Примеры.
10. Законы алгебры логики. Доказательство законов.
11. Эквивалентные преобразования формул.
12. Нормальные формы формул. Алгоритм приведения к нормальной форме.
13. Совершенные нормальные формы. Алгоритм приведения формул к совершенному виду.
14. Формирование совершенных форм по значениям функции.
15. Исчисление высказываний. Интерпретация формул.
16. Аксиомы исчисления высказываний.
17. Правила вывода.
18. Правила подстановки.
19. Правила введения и удаления логических связок.
20. Правила заключения.
21. Метод дедуктивного вывода.
22. Принцип резолюции.
23. Алгоритм вывода по принципу резолюции.
24. Проблемы исчисления высказываний.
25. Описание высказываний на языке ПРОЛОГ.
26. Понятие предиката. Одноместные и двухместные предикаты.
27. Логические операции над предикатами.
28. Алгебра предикатов.
29. Квантор всеобщности. Квантор существования.
30. Понятие формулы алгебры предикатов.
31. Законы алгебры предикатов.
32. Предваренная нормальная форма.
33. Принцип логического программирования.
34. Теорема Геделя о полноте.
