Рабочая программа дисциплина ен. Ф. 01. 04 Математическая логика и теория алгоритмов направление
| Вид материала | Рабочая программа |
- Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
- Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
- Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
- Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
- Рабочая программа дисциплины «Математическая логика и теория алгоритмов» Направление, 175.54kb.
- Рабочая программа дисциплины «Математическая логика и теория алгоритмов», 143.48kb.
- В. Б. Гисин Дисциплина по выбору «Математическая логика и теория алгоритмов» Настоящий, 5.87kb.
- Рабочая программа учебной дисциплины «Теория вероятностей и математическая статистика», 165.42kb.
- Рабочая программа учебной дисциплины ен. Ф. 01. 04 Математическая логика и теория алгоритмов, 259.76kb.
- Рабочая программа по дисциплине Математическая логика и теория алгоритмов для специальности, 135.74kb.
1. Логика высказываний
1.1. Высказывания и логические операции над ними
Логика, ее задачи. Высказывание и его логическое значение. Логические операции над высказываниями: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность и их таблицы истинности.
1.2. Формулы логики высказываний и их классификация
Пропозициональные переменные. Индуктивное определение формулы логики высказываний. Подформулы. Составное высказывание и его логическое значение. Классификация формул логики высказываний: выполнимые и опровержимые формулы, тавтологии и противоречия.
1.3. Общезначимые формулы
Основные общезначимые формулы. Проверка общезначимости. Тавтологии, выражающие свойства логических операций. Правила получения тавтологий: заключения и подстановки.
1.4. Логическое следование формул (отношение логического следования формул)
Логическое следование формул логики высказываний, проверка его выполнения с помощью таблицы истинности. Признак логического следствия.
1.5. Равносильность формул (отношение равносильности)
Равносильные формулы, проверка равносильности двух формул с помощью таблицы истинности. Признак равносильности формул. Основные равносильности логики высказываний. Лемма о равносильной замене. Равносильные преобразования формул.
1.6. Нормальные формы для формул алгебры высказываний
Конъюнктивные и дизъюнктивные одночлены, дизъюнктивные и конъюнктивные нормальные формы. Совершенные нормальные формы и алгоритмы их нахождения. Теорема о единственности совершенных нормальных форм.
1.7. Формализованное исчисление высказываний
Формальные теории. Построение формализованного исчисления высказываний: алфавит, формулы, аксиомы, правила вывода. Вывод формулы из гипотез. Теоремы.
1.8. Теорема о дедукции
Теорема о дедукции и следствия из нее. Применение теоремы о дедукции.
1.9. Полнота, непротиворечивость и разрешимость исчисления высказываний
Полнота, непротиворечивость и разрешимость аксиоматических теорий. Полнота формализованного исчисления высказываний. Теорема об общезначимости всех доказуемых формул в исчислении высказываний. Теорема о доказуемости всех тавтологий в логике высказываний. Теорема о полноте исчисления высказываний. Непротиворечивость исчисления высказываний, теорема о непротиворечивости. Разрешимость исчисления высказываний, теорема о разрешимости.
2. Логика предикатов
2.1. Предикаты
Предикаты и предметы. Множество истинности предиката. Классификация предикатов: тожественно истинные, тождественно ложные, выполнимые и опровержимые. Равносильность предикатов. Следствие предиката. Теоремы о равносильности, следствии предикатов.
2.2. Логические и кванторные операции над предикатами
Логические операции над предикатами: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность и теоремы о множествах истинности полученных предикатов. Кванторные операции: квантор всеобщности и квантор существования. Эквивалентность экзистенциального высказывания дизъюнкции, универсального – конъюнкции высказываний. Свободные и связанные вхождения переменных.
2.3. Формулы логики предикатов и их классификация
Предметные и предикатные переменные. Индуктивное определение формулы логики предикатов. Атомарные и составные формулы, подформулы. Классификация формул: выполнимые, опровержимые, тождественно истинные и тождественно ложные. Основные тавтологии логики предикатов.
2.4. Равносильность и логическое следование формул логики предикатов
Равносильные формулы. Приведенная и предваренная формы для формул логики предикатов. Теоремы о их существовании для каждой формулы логики предикатов. Логическое следствие формулы.
2.5. Формализованное исчисление предикатов
Формализованное исчисление высказываний: алфавит, формулы, система аксиом, правила вывода. Формулы, выводимые из гипотез, теоремы. Теорема о дедукции. Теоремы о непротиворечивости, полноте и неразрешимости исчисления предикатов.
3. Варианты логики и логическое программирование
3.1. Классическая логика и клаузальная логика
Классическая логика. Клаузальная форма записи. Преобразование предложений из стандартной формы в клаузальную.
3.2. Логическое программирование. Клаузы Хорна и метод резолюций
Логическое программирование. Клауза Хорна. Правило резолюций. Сущность метода резолюций.
3.3. Язык логического программирования Пролог
Основные синтаксические конструкции языка: атомы, переменные, термы, список, предложения. Разделы программы на языке Пролог. Описание предикатов и целевого утверждения, запись фактов и правил логического вывода. Процедурная интерпретация клауз Хорна.
3.4. Модальная логика
Модальности, модальные операторы. Основные законы модальной логики. Варианты модальной логики.
3.5. Нечеткая логика
Четкие и нечеткие множества. Операции над нечеткими множествами. Нечеткая логика.
3.6. Темпоральная логика
Моменты времени, точечные события, аксиомы, правила вывода. Описание ситуаций.
4. Алгоритмы и вычислимость
4.1. Задачи и алгоритмы
Массовая проблема и индивидуальная задача. Неформальное определение алгоритма. Свойства алгоритма. Различные подходы к формализации понятия алгоритма.
4.2. Машина Тьюринга