Равносильность и логическое следование формул логики предикатов – 2 часа.

Цели освоения дисциплины

Целью освоения дисциплины является ознакомление студентов с теоретическими и алгоритмическими основами базовых разделов математической логики и теории алгоритмов.

В результате изучения дисциплины студенты должны:

- получить знания об основах логики высказываний, логики предикатов, нечеткой логики и теории алгоритмов;

- знать и уметь использовать теоретические основы и прикладные средства математической логики и теории алгоритмов;

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

 

Место дисциплины в структуре ООП бакалавриата

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

Дисциплина является предшествующей для изучения дисциплин «Нечеткая логика», «Введение в алгоритмы», «Системы искусственного интеллекта», «Логическое и функциональное программирование».

Компетенции обучающегося, формируемые в результате освоения дисциплины

Процесс изучения дисциплины направлен на формирование следующих компетенций:

 

научно-исследовательская деятельность:

- способность к формализации в своей предметной области с учетом ограничений используемых методов исследования (ПК-2);

- готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-3);

- умение готовить презентации, оформлять научно-технические отчеты по результатам выполненной работы, публиковать результаты исследований в виде статей и докладов на научно-технических конференциях (ПК-5);

 

аналитическая деятельность:

- способность формализовать предметную область программного проекта и разработать спецификации для компонентов программного продукта (ПК-6).

 

В результате освоения дисциплины студент должен:

· Знать: основные понятия математической логики: формальной теории, исчисления; структуру исчислений высказываний и предикатов 1-го порядка; основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы Маркова), понятия вычислимости, разрешимости; основные неразрешимые массовые проблемы;

· Уметь: доказывать формулы в исчислении высказываний и предикатов 1-го порядка; составлять программы машин Тьюринга и схемы нормальных алгоритмов для решения простых вычислительных задач;

 

4. Структура и содержание дисциплины

 

4.1. Структура дисциплины

Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часа.

 

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам)
Лекции	Практ. зан.	Лабор. зан.	КСР *	СРС **	Всего	Из ауд. зан. в интер. форме
	Введение. Логика высказываний.
	Логика предикатов.
	Варианты логики
	Алгоритмы и вычислимость
	…
	Итого										экзамен

* Контроль самостоятельной работы: аудиторные занятия для проверки самостоятельной работы студентов, приема зачета, проведения текущих консультаций.

** Самостоятельная работа студента, включая курсовой проект, курсовую работу, расчетно-графические работы.

 

4.2. Содержание лекционных занятий

Введение. – 1 час.

Логика высказываний - 9 часов.

Высказывания и логические операции над ними – 1 час.

Логика, ее задачи. Высказывание и его логическое значение. Логические операции над высказываниями: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность и их таблицы истинности.

Формулы логики высказываний и их классификация – 1 час.

Пропозициональные переменные. Индуктивное определение формулы логики высказываний. Подформулы. Составное высказывание и его логическое значение. Классификация формул логики высказываний: выполнимые и опровержимые формулы, тавтологии и противоречия.

Общезначимые формулы – 1 час.

Основные общезначимые формулы. Проверка общезначимости. Тавтологии, выражающие свойства логических операций. Правила получения тавтологий: заключения и подстановки.

Логическое следование формул (отношение логического следования формул) – 1 час.

Логическое следование формул логики высказываний, проверка его выполнения с помощью таблицы истинности. Признак логического следствия.

Равносильность формул (отношение равносильности) – 1 час.

Равносильные формулы, проверка равносильности двух формул с помощью таблицы истинности. Признак равносильности формул. Основные равносильности логики высказываний. Лемма о равносильной замене. Равносильные преобразования формул.

Нормальные формы для формул алгебры высказываний – 1 час.

Конъюнктивные и дизъюнктивные одночлены, дизъюнктивные и конъюнктивные нормальные формы. Совершенные нормальные формы и алгоритмы их нахождения. Теорема о единственности совершенных нормальных форм.

Формализованное исчисление высказываний – 1 час.

Формальные теории. Построение формализованного исчисления высказываний: алфавит, формулы, аксиомы, правила вывода. Вывод формулы из гипотез. Теоремы.

Теорема о дедукции - 1 час.

Теорема о дедукции и следствия из нее. Применение теоремы о дедукции.

Полнота, непротиворечивость и разрешимость исчисления высказываний - 1 час.

Полнота, непротиворечивость и разрешимость аксиоматических теорий. Полнота формализованного исчисления высказываний. Теорема об общезначимости всех доказуемых формул в исчислении высказываний. Теорема о доказуемости всех тавтологий в логике высказываний. Теорема о полноте исчисления высказываний. Непротиворечивость исчисления высказываний, теорема о непротиворечивости. Разрешимость исчисления высказываний, теорема о разрешимости.

Логика предикатов – 10 часов.

Предикаты – 2 часа.

Предикаты и предметы. Множество истинности предиката. Классификация предикатов: тожественно истинные, тождественно ложные, выполнимые и опровержимые. Равносильность предикатов. Следствие предиката. Теоремы о равносильности, следствии предикатов.

Логические и кванторные операции над предикатами - 2 часа.

Логические операции над предикатами: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность и теоремы о множествах истинности полученных предикатов. Кванторные операции: квантор всеобщности и квантор существования. Эквивалентность экзистенциального высказывания дизъюнкции, универсального – конъюнкции высказываний. Свободные и связанные вхождения переменных.

Формулы логики предикатов и их классификация - 2 часа.

Предметные и предикатные переменные. Индуктивное определение формулы логики предикатов. Атомарные и составные формулы, подформулы. Интерпретация предикатных формул. Классификация формул: выполнимые, опровержимые, тождественно истинные и тождественно ложные. Основные тавтологии логики предикатов.

Равносильность и логическое следование формул логики предикатов – 2 часа.

Поделиться:

Воспользуйтесь поиском по сайту: