Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

1. 
   Алгебра высказываний Высказывания и операции над ними.
   
2. 
   Формулы алгебры высказываний.
   
3. 
   Тавтологии алгебры высказываний.
   
4. 
   Логическая равносильность формул.
   
5. 
   Нормальные формы для формул алгебры высказываний.
   
6. 
   Логическое следование формул.
   

1. 
   Элементарная дизъюнкция, э конъюнкция
   
2. 
   Дизъюнктивная и конъюнктивная нормальные формы.
   
3. 
   Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ, СКНФ).
   

1. 
   Понятие логического следования, критерий логического следования.
   
2. 
   Схема логического рассуждения и правильность логического рассуждения. Способы проверки правильности логических рассуждений.
   
3. 
   Прямые и косвенные виды доказательств.
   
4. 
   Решение задач.
   

1. 
   Булевы функции от одного и двух аргументов.
   
2. 
   Булевы функции от n аргументов.
   
3. 
   Системы булевых функций.
   
4. 
   Применение булевых функций к релейно-контактным схемам.
   

План.

1. 
   Логика предикатов. Понятие предиката.
   
2. 
   Классификация предикатов. Множество истинности предиката.
   
3. 
   Логические операции над предикатами.
   
4. 
   Кванторные операции.
   
5. 
   Формулы логики предикатов.
   
6. 
   Равносильные формулы логики предикатов.
   
7. 
   Предваренная нормальная форма.
   
8. 
   Формализация в логике предикатов.
   

План.

1. 
   Понятие алгоритма и неформальной вычислимости: определения и основные особенности алгоритма.
   
2. 
   Подход Геделя - Клини к формализации понятия алгоритма.
   
3. 
   Решение задач.
   

Тема 8. Машины Тьюринга.

План.

1. 
   Определение машины Тьюринга.
   
2. 
   Конструирование машин Тьюринга. Частные производные.
   
3. 
   Композиция машин Тьюринга. Частные производные высших порядков.
   

План.

1. 
   Основные понятия теории рекурсивных функций и тезис Чёрча.
   
2. 
   Общерекурсивные и частично рекурсивные функции.
   
3. 
   Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу
   
4. 
   Нормальный алгоритм Маркова.
   

План.

1. 
   Алгоритмически неразрешимые проблемы. Сложность алгоритмов: в наихудшем случае и поведения в среднем.
   
2. 
   Сложность задачи. Классификация задач по сложности: класс Р и класс Е. Класс NP. NP-трудные и NP-полные задачи.
   
3. 
   Теорема Кука.
   
4. 
   Неклассические логики.
   
5. 
   Предикатные логики и их приложения к программированию.
   
6. 
   Алгоритмические логики.
   
7. 
   Контрольная работа.