Скачать 404.06 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Мурманский государственный гуманитарный университет» (ФГБОУ ВПО «МГГУ») УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Математическая логика Основная образовательная программа подготовки специалиста по специальностям: 050202 Информатика (СД.Ф.1) 050202 Информатика с доп.спец. «Математика» (СД.Ф.1) 050708 ПиМНО с доп. спец. «Информатика» (ДДС.Ф.1) 050708 ПиМНО со специализацией (ДС.5) 050502 Технология и предпринимательство со специализацией (ДС.8) Утверждено на заседании кафедры физики, информатики и ИТ факультета физико-математического образования, информатики и программирования (протокол №11 от «24» апреля 2013 г.) Зав. кафедрой физики, информатики и ИТ ___________________Н.Ю.Королева РАЗДЕЛ I.Программа учебной дисциплины.
Кириченко А.Э. – канд. техн. наук, доцент кафедры информационных систем и прикладной математики, МГТУ
Цель: изучение теоретических и алгоритмических основ базовых разделов математической логики, методов оценки сложности алгоритмов и построения эффективных алгоритмов; содействие фундаментализации образования, формированию мировоззрения и развитию логического мышления. Задачи: изучить основы математической логики, символьные обозначения, теорию формальных доказательств, свойства многозначных логик, минимизацию формул. Место курса в общей системе подготовки специалиста: Дисциплина «Математическая логика» обеспечивает приобретение знаний и умений в соответствии с государственным образовательным стандартом; относится к числу прикладных математических дисциплин в силу отбора изучаемого материала и его важности для подготовки специалиста. Знания и навыки, полученные при изучении дисциплины "Математическая логика", используются обучаемыми при изучении общепрофессиональных и специальных дисциплин компьютерного цикла. Требования к уровню освоения содержания дисциплины: должны знать: основы логики высказываний, логики предикатов и нечёткой логики; представления булевых функций и способы минимизации формул; типовые свойства и способы задания функций многозначной логики; должны уметь: употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами; Ссылки на авторов и программы, которые использовались в подготовке: нет.
ДПП.Ф.01 Математическая логика (130 часов) Алгебра высказываний. Нормальные формы. Совершенные нормальные формы. Теорема существования и единственности совершенных нормальных форм. Логическое следствие. Прямая и обратная теоремы, противоположная и обратная теоремы; закон контрапозиции. Методы математических доказательств. Применение алгебры высказываний к описанию релейно-контактных схем. Исчисление высказываний. Формулы исчисления высказываний. Аксиомы исчисления высказывания и правила вывода. Теорема дедукции и ее применение. Исследования системы аксиом исчисления высказываний; их непротиворечивость и полнота. Логика предикатов. Формулы логики предикатов и их классификация. Приведенная форма для формул логики предикатов. Предваренная нормативная форма. Проблема разрешения в логике предикатов. Применение логики предикатов. Строение математических теорем. Методы доказательства теорем. Исчисление предикатов. Непротиворечивость исчисления предикатов. Теорема Геделя о полноте исчисления предикатов.
Примечание: Вариант 1 для специальности 050202 Информатика. Вариант 2 для специальности 050708 ПиМНО с доп. спец. «Информатика». Вариант 3 для специальности 050708 ПиМНО со специализацией. Вариант 4 для специальности 050502 Технология и предпринимательство со специализацией. Вариант 5 для специальности 050202 Информатика с доп.спец. «Математика»
1. Алгебра логики, логика высказываний, булевы функции. Высказывания и операции над ними. Общий взгляд на логические операции. Основные логические операции и их свойства. Понятие булевой алгебры. Алгебра высказываний и алгебра подмножеств. Выполнимые, тождественно истинные и тождественно ложные формулы. Равносильность формул, основные соотношения равносильности и их использование для упрощения формул. Нормальные формы. Существование для каждой формулы алгебры высказываний приведенной формы, нормальных форм. Совершенные нормальные формы. Теорема существования и единственности совершенных нормальных форм. Логическое следствие. Понятие тупиковых нормальных форм. Понятие минимальных форм. Методы минимизации: Квайна, Квайна-Мак-Класки, Блейка-Порецкого. Применение алгебры высказываний к описанию релейно-контактных схем. Системы булевых функций. Понятие полноты системы булевых функций. Теорема Поста о полноте. 2. Логика предикатов. Предикаты на множестве. Логические операции над предикатами. Логика предикатов. Кванторные операции над предикатами. Формулы логики предикатов и их классификация. Тавтологии. Равносильные преобразования формул. Выводимость и доказуемость формул в исчислении предикатов. Вспомогательные правила вывода: правило силлогизма, правила умножения и разделения формул, правила умножения и разделения посылок, правило умножения заключений, правило перестановки посылок, правило контрапозиции, правила де Моргана, правила противоречия, закон исключенного третьего. Приведённая форма для формул логики предикатов. Предварённая нормальная форма. Проблема разрешения в логике предикатов. 3. Формальные исчисления. а) исчисление высказываний. Определение формального исчисления. Формулы исчисления высказываний. Аксиомы исчисления высказывания и правила вывода. Теорема дедукции и ее применение. Исчисление высказываний генценовского типа. Эквивалентность формул. Нормальные формы. Семантика исчисления секвенций. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний. Прямая и обратная теоремы, противоположная и обратная теоремы; закон контрапозиции. Методы математических доказательств. б) исчисление предикатов. Язык, аксиомы и правила вывода исчисления предикатов. Теорема дедукции для замкнутой формулы. Эквивалентность формул. Приведение формул к нормальным формам. Понятие об интерпретации исчисления предикатов. Секвенциальное исчисление предикатов. Секвенциальный и натуральный вывод в исчислении предикатов. Исчисление предикатов гильбертовского типа. в) метод резолюции. Применение логики (исчисления) предикатов для доказательства теорем. Эрбановские интерпретации. Теорема Эрбрана. Скулемовская стандартная форма. Скулемизация алгебраических систем. Семантические деревья. Метод резолюции для логики предикатов. Унификация. Теорема о наиболее общем унификаторе. Теорема о полноте метода резолюции для логики предикатов. Применение логики предикатов в дедуктивных базах данных и экспертных системах. Основные понятия логического программирования: хорновские дизъюнкты, SLD-резолюция. Методика составления и реализация логических программ. 4. Элементы теории моделей. а) аксиоматические системы. Теории первого порядка. Исследования системы аксиом исчисления высказываний; их непротиворечивость и полнота. Натуральный вывод в логике высказываний. Корректность правил вывода. Непротиворечивость исчисления предикатов. Теорема Геделя о полноте исчисления предикатов. Теорема о дедукции. Теорема Генцена об устранении сечения. Основные понятия многозначной логики. Пороговая логика. Формальная арифметика. Теорема Гёделя о неполноте. Вторая теорема Гёделя. Определение истинности. Выразимость. Элиминация кванторов. Арифметика Пресбургера. Теорема Тарского-Зайденберга. Игра Эренфойхта. Понижение мощности. Программа Гильберта обоснования математики. Нестандартный анализ. Теоремы Лёвенгейма-Скулема. б) поиск вывода. Теория поиска логического вывода. Автоматический поиск вывода. Теорема Мальцева о компактности и ее приложения. Строение математических теорем. Методы доказательства теорем. Применение исчисления предикатов. Понятие сложности вывода и переход к табличным исчислениям. 5. Неклассические логики. Тезис Гильберта. Пропозициональные логики, временнЫе логики (Прайора, Леммона, фон Вригта). Предикатные логики (многосортные логики первого порядка, теорема Линдстрёма). Предикатные временнЫе логики и их приложения к программированию.
Практическое занятие 1. Высказывания и операции над ними. Построение таблиц истинности пропозициональных формул. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 2. Упрощение логических выражений с использованием основных тождеств алгебры логики. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 3. Приведение пропозициональных формул к дизъюнктивной и конъюнктивной нормальной формам. Аналитический и табличный методы приведения пропозициональных формул к совершенным нормальным формам. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 4. Минимизация булевых функций с использованием алгоритма Квайна и карт Карно. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 5. Применение булевых функций для анализа и синтеза дискретных устройств. Анализ и синтез релейно-контактных схем. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 6. Предикаты. Использование кванторных предикатов для записи различных предложений. Определение выполнимости и общезначимости предикатных формул. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 7. Основные равносильности логики предикатов. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 8. Вывод в логике предикатов. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 9. Приведённая форма для формул логики предикатов. Предварённая нормальная форма. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 10. Исчисление высказываний. Упрощение и преобразование логических схем. Использование аксиом и правил для организации логического вывода. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 11. Исчисление предикатов. Организация логического вывода в исчислении предикатов. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 12. Приведение предикатных формул к клаузальной форме. Метод резолюций в логике предикатов. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 13. Аксиоматические системы. Формальные грамматики и их свойства. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 14. Аксиоматические системы. Булевы функции и способы их представления. Многочлены Жегалкина. Определение полноты систем булевых функций. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 15. Поиск вывода. Проверка логической правильности рассуждений. Логическое следствие. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 16. Истинность в неклассических логиках. Логические преобразования. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 17. Доказательство полноты систем в k-значной логике. Практическое занятие предусматривает следующие виды упражнений:
Практическое занятие 18. Нечеткая логика. Преобразования. Модальная логика. Практическое занятие предусматривает следующие виды упражнений:
ЭБС "Университетская библиотека on-line"
ЭБС "Ibooks"
|
Учебно-методический комплекс дисциплины архитектура компьютера (Архитектура... Рындина Татьяна Николаевна, ст преподаватель кафедры Физики, информатики и информационных технологий | Учебно-методический комплекс дисциплины специальность: 050202 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Математическая логика» для студентов очной формы обучения по специальности 050202... | ||
Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск ... | Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Программирование» для студентов очной формы обучения по специальности 050202. 65... | ||
Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Эстетика» для студентов очной формы обучения по специальности 050202. 65 «Информатика»... | Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Химия» для студентов очной формы обучения по специальности 050202. 65 «Информатика»... | ||
Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Физика» для студентов очной формы обучения по специальности 050202. 65 «Информатика»... | Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Сайтостроение» для студентов очной формы обучения по специальности 050202. 65 «Информатика»... | ||
Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «История информатики» для студентов очной формы обучения по специальности 050202.... | Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Информационные системы» для студентов очной формы обучения по специальности 050202.... | ||
Учебно-методический комплекс дисциплины специальность: 050202 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Архитектура компьютера» для студентов очной формы обучения по специальности 050202... | Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Информационная культура» для студентов очной формы обучения по специальности 050202.... | ||
Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Основы микроэлектроники» для студентов очной формы обучения по специальности 050202.... | Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Протокол согласования рабочей программы дисциплины «культурология» с другими дисциплинами специальности 050202. 65 Информатика | ||
Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск ... | Основная образовательная программа подготовки специалиста по специальности(специальностям)... Шифр дисциплины и ее название в строгомсоответствии с государственным образовательнымстандартом и учебным планом |