Математическая логика и теория алгоритмов (стр. 2 )

строить таблицы истинности формул исчисления высказываний; выполнять равносильные преобразования формул; находить совершенные дизъюнктивную и конъюнктивную нормальные формы формул исчисления высказываний; строить простейшие релейно-контактные схемы; доказывать простейшие теоремы исчисления высказываний, исчисления предикатов; использовать выразительные возможности языка логики предикатов и алгебры высказываний для записи математических выражений, для анализа правильности рассуждений и строения математических теорем; писать простейшие программы для машин  Тьюринга.

ВЛАДЕТЬ

методами решения рассмотренных при изучении дисциплины задач; навыками применения современного математического инструментария для решения задач математики и информатики; методикой построения, анализа и применения математических моделей для прикладных задач математики и информатики.

2.  Структура  и  трудоёмкость  дисциплины

Семестр:  IX.  Форма промежуточной аттестации:  экзамен.  Общая трудоёмкость дисциплины составляет  5  зачётных единиц,  180  академических часов, из них  56  часов, выделенных на контактную работу с преподавателем  (12  часов в интерактивном режиме),  88  часов выделено на самостоятельную работу.

Таблица  2.

Вид учебной работы	Всего часов	Семестры
IX
Контактная работа:	56	56
Аудиторные занятия	56	56
В том числе:	–	–
Лекции	28	28
Практические занятия	28	28
Самостоятельная работа	88	88
Общая трудоемкость  5  зач. ед. 180  час	5	5
180	180
Вид промежуточной аттестации	экзамен

3. Тематический  план

Таблица  3.

№	Тема	Недели семестра	Виды учебной работы и самостоятельная работа, в час.	Итого  часов  по  теме	Из них в  интерактивной форме,  в часах	Итого количество баллов
Лекции	Практические занятия	Лабораторные занятия*	Самостоятельная работа*
1	2	3	4	5	6	7	8	9	10
Модуль  1	1–7	14	14	–	40	68	3	0-50
Всего	14	14	–	40	68	3	0-50
Модуль 2	8–10	6	6	–	18	30	3	0–15
Всего	6	6	–	18	30	3	0–15
Модуль 3	11–12	4	4	–	16	24	3	0-15
Всего	4	4	–	16	24	3	0-15
Модуль 4	13–14	4	4	–	14	22	3	0-20
Всего	4	4	–	14	22	3	0-20
Итого (часов, баллов):	28	28	–	88	144	12	0-100

4.  Виды  и  формы  оценочных  средств  в  период  текущего  контроля

Таблица  4.

№ Темы	Устные ответы	Письменные работы	Итого  баллов
коллоквиумы	ответ на семинаре	контрольная работа	тесты
Модуль  1
Всего	0–10	0–20	0–10	0–10	0–50
Модуль  2
Всего	–	0–5	0–10	–	0–15
Модуль  3
Всего	–	0–5	0–5	0–5	0–15
Модуль  4
Всего	–	0–5	0–10	0–5	0–20
Итого	0–10	0–35	0–35	0–20	0–100

5.  Содержание  дисциплины

МОДУЛЬ  1:  Алгебра  высказываний

Высказывания и логические операции над высказываниями. Язык исчисления высказываний:  алфавит, сигнатура.  Формулы алгебры высказываний, их истинностные значения и классификация: законы логики, противоречия, выполнимые формулы.  Равносильные формулы алгебры высказываний  и  равносильные преобразования формул.  Совершенные нормальные формы  (СНФ). Теорема существования и единственности  СНФ. Функции алгебры высказываний. Представление функций формулами.  Логическое следование.  Логический анализ правильности рассуждений.  Применение алгебры логики высказываний к конструированию  РКС  и  СБИС.

МОДУЛЬ  2:  Алгебра  предикатов

Предикаты и кванторы, множества истинности предикатов.  Логические операции над предикатами.  Язык исчисления предикатов.  Интерпретации символов формул логики предикатов и истинностные значения формул логики предикатов.  Классификация формул логики предикатов: общезначимые, выполнимые формулы и противоречия.  Равносильные формулы логики предикатов.  Предварённая приведённая нормальная форма  (ППНФ).

МОДУЛЬ  3:  Формальные  аксиоматические  теории

Структура математических теорий.  Виды математических утверждений.  Содержательный и формальный аксиоматические методы.  Построение исчисления предикатов гильбертовского типа  (алфавит, сигнатура, формулы, связанные и свободные переменные, аксиомы, правила вывода).  Доказательство и выводимость из гипотез. Свойства выводимости.  Теорема о дедукции и её следствия.  Примеры доказательства теорем исчисления предикатов гильбертовского типа.  Исследование свойств системы аксиом исчисления предикатов: непротиворечивость, независимость и полнота системы аксиом исчисления предикатов.  Теорема  Гёделя  о неполноте формальной арифметики.

МОДУЛЬ  4:  Основы теории алгоритмов

Определение машины Тьюринга.  Тезис  Тьюринга.  Нумерация машин Тьюринга.  Алгоритмические проблемы в разных областях математики и других областях знаний.  Неразрешимые алгоритмические проблемы.  Некоторые другие уточнения понятия  “алгоритм”  (частично рекурсивные функции, нормальные алгоритмы  Маркова)  и их эквивалентность.

6.  Планы  практических  занятий

№	Модуль	План  практического  занятия
1–2	Модуль  1: Алгебра высказываний	Высказывания.  Язык исчисления высказываний.  Интерпретации и таблицы истинности формул алгебры высказываний.  Классификация формул: законы логики, противоречия, выполнимые формулы.
3–4	Равносильные формулы алгебры высказываний  и  равносильные преобразования формул.
5	Полиномы  Жегалкина.  Построение полиномов  Жегалкина для булевых функций.  Построение  СДНФ  или  СКНФ  по полиномам  Жегалкина.
6	Применение алгебры логики высказываний к конструированию  РКС  и  СБИС.
7	Логическое следование.  Различные методы проверки логического следования.  Логический анализ правильности рассуждений.
8	Модуль  2: Алгебра предикатов	Предикаты, области определения, множества истинности и ложности предикатов.  Логические операции над предикатами.  Кванторы.  Высказывания с предикатами и кванторами.
9-10	Формулы исчисления предикатов.  Интерпретации формул исчисления предикатов.  Классификация формул логики предикатов: общезначимые, выполнимые формулы и противоречия.  Равносильные формулы.  Предварённая приведённая нормальная форма  (ППНФ).  Структура математических теорий.
11–12	Модуль  3: Формальные аксиоматические теории	Формальное доказательство теорем исчисления высказываний и предикатов.
13	Модуль  4: Основы теории алгоритмов	Машины  Тьюринга.  Составление программ для машин  Тьюринга.
14	Стандартные машины  Тьюринга.  Конструирование машин  Тьюринга  из стандартных.

7.  Лабораторный практикум