Равносильность и логическое следование формул логики предикатов – 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 часа.
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|